Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs

DOI10.21494/ISTE.OP.2023.0903MaRDI QIDQ6136471zbMATH OpenFDO

Authors S. Dhanalakshmi, N. Sadagopan

Publication date 31 August 2023

Published in Advances in Pure and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Steiner treefeedback vertex set\(2K_2\)-free graphsodd (Even) cycle transversalstrictly chordality-\(k\) graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Paths and cycles (05C38) Transversal (matching) theory (05D15)

Abstract: emph{Strictly Chordality-$k$ graphs ($S{C}_k$)} are graphs which are either cycle-free or every induced cycle is of length exactly $k,kgeq3$. Strictly chordality-3 and strictly chordality-4 graphs are well known chordal and chordal bipartite graphs, respectively. For $kgeq5$, the study has been recently initiated in cite{sadagopan} and various structural and algorithmic results are reported. In this paper, we show that maximum independent set (MIS), minimum vertex cover, minimum dominating set, feedback vertex set (FVS), odd cycle transversal (OCT), even cycle transversal (ECT) and Steiner tree problem are polynomial time solvable on $S{C}_k$ graphs, $kgeq5$. We next consider $2K_2$-free graphs and show that FVS, OCT, ECT, Steiner tree problem are polynomial time solvable on subclasses of $2K_2$-free graphs.

Recommendations

• On strictly chordality-\(k\) graphs
• Steiner trees for hereditary graph classes: a treewidth perspective
• Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy
• Doubly chordal graphs, steiner trees, and connected domination
• Tree polytope on 2-trees

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Dominating Sets in Chordal Graphs
• Dominating sets for split and bipartite graphs
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• Hamiltonian circuits in interval graph generalizations
• Node-and edge-deletion NP-complete problems
• On strictly chordality-\(k\) graphs
• Parameterized algorithms for even cycle transversal
• Steiner trees, connected domination and strongly chordal graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The complexity of generalized clique covering
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs

Cited in

(1)

• On strictly chordality-\(k\) graphs

This page was built for publication: Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs

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