58 citations · 327 across the 60 of their papers we have counts for
6 papers · 2 filters
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…
Not So Easy Problems for Tree Decomposable Graphs
Stefan Szeider
We consider combinatorial problems that can be solved in polynomial time for graphs of bounded treewidth but where the order of the polynomial that bounds the running time is expec…
Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming
Gregory Gutin, Eun Jung Kim, Arezou Soleimanfallah +2
The NP-hard general factor problem asks, given a graph and for each vertex a list of integers, whether the graph has a spanning subgraph where each vertex has a degree that belongs…
Satisfiability of Acyclic and Almost Acyclic CNF Formulas
Sebastian Ordyniak, Daniel Paulusma, Stefan Szeider
We show that the Satisfiability (SAT) problem for CNF formulas with β-acyclic hypergraphs can be solved in polynomial time by using a special type of Davis-Putnam resolution in whi…