16 citations · 188 across the 122 of their papers we have counts for
9 papers · 1 filter
Largest chordal and interval subgraphs faster than 2^n
Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk +1
We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time for some . These are the first…
Minimum Bisection is fixed parameter tractable
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk +2
In the classic Minimum Bisection problem we are given as input a graph and an integer . The task is to determine whether there is a partition of into two parts an…
Minimizing Rosenthal Potential in Multicast Games
Fedor V. Fomin, Petr A. Golovach, Jesper Nederlof +1
A multicast game is a network design game modelling how selfish non-cooperative agents build and maintain one-to-many network communication. There is a special source node and a co…
Exploring Subexponential Parameterized Complexity of Completion Problems
Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk +1
Let be a family of graphs. In the -Completion problem, we are given a graph and an integer as input, and asked whether at most edges can be added t…
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
Dániel Marx, Michał Pilipczuk
Given two graphs and , the Subgraph Isomorphism problem asks if is isomorphic to a subgraph of . While NP-hard in general, algorithms exist for various parameterized…
Computing Tree-depth Faster Than
Fedor V. Fomin, Archontia C. Giannopoulou, Michał Pilipczuk
A connected graph has tree-depth at most if it is a subgraph of the closure of a rooted tree whose height is at most . We give an algorithm which for a given -vertex grap…
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski +1
We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is…
The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable
Marek Cygan, Dániel Marx, Marcin Pilipczuk +1
Given a graph G and k pairs of vertices (s_1,t_1), ..., (s_k,t_k), the k-Vertex-Disjoint Paths problem asks for pairwise vertex-disjoint paths P_1, ..., P_k such that P_i goes from…
Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
Fedor V. Fomin, Michał Pilipczuk
Cutwidth of a digraph is a width measure introduced by Chudnovsky, Fradkin, and Seymour [4] in connection with development of a structural theory for tournaments, or more generally…