Polynomial-time algorithms exist for all CMSO2-expressible sparse induced subgraph problems in P7-free graphs of bounded clique number.
Feedback vertex set on chordal bipartite graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
cs.DS 1years
2024 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
Polynomial-time algorithms exist for all CMSO2-expressible sparse induced subgraph problems in P7-free graphs of bounded clique number.