23 citations · 60 across the 50 of their papers we have counts for
8 papers · 1 filter
Compound Logics for Modification Problems
Fedor V. Fomin, Petr A. Golovach, Ignasi Sau +2
We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framew…
FPT algorithms for packing -safe spanning rooted sub(di)graphs
Stéphane Bessy, Florian Hörsch, Ana Karolinna Maia +2
We study three problems introduced by Bang-Jensen and Yeo [Theor. Comput. Sci. 2015] and by Bang-Jensen, Havet, and Yeo [Discret. Appl. Math. 2016] about finding disjoint "balanced…
Hitting minors on bounded treewidth graphs. III. Lower bounds
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos
For a finite collection of graphs , the -M-DELETION problem consists in, given a graph and an integer , decide whether there exists wi…
Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos
For a finite collection of graphs , the -M-DELETION (resp. -TM-DELETION) problem consists in, given a graph and an integer , decide whether the…
k-apices of minor-closed graph classes. I. Bounding the obstructions
Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos
Let be a minor-closed graph class. We say that a graph is a -apex of if contains a set of at most vertices such that b…
Parameterized complexity of computing maximum minimal blocking and hitting sets
Júlio Araújo, Marin Bougeret, Victor A. Campos +1
A blocking set in a graph is a subset of vertices that intersects every maximum independent set of . Let be the size of a maximum (inclusion-wise) minimal bl…