Tractability of König edge deletion problems

DOI10.1016/J.TCS.2019.09.011MaRDI QIDQ2333799zbMATHOpenAlexFDO

Authors Diptapriyo Majumdar, Rian Neogi, Venkatesh Raman, S. Vaishali

Publication date 13 November 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.04560

zbMATH Keywords

parameterized complexityvertex coverW-hardnessKönig graphsKönig edge deletion

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: 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.

Recommendations

• König Deletion Sets and Vertex Covers above the Matching Size
• The complexity of König subgraph problems and above-guarantee vertex cover
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• König graphs for 3-paths and 3-cycles
• Publication:5750892

Cites work

• A characterization of the graphs in which the transversal number equals the matching number
• Almost 2-SAT is fixed-parameter tractable
• Edge Bipartization Faster Than 2^k
• Fast FAST
• Faster exact and parameterized algorithm for feedback vertex set in tournaments
• Faster parameterized algorithms using linear programming
• Finding small stabilizers for unstable graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fixed-parameter tractability results for feedback set problems in tournaments
• Fractional matchings and the Edmonds-Gallai theorem
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Integer and Fractional Matchings
• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
• Matching theory
• New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
• On the integer-valued variables in the linear vertex packing problem
• Parameterized algorithms
• Parameterized complexity of finding subgraphs with hereditary properties.
• Properties of vertex packing and independence system polyhedra
• The complexity of König subgraph problems and above-guarantee vertex cover
• The node-deletion problem for hereditary properties is NP-complete
• Vertex packings: Structural properties and algorithms
• Wheel-Free Deletion Is W[2]-Hard
• Which problems have strongly exponential complexity?

Cited in

(8)

• Tree-edges deletion problems with bounded diameter obstruction sets
• Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
• Node-and edge-deletion NP-complete problems
• König Deletion Sets and Vertex Covers above the Matching Size
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• König graphs for 3-paths and 3-cycles
• A survey of parameterized algorithms and the complexity of edge modification
• The complexity of König subgraph problems and above-guarantee vertex cover

This page was built for publication: Tractability of König edge deletion problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2333799)