Get all the updates for this publication

Conferences

The complexity of finding subgraphs whose matching number equals the vertex cover numberPublished in

2007

Volume: 4835 LNCS

Pages: 268 - 279

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.

Content may be subject to copyright.

About the journal

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

ISSN | 03029743 |

Open Access | No |

Concepts (8)

- Computational complexity
- Number theory
- Parameterization
- Problem solving
- Maximum matching
- PARAMETERIZED COMPLEXITY
- VERTEX COVER NUMBER
- Graph theory