Tractability of König edge deletion problems

DOI10.1016/J.TCS.2019.09.011zbMATH Open1435.68125arXiv1811.04560OpenAlexW2972767602MaRDI QIDQ2333799FDOQ2333799

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

Publication date: 13 November 2019

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

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.

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)

Cites Work

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

Cited In (4)

• Node-and edge-deletion NP-complete problems
• Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
• A survey of parameterized algorithms and the complexity of edge modification
• Tree-edges deletion problems with bounded diameter obstruction sets

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)