Two hardness results on feedback vertex sets. (English)
Atallah, Mikhail (ed.) et al., Frontiers in algorithmics and algorithmic aspects in information and management. Joint international conference, FAW-AAIM 2011, Jinhua, China, May 28‒31, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21203-1/pbk). Lecture Notes in Computer Science 6681, 233-243 (2011).
Summary: 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.
Start
Contact
Print
General Help
