121 citations · 375 across the 53 of their papers we have counts for
7 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…
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
Marek Cygan, Fabrizio Grandoni, Danny Hermelin
In this paper we consider kernelization for problems on d-degenerate graphs, i.e. graphs such that any subgraph contains a vertex of degree at most . This graph class generalize…
Fast branching algorithm for Cluster Vertex Deletion
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka +1
In the family of clustering problems, we are given a set of objects (vertices of the graph), together with some observed pairwise similarities (edges). The goal is to identify clus…
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…
Improved approximation for 3-dimensional matching via bounded pathwidth local search
Marek Cygan
One of the most natural optimization problems is the k-Set Packing problem, where given a family of sets of size at most k one should select a maximum size subfamily of pairwise di…
Faster exponential-time algorithms in graphs of bounded average degree
Marek Cygan, Marcin Pilipczuk
We first show that the Traveling Salesman Problem in an n-vertex graph with average degree bounded by d can be solved in O*(2^{(1-\eps_d)n}) time and exponential space for a consta…
On Pairwise Spanners
Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha
Given an undirected -node unweighted graph , a spanner with stretch function is a subgraph such that, if two nodes are at distance in $…