Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
In this paper, we consider the minimum unweighted Vertex Cover problem with Hard Capacity constraints (VCHC) on multigraphs and hypergraphs. Given a graph, the objective of VCHC is to find a smallest multiset of vertices that cover all edges, under the constraints that each vertex can only cover a l...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2015
|
| Online Access: | http://hdl.handle.net/1721.1/92853 https://orcid.org/0000-0003-2809-9623 https://orcid.org/0000-0002-0520-1165 |
| _version_ | 1811081485148487680 |
|---|---|
| author | Cheung, Wang Chi Goemans, Michel X. Wong, Sam Chiu-Wai |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Cheung, Wang Chi Goemans, Michel X. Wong, Sam Chiu-Wai |
| author_sort | Cheung, Wang Chi |
| collection | MIT |
| description | In this paper, we consider the minimum unweighted Vertex Cover problem with Hard Capacity constraints (VCHC) on multigraphs and hypergraphs. Given a graph, the objective of VCHC is to find a smallest multiset of vertices that cover all edges, under the constraints that each vertex can only cover a limited number of incident edges, and the number of available copies of each vertex is bounded. This problem generalizes the classical unweighted vertex cover problem. Here we restrict our attention to unweighted instances, since the weighted version of VCHC is as hard as the set cover problem, as shown by Chuzhoy and Naor (FOCS 2002).
We obtain improved approximation algorithms for VCHC on multigraphs and hypergraphs. This problem has first been studied by Saha and Khuller (ICALP 2012). They proposed a 38-approximation for multigraphs, and a max {6 f, 65}-approximation for hypergraphs, where f is the size of the largest hyperedge. In this paper, we significantly improve these approximation ratios to 1 + 2/√3 < 2.155 and 2 f respectively. In the case of multigraphs, our approximation ratio is very close to the longstanding bound of 2 for the classical vertex cover problem. Our algorithms consist of a two-step process, each based on rounding an appropriate linear program. In particular, for multigraphs, the analysis in the second step relies on identifying a matching structure within any extreme point solution.
Furthermore, we consider the partial VCHC problem in which one only needs to cover all but ℓ edges. We propose a generic reduction from partial VCHC on f-hypergraphs to VCHC on (f + 1)-hypergraphs, with a small loss in the approximation factor. In particular, we present a (2f + 2)(1 + ∊)-approximation algorithm for partial VCHC on f-hypergraphs. |
| first_indexed | 2024-09-23T11:47:25Z |
| format | Article |
| id | mit-1721.1/92853 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:47:25Z |
| publishDate | 2015 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/928532022-09-27T21:54:12Z Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs Cheung, Wang Chi Goemans, Michel X. Wong, Sam Chiu-Wai Massachusetts Institute of Technology. Department of Mathematics Sloan School of Management Cheung, Wang Chi Goemans, Michel X. Wong, Sam Chiu-Wai In this paper, we consider the minimum unweighted Vertex Cover problem with Hard Capacity constraints (VCHC) on multigraphs and hypergraphs. Given a graph, the objective of VCHC is to find a smallest multiset of vertices that cover all edges, under the constraints that each vertex can only cover a limited number of incident edges, and the number of available copies of each vertex is bounded. This problem generalizes the classical unweighted vertex cover problem. Here we restrict our attention to unweighted instances, since the weighted version of VCHC is as hard as the set cover problem, as shown by Chuzhoy and Naor (FOCS 2002). We obtain improved approximation algorithms for VCHC on multigraphs and hypergraphs. This problem has first been studied by Saha and Khuller (ICALP 2012). They proposed a 38-approximation for multigraphs, and a max {6 f, 65}-approximation for hypergraphs, where f is the size of the largest hyperedge. In this paper, we significantly improve these approximation ratios to 1 + 2/√3 < 2.155 and 2 f respectively. In the case of multigraphs, our approximation ratio is very close to the longstanding bound of 2 for the classical vertex cover problem. Our algorithms consist of a two-step process, each based on rounding an appropriate linear program. In particular, for multigraphs, the analysis in the second step relies on identifying a matching structure within any extreme point solution. Furthermore, we consider the partial VCHC problem in which one only needs to cover all but ℓ edges. We propose a generic reduction from partial VCHC on f-hypergraphs to VCHC on (f + 1)-hypergraphs, with a small loss in the approximation factor. In particular, we present a (2f + 2)(1 + ∊)-approximation algorithm for partial VCHC on f-hypergraphs. Singapore. Agency for Science, Technology and Research National Science Foundation (U.S.) (Contract CCF-1115849) United States. Office of Naval Research (Grant N00014-05-1-0148) 2015-01-14T16:32:55Z 2015-01-14T16:32:55Z 2014-01 Article http://purl.org/eprint/type/ConferencePaper 978-1-61197-338-9 978-1-61197-340-2 http://hdl.handle.net/1721.1/92853 Cheung, Wang Chi, Michel X. Goemans, and Sam Chiu-Wai Wong. “Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs.” Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (December 18, 2013): 1714–1726. © 2014 the Society for Industrial and Applied Mathematics https://orcid.org/0000-0003-2809-9623 https://orcid.org/0000-0002-0520-1165 en_US http://dx.doi.org/10.1137/1.9781611973402.124 Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Cheung, Wang Chi Goemans, Michel X. Wong, Sam Chiu-Wai Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs |
| title | Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs |
| title_full | Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs |
| title_fullStr | Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs |
| title_full_unstemmed | Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs |
| title_short | Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs |
| title_sort | improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs |
| url | http://hdl.handle.net/1721.1/92853 https://orcid.org/0000-0003-2809-9623 https://orcid.org/0000-0002-0520-1165 |
| work_keys_str_mv | AT cheungwangchi improvedalgorithmsforvertexcoverwithhardcapacitiesonmultigraphsandhypergraphs AT goemansmichelx improvedalgorithmsforvertexcoverwithhardcapacitiesonmultigraphsandhypergraphs AT wongsamchiuwai improvedalgorithmsforvertexcoverwithhardcapacitiesonmultigraphsandhypergraphs |