Talk:Feedback vertex set
Latest comment: 2 years ago by 68.5.117.23 in topic NP-hard vs NP-complete
 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||
Notability?
editWhy does this have its own Wiki article? Is there some other article this can be merged to? I just don't see how this concept warrants an article. Torc2 (talk) 23:03, 28 November 2007 (UTC)
- scholar.google.com lists 908 scientific articles mentioning Feedback Vertex Set; 88 have it in their title. It would be easy to fill a whole book with the results. So in my opinion, this concepts does warrant an article. --Mellum (talk) 23:28, 29 November 2007 (UTC)
- OK, I was just legitimately curious - I didn't tag it or nominate it for deletion. It'd be nice to flesh out the section on uses for the function. Torc2 (talk) 23:42, 29 November 2007 (UTC)
Statement removed from main article
editI have removed the following sentence from the main article:
- In contrast, the problem is polynomial-time solvable on graphs of maximum degree at most three.[citation needed]
This statement was initially sourced Cao, Chen & Liu (2010), but is not supported by that reference. Hermel (talk) 19:35, 27 October 2011 (UTC)
NP-hard vs NP-complete
editThe article keeps saying that the optimization version (MINIMUM FVS) is NP-complete. It is not. It is NP-hard. It is the decision problem that is NP-complete.
This is probably happening in other articles as well. 68.5.117.23 (talk) 01:21, 15 July 2022 (UTC)