16 citations · 188 across the 122 of their papers we have counts for
10 papers · 1 filter
Shortest paths in one-counter systems
Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman +2
We show that any one-counter automaton with states, if its language is non-empty, accepts some word of length at most . This closes the gap between the previously known…
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…
Linear kernels for outbranching problems in sparse digraphs
Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk +1
In the -Leaf Out-Branching and -Internal Out-Branching problems we are given a directed graph with a designated root and a nonnegative integer . The question is to…
On space efficiency of algorithms working on structural decompositions of graphs
Michał Pilipczuk, Marcin Wrochna
Dynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponential-time algorithms. However, one of its d…
On ultralimits of sparse graph classes
Michał Pilipczuk, Szymon Toruńczyk
The notion of nowhere denseness is one of the central concepts of the recently developed theory of sparse graphs. We study the properties of nowhere dense graph classes by investig…
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…
Edge Bipartization faster than
Marcin Pilipczuk, Michał Pilipczuk, Marcin Wrochna
In the Edge Bipartization problem one is given an undirected graph and an integer , and the question is whether edges can be deleted from so that it becomes bipartit…
Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
Dániel Marx, Michał Pilipczuk
We study a general family of facility location problems defined on planar graphs and on the 2-dimensional plane. In these problems, a subset of objects has to be selected, sati…
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)-…
How to Hunt an Invisible Rabbit on a Graph
Tatjana V. Abramovskaya, Fedor V. Fomin, Petr A. Golovach +1
We investigate Hunters & Rabbit game, where a set of hunters tries to catch an invisible rabbit that slides along the edges of a graph. We show that the minimum number of hunters r…