14 citations · 19 across the 8 of their papers we have counts for
18 papers
On the Complexity of Fundamental Problems for DAG-Compressed Graphs
Florian Chudigiewitsch, Till Tantau, Felix Winkler
A DAG compression of a (typically dense) graph is a simple data structure that stores how vertex clusters are connected, where the clusters are described indirectly as sets of reac…
The Descriptive Complexity of Relation Modification Problems
Florian Chudigiewitsch, Marlene Gründel, Christian Komusiewicz +2
A relation modification problem gets a logical structure and a natural number k as input and asks whether k modifications of the structure suffice to make it satisfy a predefined p…
On the Descriptive Complexity of Vertex Deletion Problems
Max Bannach, Florian Chudigiewitsch, Till Tantau
Vertex deletion problems for graphs are studied intensely in classical and parameterized complexity theory. They ask whether we can delete at most k vertices from an input graph su…
Existential Second-Order Logic Over Graphs: Parameterized Complexity
Max Bannach, Florian Chudigiewitsch, Till Tantau
By Fagin's Theorem, NP contains precisely those problems that can be described by formulas starting with an existential second-order quantifier, followed by only first-order quanti…
On the Parallel Parameterized Complexity of MaxSAT Variants
Max Bannach, Malte Skambath, Till Tantau
In the maximum satisfiability problem (MAX-SAT) we are given a propositional formula in conjunctive normal form and have to find an assignment that satisfies as many clauses as pos…
On the Satisfaction Probabilities of -CNF Formulas
Till Tantau
The satisfaction probability Pr[] := Pr of a propositional formula is the likelihood that a random assignment makes the formula tru…