Abstract
A graph is König-Egerváry if the size of a minimum vertex cover equals that of a maximum matching in the graph. These graphs have been studied extensively from a graph-theoretic point of view. In this paper, we introduce and study the algorithmic complexity of finding König-Egerváry subgraphs of a given graph. In particular, given a graph G and a nonnegative integer k, we are interested in the following questions:
-
1.
does there exist a set of k vertices (edges) whose deletion makes the graph König-Egerváry?
-
2.
does there exist a set of k vertices (edges) that induce a König-Egerváry subgraph?
We show that these problems are NP-complete and study their complexity from the points of view of approximation and parameterized complexity. Towards this end, we first study the algorithmic complexity of Above Guarantee Vertex Cover, where one is interested in minimizing the additional number of vertices needed beyond the maximum matching size for the vertex cover. Further, while studying the parameterized complexity of the problem of deleting k vertices to obtain a König-Egerváry graph, we show a number of interesting structural results on matchings and vertex covers which could be useful in other contexts.
Similar content being viewed by others
References
Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, min-2CNF deletion, and directed cut problems. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 573–581 (2005)
Bourjolly, J.M., Pulleyblank, W.R.: König-Egerváry graphs, 2-bicritical graphs and fractional matchings. Discrete Appl. Math. 24, 63–82 (1989)
Chlebik, M., Chlebikova, J.: On approximation hardness of the minimum 2-SAT deletion problem. Discrete Appl. Math. 155(2), 172–179 (2007)
Chen, J., Kanj, I.A.: On approximating minimum vertex cover for graphs with perfect matching. Theor. Comput. Sci. 337, 305–318 (2005)
Deming, R.W.: Independence numbers of graphs—an extension of the König-Egerváry theorem. Discrete Math. 27, 23–33 (1979)
Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439–485 (2005)
Downey, R., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, New York (2006)
Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: a simple O(20.288n) independent set algorithm. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 18–25 (2006)
Gavril, F.: Testing for equality between maximum matching and minimum node covering. Inf. Process. Lett. 6(6), 199–202 (1977)
Gavril, F., Yannakakis, M.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364–372 (1980)
Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386–1396 (2006)
Håstad, J.: Clique is hard to approximate to within n 1−ε. Acta Math. 182, 105–142 (1999)
Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), pp. 767–775 (2002)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2−ε. J. Comput. Syst. Sci. 74(3), 335–349 (2008)
Klein, P.N., Plotkin, S.A., Rao, S., Tardos, E.: Approximation algorithms for Steiner and directed multicuts. J. Algorithms 22(2), 241–269 (1997)
Korach, E., Nguyen, T., Peis, B.: Subgraph characterization of red/blue-split graphs and König-Egerváry graphs. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 842–850 (2006)
Lovász, L.: Ear-decompositions of matching-covered graphs. Combinatorica 3, 105–118 (1983)
Lovász, L., Plummer, M.D.: Matching Theory. North Holland, Amsterdam (1986)
Mahajan, M., Raman, V.: Parameterizing above guaranteed values: max sat and max cut. J. Algorithms 31(2), 335–354 (1999)
Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. In: Proceedings of the 2nd Workshop on Algorithms and Complexity in Durham (ACiD 2006), pp. 107–118 (2006)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)
Razgon, I., O’Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci. 75(8), 435–450 (2009)
Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32, 299–301 (2004)
Schröder, H., May, A.E., Sýkora, O., Vrt’o, I.: Approximation algorithms for the vertex bipartization problem. In: Proceedings of the 24th Seminar on Current Trends in Theory and Practice of Informatics (SOFSEM 1997). LNCS, vol. 1338, pp. 547–554. Springer, Berlin (1997)
Sterboul, F.: A characterization of graphs in which the transversal number equals the matching number. J. Comb. Theory, Ser. B 27, 228–229 (1979)
Subramanian, C.R.: Vertex covers: parameterizing above the requirement. IMSc Technical Report, February 2001
Vazirani, V.V.: A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm. Combinatorica 14(1), 71–109 (1994)
Vishwanathan, S.: On hard instances of approximate vertex cover. ACM Trans. Algorithms 5(1) (2008). doi:10.1145/1435375.1435382
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the 38th ACM Symposium on Theory of Computing (STOC 2006), pp. 681–690 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
Preliminary versions of this paper appeared in the proceedings of the 18th and 19th International Symposium on Algorithms and Computation (ISAAC 2007 and ISAAC 2008).
Rights and permissions
About this article
Cite this article
Mishra, S., Raman, V., Saurabh, S. et al. The Complexity of König Subgraph Problems and Above-Guarantee Vertex Cover. Algorithmica 61, 857–881 (2011). https://doi.org/10.1007/s00453-010-9412-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-010-9412-2