7 citations · 7 across the 3 of their papers we have counts for
5 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…
Kernelization lower bound for Permutation Pattern Matching
Ivan Bliznets, Marek Cygan, Pawel Komosa +1
A permutation contains a permutation as a pattern if it contains a subsequence of length whose elements are in the same relative order as in the permutation . This…