In this paper we show that every graph G of bounded maximum average degree mad(G) and with maximum degree Δ can be edge-colored using the optimal number of Δ colors in quasilinear time, whenever Δ ≥ 2mad(G). The maximum average degree is within a multiplicative constant of other popular graph sparsity parameters like arboricity, degeneracy or maximum density. Our algorithm extends previous results of Chrobak and Nishizeki [Marek Chrobak and Takao Nishizeki, 1990] and Bhattacharya, Costa, Panski and Solomon [Sayan Bhattacharya et al., 2023].

We study the Many-Visits Traveling Salesman 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 O⁎(5n). They also show a polynomial-space algorithm running in time O(16n+o(n)). In this work, we show three main results: A randomized polynomial-space algorithm running in time O⁎(2nD), where D is the maximum distance between two cities. By using standard methods, this results in a (1+ϵ)-approximation running in time O⁎(2nϵ−1). A tight analysis of Berger et al.'s exponential-space algorithm, resulting in an O⁎(4n) running time bound. A new polynomial-space algorithm, running in time O(7.88n).

Publikacja bezkosztowa

Asymmetric Travelling Salesman Problem (ATSP) and its special case Directed Hamiltonicity are among the most fundamental problems in computer science. The dynamic programming algorithm running in time 𝒪^*(2ⁿ) developed almost 60 years ago by Bellman, Held and Karp, is still the state of the art for both of these problems. In this work we focus on sparse digraphs. First, we recall known approaches for Undirected Hamiltonicity and TSP in sparse graphs and we analyse their consequences for Directed Hamiltonicity and ATSP in sparse digraphs, either by adapting the algorithm, or by using reductions. In this way, we get a number of running time upper bounds for a few classes of sparse digraphs, including 𝒪^*(2^(n/3)) for digraphs with both out- and indegree bounded by 2, and 𝒪^*(3^(n/2)) for digraphs with outdegree bounded by 3. Our main results are focused on digraphs of bounded average outdegree d. The baseline for ATSP here is a simple enumeration of cycle covers which can be done in time bounded by 𝒪^*(μ(d)ⁿ) for a function μ(d) ≤ (⌈d⌉!)^(1/⌈d⌉). One can also observe that Directed Hamiltonicity can be solved in randomized time 𝒪^*((2-2^(-d))ⁿ) and polynomial space, by adapting a recent result of Björklund [ISAAC 2018] stated originally for Undirected Hamiltonicity in sparse bipartite graphs. We present two new deterministic algorithms for ATSP: the first running in time 𝒪(2^(0.441(d-1)n)) and polynomial space, and the second in exponential space with running time of 𝒪^*(τ(d)^(n/2)) for a function τ(d) ≤ d.

Publikacja bezkosztowa

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.

The availability of complex temporal datasets in social, health and consumer contexts has driven the development of pattern mining techniques that enable the use of classical machine learning tools for model building. In this work we introduce a robust temporal pattern mining framework for finding predictive patterns in complex timestamped multivariate and noisy data. We design an algorithm RobustSPAM that enables mining of temporal patterns from data with noisy timestamps. We apply our algorithm to social care data from a local government body and investigate how the efficiency and accuracy of the method depends on the level of noise. We further explore the trade-off between the loss of predictivity due to perturbation of timestamps and the risk of person re-identification.

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 show two results related to finding trees and paths in graphs. First, we show that in $O^*(1.657^k2^{l/2})$ time one can either find a $k$-vertex tree with $l$ leaves in an $n$-vertex undirected graph or conclude that such a tree does not exist. Our solution can be applied as a subroutine to solve the $k$-Internal Spanning Tree 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 running time 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 Hamiltonicity and $k$-Path in any graph of maximum degree $\Delta=4,\ldots,12$ or with vector chromatic number at most 8. Our results extend the technique by Björklund [SIAM J. Comput., 43 (2014), pp. 280--299] and Björklund et al. [Narrow Sieves for Parameterized Paths and Packings, CoRR, arXiv:1007. 1161, 2010] to finding structures more general than paths as well as refine it to handle special classes of graphs more efficiently.

Vassilevska and Williams (STOC’09) 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’09), and Björklund et al. (ESA’09), 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’10) showed that these problems have Ω( n ⌊ st /2⌋ ) and Ω( n ⌊ k /2⌋ ) lower bounds when counting by color coding. Here, we show that one can do better—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 ≪ k in an n -vertex graph in n 0.45470382 k +2 p + 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.

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 introduce a new algebraic sieving technique to detect constrained multilinear monomials in multivariate polynomial generating functions given by an evaluation oracle. The polynomials are assumed to have coefficients from a field of characteristic two. As applications of the technique, we show an $$O^*(2^k)$$ -time polynomial space algorithm for the $$k$$ -sized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, Min-Substitute Graph Motif, and Min-Add Graph Motif. Finally, we provide a piece of evidence that our result might be essentially tight: the existence of an $$O^*((2-\epsilon )^k)$$ -time algorithm for the Graph Motif problem implies an $$O((2-\epsilon ')^n)$$ -time algorithm for Set Cover.

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.

In the graph motif problem, we are given as input a vertex-colored graph H (the host graph) and a multiset of colors M (the motif). Our task is to decide whether H has a connected set of vertices whose multiset of colors agrees with M. The graph motif problem is NP-complete but known to admit parameterized algorithms that run in linear time in the size of H. We demonstrate that algorithms based on constrained multilinear sieving are viable in practice, scaling to graphs with hundreds of millions of edges as long as M remains small. Furthermore, our implementation is topology-invariant relative to the host graph H, meaning only the most crude graph parameters (number of edges and number of vertices) suffice in practice to determine the algorithm performance.

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 nk/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 et al. (ESA 2009), via nst/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⌊st/2⌋) and Ω(n⌊k/2⌋) 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 n0.4547st+O(1) for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth p ≪ k in an n-vertex graph in n0.4547k+2p+O(1) time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound.

Let $G=(V,E)$ be a simple graph of maximum degree $\Delta$. The edges of $G$ can be colored with at most $\Delta +1$ colors by Vizing's theorem. We study lower bounds on the size of subgraphs of $G$ that can be colored with $\Delta$ colors. Vizing's theorem gives a bound of $\frac{\Delta}{\Delta+1}|E|$. This is known to be tight for cliques $K_{\Delta+1}$ when $\Delta$ is even. However, for $\Delta=3$ it was improved to $\frac{26}{31}|E|$ by Albertson and Haas [Discrete Math., 148 (1996), pp. 1--7] and later to $\frac{6}7|E|$ by Rizzi [Discrete Math., 309 (2009), pp. 4166--4170]. It is tight for $B_3$, the graph isomorphic to a $K_4$ with one edge subdivided. We improve previously known bounds for $\Delta\in\{3,\ldots,7\}$, under the assumption that for $\Delta=3,4,6$, graph $G$ is not isomorphic to $B_3$, $K_5$, and $K_7$, respectively. For $\Delta \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 the maximum number of edges. In particular, when $G$ is simple for $k=3,4,5,6,7$ we obtain approximation ratios of $\frac{13}{15},\frac{9}{11}$, $\frac{19}{22}$, $\frac{23}{27}$, and $\frac{22}{25}$, respectively. We also present a $\frac{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$.

We show an O^*(2^k)-time polynomial space algorithm for the k-sized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, Min-Substitute, and Min-Add. Moreover, we provide a piece of evidence that our result might be essentially tight: the existence of an O^*((2-epsilon)^k)-time algorithm for the Graph Motif problem implies an ((2-epsilon')^n)-time algorithm for Set Cover.

The central problem of the total-colorings is the total-coloring conjecture, which asserts that every graph of maximum degree $\Delta$ admits a $(\Delta+2)$-total-coloring. Similar to edge-colorings—with Vizing's edge-coloring conjecture—this bound can be decreased by 1 for plane graphs of higher maximum degree. More precisely, it is known that if $\Delta\ge10$, then every plane graph of maximum degree $\Delta$ is $(\Delta+1)$-totally-colorable. On the other hand, such a statement does not hold if $\Delta\le3$. We prove that every plane graph of maximum degree 9 can be 10-totally-colored.

An edge of a graph is light when the sum of the degrees of its end‐vertices is at most 13. The well‐known Kotzig theorem states that every 3‐connected planar graph contains a light edge. Later, Borodin [J. Reine Angew. Math., 394 (1989), pp. 180–185] extended this result to the class of planar graphs of minimum degree at least 3. We deal with generalizations of these results for planar graphs of minimum degree 2. Borodin, Kostochka, and Woodall [J. Combin. Theory Ser. B, 71 (1997), pp. 184–204] showed that each such graph contains a light edge or a member of two infinite sets of configurations, called 2‐alternating cycles and 3‐alternators. This implies that planar graphs with maximum degree $\Delta \geq 12$ are $\Delta$‐edge‐choosable. We prove a similar result with 2‐alternating cycles and 3‐alternators replaced by five fixed bounded‐sized configurations called crowns. This gives another proof of $\Delta$‐edge‐choosability of planar graphs with $\Delta \geq 12$. However, we show efficient choosability; i.e., we describe a linear‐time algorithm for $\max\{\Delta,12\}$‐edge‐list‐coloring planar graphs. This extends the result of Chrobak and Yung [J. Algorithms, 10 (1989), pp. 35–51].

We present a new approach for answering short path queries in planar graphs. For any fixed constant k and a given unweighted planar graph G = ( V , E ), one can build in O(|V|) time a data structure, which allows to check in O(1) time whether two given vertices are at distance at most k in G and if so a shortest path between them is returned. Graph G can be undirected as well as directed.Our data structure works in fully dynamic environment. It can be updated in O(1) time after removing an edge or a vertex while updating after an edge insertion takes polylogarithmic amortized time. Besides deleting elements one can also disable ones for some time. It is motivated by a practical situation where nodes or links of a network may be temporarily out of service.Our results can be easily generalized to other wide classes of graphs---for instance we can take any minor-closed family of graphs.

We present a new algorithm for answering short path queries in planar graphs. For any fixed constant k and a given unweighted planar graph G=(V,E) one can build in O(|V|) time a data structure, which allows to check in O(1) time whether two given vertices are distant by at most k in G and if so a shortest path between them is returned. This significantly improves the previous result of D. Eppstein [5] where after a linear preprocessing the queries are answered in O(log |V|) time. Our approach can be applied to compute the girth of a planar graph and a corresponding shortest cycle in O(|V|) time provided that the constant bound on the girth is known.Our results can be easily generalized to other wide classes of graphs~--~for instance we can take graphs embeddable in a surface of bounded genus or graphs of bounded tree-width.