Get all the updates for this publication

Articles

The complexity of König subgraph problems and above-guarantee vertex coverOpen Access

Published in

2011

Volume: 61

Issue: 4

Pages: 857 - 881

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. © 2010 Springer Science+Business Media, LLC.

Preprint Version

Content may be subject to copyright.This is a green open access articleThis is a green open access article

About the journal

Journal | Algorithmica (New York) |
---|---|

ISSN | 01784617 |

Open Access | Yes |

Concepts (19)

- Algorithmic complexity
- Graph g
- Graph-theoretic
- MATCHINGS
- Maximum matchings
- MINIMUM VERTEX COVER
- NONNEGATIVE INTEGERS
- Np complete
- PARAMETERIZED COMPLEXITY
- Subgraph problems
- Subgraphs
- UNIQUE GAMES
- Vertex cover
- Approximation algorithms
- Computational complexity
- Integer programming
- Parallel processing systems
- Parameterization
- Graph theory