1 citations · 2 across the 11 of their papers we have counts for
13 papers
Elimination Distance to Dominated Clusters
Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny
In the Dominated Cluster Deletion problem, we are given an undirected graph and integers and and the question is to decide whether there exists a set of at most ver…
Advances in Algorithmic Meta Theorems
Sebastian Siebertz, Alexandre Vigny
Tractability results for the model checking problem of logics yield powerful algorithmic meta theorems of the form: Every computational problem expressible in a logic can be so…
Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis +2
Disjoint-paths logic, denoted +, extends first-order logic () with atomic predicates , expressing…
Distributed domination on sparse graph classes
Ozan Heydt, Simeon Kublenz, Patrice Ossona de Mendez +2
We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with boun…
Combinatorial and Algorithmic Aspects of Monadic Stability
Jan Dreier, Nikolas Mählmann, Amer E. Mouawad +2
Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Mon…
Local planar domination revisited
Ozan Heydt, Sebastian Siebertz, Alexandre Vigny
We show how to compute a 20-approximation of a minimum dominating set in a planar graph in a constant number of rounds in the LOCAL model of distributed computing. This improves on…
Algorithms and data structures for first-order logic with connectivity under vertex failures
Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz +2
We introduce a new data structure for answering connectivity queries in undirected graphs subject to batched vertex failures. Precisely, given any graph G and integer k, we can in…
First-Order Logic with Connectivity Operators
Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny
First-order logic (FO) can express many algorithmic problems on graphs, such as the independent set and dominating set problem, parameterized by solution size. On the other hand, F…
Discrepancy and Sparsity
Mario Grobler, Yiting Jiang, Patrice Ossona de Mendez +2
We study the connections between the notions of combinatorial discrepancy and graph degeneracy. In particular, we prove that the maximum discrepancy over all subgraphs of a gra…
Recursive Backdoors for SAT
Nikolas Mählmann, Sebastian Siebertz, Alexandre Vigny
A strong backdoor in a formula of propositional logic to a tractable class of formulas is a set of variables of such that every assignment of the variable…
Constant round distributed domination on graph classes with bounded expansion
Simeon Kublenz, Sebastian Siebertz, Alexandre Vigny
We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with boun…
Dynamic Query Evaluation Over Structures with Low Degree
Alexandre Vigny
We consider the evaluation of first-order queries over classes of databases that have bounded degree and low degree. More precisely, given a query and a database, we want to effici…
Elimination distance to bounded degree on planar graphs
Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny
We study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphis…