121 citations · 360 across the 111 of their papers we have counts for
6 papers · 1 filter
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…
Polynomial Kernels for λ-extendible Properties Parameterized Above the Poljak-Turzík Bound
Robert Crowston, Mark Jones, Gabriele Muciaccia +3
Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of λ-extendible properties of graphs as a generalization of the property of being bipartite. They showed that fo…
Irrelevant Vertices for the Planar Disjoint Paths Problem
Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause +3
The Disjoint Paths Problem asks, given a graph and a set of pairs of terminals , whether there is a collection of pairwise vertex-disjoi…
Tree Deletion Set has a Polynomial Kernel (but no OPT^O(1) approximation)
Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh +1
In the Tree Deletion Set problem the input is a graph G together with an integer k. The objective is to determine whether there exists a set S of at most k vertices such that G-S i…
Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
M. S. Ramanujan, Saket Saurabh
A skew-symmetric graph is a directed graph with an involution on the set of vertices and arcs. In this paper, we introduce a separation problem, -Skew-Symm…
Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan +1
We give two algorithms computing representative families of linear and uniform matroids and demonstrate how to use representative families for designing single-exponential paramete…