Tractability of König edge deletion problems

DOI10.1016/j.tcs.2019.09.011zbMath1435.68125arXiv1811.04560OpenAlexW2972767602MaRDI QIDQ2333799

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

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

vertex coverparameterized complexityW-hardnessKönig graphsKönig edge deletion

Mathematics Subject Classification ID

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

Related Items (2)

Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ A survey of parameterized algorithms and the complexity of edge modification

Cites Work

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

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