caa a22 4500 445805315 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00453-010-9412-2 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9412-2 The Complexity of König Subgraph Problems andAbove-Guarantee Vertex Cover [Elektronische Daten] [Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar, C. Subramanian] 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 graphG and a nonnegative integerk, we are interested in the following questions: 1.does there exist a set ofk vertices (edges) whose deletion makes the graph König-Egerváry?2.does there exist a set ofk 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. Springer Science+Business Media, LLC, 2010 Vertex cover nationallicence Above guarantee vertex cover nationallicence König graphs nationallicence König vertex/edge deletion sets nationallicence Maximum matching nationallicence Parameterized complexity nationallicence Approximation algorithms nationallicence Unique game conjecture nationallicence Mishra Sounaka Department of Mathematics, The Indian Institute of Technology, Chennai, India aut Raman Venkatesh The Institute of Mathematical Sciences, Chennai, India aut Saurabh Saket The Institute of Mathematical Sciences, Chennai, India aut Sikdar Somnath Department of Computer Science, RWTH Aachen University, 52056, Aachen, Germany aut Subramanian C. The Institute of Mathematical Sciences, Chennai, India aut Algorithmica Springer-Verlag 61/4(2011-12-01), 857-881 0178-4617 61:4<857 2011 61 453 https://doi.org/10.1007/s00453-010-9412-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9412-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Mishra Sounaka Department of Mathematics, The Indian Institute of Technology, Chennai, India aut NATIONALLICENCE 700 1- Raman Venkatesh The Institute of Mathematical Sciences, Chennai, India aut NATIONALLICENCE 700 1- Saurabh Saket The Institute of Mathematical Sciences, Chennai, India aut NATIONALLICENCE 700 1- Sikdar Somnath Department of Computer Science, RWTH Aachen University, 52056, Aachen, Germany aut NATIONALLICENCE 700 1- Subramanian C. The Institute of Mathematical Sciences, Chennai, India aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/4(2011-12-01), 857-881 0178-4617 61:4<857 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer