Constrained Hitting Set and Steiner Tree in SC_k and 2K₂-free Graphs

2016/10/04 by S. Dhanalakshmi, Dhanalakshmi, S., N. Sadagopan +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1610.00853

openalex publication_date 2016/10/04 · openalex created_date 2016/10/14 · openalex updated_date 2026/07/28

Abstract

Strictly Chordality-k graphs (SC_k) are graphs which are either cycle-free or every induced cycle is of length exactly k, k ≥ 3. Strictly chordality-3 and strictly chordality-4 graphs are well known chordal and chordal bipartite graphs, respectively. For k≥ 5, the study has been recently initiated in \citesadagopan 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 SC_k graphs, k≥ 5. We next consider 2K₂-free graphs and show that FVS, OCT, ECT, Steiner tree problem are polynomial time solvable on subclasses of 2K₂-free graphs.

Related

• On strictly Chordality-k graphs
• Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
• Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
• On Cycle Transversals and Their Connected Variants in the Absence of a\n Small Linear Forest
• Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs