Edge deletion to tree-like graph classes

DOI10.1016/J.DAM.2024.01.028MaRDI QIDQ6124427zbMATH OpenWikidataFDO

Authors Ivo Koch, Nina Pardal, Vinícius F. dos Santos

Publication date 27 March 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

edge deletion problemsmodification problemssparse graph classes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: For a fixed property (graph class) $Pi$, given a graph G and an integer k, the $Pi$-deletion problem consists in deciding if we can turn $G$ into a graph with the property $Pi$ by deleting at most $k$ edges. The $Pi$-deletion problem is known to be NP-hard for most of the well-studied graph classes, such as chordal, interval, bipartite, planar, comparability and permutation graphs, among others; even deletion to cacti is known to be NP-hard for general graphs. However, there is a notable exception: the deletion problem to trees is polynomial. Motivated by this fact, we study the deletion problem for some classes similar to trees, addressing in this way a knowledge gap in the literature. We prove that deletion to cacti is hard even when the input is a bipartite graph. On the positive side, we show that the problem becomes tractable when the input is chordal, and for the special case of quasi-threshold graphs we give a simpler and faster algorithm. In addition, we present sufficient structural conditions on the graph class $Pi$ that imply the NP-hardness of the $Pi$-deletion problem, and show that deletion from general graphs to some well-known subclasses of forests is NP-hard.

Recommendations

• The complexity of some edge deletion problems
• An Application of Duality to Edge-Deletion Problems
• Chordal deletion is fixed-parameter tractable
• Node-and edge-deletion NP-complete problems
• Tree-edges deletion problems with bounded diameter obstruction sets

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• An induced subgraph characterization of domination perfect graphs
• Chordal completions of planar graphs
• Clustering and domination in perfect graphs
• Dominating sets for split and bipartite graphs
• Edge-Deletion Problems
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph theory
• Hamilton Paths in Grid Graphs
• Hamiltonian circuits in interval graph generalizations
• Matroid matching and some applications
• On the complexity of DNA physical mapping
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The complexity of some edge deletion problems
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• The node-deletion problem for hereditary properties is NP-complete
• The path partition problem and related problems in bipartite graphs

Cited in

(3)

• Deleting to structured trees
• Parameterised distance to local irregularity
• Exact algorithms for edge deletion to Cactus

This page was built for publication: Edge deletion to tree-like graph classes

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