4 citations · 12 across the 8 of their papers we have counts for
12 papers
Tight Lower Bounds for List Edge Coloring
Łukasz Kowalik, Arkadiusz Socała
The fastest algorithms for edge coloring run in time , where and are the number of edges and vertices of the input graph, respectively. For dense graphs, this…
On Directed Feedback Vertex Set parameterized by treewidth
Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof +3
We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot…
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…
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…
Linear kernels for outbranching problems in sparse digraphs
Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk +1
In the -Leaf Out-Branching and -Internal Out-Branching problems we are given a directed graph with a designated root and a nonnegative integer . The question is to…
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…
Assigning channels via the meet-in-the-middle approach
Łukasz Kowalik, Arkadiusz Socała
We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the -bounded Channel Assignment (when the edge…
Tight lower bound for the channel assignment problem
Arkadiusz Socala
We study the complexity of the Channel Assignment problem. A major open problem asks whether Channel Assignment admits an -time algorithm, for a constant independent of…
Beyond the Shannon's Bound
Michał Farnik, Łukasz Kowalik, Arkadiusz Socała
Let be a multigraph of maximum degree . The edges of can be colored with at most colors by Shannon's theorem. We study lower bounds on the size of s…