66 citations · 206 across the 36 of their papers we have counts for
27 papers · 1 filter
Enumeration of Preferred Extensions in Almost Oriented Digraphs
Serge Gaspers, Ray Li
In this paper, we present enumeration algorithms to list all preferred extensions of an argumentation framework. This task is equivalent to enumerating all maximal semikernels of a…
Minimizing and Computing the Inverse Geodesic Length on Trees
Serge Gaspers, Joshua Lau
For any fixed measure that maps graphs to real numbers, the MinH problem is defined as follows: given a graph , an integer , and a target , is there a set of v…
Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements
Serge Gaspers, Joachim Gudmundsson, Julián Mestre +1
Given a line segment , the so-called barrier, and a set of sensors with varying ranges positioned on the line containing , the barrier coverage problem is to move t…
Exact Algorithms via Multivariate Subroutines
Serge Gaspers, Edward Lee
We consider the family of -Subset problems, where the input consists of an instance of size over a universe of size and the task is to check whether the univer…
Faster Graph Coloring in Polynomial Space
Serge Gaspers, Edward Lee
We present a polynomial-space algorithm that computes the number independent sets of any input graph in time for graphs with maximum degree 3 and in time $O(1.2355^n)…
On Satisfiability Problems with a Linear Structure
Serge Gaspers, Christos Papadimitriou, Sigve Hortemo Saether +1
It was recently shown \cite{STV} that satisfiability is polynomially solvable when the incidence graph is an interval bipartite graph (an interval graph turned into a bipartite gra…
Exact Algorithms via Monotone Local Search
Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov +1
We give a new general approach for designing exact exponential-time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a unive…
Faster algorithms to enumerate hypergraph transversals
Manfred Cochefert, Jean-Francois Couturier, Serge Gaspers +1
A transversal of a hypergraph is a set of vertices intersecting each hyperedge. We design and analyze new exponential-time algorithms to enumerate all inclusion-minimal transversal…
On the Number of Minimal Separators in Graphs
Serge Gaspers, Simon Mackenzie
We consider the largest number of minimal separators a graph on n vertices can have at most. We give a new proof that this number is in . We prove that t…
Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets
Serge Gaspers, Gregory B. Sorkin
We show a method resulting in the improvement of several polynomial-space, exponential-time algorithms. An instance of the problem Max (r,2)-CSP, or simply Max 2-CSP, is parametriz…
Augmenting graphs to minimize the diameter
Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson +1
We study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT 4-appro…
Don't Be Strict in Local Search!
Serge Gaspers, Eun Jung Kim, Sebastian Ordyniak +2
Local Search is one of the fundamental approaches to combinatorial optimization and it is used throughout AI. Several local search algorithms are based on searching the k-exchange…
On Finding Optimal Polytrees
Serge Gaspers, Mikko Koivisto, Mathieu Liedloff +2
Inferring probabilistic networks from data is a notoriously difficult task. Under various goodness-of-fit measures, finding an optimal network is NP-hard, even if restricted to pol…
Strong Backdoors to Bounded Treewidth SAT
Serge Gaspers, Stefan Szeider
There are various approaches to exploiting "hidden structure" in instances of hard combinatorial problems to allow faster algorithms than for general unstructured or random instanc…
Strong Backdoors to Nested Satisfiability
Serge Gaspers, Stefan Szeider
Knuth (1990) introduced the class of nested formulas and showed that their satisfiability can be decided in polynomial time. We show that, parameterized by the size of a smallest s…
k-Gap Interval Graphs
Fedor V. Fomin, Serge Gaspers, Petr Golovach +5
We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real…
Backdoors to Satisfaction
Serge Gaspers, Stefan Szeider
A backdoor set is a set of variables of a propositional formula such that fixing the truth values of the variables in the backdoor set moves the formula into some polynomial-time d…
Backdoors to Acyclic SAT
Serge Gaspers, Stefan Szeider
Backdoor sets, a notion introduced by Williams et al. in 2003, are certain sets of key variables of a CNF formula F that make it easy to solve the formula; by assigning truth value…
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set
Serge Gaspers, Mathieu Liedloff
An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two…
Parameterizing by the Number of Numbers
Michael R. Fellows, Serge Gaspers, Frances A. Rosamond
The usefulness of parameterized algorithmics has often depended on what Niedermeier has called, "the art of problem parameterization". In this paper we introduce and explore a nove…
Complexity of Splits Reconstruction for Low-Degree Trees
Serge Gaspers, Mathieu Liedloff, Maya Stein +1
Given a vertex-weighted tree T, the split of an edge xy in T is min{s_x(xy), s_y(xy)} where s_u(uv) is the sum of all weights of vertices that are closer to u than to v in T. Given…
A Linear Vertex Kernel for Maximum Internal Spanning Tree
Fedor V. Fomin, Serge Gaspers, Saket Saurabh +1
We present a polynomial time algorithm that for any graph G and integer k >= 0, either finds a spanning tree with at least k internal vertices, or outputs a new graph G' on at most…
Kernels for Feedback Arc Set In Tournaments
Stéphane Bessy, Fedor V. Fomin, Serge Gaspers +4
A tournament T=(V,A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Fe…
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
Serge Gaspers, Gregory B. Sorkin
In this paper we introduce "hybrid" Max 2-CSP formulas consisting of "simple clauses", namely conjunctions and disjunctions of pairs of variables, and general 2-variable clauses, w…