Abstract
In 2017, Knop, Koutecký, Masařík, and Toufar [WG 2017] asked about the complexity of deciding graph problems \(\varPi \) on the complement of G considering a parameter p of G, especially for sparse graph parameters such as treewidth. In 2021, Duarte, Oliveira, and Souza [MFCS 2021] showed some problems that are FPT when parameterized by the treewidth of the complement graph (called co-treewidth). Since the degeneracy of a graph is at most its treewidth, they also introduced the study of co-degeneracy (the degeneracy of the complement graph) as a parameter. In 1976, Bondy and Chvátal [DM 1976] introduced the notion of closure of a graph: let \(\ell \) be an integer; the \((n+\ell )\)-closure, \({\text {cl}}_{n+\ell }(G)\), of a graph G with n vertices is obtained from G by recursively adding an edge between pairs of nonadjacent vertices whose degree sum is at least \(n+\ell \) until no such pair remains. A graph property \(\varUpsilon \) defined on all graphs of order n is said to be \((n+\ell )\)-stable if for any graph G of order n that does not satisfy \(\varUpsilon \), the fact that uv is not an edge of G and that \(G+uv\) satisfies \(\varUpsilon \) implies \(d(u)+d(v)< n+\ell \). Duarte et al. [MFCS 2021] developed an algorithmic framework for co-degeneracy parameterization based on the notion of closures for solving problems that are \((n+\ell )\)-stable for some \(\ell \) bounded by a function of the co-degeneracy. In 2019, Jansen, Kozma, and Nederlof [WG 2019] relax the conditions of Dirac’s theorem and consider input graphs G in which at least \(n-k\) vertices have degree at least \(\frac{n}{2}\), and present an FPT algorithm concerning to k, to decide whether such graphs G are Hamiltonian. In this paper, we first determine the stability of the property of having a bounded cycle cover. After that, combining the framework of Duarte et al. [MFCS 2021] with some results of Jansen et al. [WG 2019], we obtain a \(2^{\mathcal {O}(k)}\cdot n^{\mathcal {O}(1)}\)-time algorithm for Minimum Cycle Cover on graphs with co-degeneracy at most k, which generalizes Duarte et al. [MFCS 2021] and Jansen et al. [WG 2019] results concerning the Hamiltonian Cycle problem.
This research has received funding from Rio de Janeiro Research Support Foundation (FAPERJ) under grant agreement E-26/201.344/2021, National Council for Scientific and Technological Development (CNPq) under grant agreement 309832/2020-9, and the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme under grant agreement CUTACOMBS (No. 714704). .
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Originally this required a clique-width expression as part of the input.
- 2.
A parameter y is stronger than x, if the set of instances where x is bounded is a subset of those where y is bounded.
- 3.
\(co\text{- }vc(G)\) is also called the distance to clique of G, and a co-vertex cover set is also called a clique modulator.
References
Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86–111 (2015). 40th International Colloquium on Automata, Languages and Programming (ICALP 2013)
Bondy, J.A., Chvátal, V.: A method in graph theory. Discret. Math. 15(2), 111–135 (1976)
Broersma, H., Ryjáček, Z., Schiermeyer, I.: Closure concepts: a survey. Graphs Comb. 16(1), 17–48 (2000)
Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825–847 (2005)
Courcelle, B.: The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990)
Courcelle, B.: The monadic second order logic of graphs VI: on several representations of graphs by relational structures. Discret. Appl. Math. 54(2–3), 117–149 (1994)
Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125–150 (2000)
Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101(1–3), 77–114 (2000)
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. ACM Trans. Algorithms 18(2), 1–31 (2022)
Dirac, G.A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. 3(1), 69–81 (1952)
Duarte, G.L., de Oliveira Oliveira, M., Souza, U.S.: Co-degeneracy and co-treewidth: using the complement to solve dense instances. In: Bonchi, F., Puglisi, S.J. (eds.) 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, vol. 202, pp. 42:1–42:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
Duarte, G.L., et al.: Computing the largest bond and the maximum connected cut of a graph. Algorithmica 83(5), 1421–1458 (2021)
Dvořák, P., Knop, D., Masarík, T.: Anti-path cover on sparse graph classes. In: Bouda, J., Holík, L., Kofron, J., Strejcek, J., Rambousek, A. (eds.) Proceedings 11th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2016, Telč, Czech Republic, 21–23 October 2016. EPTCS, vol. 233, pp. 82–86 (2016)
Fomin, F.V., Golovach, P.A., Lokshtanov, D., Panolan, F., Saurabh, S., Zehavi, M.: Going far from degeneracy. SIAM J. Discret. Math. 34(3), 1587–1601 (2020)
Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Clique-width: on the price of generality. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 825–834. SIAM (2009)
Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Algorithmic lower bounds for problems parameterized by clique-width. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 493–502. SIAM (2010)
Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941–1956 (2010)
Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput. 43(5), 1541–1563 (2014)
Fomin, F.V., Golovach, P.A., Sagunov, D., Simonov, K.: Algorithmic extensions of Dirac’s theorem. In: Naor, J.S., Buchbinder, N. (eds.) Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference, Alexandria, VA, USA, 9–12 January 2022, pp. 406–416. SIAM (2022)
Jansen, B.M.P., Kozma, L., Nederlof, J.: Hamiltonicity below Dirac’s condition. In: Sau, I., Thilikos, D.M. (eds.) WG 2019. LNCS, vol. 11789, pp. 27–39. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30786-8_3
Knop, D., Koutecký, M., Masařík, T., Toufar, T.: Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity. In: Bodlaender, H.L., Woeginger, G.J. (eds.) WG 2017. LNCS, vol. 10520, pp. 344–357. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68705-6_26
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Duarte, G.L., Souza, U.S. (2022). On the Minimum Cycle Cover Problem on Graphs with Bounded Co-degeneracy. In: Bekos, M.A., Kaufmann, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 2022. Lecture Notes in Computer Science, vol 13453. Springer, Cham. https://doi.org/10.1007/978-3-031-15914-5_14
Download citation
DOI: https://doi.org/10.1007/978-3-031-15914-5_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-15913-8
Online ISBN: 978-3-031-15914-5
eBook Packages: Computer ScienceComputer Science (R0)