Given a traveling salesman problem (TSP) tour H in graph G , a k -move is an operation that removes k edges from H and adds k edges of G so that a new tour H ′ is formed. The popular k -OPT heuristic for TSP finds a local optimum by starting from an arbitrary tour H and then improving it by a sequence of k -moves. Until 2016, the only known algorithm to find an improving k -move for a given tour was the naive solution in time O ( n k ). At ICALP’16, de Berg, Buchin, Jansen, and Woeginger showed an O ( n ⌊2 k /3⌋+1 )-time algorithm. We show an algorithm that runs in O ( n (1/4+ϵ k ) k ) time, where lim k → ∞ ϵ k = 0. It improves over the state of the art for every k ≥ 5. For the most practically relevant case k = 5, we provide a slightly refined algorithm running in O ( n 3.4 ) time. We also show that for the k = 4 case, improving over the O ( n 3 )-time algorithm of de Berg et al. would be a major breakthrough: An O ( n 3−ϵ )-time algorithm for any ϵ > 0 would imply an O ( n 3−δ )-time algorithm for the A ll P airs S hortest P aths problem, for some δ > 0.

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 O*(2o(d log d)), unless the Exponential Time Hypothesis (ETH) fails. This means that the O*(d2d) algorithm of Misra, Nabeel and Singh is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O*((3/ε)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 nO(1/ε2⋅log(1/ε))⋅poly(m), where n is a number of voters and m is a number of alternatives. It almost matches the running time of the fastest known PTAS for Closest String due to Ma and Sun.

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 the exponential time hypothesis fails. Motivated by this negative result we consider two parameterized variants of the problem. In the Subset Rainbow $k$-Coloring problem, introduced by Chakraborty et al. [ J. Comb. Optim., 21 (2009), pp. 330--347], 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 fixed parameter tractable (FPT) when parameterized by $|S|$. We also study the 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$, extending the result of Ananth, Nasre, and Sarpatwar, in FSTTCS, LIPIcs, Schloss Dagstuhl--Leibniz-Zentum für Informatik, Dagstuhl, Germany, 2011, pp. 241--251. We believe that our techniques used for the lower bounds may shed some light on the complexity of the classical Edge Coloring problem, where it is a major open question if a $2^{O(n)}$-time algorithm exists.

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 O⋆(2o(d log d), unless the Exponential Time Hypothesis (ETH) fails. This means that the O⋆(d2d) algorithm of Misra et al. (AAMAS 2015) is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O⋆((3/ε)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 nO(1/ε2·log(1/ε))· poly(m), almost matching the running time of the fastest known PTAS for CLOSEST STRING due to Ma and Sun (SIAM J. Comp. 2009).

Given a traveling salesman problem (TSP) tour H in graph G, a k-move is an operation which removes k edges from H, and adds k edges of G so that a new tour H' is formed. The popular k-opt heuristic for TSP finds a local optimum by starting from an arbitrary tour H and then improving it by a sequence of k-moves. Until 2016, the only known algorithm to find an improving k-move for a given tour was the naive solution in time O(n^k). At ICALP'16 de Berg, Buchin, Jansen and Woeginger showed an O(n^{floor(2/3k)+1})-time algorithm. We show an algorithm which runs in O(n^{(1/4 + epsilon_k)k}) time, where lim_{k -> infinity} epsilon_k = 0. It improves over the state of the art for every k >= 5. For the most practically relevant case k=5 we provide a slightly refined algorithm running in O(n^{3.4}) time. We also show that for the k=4 case, improving over the O(n^3)-time algorithm of de Berg et al. would be a major breakthrough: an O(n^{3 - epsilon})-time algorithm for any epsilon > 0 would imply an O(n^{3 - delta})-time algorithm for the All Pairs Shortest Paths problem, for some delta>0.

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 whether there exists an outbranching rooted at r that has at least k leaves, or at least k internal vertices, respectively. Both these problems have been 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.

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time | V ( H )| o (| V ( G )|) . We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of | V ( H )| o (| V ( H )|) -time algorithm deciding if graph G is a subgraph of H . For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems. Moreover, as a consequence of our reductions, conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem.

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 >= 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 the 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 Subset 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 >= 2, extending the result of Ananth et al. [FSTTCS 2011]. We believe that our techniques used for the lower bounds may shed some light on the complexity of the classical Edge Coloring problem, where it is a major open question if a 2^{O(n)}-time algorithm exists.

We prove that unless Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time |V (H)|o(|V (G)|). We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of |V (H)|o(|V (H)|)-time algorithm deciding if graph G is a subgraph of H. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems.

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. Very recently the second author showed that Channel Assignment does not admit 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 Channel Assignment. We show that Generalized $$T$$ -Coloring does not admit a $$2^{2^{o\left( \sqrt{n}\right) }} \mathrm{poly}(r)$$ -time algorithm, where r is the size of the instance.

We study the complexity of the C hannel A ssignment problem. An open problem asks whether C hannel A ssignment admits an O ( c n ) (times a polynomial in the bit size) time algorithm, where n is a number of the vertices, for a constant c independent of the weights on the edges. We answer this question in the negative. Indeed, we show that in the standard Word RAM model, there is no 2 o ( n log n ) (times a polynomial in the bit size) time algorithm solving C hannel A ssignment unless the exponential time hypothesis fails. Note that the currently best known algorithm works in time O *( n !) = 2 O ( n log n ) , so our lower bound is tight (where the O *() notation suppresses polynomial factors).

We study the complexity of the Channel Assignment problem. An open problem asks whether Channel Assignment admits an O(cn)-time algorithm, for a constant c independent of the weights on the edges. We answer this question in the negative i.e. we show that there is no 2°(n log n)-time algorithm solving Channel Assignment unless the Exponential Time Hypothesis fails. Note that the currently best known algorithm works in time O*(n!) = 2O(n log n) so our, lower bound is tight.