4 citations · 12 across the 8 of their papers we have counts for
4 papers · 1 filter
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…
Tight lower bounds for the complexity of multicoloring
Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk +2
In the multicoloring problem, also known as (:)-coloring or -fold coloring, we are given a graph G and a set of colors, and the task is to assign a subset of color…
On the fine-grained complexity of rainbow coloring
Łukasz Kowalik, Juho Lauri, Arkadiusz Socała
The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in colors so that every pair of vertices is connected by a rainbow path, i.e., a path with…
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…