Abstract
We study extension variants of the classical problems Vertex Cover and Independent Set. Given a graph \(G=(V,E)\) and a vertex set \(U \subseteq V\), it is asked if there exists a minimal vertex cover (resp. maximal independent set) S with \(U\subseteq S\) (resp. \(U \supseteq S\)). Possibly contradicting intuition, these problems tend to be \({\mathsf {NP}}\)-complete, even in graph classes where the classical problem can be solved efficiently. Yet, we exhibit some graph classes where the extension variant remains polynomial-time solvable. We also study the parameterized complexity of theses problems, with parameter |U|, as well as the optimality of simple exact algorithms under ETH. All these complexity considerations are also carried out in very restricted scenarios, be it degree or topological restrictions (bipartite, planar or chordal graphs). This also motivates presenting some explicit branching algorithms for degree-bounded instances. e further discuss the price of extension, measuring the distance of U to the closest set that can be extended, which results in natural optimization problems related to extension problems for which we discuss polynomial-time approximability.
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
Bazgan, C., Brankovic, L., Casel, K., Fernau, H.: On the complexity landscape of the domination chain. In: Govindarajan, S., Maheshwari, A. (eds.) CALDAM 2016. LNCS, vol. 9602, pp. 61–72. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29221-2_6
Bazgan, C., et al.: The many facets of upper domination. Theor. Comput. Sci. 717, 2–25 (2018)
Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT. In: ECCC, no. 049 (2003)
Boria, N., Croce, F.D., Paschos, V.T.: On the max min vertex cover problem. Disc. Appl. Math. 196, 62–71 (2015)
Boros, E., Gurvich, V., Hammer, P.L.: Dual subimplicants of positive Boolean functions. Optim. Meth. Softw. 10(2), 147–156 (1998)
Casel, K., Fernau, H., Ghadikolaei, M.K., Monnot, J., Sikora, F.: On the complexity of solution extension of optimization problems. CoRR, abs/1810.04553 (2018)
Chang, G.J.: The weighted independent domination problem is NP-complete for chordal graphs. Disc. Appl. Math. 143(1–3), 351–352 (2004)
Chang, M.: Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27(6), 1671–1694 (1998)
Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM J. Comput. 37(4), 1077–1106 (2007)
Farber, M.: Independent domination in chordal graphs. Oper. Res. Lett. 4(1), 134–138 (1982)
Halldórsson, M.M.: Approximating the minimum maximal independence number. Inf. Proc. Lett. 46(4), 169–172 (1993)
Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of kemeny elections. Theor. Comput. Sci. 349(3), 382–391 (2005)
Kanté, M.M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. SIAM J. Disc. Math. 28(4), 1916–1929 (2014)
Kanté, M.M., Limouzy, V., Mary, A., Nourine, L., Uno, T.: Polynomial delay algorithm for listing minimal edge dominating sets in graphs. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 446–457. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21840-3_37
Kanté, M.M., Limouzy, V., Mary, A., Nourine, L., Uno, T.: A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs. In: Mayr, E.W. (ed.) WG 2015. LNCS, vol. 9224, pp. 138–153. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53174-7_11
Kratochvíl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Disc. Appl. Math. 52, 233–252 (1994)
Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comp. 9, 558–565 (1980)
Manlove, D.F.: On the algorithmic complexity of twelve covering and independence parameters of graphs. Disc. Appl. Math. 91(1–3), 155–175 (1999)
Mishra, S., Sikdar, K.: On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem. RAIRO Inf. Théor. Appl. 35(3), 287–309 (2001)
Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Vitter, J.S., Spirakis, P.G., Yannakakis, M. (eds.) Proceedings on 33rd Annual ACM Symposium on Theory of Computing, STOC, pp. 453–461. ACM (2001)
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comp. Syst. 3(1), 103–128 (2007)
Acknowledgements
The first author was partially supported by the Deutsche Forschungsgemeinschaft DFG (FE 560/6-1).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Casel, K., Fernau, H., Ghadikoalei, M.K., Monnot, J., Sikora, F. (2019). Extension of Vertex Cover and Independent Set in Some Classes of Graphs. In: Heggernes, P. (eds) Algorithms and Complexity. CIAC 2019. Lecture Notes in Computer Science(), vol 11485. Springer, Cham. https://doi.org/10.1007/978-3-030-17402-6_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-17402-6_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-17401-9
Online ISBN: 978-3-030-17402-6
eBook Packages: Computer ScienceComputer Science (R0)