History

Please fill in your query. A complete syntax description you will find on the General Help page.
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.