Source author record

Łukasz Kowalik

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics math.CO Artificial Intelligence Computer Science and Game Theory Multiagent Systems

Catalog footprint

Research overview

11works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Many visits TSP revisited

We study the Many Visits TSP problem, where given a number $k(v)$ for each of $n$ cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city $v$ exactly $k(v)$ times. The currently fastest algorithm is due to Berger, Kozma, Mnich and Vincze [SODA 2019, TALG 2020] and runs in time and space $\mathcal{O}^*(5^n)$ . They also show a polynomial space algorithm running in time $\mathcal{O}^*(16^{n+o(n)})$ . In this work, we show three main results: (i) A randomized polynomial space algorithm in time $\mathcal{O}^*(2^nD)$ , where $D$ is the maximum distance between two cities. By using standard methods, this results in $(1+ε)$ -approximation in time $\mathcal{O}^*(2^nε^{-1})$ . Improving the constant $2$ in these results would be a major breakthrough, as it would result in improving the $\mathcal{O}^*(2^n)$ -time algorithm for Directed Hamiltonian Cycle, which is a 50 years old open problem. (ii) A tight analysis of Berger et al.'s exponential space algorithm, resulting in $\mathcal{O}^*(4^n)$ running time bound. (iii) A new polynomial space algorithm, running in time $\mathcal{O}(7.88^n)$ .

preprint2016arXiv

Approximation and Parameterized Complexity of Minimax Approval Voting

We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance $d$ from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in time $\mathcal{O}^\star(2^{o(d\log d)})$ , unless the Exponential Time Hypothesis (ETH) fails. This means that the $\mathcal{O}^\star(d^{2d})$ algorithm of Misra et al. [AAMAS 2015] is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time $\mathcal{O}^\star(\left({3}/ε\right)^{2d})$ , which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for Minimax Approval Voting, which runs in time $n^{\mathcal{O}(1/ε^2 \cdot \log(1/ε))} \cdot \mathrm{poly}(m)$ , almost matching the running time of the fastest known PTAS for Closest String due to Ma and Sun [SIAM J. Comp. 2009].

preprint2016arXiv

On the fine-grained complexity of rainbow coloring

The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in $k$ colors so that every pair of vertices is connected by a rainbow path, i.e., a path with all edges of different colors. Our main result states that for any $k\ge 2$ , there is no algorithm for Rainbow k-Coloring running in time $2^{o(n^{3/2})}$ , unless ETH fails. Motivated by this negative result we consider two parameterized variants of the problem. In Subset Rainbow k-Coloring problem, introduced by Chakraborty et al. [STACS 2009, J. Comb. Opt. 2009], we are additionally given a set $S$ of pairs of vertices and we ask if there is a coloring in which all the pairs in $S$ are connected by rainbow paths. We show that Subset Rainbow k-Coloring is FPT when parameterized by $|S|$ . We also study Maximum Rainbow k-Coloring problem, where we are additionally given an integer $q$ and we ask if there is a coloring in which at least $q$ anti-edges are connected by rainbow paths. We show that the problem is FPT when parameterized by $q$ and has a kernel of size $O(q)$ for every $k\ge 2$ (thus proving that the problem is FPT), extending the result of Ananth et al. [FSTTCS 2011].

preprint2015arXiv

Counting thin subgraphs via packings faster than meet-in-the-middle time

Vassilevska and Williams (STOC 2009) showed how to count simple paths on $k$ vertices and matchings on $k/2$ edges in an $n$ -vertex graph in time $n^{k/2+O(1)}$ . In the same year, two different algorithms with the same runtime were given by Koutis and Williams~(ICALP 2009), and Björklund \emph{et al.} (ESA 2009), via $n^{st/2+O(1)}$ -time algorithms for counting $t$ -tuples of pairwise disjoint sets drawn from a given family of $s$ -sized subsets of an $n$ -element universe. Shortly afterwards, Alon and Gutner (TALG 2010) showed that these problems have $Ω(n^{\lfloor st/2\rfloor})$ and $Ω(n^{\lfloor k/2\rfloor})$ lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the "meet-in-the-middle" exponent $st/2$ can be beaten and give an algorithm that counts in time $n^{0.45470382 st + O(1)}$ for $t$ a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on $k$ vertices and pathwidth $p\ll k$ in an $n$ -vertex graph in $n^{0.45470382k+2p+O(1)}$ time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound. We also give improved bounds for counting $t$ -tuples of disjoint $s$ -sets for $s=2,3,4$ . Our algorithms use fast matrix multiplication. We show an argument that this is necessary to go below the meet-in-the-middle barrier.

preprint2015arXiv

Fast Witness Extraction Using a Decision Oracle

The gist of many (NP-)hard combinatorial problems is to decide whether a universe of $n$ elements contains a witness consisting of $k$ elements that match some prescribed pattern. For some of these problems there are known advanced algebra-based FPT algorithms which solve the decision problem but do not return the witness. We investigate techniques for turning such a YES/NO-decision oracle into an algorithm for extracting a single witness, with an objective to obtain practical scalability for large values of $n$ . By relying on techniques from combinatorial group testing, we demonstrate that a witness may be extracted with $O(k\log n)$ queries to either a deterministic or a randomized set inclusion oracle with one-sided probability of error. Furthermore, we demonstrate through implementation and experiments that the algebra-based FPT algorithms are practical, in particular in the setting of the $k$ -path problem. Also discussed are engineering issues such as optimizing finite field arithmetic.

preprint2015arXiv

Linear kernels for outbranching problems in sparse digraphs

In the $k$ -Leaf Out-Branching and $k$ -Internal Out-Branching problems we are given a directed graph $D$ with a designated root $r$ and a nonnegative integer $k$ . The question is to determine the existence of an outbranching rooted at $r$ that has at least $k$ leaves, or at least $k$ internal vertices, respectively. Both these problems were intensively studied from the points of view of parameterized complexity and kernelization, and in particular for both of them kernels with $O(k^2)$ vertices are known on general graphs. In this work we show that $k$ -Leaf Out-Branching admits a kernel with $O(k)$ vertices on $\mathcal{H}$ -minor-free graphs, for any fixed family of graphs $\mathcal{H}$ , whereas $k$ -Internal Out-Branching admits a kernel with $O(k)$ vertices on any graph class of bounded expansion.

preprint2015arXiv

Spotting Trees with Few Leaves

We show two results related to the Hamiltonicity and $k$ -Path algorithms in undirected graphs by Björklund [FOCS'10], and Björklund et al., [arXiv'10]. First, we demonstrate that the technique used can be generalized to finding some $k$ -vertex tree with $l$ leaves in an $n$ -vertex undirected graph in $O^*(1.657^k2^{l/2})$ time. It can be applied as a subroutine to solve the $k$ -Internal Spanning Tree ( $k$ -IST) problem in $O^*(\min(3.455^k, 1.946^n))$ time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time we break the natural barrier of $O^*(2^n)$ . Second, we show that the iterated random bipartition employed by the algorithm can be improved whenever the host graph admits a vertex coloring with few colors; it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for $k$ -Path and Hamiltonicity in any graph of maximum degree $Δ=4,\ldots,12$ or with vector chromatic number at most 8.

preprint2014arXiv

Assigning channels via the meet-in-the-middle approach

We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the $\ell$ -bounded Channel Assignment (when the edge weights are bounded by $\ell$ ) running in time $O^*((2\sqrt{\ell+1})^n)$ . This is the first algorithm which breaks the $(O(\ell))^n$ barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. A major open problem asks whether Channel Assignment admits a $O(c^n)$ -time algorithm, for a constant $c$ independent of $\ell$ . We consider a similar question for Generalized T-Coloring, a CSP problem that generalizes \CA. We show that Generalized T-Coloring does not admit a $2^{2^{o\left(\sqrt{n}\right)}} {\rm poly}(r)$ -time algorithm, where $r$ is the size of the instance.

preprint2014arXiv

Beyond the Vizing's bound for at most seven colors

Let $G=(V,E)$ be a simple graph of maximum degree $Δ$ . The edges of $G$ can be colored with at most $Δ+1$ colors by Vizing's theorem. We study lower bounds on the size of subgraphs of $G$ that can be colored with $Δ$ colors. Vizing's Theorem gives a bound of $\fracΔ{Δ+1}|E|$ . This is known to be tight for cliques $K_{Δ+1}$ when $Δ$ is even. However, for $Δ=3$ it was improved to $26/31|E|$ by Albertson and Haas [Parsimonious edge colorings, Disc. Math. 148, 1996] and later to $6/7|E|$ by Rizzi [Approximating the maximum 3-edge-colorable subgraph problem, Disc. Math. 309, 2009]. It is tight for $B_3$ , the graph isomorphic to a $K_4$ with one edge subdivided. We improve previously known bounds for $Δ\in{3,...,7}$ , under the assumption that for $Δ=3,4,6$ graph $G$ is not isomorphic to $B_3$ , $K_5$ and $K_7$ , respectively. For $Δ\geq 4$ these are the first results which improve over the Vizing's bound. We also show a new bound for subcubic multigraphs not isomorphic to $K_3$ with one edge doubled. In the second part, we give approximation algorithms for the Maximum k-Edge-Colorable Subgraph problem, where given a graph G (without any bound on its maximum degree or other restrictions) one has to find a k-edge-colorable subgraph with maximum number of edges. In particular, when G is simple for k=3,4,5,6,7 we obtain approximation ratios of 13/15, 9/11, 19/22, 23/27 and 22/25, respectively. We also present a 7/9-approximation for k=3 when G is a multigraph. The approximation algorithms follow from a new general framework that can be used for any value of k.

preprint2013arXiv

Beyond the Shannon's Bound

Let $G=(V,E)$ be a multigraph of maximum degree $Δ$ . The edges of $G$ can be colored with at most $\frac{3}{2}Δ$ colors by Shannon's theorem. We study lower bounds on the size of subgraphs of $G$ that can be colored with $Δ$ colors. Shannon's Theorem gives a bound of $\fracΔ{\lfloor\frac{3}{2}Δ\rfloor}|E|$ . However, for $Δ=3$ , Kamiński and Kowalik [SWAT'10] showed that there is a 3-edge-colorable subgraph of size at least $\frac{7}{9}|E|$ , unless $G$ has a connected component isomorphic to $K_3+e$ (a $K_3$ with an arbitrary edge doubled). Here we extend this line of research by showing that $G$ has a $Δ$ -edge colorable subgraph with at least $\fracΔ{\lfloor\frac{3}{2}Δ\rfloor-1}|E|$ edges, unless $Δ$ is even and $G$ contains $\fracΔ{2}K_3$ or $Δ$ is odd and $G$ contains $\frac{Δ-1}{2}K_3+e$ . Moreover, the subgraph and its coloring can be found in polynomial time. Our results have applications in approximation algorithms for the Maximum $k$ -Edge-Colorable Subgraph problem, where given a graph $G$ (without any bound on its maximum degree or other restrictions) one has to find a $k$ -edge-colorable subgraph with maximum number of edges. In particular, for every even $k \ge 4$ we obtain a $\frac{2k+2}{3k+2}$ -approximation and for every odd $k\ge 5$ we get a $\frac{2k+1}{3k}$ -approximation. When $4\le k \le 13$ this improves over earlier algorithms due to Feige et al. [APPROX'02]

preprint2011arXiv

Channel Assignment via Fast Zeta Transform

We show an O*((l+1)^n)-time algorithm for the channel assignment problem, where l is the maximum edge weight. This improves on the previous O*((l+2)^n)-time algorithm by Kral, as well as algorithms for important special cases, like L(2,1)-labelling. For the latter problem, our algorithm works in O*(3^n) time. The progress is achieved by applying the fast zeta transform in combination with the inclusion-exclusion principle.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Łukasz Kowalik

Research overview

Is this your work?

11 publications

Many visits TSP revisited

Approximation and Parameterized Complexity of Minimax Approval Voting

On the fine-grained complexity of rainbow coloring

Counting thin subgraphs via packings faster than meet-in-the-middle time

Fast Witness Extraction Using a Decision Oracle

Linear kernels for outbranching problems in sparse digraphs

Spotting Trees with Few Leaves

Assigning channels via the meet-in-the-middle approach

Beyond the Vizing's bound for at most seven colors

Beyond the Shannon's Bound

Channel Assignment via Fast Zeta Transform

See the researcher in context

Building this map preview