Advertisement
Published in:
2011 | OriginalPaper | Chapter
Two Hardness Results on Feedback Vertex Sets
Authors : Wei Jiang, Tian Liu, Tienan Ren, Ke Xu
Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A feedback vertex set is a subset of vertices whose deletion makes the remaining graph a forest. We show that the minimum FVS (MFVS) in star convex bipartite graphs is
$\mathcal{NP}$
-hard to find, and give a tighter lower bound on the size of MFVS in sparse random graphs, to provide further evidence on the hardness of random CSPs.