121 citations · 375 across the 53 of their papers we have counts for
10 papers · 1 filter
Fast Hamiltonicity checking via bases of perfect matchings
Marek Cygan, Stefan Kratsch, Jesper Nederlof
For an even integer t \geq 2, the Matchings Connecivity matrix H_t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K_t on t vertic…
Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time
Hans L. Bodlaender, Marek Cygan, Stefan Kratsch +1
It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2^{O(tw)}|V|^{O(1)} time for graphs G=(V,E) with a given tree decomposition…
LP Rounding for k-Centers with Non-uniform Hard Capacities
Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller
In this paper we consider a generalization of the classical k-center problem with capacities. Our goal is to select k centers in a graph, and assign each node to a nearby center, s…
On fixed-parameter algorithms for Split Vertex Deletion
Marek Cygan, Marcin Pilipczuk
In the Split Vertex Deletion problem, given a graph G and an integer k, we ask whether one can delete k vertices from the graph G to obtain a split graph (i.e., a graph, whose vert…
Designing FPT algorithms for cut problems using randomized contractions
Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi +2
We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. We apply our framework to obtain the first FPT algorithm for…
Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable
Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi +1
Given a graph and an integer , the Feedback Vertex Set (FVS) problem asks if there is a vertex set of size at most that hits all cycles in the graph. The fixed-param…
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings
Marek Cygan, Harold N. Gabow, Piotr Sankowski
Consider a directed or an undirected graph with integral edge weights from the set [-W, W], that does not contain negative weight cycles. In this paper, we introduce a general fram…
Known algorithms for EDGE CLIQUE COVER are probably optimal
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk
In the EDGE CLIQUE COVER (ECC) problem, given a graph G and an integer k, we ask whether the edges of G can be covered with k complete subgraphs of G or, equivalently, whether G ad…
Deterministic parameterized connected vertex cover
Marek Cygan
In the Connected Vertex Cover problem we are given an undirected graph G together with an integer k and we are to find a subset of vertices X of size at most k, such that X contain…
Sitting closer to friends than enemies, revisited
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk +1
Signed graphs, i.e., undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, Kermarrec and Thraves i…