Talk:Feedback vertex set

Latest comment: 2 years ago by 68.5.117.23 in topic NP-hard vs NP-complete

Notability?

edit

Why 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)Reply

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)Reply
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)Reply

Statement removed from main article

edit

I 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)Reply

NP-hard vs NP-complete

edit

The 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)Reply