Pawel Komosa

activity

20142020

most citedConstant Congestion Brambles

7 citations · 7 across the 3 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2018

Randomized contractions meet lean decompositions

Marek Cygan, Paweł Komosa, Daniel Lokshtanov +4

We show an algorithm that, given an $n$ -vertex graph $G$ and a parameter $k$ , in time $2^{O (k l o g k)} n^{O (1)}$ finds a tree decomposition of $G$ with the following properties: *…

cs.DS2016

Hardness of approximation for H-free edge modification problems

Ivan Bliznets, Marek Cygan, Pawel Komosa +1

The $H$ -Free Edge Deletion problem asks, for a given graph $G$ and an integer $k$ , whether it is possible to delete at most $k$ edges from $G$ to make it $H$ -free, that is, not con…

cs.DS2014

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…