19 papers
Fine-Grained Bounds for Courcelle's Theorem
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
Courcelle's theorem states that there exists an algorithm that takes as input a graph of treewidth at most and a MSO formula , and determines whether satisfies …
A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees
Ashwin Jacob, Diptapriyo Majumdar, Meirav Zehavi
The class of graph deletion problems has been extensively studied in theoretical computer science, particularly in the field of parameterized complexity. Recently, a new notion of…
Treewidth Parameterized by Feedback Vertex Number
Hendrik Molter, Meirav Zehavi, Amit Zivan
We provide the first algorithm for computing an optimal tree decomposition for a given graph that runs in single exponential time in the feedback vertex number of , that is,…
Minimum Temporal Spanners in Happy Graphs
Arnaud Casteigts, Hendrik Molter, Meirav Zehavi
Temporal graphs have edge sets that change over discrete time steps. Such graphs are temporally connected (TC) if all pairs of vertices can reach each other using paths that traver…
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
Jie Gao, Pawel Gawrychowski, Panos Giannopoulos +4
A \emph{disk graph} is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs,…
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
Daniel Lokshtanov, PaweÅ RzÄ Å¼ewski, Saket Saurabh +2
In this article we show that Maximum Partial List H-Coloring is polynomial-time solvable on P_5-free graphs for every fixed graph H. In particular, this implies that Maximum k-Colo…