Header menu link for other important links
X
The complexity of finding subgraphs whose matching number equals the vertex cover number
Published in
2007
Volume: 4835 LNCS
   
Pages: 268 - 279
Abstract
The class of graphs where the size of a minimum vertex cover equals that of a maximum matching is known as König-Egerváry graphs. 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 maximum König-Egerváry subgraphs of a given graph. More specifically, we look at the problem of finding a minimum number of vertices or edges to delete to make the resulting graph König-Egervary. We show that both these versions are NP-complete and study their complexity from the points of view of approximation and parameterized complexity. En route, we point out an interesting connection between the vertex deletion version and the ABOVE GUARANTEE VERTEX COVER problem where one is interested in the parameterized complexity of the VERTEX COVER problem when parameterized by the 'additional number of vertices' needed beyond the matching size. This connection is of independent interest and could be useful in establishing the parameterized complexity of ABOVE GUARANTEE VERTEX COVER problem. © Springer-Verlag Berlin Heidelberg 2007.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN03029743
Open AccessNo
Concepts (8)
  •  related image
    Computational complexity
  •  related image
    Number theory
  •  related image
    Parameterization
  •  related image
    Problem solving
  •  related image
    Maximum matching
  •  related image
    PARAMETERIZED COMPLEXITY
  •  related image
    VERTEX COVER NUMBER
  •  related image
    Graph theory