19 citations · 37 across the 14 of their papers we have counts for
19 papers
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard
Łukasz Kowalik, Alexandra Lassota, Konrad Majewski +2
Let be a positive integer. For a finite set , we define its integer cone as the set $\mathsf{IntCone}(X) := \{ \sum_{x \in X} λ_x \cdot x \mid λ_x \in…
The Asymmetric Travelling Salesman Problem in Sparse Digraphs
Łukasz Kowalik, Konrad Majewski
Asymmetric Travelling Salesman Problem (ATSP) and its special case Directed Hamiltonicity are among the most fundamental problems in computer science. The dynamic programming algor…
Many visits TSP revisited
Łukasz Kowalik, Shaohua Li, Wojciech Nadara +2
We study the Many Visits TSP problem, where given a number for each of cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that…
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen +1
Local search is a widely-employed strategy for finding good solutions to Traveling Salesman Problem. We analyze the problem of determining whether the weight of a given cycle can b…
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…