Tractability of Konig Edge Deletion Problems

Autor:	Majumdar, Diptapriyo, Neogi, Rian, Raman, Venkatesh, Vaishali, S.
Rok vydání:	2018
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics 68Q25
Druh dokumentu:	Working Paper
Popis:	A graph is said to be a Konig graph if the size of its maximum matching is equal to the size of its minimum vertex cover. The Konig Edge Deletion problem asks if in a given graph there exists a set of at most k edges whose deletion results in a Konig graph. While the vertex version of the problem (Konig vertex deletion) has been shown to be fixed-parameter tractable more than a decade ago, the fixed-parameter-tractability of the Konig Edge Deletion problem has been open since then, and has been conjectured to be W[1]-hard in several papers. In this paper, we settle the conjecture by proving it W[1]-hard. We prove that a variant of this problem, where we are given a graph G and a maximum matching M and we want a k-sized Konig edge deletion set that is disjoint from M, is fixed-parameter-tractable. Comment: Accepted for publication in Theoretical Computer Science. Major revisions from the previous version were incorporated based on the comments from anonymous reviewers
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1811.04560 Zobrazit plný text záznamu View this record from Arxiv