19 citations · 218 across the 100 of their papers we have counts for
8 papers · 1 filter
On Routing Disjoint Paths in Bounded Treewidth Graphs
Alina Ene, Matthias Mnich, Marcin Pilipczuk +1
We study the problem of routing on disjoint paths in bounded treewidth graphs with both edge and node capacities. The input consists of a capacitated graph and a collection of…
A tight lower bound for Vertex Planarization on graphs of bounded treewidth
Marcin Pilipczuk
In the Vertex Planarization problem one asks to delete the minimum possible number of vertices from an input graph to obtain a planar graph. The parameterized complexity of this pr…
Lower bounds for approximation schemes for Closest String
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk +2
In the Closest String problem one is given a family of equal-length strings over some fixed alphabet, and the task is to find a string that minimizes the maximum H…
Independence and Efficient Domination on -free Graphs
Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen
In the Independent set problem, the input is a graph , every vertex has a non-negative integer weight, and the task is to find a set of pairwise non-adjacent vertices, maxim…
Excluding hooks and their complements
Krzysztof Choromanski, Dvir Falik, Anita Liebenau +2
The celebrated Erdos-Hajnal conjecture states that for every -vertex undirected graph there exists $\eps(H)>0$ such that every graph that does not contain as an indu…
Directed multicut is W[1]-hard, even for four terminal pairs
Marcin Pilipczuk, Magnus Wahlström
We prove that Multicut in directed graphs, parameterized by the size of the cutset, is W[1]-hard and hence unlikely to be fixed-parameter tractable even if restricted to instances…