Top

Published in:

2019 | OriginalPaper | Chapter

Algorithms and Complexity Results for the Capacitated Vertex Cover Problem

Authors : Sebastiaan B. van Rooij, Johan M. M. van Rooij

Published in: SOFSEM 2019: Theory and Practice of Computer Science

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We study the capacitated vertex cover problem (CVC). In this natural extension to the vertex cover problem, each vertex has a predefined capacity which indicates the total amount of edges that it can cover. In this paper, we study the complexity of the CVC problem. We give NP-completeness proofs for the problem on modular graphs, tree-convex graphs, and planar bipartite graphs of maximum degree three. For the first two graph classes, we prove that no subexponential-time algorithm exist for CVC unless the ETH fails.

Furthermore, we introduce a series of exact exponential-time algorithms which solve the CVC problem on several graph classes in \(\mathcal {O}((2 - \epsilon )^n)\) time, for some \(\epsilon > 0\). Amongst these graph classes are, graphs of maximum degree three, other degree-bounded graphs, regular graphs, graphs with large matchings, c-sparse graphs, and c-dense graphs. To obtain these results, we introduce an FPT treewidth algorithm which runs in \(\mathcal {O}^*((k + 1)^{tw})\) or \(\mathcal {O}^*(k^k)\) time, where k is the solution size and tw the treewidth, improving an earlier algorithm from Dom et al.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Bayesian Root Cause Analysis by Separable Likelihoods

next chapter Comparative Expressiveness of Product Line Calculus of Communicating Systems and 1-Selecting Modal Transition Systems

Note that Vertex Cover equals Independet Set and Clique when considered from the viewpoint of exact exponential-time algorithms.

Bandelt, H.J.: Hereditary modular graphs. Combinatorica 8(2), 149–157 (1988)MathSciNetCrossRef

Bodlaender, H.L., et al.: Open problems in parameterized and exact computation - IWPEC 2008. Technical report UU-CS-2008-017, Department of Information and Computing Sciences, Utrecht University (2008)

Bourgeois, N., Escoffier, B., Paschos, V.Th., van Rooij, J.M.M.: Fast algorithms for max independent set. Algorithmica 62(1), 382–415 (2012)MathSciNetCrossRef

Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoret. Comput. Sci. 411(40), 3736–3756 (2010)MathSciNetCrossRef

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. arXiv.org. The Computing Research Repository abs/1103.0534 (2011)

Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theoret. Comput. Sci. 411(40–42), 3701–3713 (2010)MathSciNetCrossRef

Cygan, M., Pilipczuk, M., Wojtaszczyk, J.O.: Capacitated domination faster than O(\(2^n\)). Inf. Process. Lett. 111(23), 1099–1103 (2011)MathSciNetCrossRef

Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 78–90. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-79723-4_9CrossRefMATH

Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 25:1–25:32 (2009)MathSciNetCrossRef

10.

Fomin, F.V., Høie, K.: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97(5), 191–196 (2006)MathSciNetCrossRef

11.

Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. TTCSAES. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16533-7CrossRefMATH

12.

Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 245–256. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30559-0_21CrossRef

13.

Fomin, F.V., Thilikos, D.M.: A simple and fast approach for solving problems on planar graphs. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 56–67. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24749-4_6CrossRef

14.

Fürer, M., Raghavachari, B.: Approximating the minimum degree spanning tree to within one from the optimal degree. In: 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1992. pp. 317–324. Society for Industrial and Applied Mathematics (1992)

15.

Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826–834 (1977)MathSciNetCrossRef

16.

Grandoni, F.: A note on the complexity of minimum dominating set. J. Discret. Algorithms 4(2), 209–214 (2006)MathSciNetCrossRef

17.

Guha, S., Hassin, R., Khuller, S., Or, E.: Capacitated vertex covering with applications. In: 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, pp. 858–865. Society for Industrial and Applied Mathematics (2002)

18.

Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory Comput. Syst. 41(3), 501–520 (2007)MathSciNetCrossRef

19.

Henning, M.A., Yeo, A.: Tight lower bounds on the size of a maximum matching in a regular graph. Graphs Comb. 23(6), 647–657 (2007)MathSciNetCrossRef

20.

Impagliazzo, R., Paturi, R.: On the complexity of \(k\)-SAT. J. Comput. Syst. Sci. 62(2), 367–375 (2001)MathSciNetCrossRef

21.

Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001)MathSciNetCrossRef

22.

Iwata, Y.: A faster algorithm for dominating set analyzed by the potential method. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 41–54. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28050-4_4CrossRef

23.

Jian, T.: An \({O}(2^{0.304n})\) algorithm for solving maximum independent set problem. IEEE Trans. Comput. 35(9), 847–851 (1986)

24.

Kloks, T. (ed.): Treewidth. LNCS, vol. 842. Springer, Heidelberg (1994). https://doi.org/10.1007/BFb0045375CrossRefMATH

25.

Kneis, J., Langer, A., Rossmanith, P.: A fine-grained analysis of a simple independent set algorithm. In: 29th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, pp. 287–298. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2009)

26.

Liedloff, M., Todinca, I., Villanger, Y.: Solving capacitated dominating set by using covering by subsets and maximum matching. Discret. Appl. Math. 168, 60–68 (2014)MathSciNetCrossRef

27.

Nederlof, J., van Rooij, J.M.M., van Dijk, T.C.: Inclusion/exclusion meets measure and conquer. Algorithmica 69, 685–740 (2014)MathSciNetMATH

28.

Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7(3), 425–440 (1986)MathSciNetCrossRef

29.

Robson, J.M.: Finding a maximum independent set in time \({O}(2^{n/4})\). Technical report, Laboratoire Bordelais de Recherche en Informatique, Université Bordeaux I, 1251–01, Bordeaux, France (2001)

30.

van Rooij, S.B.: A search for faster algorithms for the capacitated vertex cover problem. Master’s thesis. Department of Information and Computing Sciences, Utrecht University (2018)

31.

van Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for dominating set. Discret. Appl. Math. 159(17), 2147–2164 (2011)MathSciNetCrossRef

32.

Schiermeyer, I.: Efficiency in exponential time for domination-type problems. Discret. Appl. Math. 156(17), 3291–3297 (2008)MathSciNetCrossRef

33.

Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM J. Comput. 6(3), 537–546 (1977)MathSciNetCrossRef

34.

Xiao, M., Nagamochi, H.: Exact algorithms for maximum independent set. Inf. Comput. 255, 126–146 (2017)MathSciNetCrossRef

Title: Algorithms and Complexity Results for the Capacitated Vertex Cover Problem
Authors: Sebastiaan B. van Rooij
Johan M. M. van Rooij
Publisher: Springer International Publishing
Book: SOFSEM 2019: Theory and Practice of Computer Science
Print ISBN: 978-3-030-10800-7

Electronic ISBN: 978-3-030-10801-4

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-10801-4_37

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner