On the parameterized vertex cover problem for graphs with perfect matching. (English) Zbl 1343.68122
Summary: A vertex cover of an \(n\)-vertex graph with perfect matching contains at least \(n/2\) vertices. In this paper, we study the parameterized complexity of the problem vc-pm* that decides if a given graph with perfect matching has a vertex cover of size bounded by \(n/2 + k\). We first present an algorithm of running time \(O^\ast(4^k)\) for a variation of the vertex cover problem on König graphs with perfect matching. This algorithm combined with the iterative compression technique leads to an algorithm of running time \(O^\ast(9^k)\) for the problem vc-pm*. Our result improves the previous best algorithm of running time \(O^\ast(15^k)\) for the vc-pm* problem, which reduces the problem to the almost 2-sat problem and solves the latter by I. Razgon and B. O’Sullivan’s recent algorithm [Lect. Notes Comput. Sci. 5125, 551–562 (2008; Zbl 1153.68397)].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Citations:
Zbl 1153.68397Software:
DIMACSReferences:
| [1] | Garey M R, Johnson D S. Computers and Intractability: a Guide to the Thoery of NP-completeness. New York: Freeman, W. H. and Company, 1979 · Zbl 0411.68039 |
| [2] | Roth-Korostensky C. Algorithms for building multiple sequence alignments and evolutionary trees. Dissertation for Doctoral Degree. ETH Zürich 13550, 2000 |
| [3] | Stege U. Resolving conflicts from problems in computational biology. Dissertation for Doctoral Degree. ETH Zürich 13364, 2000 |
| [4] | Hochbaum, D.; Hochbaum, D. (ed.), Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems, 94-143 (1997), Boston |
| [5] | Balasubramanian R, Fellows M R, Raman V. An improved fixed parameter algorithm for vertex cover. Inf Process Lett, 1998, 65: 163-168 · Zbl 1337.05095 · doi:10.1016/S0020-0190(97)00213-5 |
| [6] | Chen J, Kanj I A, Jia W. Vertex cover: further observations and further improvements. J Algorithm, 2001, 41: 280-301 · Zbl 1017.68087 · doi:10.1006/jagm.2001.1186 |
| [7] | Downey, R. G.; Fellows, M. R.; Clote, P. (ed.); Remmel, J. (ed.), Parameterized computational feasibility, 219-244 (1995), Boston · Zbl 0834.68046 · doi:10.1007/978-1-4612-2566-9_7 |
| [8] | Niedermeier R, Rossmanith P. Upper bounds for vertex cover further improved. Lect Note Comput Sci, 1999, 1563: 561-570 · Zbl 0921.05046 · doi:10.1007/3-540-49116-3_53 |
| [9] | Khot S, Regev O. Vertex cover might be hard to approximate to within 2 − ε. J Comput Syst Sci, 2008, 74: 335-349 · Zbl 1133.68061 · doi:10.1016/j.jcss.2007.06.019 |
| [10] | Chen J, Kanj I A, Xia G. Improved parameterized upper bounds for vertex cover. Lect Note Comput Sci, 2006, 4162: 238-249 · Zbl 1132.68421 · doi:10.1007/11821069_21 |
| [11] | Cai L, Juedes D W. On the existence of subexponential parameterized algorithms. J Comput Syst Sci, 2003, 67: 789-807 · Zbl 1091.68121 · doi:10.1016/S0022-0000(03)00074-6 |
| [12] | Cai S, Su K, Sattar A. Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artif Intell, 2001, 175: 1672-1696 · Zbl 1225.68242 · doi:10.1016/j.artint.2011.03.003 |
| [13] | Johnson D S, Trick M A, eds. Cliques, Coloring, and Satisfiability: second DIMACS Implementation Challenge. American Mathematical Society, 1996. Benchmarks available at ftp://dimacs.rutgers.edu/pub/challenges · Zbl 0851.00080 |
| [14] | Xu K, Boussemart F, Hemery F, et al. Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif Intell, 2007, 171: 514-534. Benchmarks available at http://www.nlsde.buaa.edu.cn/ kexu/benchmarks/graphbenchmarks.htm · Zbl 1168.68554 · doi:10.1016/j.artint.2007.04.001 |
| [15] | Chen J, Kanj I A. On approximating minimum vertex cover for graphs with perfect matching. Theor Comput Sci, 2005, 337: 305-318 · Zbl 1074.05071 · doi:10.1016/j.tcs.2004.12.034 |
| [16] | Imamura T, Iwama K, Tsukiji T. Approximated vertex cover for graphs with perfect matchings. Trans Inf Syst, 2009, E89-D(8): 2405-2410 · doi:10.1093/ietisy/e89-d.8.2405 |
| [17] | Chlebik M, Chlebikova J. Minimum 2sat-deletion inapproximability results and relations to minimum vertex cover. Discrete Appl Math, 2007, 155: 172-179 · Zbl 1110.68169 · doi:10.1016/j.dam.2006.04.039 |
| [18] | Mahajan M, Raman V. Parametrizing above guaranteed values: maxSat and maxCut. J Algorithm, 1999 3: 335-354 · Zbl 0921.68052 · doi:10.1006/jagm.1998.0996 |
| [19] | Mahajan M, Raman V, Sikdar S. Parameterizing MAX SNP problems above guaranteed values. Lect Note Comput Sci, 2006, 4169: 38-49 · Zbl 1154.68430 · doi:10.1007/11847250_4 |
| [20] | Mahajan M, Raman V, Sikdar S. Parameterizing above or below guaranteed values. J Comput Syst Sci, 2009, 75: 137-153 · Zbl 1155.68400 · doi:10.1016/j.jcss.2008.08.004 |
| [21] | Razgon I, O’Sullivan B. Almost 2-SAT is Fixed-Parameter Tractable. Berlin: Springer, 2008. 551-562 · Zbl 1153.68397 |
| [22] | Mishra S, Raman V, Saurabh S, et al. The complexity of finding subgraphs whose matching number equals the vertex cover number. Lect Note Comput Sci, 2007, 4835: 268-279 · Zbl 1193.05133 · doi:10.1007/978-3-540-77120-3_25 |
| [23] | Reed B, Smith K, Vetta A. Finding odd cycle transversals. Oper Res Lett, 2004, 32: 299-301 · Zbl 1052.05061 · doi:10.1016/j.orl.2003.10.009 |
| [24] | Deming R. Independence numbers of graphs—an extension of the König-Egerváry theorem. Discrete Math, 1979, 27: 23-33 · Zbl 0404.05034 · doi:10.1016/0012-365X(79)90066-9 |
| [25] | Vazirani V. A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt V\) E) general graph maximum matching algorithm. Combinatorica, 1994, 14: 71-109 · Zbl 0806.05058 · doi:10.1007/BF01305952 |
| [26] | Korach, E.; Nguyen, T.; Peis, B., Subgraph characterization of red/blue-split graph and König-Egerváry graphs, 842-850 (2006) · Zbl 1192.05116 |
| [27] | Cormen T, Teiserson C, Rivest R, et al. Introduction to Algorithms. 2nd ed. Cambridge: MIT Press, 2011 |
| [28] | Mishra S, Raman V, Saurabh S, et al. König deletion sets and vertex covers above the matching size. Lect Note Comput Sci, 2008, 5369: 836-847 · Zbl 1183.68313 · doi:10.1007/978-3-540-92182-0_73 |
| [29] | Raman V, Ramanujan S, Saurabh S. Paths, flowers and vertex cover. Lect Note Comput Sci, 2011, 6942: 382-393 · Zbl 1346.05287 · doi:10.1007/978-3-642-23719-5_33 |
| [30] | Cygan M, Pilipczuk M, Pilipczuk M, et al. On multiway cut parameterized above lower bounds. Lect Note Comput Sci, 2011, 7112: 1-12 · Zbl 1352.68100 · doi:10.1007/978-3-642-28050-4_1 |
| [31] | Narayanaswamy, S.; Raman, V.; Ramanujan, S.; etal., LP can be a cure for parameterized problems, 338-349 (2011) · Zbl 1245.68111 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
