nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Kernelization of Graph Hamiltonicity: Proper H-Graphs

verfasst von : Steven Chaplick, Fedor V. Fomin, Petr A. Golovach, Dušan Knop, Peter Zeman

Erschienen in: Algorithms and Data Structures

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization is strongly influenced by the work of Biró, Hujter, and Tuza, who in 1992 introduced H-graphs, intersection graphs of connected subgraphs of a subdivision of a fixed (multi) graph H. In this work, we turn to proper H-graphs, where the containment relationship between the representations of the vertices is forbidden. As the treewidth of a graph measures how similar the graph is to a tree, the size of graph H is the parameter measuring the closeness of the graph to a proper interval graph. We prove the following results.

Path Cover admits a kernel of size \(\mathcal {O}(\Vert H\Vert ^8)\), that is, we design an algorithm that for an n-vertex graph G and an integer \(k\ge 1\), in time polynomial in n and \(\Vert H\Vert \), outputs a graph \(G'\) of size \(\mathcal {O}(\Vert H\Vert ^8)\) and \(k'\le |V(G')|\) such that the vertex set of G is coverable by k vertex-disjoint paths if and only if the vertex set of \(G'\) is coverable by \(k'\) vertex-disjoint paths.
Cycle Cover admits a compression of size \(\mathcal {O}(\Vert H\Vert ^{10})\) into another problem, called Prize Collecting Cycle Cover, that is, we design an algorithm that, in time polynomial in n and \(\Vert H\Vert \), outputs an equivalent instance of Prize Collecting Cycle Cover of size \(\mathcal {O}(\Vert H\Vert ^{10})\).

In all our algorithms we assume that a proper H-decomposition is given as a part of the input.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles

Nächstes Kapitel Weighted Throughput Maximization with Calibrations

Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)MathSciNetCrossRef

Bertossi, A.A.: Finding Hamiltonian circuits in proper interval graphs. Inf. Process. Lett. 17(2), 97–101 (1983)MathSciNetCrossRef

Biro, M., Hujter, M., Tuza, Z.: Precoloring extension. I. Interval graphs. Discrete Math. 100(1), 267–279 (1992)MathSciNetMATH

Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings. CoRR abs/1007.1161 (2010)

Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)MathSciNetCrossRef

Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernel bounds for path and cycle problems. Theor. Comput. Sci. 511, 117–136 (2013)MathSciNetCrossRef

Brandstädt, A., Dragan, F.F., Köhler, E.: Linear time algorithms for hamiltonian problems on (claw, net)-free graphs. SIAM J. Comput. 30(5), 1662–1677 (2000)MathSciNetCrossRef

Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, SIAM Monographs on Discrete Mathematics and Applications (1999)

Broersma, H., Fiala, J., Golovach, P.A., Kaiser, T., Paulusma, D., Proskurowski, A.: Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. J. Graph Theor. 79, 282–299 (2015)MathSciNetCrossRef

10.

Chang, M., Peng, S., Liaw, J.: Deferred-query: an efficient approach for some problems on interval graphs. Networks 34(1), 1–10 (1999)MathSciNetCrossRef

11.

Chaplick, S., Töpfer, M., Voborník, J., Zeman, P.: On H-topological intersection graphs. In: Bodlaender, H.L., Woeginger, G.J. (eds.) WG 2017. LNCS, vol. 10520, pp. 167–179. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68705-6_13CrossRef

12.

Chaplick, S., Zeman, P.: Combinatorial problems on H-graphs. In: EUROCOMB, vol. 61, ENDM, pp. 223–229 (2017). arXiv:1706.00575CrossRef

13.

Chen, C., Chang, C., Chang, G.J.: Proper interval graphs and the guard problem. Discrete Math. 170(1–3), 223–230 (1997)MathSciNetCrossRef

14.

Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3CrossRefMATH

15.

Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: FOCS 2011, pp. 150–159. IEEE (2011)

16.

Damaschke, P.: Paths in interval graphs and circular arc graphs. Discrete Math. 112(1–3), 49–64 (1993)MathSciNetCrossRef

17.

Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013). https://doi.org/10.1007/978-1-4471-5559-1CrossRefMATH

18.

Etscheid, M., Kratsch, S., Mnich, M., Röglin, H.: Polynomial kernels for weighted problems. J. Comput. Syst. Sci. 84, 1–10 (2017)MathSciNetCrossRef

19.

Fellows, M.R., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F.A., Saurabh, S.: The complexity ecology of parameters: an illustration using bounded max leaf number. Theory Comput. Syst. 45(4), 822–848 (2009)MathSciNetCrossRef

20.

Fomin, F.V., Golovach, P.A., Raymond, J.: On the tractability of optimization problems on H-graphs. In: ESA 2018, vol. 112 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 30:1–30:14 (2018)

21.

Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization. In: Theory of Parameterized Preprocessing, Cambridge University Press (2019)

22.

Frank, A., Tardos, É.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49–65 (1987)MathSciNetCrossRef

23.

Garey, M.R., Johnson, D.S.: Computers and intractability. In: Computers and Intractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences. W. H. Freeman & Co. (1979)

24.

Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57, 2nd edn. Elsevier Science B.V., Amsterdam (2004). With a foreword by Claude Berge

25.

Hung, R., Chang, M.: Linear-time certifying algorithms for the path cover and hamiltonian cycle problems on interval graphs. Appl. Math. Lett. 24(5), 648–652 (2011)MathSciNetCrossRef

26.

Ibarra, L.: A simple algorithm to find Hamiltonian cycles in proper interval graphs. Inf. Process. Lett. 109(18), 1105–1108 (2009)MathSciNetCrossRef

27.

Keil, J.M.: Finding hamiltonian circuits in interval graphs. Inf. Process. Lett. 20(4), 201–206 (1985)MathSciNetCrossRef

28.

Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 575–586. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70575-8_47CrossRefMATH

29.

Lampis, M., Makino, K., Mitsou, V., Uno, Y.: Parameterized edge hamiltonicity. Discrete Appl. Math. 248, 68–78 (2018)MathSciNetCrossRef

30.

Manacher, G.K., Mankus, T.A., Smith, C.J.: An optimum theta (n log n) algorithm for finding a canonical hamiltonian path and a canonical hamiltonian circuit in a set of intervals. Inf. Process. Lett. 35(4), 205–211 (1990)CrossRef

31.

Müller, H.: Hamiltonian circuits in chordal bipartite graphs. Discrete Math. 156(1–3), 291–298 (1996)MathSciNetCrossRef

32.

Roberts, F.S.: Indifference graphs. In: Proof Techniques in Graph Theory (Proceedings of the Second Ann Arbor Graph Theory Conference, Ann Arbor, Michigan, 1968), pp. 139–146. Academic Press, New York (1969)

33.

Shih, W., Chern, T.C., Hsu, W.: An o(n\({^2}\) log n) algorithm for the hamiltonian cycle problem on circular-arc graphs. SIAM J. Comput. 21(6), 1026–1046 (1992)MathSciNetCrossRef

34.

Williams, R.: Finding paths of length \(k\) in \(O(2^k)\) time. Inf. Process. Lett. 109(6), 315–318 (2009)CrossRef

Titel: Kernelization of Graph Hamiltonicity: Proper H-Graphs
verfasst von: Steven Chaplick
Fedor V. Fomin
Petr A. Golovach
Dušan Knop
Peter Zeman
Verlag: Springer International Publishing
Buch: Algorithms and Data Structures
Print ISBN: 978-3-030-24765-2

Electronic ISBN: 978-3-030-24766-9

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-24766-9_22

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner