7 citations · 7 across the 1 of their papers we have counts for
4 papers
Constant Congestion Brambles
Meike Hatzel, Pawel Komosa, Marcin Pilipczuk +1
A bramble in an undirected graph is a family of connected subgraphs of such that for every two subgraphs and in the bramble either $V(H_1) \cap V(H_2) \neq \emp…
Randomized contractions meet lean decompositions
Marek Cygan, Paweł Komosa, Daniel Lokshtanov +4
We show an algorithm that, given an -vertex graph and a parameter , in time finds a tree decomposition of with the following properties: *…
Hardness of approximation for H-free edge modification problems
Ivan Bliznets, Marek Cygan, Pawel Komosa +1
The -Free Edge Deletion problem asks, for a given graph and an integer , whether it is possible to delete at most edges from to make it -free, that is, not con…
Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
Ivan Bliznets, Marek Cygan, Pawel Komosa +2
In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and…