121 citations · 375 across the 53 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016★ 4 cited
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…
cs.DS2016
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…
cs.DS2016
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…