10 citations · 26 across the 5 of their papers we have counts for
5 papers
Transducing paths in graph classes with unbounded shrubdepth
Michał Pilipczuk, Patrice Ossona de Mendez, Sebastian Siebertz
Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class ca…
Finding large induced sparse subgraphs in -free graphs in quasipolynomial time
Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk +2
For an integer , a graph is called {\em{-free}} if does not contain any induced cycle on more than~ vertices. We prove the following statement: for every pair…
Jones' Conjecture in subcubic graphs
Marthe Bonamy, François Dross, Tomáš Masařík +3
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic planar graph does not contain vertex-disjoint cycles, then it suffices to delete vertices to obta…
A O(c^k n) 5-Approximation Algorithm for Treewidth
Hans Bodlaender, Pål G. Drange, Markus S. Dregi +3
We give an algorithm that for an input n-vertex graph G and integer k>0, in time 2^[O(k)]n either outputs that the treewidth of G is larger than k, or gives a tree decomposition of…
Designing FPT algorithms for cut problems using randomized contractions
Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi +2
We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. We apply our framework to obtain the first FPT algorithm for…