Feedback vertex set on chordal bipartite graphs

2011/04/20 by Kloks, Ton, Liu, Ching-Hao, Poon, Sheung-Hung · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1104.3915

Abstract

Let G=(A,B,E) be a bipartite graph with color classes A and B. The graph G is chordal bipartite if G has no induced cycle of length more than four. Let G=(V,E) be a graph. A feedback vertex set F is a set of vertices F subset V such that G-F is a forest. The feedback vertex set problem asks for a feedback vertex set of minimal cardinality. We show that the feedback vertex set problem can be solved in polynomial time on chordal bipartite graphs.

Cited by

• Chordal signed graphs and signed bigraphs

Related

• Computing Subset Feedback Vertex Set via Leafage
• Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs
• Independent Feedback Vertex Sets for Graphs of Bounded Diameter
• A Note on Finding Dual Feedback Vertex Set
• Polynomial-time Algorithms for the Subset Feedback Vertex Set Problem on\n Interval Graphs and Permutation Graphs