TY - GEN
T1 - Feedback vertex sets on tree convex bipartite graphs
AU - Wang, Chaoyi
AU - Liu, Tian
AU - Jiang, Wei
AU - Xu, Ke
PY - 2012
Y1 - 2012
N2 - A feedback vertex set in a graph is a subset of vertices, such that the complement of this subset induces a forest. Finding a minimum feedback vertex set (FVS) is -complete on bipartite graphs, but tractable on chordal bipartite graphs. A bipartite graph is called tree convex, if a tree is defined on one part of the vertices, such that for every vertex in the other part, the neighborhood of this vertex induces a subtree. First, we show that chordal bipartite graphs form a proper subset of tree convex bipartite graphs. Second, we show that FVS is -complete on the tree convex bipartite graphs where the sum of the degrees of vertices whose degree is at least three on the tree is unbounded. Combined with known tractability where this sum is bounded, we show a dichotomy of complexity of FVS on tree convex bipartite graphs.
AB - A feedback vertex set in a graph is a subset of vertices, such that the complement of this subset induces a forest. Finding a minimum feedback vertex set (FVS) is -complete on bipartite graphs, but tractable on chordal bipartite graphs. A bipartite graph is called tree convex, if a tree is defined on one part of the vertices, such that for every vertex in the other part, the neighborhood of this vertex induces a subtree. First, we show that chordal bipartite graphs form a proper subset of tree convex bipartite graphs. Second, we show that FVS is -complete on the tree convex bipartite graphs where the sum of the degrees of vertices whose degree is at least three on the tree is unbounded. Combined with known tractability where this sum is bounded, we show a dichotomy of complexity of FVS on tree convex bipartite graphs.
UR - https://www.scopus.com/pages/publications/84865024120
U2 - 10.1007/978-3-642-31770-5_9
DO - 10.1007/978-3-642-31770-5_9
M3 - 会议稿件
AN - SCOPUS:84865024120
SN - 9783642317699
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 95
EP - 102
BT - Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Proceedings
T2 - 6th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2012
Y2 - 5 August 2012 through 9 August 2012
ER -