121 citations · 375 across the 53 of their papers we have counts for
49 papers · 1 filter
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems
Marek Cygan, Magnús M. Halldórsson, Guy Kortsarz
We show that Set Cover on instances with elements cannot be approximated within -factor in time exp(, for any and any , assuming the Expo…
On subexponential running times for approximating directed Steiner tree and related problems
Marek Cygan, Guy Kortsarz, Bundit Laekhanukit
This paper concerns proving almost tight (super-polynomial) running times, for achieving desired approximation ratios for various problems. To illustrate, the question we study, le…
Randomized contractions meet lean decompositions
Marek Cygan, Paweł Komosa, Daniel Lokshtanov +4
We show an algorithm that, given an -vertex graph and a parameter , in time finds a tree decomposition of with the following properties: *…
Online Facility Location with Deletions
Marek Cygan, Artur Czumaj, Marcin Mucha +1
In this paper we study three previously unstudied variants of the online Facility Location problem, considering an intrinsic scenario when the clients and facilities are not only a…
Improving TSP tours using dynamic programming over tree decomposition
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
Given a traveling salesman problem (TSP) tour in graph a -move is an operation which removes edges from , and adds edges of so that a new tour is for…
On problems equivalent to (min,+)-convolution
Marek Cygan, Marcin Mucha, Karol Węgrzycki +1
In recent years, significant progress has been made in explaining the apparent hardness of improving upon the naive solutions for many fundamental polynomially solvable problems. T…
Approximation and Parameterized Complexity of Minimax Approval Voting
Marek Cygan, Łukasz Kowalik, Arkadiusz Socała +1
We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance from the solution to the vo…
Hardness of approximation for H-free edge modification problems
Ivan Bliznets, Marek Cygan, Pawel Komosa +1
The -Free Edge Deletion problem asks, for a given graph and an integer , whether it is possible to delete at most edges from to make it -free, that is, not con…
Tight Lower Bounds on Graph Embedding Problems
Marek Cygan, Fedor V. Fomin, Alexander Golovnev +4
We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph to graph cannot be done in time . We al…
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…
Algorithmic Complexity of Power Law Networks
Paweł Brach, Marek Cygan, Jakub Łącki +1
It was experimentally observed that the majority of real-world networks follow power law degree distribution. The aim of this paper is to study the algorithmic complexity of such "…
The Hardness of Subgraph Isomorphism
Marek Cygan, Jakub Pachocki, Arkadiusz Socała
Subgraph Isomorphism is a very basic graph problem, where given two graphs and one is to check whether is a subgraph of . Despite its simple definition, the Subgraph…
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)-…
Hitting forbidden subgraphs in graphs of bounded treewidth
Marek Cygan, Dániel Marx, Marcin Pilipczuk +1
We study the complexity of a generic hitting problem H-Subgraph Hitting, where given a fixed pattern graph and an input graph , the task is to find a set …
Approximating Upper Degree-Constrained Partial Orientations
Marek Cygan, Tomasz Kociumaka
In the Upper Degree-Constrained Partial Orientation problem we are given an undirected graph , together with two degree constraint functions .…
Kernelization lower bound for Permutation Pattern Matching
Ivan Bliznets, Marek Cygan, Pawel Komosa +1
A permutation contains a permutation as a pattern if it contains a subsequence of length whose elements are in the same relative order as in the permutation . This…
Constant Factor Approximation for Capacitated k-Center with Outliers
Tomasz Kociumaka, Marek Cygan
The -center problem is a classic facility location problem, where given an edge-weighted graph one is to find a subset of vertices , such that each vertex in…
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…
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 $…
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…