×

Spotting trees with few leaves. (English) Zbl 1362.05078

Summary: We show two results related to finding trees and paths in graphs. First, we show that in \(O^\ast(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^\ast(\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^\ast(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,\dots,12\) or with vector chromatic number at most 8. Our results extend the technique by A. Björklund [SIAM J. Comput. 43, No. 1, 280–299 (2014; Zbl 1292.05244)] and A. Björklund et al. [J. Comput. Syst. Sci. 87, 119–139 (2017; Zbl 1370.68321)] to finding structures more general than paths as well as refine it to handle special classes of graphs more efficiently.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C05 Trees
05C85 Graph algorithms (graph-theoretic aspects)
68W05 Nonnumerical algorithms
68W20 Randomized algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon, R. Yuster, and U. Zwick, {\it Color coding}, J. ACM, 42 (1995), pp. 844-856. · Zbl 0885.68116
[2] D. Binkele-Raible, H. Fernau, S. Gaspers, and M. Liedloff, {\it Exact and parameterized algorithms for max internal spanning tree}, Algorithmica, 65 (2013), pp. 95-128. · Zbl 1259.05159
[3] A. Björklund, {\it Determinant sums for undirected hamiltonicity}, SIAM J. Comput., 43 (2014), pp. 280-299. · Zbl 1292.05244
[4] A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, {\it The travelling salesman problem in bounded degree graphs}, in Proceedings of ICALP’08, 2008, pp. 198-209. · Zbl 1152.90575
[5] A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, {\it Narrow Sieves for Parameterized Paths and Packings}, CoRR, , 2010. · Zbl 1370.68321
[6] A. Björklund, P. Kaski, and L. Kowalik, {\it Probably optimal graph motifs}, in STACS, N. Portier and T. Wilke, eds., Leibniz Int. Proc. Informatics 20, Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, 2013, pp. 20-31. · Zbl 1354.68108
[7] A. Björklund, P. Kaski, and L. Kowalik, {\it Fast witness extraction using a decision oracle}, in Proceedings of ESA’14, Lectere Notes in Comput. Sci. 8737, Springer, New York, 2014, pp. 149-160. · Zbl 1423.68203
[8] H. L. Bodlaender, {\it On linear time minor tests with depth-first search}, J. Algorithms, 14 (1993), pp. 1-23. · Zbl 0764.68107
[9] J. Chen, J. Kneis, S. Lu, D. Mölle, S. Richter, P. Rossmanith, S.-H. Sze, and F. Zhang, {\it Randomized divide-and-conquer: Improved path, matching, and packing algorithms}, SIAM J. Comput., 38 (2009), pp. 2526-2547. · Zbl 1191.68849
[10] N. Cohen, F. V. Fomin, G. Gutin, E. J. Kim, S. Saurabh, and A. Yeo, {\it Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem}, J. Comput. Syst. Sci., 76 (2010), pp. 650-662. · Zbl 1210.05022
[11] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, {\it Parameterized Algorithms}, Springer, New York, 2015. · Zbl 1334.90001
[12] M. Cygan, S. Kratsch, and J. Nederlof, {\it Fast hamiltonicity checking via bases of perfect matchings}, in Proceedings of STOC’13, 2013, pp. 301-310. · Zbl 1293.05288
[13] M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O. Wojtaszczyk, {\it Solving connectivity problems parameterized by treewidth in single exponential time}, in Proceedings of FOCS’11, 2011, pp. 150-159. · Zbl 1292.68122
[14] J. Daligault, {\it Combinatorial Techniques for Parameterized Algorithms and Kernels, with Applications to Multicut}, Ph.D. thesis, Universite Montpellier II, Montpellier, Herault, France, 2011.
[15] A. Demers and A. Downing, {\it Minimum Leaf Spanning Tree}, US Patent 6,105,018, 2013.
[16] R. A. DeMillo and R. J. Lipton, {\it A probabilistic remark on algebraic program testing}, Inform. Process. Lett., 7 (1978), pp. 193-195. · Zbl 0397.68011
[17] R. Diestel, {\it Graph Theory, 4th ed.}, Grad. Texts in Math. 173, Springer, New York, 2012.
[18] Z. Dvořák, J.-S. Sereni, and J. Volec, {\it Subcubic triangle-free graphs have fractional chromatic number at most 14/5}, J. London Math. Soc., 89 (2014), pp. 641-662, . · Zbl 1295.05103
[19] D. Eppstein, {\it The traveling salesman problem for cubic graphs}, J. Graph Algorithms Appl., 11 (2007), pp. 61-81, . · Zbl 1161.68662
[20] T. Feder, R. Motwani, and C. S. Subi, {\it Approximating the longest cycle problem in sparse graphs}, SIAM J. Comput., 31 (2002), pp. 1596-1607, . · Zbl 1041.68069
[21] D. G. Ferguson, T. Kaiser, and D. Král’, {\it The fractional chromatic number of triangle-free subcubic graphs}, European. J. Combin., 35 (2014), pp. 184-220, . · Zbl 1292.05217
[22] F. V. Fomin, S. Gaspers, S. Saurabh, and S. Thomassé, {\it A linear vertex kernel for maximum internal spanning tree}, J. Comput. Systems Sci., 79 (2013), pp. 1-6. · Zbl 1258.05117
[23] F. V. Fomin, F. Grandoni, D. Lokshtanov, and S. Saurabh, {\it Sharp separation and applications to exact and parameterized algorithms}, Algorithmica, 63 (2012), pp. 692-706. · Zbl 1236.68090
[24] F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh, {\it Representative sets of product families}, in Proceedings of ESA’14, 2014, pp. 443-454. · Zbl 1425.68448
[25] F. V. Fomin, D. Lokshtanov, and S. Saurabh, {\it Efficient computation of representative sets with applications in parameterized and exact agorithms}, in Proceedings SODA’14, 2014, pp. 142-151. · Zbl 1421.68077
[26] B. Gärtner and J. Matǒusek, {\it Approximation Algorithms and Semidefinite Programming}, Springer, New York, 2012. · Zbl 1257.90001
[27] H. Gebauer, {\it On the number of hamilton cycles in bounded degree graphs}, in Proceedings of ANALCO’08, 2008, pp. 241-248. · Zbl 1429.05113
[28] M. X. Goemans and D. P. Williamson, {\it Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming}, J. ACM, 42 (1995), pp. 1115-1145. · Zbl 0885.68088
[29] F. Grandoni, {\it A note on the complexity of minimum dominating set}, J. Discrete Algorithms, 4 (2006), pp. 209-214, . · Zbl 1127.05070
[30] G. Gutin, I. Razgon, and E. J. Kim, {\it Minimum leaf out-branching and related problems}, Theoret. Comput. Sci., 410 (2009), pp. 4571-4579. · Zbl 1343.68183
[31] N. Gvozdenovic and M. Laurent, {\it The operator \(Ψ\) for the chromatic number of a graph}, SIAM J. Optim., 19 (2008), pp. 572-591, . · Zbl 1213.05080
[32] H. Hatami and X. Zhu, {\it The fractional chromatic number of graphs of maximum degree at most three}, SIAM J. Discrete Math., 23 (2009), pp. 1762-1775, . · Zbl 1207.05054
[33] K. Iwama and T. Nakashima, {\it An improved exact algorithm for cubic graph TSP}, in Proceedings of COCOON’07, 2007, pp. 108-117. · Zbl 1206.68146
[34] I. Koutis, {\it Faster algebraic algorithms for path and packing problems}, in Proceedings of ICALP’08, Lecture Notes in Comput. Sci. 5125, Springer, New York, 2008, pp. 575-586. · Zbl 1153.68562
[35] W. Li, J. Wang, J. Chen, and Y. Cao, {\it A 2k-vertex kernel for maximum internal spanning tree}, in Proceedings of WADS’15, Lecture Notes in Comput. Sci. 9214, Springer, New York, 2015, pp. 495-505. · Zbl 1451.68206
[36] C. Liu, {\it An upper bound on the fractional chromatic number of triangle-free subcubic graphs}, SIAM J. Discrete Math., 28 (2014), pp. 1102-1136, . · Zbl 1305.05080
[37] C. Liu, {\it personal communication}, 2015.
[38] L. Lovász, {\it Three short proofs in graph theory}, J. Combin. Theory Ser., 19 (1975), pp. 269-271. · Zbl 0322.05142
[39] B. Monien, {\it How to find long paths efficiently}, Ann. Discrete Math., 25 (1985), pp. 239-254. · Zbl 0603.68069
[40] J. Nederlof, {\it Fast polynomial-space algorithms using Möbius inversion: Improving on Steiner tree and related problems}, in Proceedings of ICALP’09, Lecture Notes in Comput. Sci. 5555, Springer, New York, 2009, pp. 713-725. · Zbl 1248.68258
[41] J. Nederlof, {\it Fast polynomial-space algorithms using inclusion-exclusion}, Algorithmica, 65 (2013), pp. 868-884. · Zbl 1272.68148
[42] E. Prieto and C. Sloper, {\it Reducing to independent set structure: The case of k-internal spanning tree}, Nordio J. Comput., 12 (2005), pp. 308-318. · Zbl 1087.68075
[43] I. Razgon, {\it Exact computation of maximum induced forest}, in Proceedings of SWAT’06, 2006, pp. 160-171. · Zbl 1141.05340
[44] E. R. Scheinerman and D. H. Ullman, {\it Fractional Graph Theory}, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 1997. · Zbl 0891.05003
[45] J. T. Schwartz, {\it Fast probabilistic algorithms for verification of polynomial identities}, J. ACM, 27 (1980), pp. 701-717. · Zbl 0452.68050
[46] H. Shachnai and M. Zehavi, {\it Representative families: A unified tradeoff-based approach}, in Algorithms–ESA 2014–22th Annual European Symposium, Wroclaw, Poland, Lecture Notes in Comput. Sci. 8737, Springer, New York, 2014, pp. 786-797. · Zbl 1333.68265
[47] R. Williams, {\it Finding paths of length \(k\) in \(O^*(2^k)\) time}, Inform. Process. Lett., 109 (2009), pp. 315-318. · Zbl 1191.68857
[48] M. Xiao and H. Nagamochi, {\it An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure}, in Proceedings of TAMC, Lecture Notes in Comput. Sci. 7876, Springer, New York, 2013, pp. 96-107. · Zbl 1382.90097
[49] M. Zehavi, {\it Algorithms for k-internal out-branching}, in Proceedings of IPEC’13, Lecture Notes in Comput. Sci. 8246, Springer, New York, 2013, pp. 361-373. · Zbl 1359.05130
[50] M. Zehavi, {\it Solving parameterized problems by mixing color coding-related techniques}, CoRR, , 2014.
[51] R. Zippel, {\it Probabilistic algorithms for sparse polynomials}, in Proceedings of the International Symposium on Symbolic and Algebraic Computation, Lecture Notes in Comput. Sci. 72, Springer, New York, 1979, pp. 216-226. · Zbl 0418.68040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.