Search

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seems to escape from the literature. A path containing at least k vertices is considered long. When k ≤ 3 , the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4 , the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4 , the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O (1)) -approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4 . Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies. [ABSTRACT FROM AUTHOR]

The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether k -Path admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size k O (1) ? We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and K 3 , t -minor-free graphs. Moreover, we show that k -Path even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path, has a separation that can safely be reduced after communication with the oracle. [ABSTRACT FROM AUTHOR]

The classic K-CYCLE problem asks if a graph G, with vertex-set V(G), has a simple cycle containing all vertices of a given set K⊆V(G). In terms of colored graphs, it can be rephrased as follows: Given a graph G, a set K⊆V(G) and an injective coloring c:K→{1,2,...,|K|}, decide if G has a simple cycle containing each color in {1,2,...,|K|} exactly once. Another problem widely known since the introduction of color coding is COLORFUL CYCLE. Given a graph G and a coloring c:V(G)→{1,2,...,k} for some k∈N, it asks if G has a simple cycle of length k containing each color in {1,2,...,k} exactly once. We study a generalization of these problems: Given a graph G, a set K⊆V(G), a list-coloring L:K→2{1,2,...,k∗} for some k∗∈N and a parameter k∈N, LISTK-CYCLE asks if one can assign a color to each vertex in K so that G has a simple cycle (of arbitrary length) containing exactly k vertices from K with distinct colors. We design a randomized algorithm for LISTK-CYCLE running in time 2knO(1) on an n-vertex graph, matching the best known running times of algorithms for both K-CYCLE and COLORFUL CYCLE. Moreover, unless the Set Cover Conjecture is false, our algorithm is essentially optimal. We also study a variant of LISTK-CYCLE that generalizes the classic HAMILTONICITY problem, where one specifies the size of a solution. Our results integrate three related algebraic approaches, introduced by Björklund, Husfeldt and Taslaman (SODA'12), Björklund, Kaski and Kowalik (STACS'13), and Björklund (FOCS'10). [ABSTRACT FROM AUTHOR]