{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:13:54Z","timestamp":1781259234393,"version":"3.54.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,5,20]],"date-time":"2010-05-20T00:00:00Z","timestamp":1274313600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1007\/s00453-010-9412-2","type":"journal-article","created":{"date-parts":[[2010,5,19]],"date-time":"2010-05-19T18:28:24Z","timestamp":1274293704000},"page":"857-881","source":"Crossref","is-referenced-by-count":28,"title":["The Complexity of K\u00f6nig Subgraph Problems and\u00a0Above-Guarantee Vertex Cover"],"prefix":"10.1007","volume":"61","author":[{"given":"Sounaka","family":"Mishra","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Somnath","family":"Sikdar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C. R.","family":"Subramanian","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,5,20]]},"reference":[{"key":"9412_CR1","doi-asserted-by":"crossref","unstructured":"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\u2013581 (2005)","DOI":"10.1145\/1060590.1060675"},{"key":"9412_CR2","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0166-218X(92)90273-D","volume":"24","author":"J.M. Bourjolly","year":"1989","unstructured":"Bourjolly, J.M., Pulleyblank, W.R.: K\u00f6nig-Egerv\u00e1ry graphs, 2-bicritical graphs and fractional matchings. Discrete Appl. Math. 24, 63\u201382 (1989)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9412_CR3","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.dam.2006.04.039","volume":"155","author":"M. Chlebik","year":"2007","unstructured":"Chlebik, M., Chlebikova, J.: On approximation hardness of the minimum 2-SAT deletion problem. Discrete Appl. Math. 155(2), 172\u2013179 (2007)","journal-title":"Discrete Appl. Math."},{"key":"9412_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/j.tcs.2004.12.034","volume":"337","author":"J. Chen","year":"2005","unstructured":"Chen, J., Kanj, I.A.: On approximating minimum vertex cover for graphs with perfect matching. Theor. Comput. Sci. 337, 305\u2013318 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9412_CR5","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0012-365X(79)90066-9","volume":"27","author":"R.W. Deming","year":"1979","unstructured":"Deming, R.W.: Independence numbers of graphs\u2014an extension of the K\u00f6nig-Egerv\u00e1ry theorem. Discrete Math. 27, 23\u201333 (1979)","journal-title":"Discrete Math."},{"issue":"1","key":"9412_CR6","doi-asserted-by":"crossref","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I. Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439\u2013485 (2005)","journal-title":"Ann. Math."},{"key":"9412_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"9412_CR8","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, New York (2006)"},{"key":"9412_CR9","doi-asserted-by":"crossref","unstructured":"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\u201325 (2006)","DOI":"10.1145\/1109557.1109560"},{"issue":"6","key":"9412_CR10","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(77)90068-0","volume":"6","author":"F. Gavril","year":"1977","unstructured":"Gavril, F.: Testing for equality between maximum matching and minimum node covering. Inf. Process. Lett. 6(6), 199\u2013202 (1977)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9412_CR11","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"F. Gavril","year":"1980","unstructured":"Gavril, F., Yannakakis, M.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."},{"issue":"8","key":"9412_CR12","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J. Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9412_CR13","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate to within n 1\u2212\u03b5 . Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"9412_CR14","doi-asserted-by":"crossref","unstructured":"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\u2013775 (2002)","DOI":"10.1145\/510014.510017"},{"issue":"3","key":"9412_CR15","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S. Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2212\u03b5. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9412_CR16","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1006\/jagm.1996.0833","volume":"22","author":"P.N. Klein","year":"1997","unstructured":"Klein, P.N., Plotkin, S.A., Rao, S., Tardos, E.: Approximation algorithms for Steiner and directed multicuts. J. Algorithms 22(2), 241\u2013269 (1997)","journal-title":"J. Algorithms"},{"key":"9412_CR17","doi-asserted-by":"crossref","unstructured":"Korach, E., Nguyen, T., Peis, B.: Subgraph characterization of red\/blue-split graphs and K\u00f6nig-Egerv\u00e1ry graphs. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 842\u2013850 (2006)","DOI":"10.1145\/1109557.1109650"},{"key":"9412_CR18","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579346","volume":"3","author":"L. Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Ear-decompositions of matching-covered graphs. Combinatorica 3, 105\u2013118 (1983)","journal-title":"Combinatorica"},{"key":"9412_CR19","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. North Holland, Amsterdam (1986)"},{"issue":"2","key":"9412_CR20","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: max sat and max cut. J. Algorithms 31(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"key":"9412_CR21","unstructured":"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\u2013118 (2006)"},{"key":"9412_CR22","doi-asserted-by":"crossref","DOI":"10.1145\/211542.606546","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"9412_CR23","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)"},{"issue":"8","key":"9412_CR24","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I. Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci. 75(8), 435\u2013450 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9412_CR25","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B. Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32, 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"key":"9412_CR26","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1007\/3-540-63774-5_137","volume-title":"Proceedings of the 24th Seminar on Current Trends in Theory and Practice of Informatics (SOFSEM 1997)","author":"H. Schr\u00f6der","year":"1997","unstructured":"Schr\u00f6der, H., May, A.E., S\u00fdkora, O., Vrt\u2019o, 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\u2013554. Springer, Berlin (1997)"},{"key":"9412_CR27","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/0095-8956(79)90085-6","volume":"27","author":"F. Sterboul","year":"1979","unstructured":"Sterboul, F.: A characterization of graphs in which the transversal number equals the matching number. J. Comb. Theory, Ser. B 27, 228\u2013229 (1979)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9412_CR28","unstructured":"Subramanian, C.R.: Vertex covers: parameterizing above the requirement. IMSc Technical Report, February 2001"},{"issue":"1","key":"9412_CR29","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF01305952","volume":"14","author":"V.V. Vazirani","year":"1994","unstructured":"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\u2013109 (1994)","journal-title":"Combinatorica"},{"key":"9412_CR30","doi-asserted-by":"crossref","unstructured":"Vishwanathan, S.: On hard instances of approximate vertex cover. ACM Trans. Algorithms 5(1) (2008). doi: 10.1145\/1435375.1435382","DOI":"10.1145\/1435375.1435382"},{"key":"9412_CR31","doi-asserted-by":"crossref","unstructured":"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\u2013690 (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9412-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9412-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9412-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T01:05:53Z","timestamp":1635383153000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9412-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,20]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["9412"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9412-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5,20]]}}}