121 citations · 375 across the 53 of their papers we have counts for
5 papers · 1 filter
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…
Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
Ivan Bliznets, Marek Cygan, Pawel Komosa +2
In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and…
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)-…