5 citations · 9 across the 4 of their papers we have counts for
5 papers · 1 filter
Sallow: a heuristic algorithm for treedepth decompositions
Marcin Wrochna
We describe a heuristic algorithm for computing treedepth decompositions, submitted for the PACE 2020 challenge. It relies on a variety of greedy algorithms computing elimination o…
Tight complexity lower bounds for integer linear programming with few constraints
Dušan Knop, Michał Pilipczuk, Marcin Wrochna
We consider the ILP Feasibility problem: given an integer linear program , where is an integer matrix with rows and columns and is a vector…
Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers…
On Directed Feedback Vertex Set parameterized by treewidth
Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof +3
We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot…
Polynomial kernelization for removing induced claws and diamonds
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk +2
A graph is called (claw,diamond)-free if it contains neither a claw (a ) nor a diamond (a with an edge removed) as an induced subgraph. Equivalently, (claw,diamond)-…