article

The minimum generalized vertex cover problem

Authors:

Refael Hassin,

Asaf LevinAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 2, Issue 1

Pages 66 - 78

https://doi.org/10.1145/1125994.1125998

Published: 01 January 2006 Publication History

Get Access

Abstract

Let G = (V, E) be an undirected graph, with three numbers d₀(e) ≥ d₁(e) ≥ d₂(e) ≥ 0 for each edge e ∈ E. A solution is a subset U ⊆ V and d_i(e) represents the cost contributed to the solution by the edge e if exactly i of its endpoints are in the solution. The cost of including a vertex v in the solution is c(v). A solution has cost that is equal to the sum of the vertex costs and the edge costs. The minimum generalized vertex cover problem is to compute a minimum cost set of vertices. We study the complexity of the problem with the costs d₀(e) = 1, d₁(e) = α and d₂(e) = 0 ∀e ∈ E and c(v) = β∀v ∈ V, for all possible values of α and β. We also provide 2-approximation algorithms for the general case.

References

[1]

Bar-Yehuda, R., Bendel, K., Freund, A., and Rawitz, D. 2004. Local ratio: A unified framework for approximation algorithms. ACM Comput. Surv., 36, 422--463.]]

Digital Library

Google Scholar

[2]

Bar-Yehuda, R., and Even, S. 1981. A linear time approximation algorithm for the weighted vertex cover problem. J. Algor. 2, 198--203.]]

Crossref

Google Scholar

[3]

Bar-Yehuda, R., and Rawitz, D. 2001. On the equivalence between the primal-dual schema and the local-ratio technique. In Proceedings of APPROX 2001. 24--35.]]

Digital Library

Google Scholar

[4]

Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company.]]

Digital Library

Google Scholar

[5]

Hassin, R., and Levin, A. 2003. The minimum generalized vertex cover problem. In Proceedings of the ESA 2003. 289--300.]]

Google Scholar

[6]

Hochbaum, D. S. 2002. Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations. Europ. J. Oper. Res. 140, 291--321.]]

Crossref

Google Scholar

[7]

Krumke, S. O., Marathe, M. V., Noltemeier, H., Ravi, R., Ravi, S. S., Sundaram, R., and Wirth, H. C. 1999. Improving minimum cost spanning trees by upgrading nodes. J. Algor., 33, 92--111.]]

Digital Library

Google Scholar

[8]

Lawler, E. L. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston.]]

Google Scholar

[9]

Nemhauser, G. L., and Trotter, Jr., L. E. 1975. Vertex packing: Structural properties and algorithms. Math. Prog. 8, 232--248.]]

Digital Library

Google Scholar

[10]

Paik, D., and Sahni, S. 1995. Network upgrading problems. Networks. 26, 45--58.]]

Crossref

Google Scholar

[11]

Yannakakis, M. 1981. Edge deletion problems. SIAM J. Computing. 10, 297--309.]]

Crossref

Google Scholar

Cited By

View all

Fujito TMukae KTsuzuki J(2024)Approximating power node-deletion problemsTheoretical Computer Science10.1016/j.tcs.2024.1147331012(114733)Online publication date: Oct-2024
https://doi.org/10.1016/j.tcs.2024.114733
Mkrtchyan VPetrosyan GSubramani KWojciechowski P(2024)On the Partial Vertex Cover Problem in Bipartite Graphs - a Parameterized PerspectiveTheory of Computing Systems10.1007/s00224-023-10152-w68:1(122-143)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00224-023-10152-w
Tai ROuyang DLi RZhang L(2023)ILSGVCP: An improved local search algorithm for generalized vertex cover problemJournal of the Operational Research Society10.1080/01605682.2022.214745874:11(2382-2390)Online publication date: 21-Jan-2023
https://doi.org/10.1080/01605682.2022.2147458
Show More Cited By

Index Terms

The minimum generalized vertex cover problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R"1xR"2x...xR"k where each R"i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-...
Price of Connectivity for the Vertex Cover Problem and the Dominating Set Problem: Conjectures and Investigation of Critical Graphs

The vertex cover problem and the dominating set problem are two well-known problems in graph theory. Their goal is to find the minimum size of a vertex subset satisfying some properties. Both hold a connected version, which imposes that the vertex ...
Minimum k-path vertex cover

A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by @j"k(G) the minimum cardinality of a k-path vertex cover in G. It is shown that the problem of determining @...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 2, Issue 1

January 2006

134 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1125994

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2006

Published in TALG Volume 2, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
1,115
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fujito TMukae KTsuzuki J(2024)Approximating power node-deletion problemsTheoretical Computer Science10.1016/j.tcs.2024.1147331012(114733)Online publication date: Oct-2024
https://doi.org/10.1016/j.tcs.2024.114733
Mkrtchyan VPetrosyan GSubramani KWojciechowski P(2024)On the Partial Vertex Cover Problem in Bipartite Graphs - a Parameterized PerspectiveTheory of Computing Systems10.1007/s00224-023-10152-w68:1(122-143)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00224-023-10152-w
Tai ROuyang DLi RZhang L(2023)ILSGVCP: An improved local search algorithm for generalized vertex cover problemJournal of the Operational Research Society10.1080/01605682.2022.214745874:11(2382-2390)Online publication date: 21-Jan-2023
https://doi.org/10.1080/01605682.2022.2147458
Fujito TMukae KTsuzuki J(2023)Approximating Power Node-Deletion ProblemsAlgorithms and Complexity10.1007/978-3-031-30448-4_16(217-231)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-30448-4_16
Jadliwala MBilogrevic IHubaux J(2018)Optimizing mix-zone coverage in pervasive wireless networksJournal of Computer Security10.5555/2590618.259061921:3(317-346)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.5555/2590618.2590619
Pandey PPunnen A(2018)The generalized vertex cover problem and some variationsDiscrete Optimization10.1016/j.disopt.2018.06.00430(121-143)Online publication date: Nov-2018
https://doi.org/10.1016/j.disopt.2018.06.004
Li RHu SWang YYin M(2017)A local search algorithm with tabu strategy and perturbation mechanism for generalized vertex cover problemNeural Computing and Applications10.1007/s00521-015-2172-928:7(1775-1785)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s00521-015-2172-9
Hu SLi RZhao PYin M(2016)A hybrid metaheuristic algorithm for generalized vertex cover problemMemetic Computing10.1007/s12293-016-0216-z10:2(165-176)Online publication date: 12-Nov-2016
https://doi.org/10.1007/s12293-016-0216-z
Kochenberger GLewis MGlover FWang H(2015)Exact solutions to generalized vertex covering problems: a comparison of two modelsOptimization Letters10.1007/s11590-015-0851-19:7(1331-1339)Online publication date: 14-Feb-2015
https://doi.org/10.1007/s11590-015-0851-1
Jadliwala MBilogrevic IHubaux J(2011)Optimizing mixing in pervasive networksProceedings of the 16th European conference on Research in computer security10.5555/2041225.2041264(548-567)Online publication date: 12-Sep-2011
https://dl.acm.org/doi/10.5555/2041225.2041264
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Cubicity, boxicity, and vertex cover

Price of Connectivity for the Vertex Cover Problem and the Dominating Set Problem: Conjectures and Investigation of Critical Graphs

Minimum k-path vertex cover

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations