Abstract
We consider the following problem: for a given graph G and two integers k and d, can we apply a fixed graph operation at most k times in order to reduce a given graph parameter \(\pi \) by at least d? We show that this problem is NP-hard when the parameter is the independence number and the graph operation is vertex deletion or edge contraction, even for fixed \(d=1\) and when restricted to chordal graphs. We also give a polynomial time algorithm for bipartite graphs when the operation is edge contraction, the parameter is the independence number and d is fixed. Further, we complete the complexity dichotomy on H-free graphs when the parameter is the clique number and the operation is edge contraction by showing that this problem is NP-hard in \((C_3+P_1)\)-free graphs even for fixed \(d=1\). Our results answer several open questions stated in [Diner et al., Theoretical Computer Science, 746, p. 49–72 (2012)].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows - Theory, Algorithms and Applications, pp. 461–509. Prentice Hall, New Jersey (1993)
Bentz, C., Costa, M.C., de Werra, D., Picouleau, C., Ries, B.: Minimum d-transversals of maximum-weight stable sets in trees. Electron. Notes Discrete Math. 38, 129–134 (2011). https://doi.org/10.1016/j.endm.2011.09.022. The Sixth European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2011
Cerioli, M.R., Lima, P.T.: Intersection of longest paths in graph classes. Discrete Appl. Math. 281, 96–105 (2020). https://doi.org/10.1016/j.dam.2019.03.022. lAGOS 2017: IX Latin and American Algorithms, Graphs and Optimization Symposium, C.I.R.M., Marseille, France (2017)
Diestel, R.: Graph Theory, p. 37. Springer, Heidelberg (2016)
Diner, Ö.Y., Paulusma, D., Picouleau, C., Ries, B.: Contraction and deletion blockers for perfect graphs and H-free graphs. Theoret. Comput. Sci. 746, 49–72 (2018). https://doi.org/10.1016/j.tcs.2018.06.023
Galby, E., Mann, F., Ries, B.: Blocking total dominating sets via edge contractions. Theoret. Comput. Sci. 877, 18–35 (2021). https://doi.org/10.1016/j.tcs.2021.03.028
Galby, E., Mann, F., Ries, B.: Reducing the domination number of (p3+kp2)-free graphs via one edge contraction. Discrete Appl. Math. 305, 205–210 (2021). https://doi.org/10.1016/j.dam.2021.09.009
Galby, E., Lima, P.T., Mann, F., Ries, B.: Using edge contractions to reduce the semitotal domination number (2021). 10.48550/ARXIV.2107.03755. https://arxiv.org/abs/2107.03755
Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180–187 (1972). https://doi.org/10.1137/0201013
Paik, D., Reddy, S., Sahni, S.: Deleting vertices to bound path length. IEEE Trans. Comput. 43(9), 1091–1096 (1994). https://doi.org/10.1109/12.312117
Paulusma, D., Picouleau, C., Ries, B.: Reducing the clique and chromatic number via edge contractions and vertex deletions. In: Cerulli, R., Fujishige, S., Mahjoub, A.R. (eds.) ISCO 2016. LNCS, vol. 9849, pp. 38–49. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45587-7_4
Picouleau, C., Paulusma, D., Ries, B.: Reducing the chromatic number by vertex or edge deletions. Electron. Notes Discrete Math. 62, 243–248 (2017). https://doi.org/10.1016/j.endm.2017.10.042. lAGOS 2017 - IX Latin and American Algorithms, Graphs and Optimization
Poljak, S.: A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae 15(2), 307–309 (1974)
Zenklusen, R., Ries, B., Picouleau, C., de Werra, D., Costa, M.C., Bentz, C.: Blockers and transversals. Discrete Math. 309(13), 4306–4314 (2009). https://doi.org/10.1016/j.disc.2009.01.006
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
Lucke, F., Mann, F. (2022). Using Edge Contractions and Vertex Deletions to Reduce the Independence Number and the Clique Number. In: Bazgan, C., Fernau, H. (eds) Combinatorial Algorithms. IWOCA 2022. Lecture Notes in Computer Science, vol 13270. Springer, Cham. https://doi.org/10.1007/978-3-031-06678-8_30
Download citation
DOI: https://doi.org/10.1007/978-3-031-06678-8_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-06677-1
Online ISBN: 978-3-031-06678-8
eBook Packages: Computer ScienceComputer Science (R0)