Talk:Feedback arc set

{{GA|00:26, 17 November 2021 (UTC)|topic=Computing and engineering|page=1|oldid=1055640007}}

{{DYK talk|5 December|2021|entry=... that for round-robin sports tournaments, finding a ranking of the competitors that minimizes the number of upset games is an instance of the feedback arc set problem?|nompage=Template:Did you know nominations/Feedback arc set}}

{{WikiProject banner shell|class=GA|

}}

Taken from

http://www-inst.eecs.berkeley.edu/~cs170/hw/hw12.pdf

- homework problems. Charles Matthews 10:49, 9 May 2005 (UTC)

Undirected graphs.

The article states On the other hand, if the edges are undirected, the problem of deleting edges to make the graph cycle-free is equivalent to finding a minimum spanning tree, which can be done easily in polynomial time.

Why is this? If we consider the example given in the introduction as an undirected graph, then the any spanning tree would need two edges, but removing a single edge would still suffice to break the cycle. 129.240.70.72 11:22, 7 September 2007 (UTC)

:"equivalent" here means that there is a trivial reduction in both directions: the feedback arc set comprises those edges that the spanning tree does not. --Mellum 18:54, 7 September 2007 (UTC)

Complexity

The article states that figuring the number of edges is an NP-Hard problem and the decision procedure NP-complete. But if the decision procedure is NP-complete I would have thought the optimization problem would also be NP-complete. Taemyr 06:46, 14 September 2007 (UTC)

:Optimization problems are never NP-complete, because to be NP-complete a problem must be in NP, and NP is a class of decision problems only. Dcoetzee 18:51, 14 September 2007 (UTC)

::Thanks. Taemyr 08:24, 20 September 2007 (UTC)

Approximatability

The article says that the problem is APX-hard, but [http://www.cs.brown.edu/people/ws/tournament.pdf] gives a PTAS for the problem. What's going on? If these are talking about the same problem, one has to be wrong.

CRGreathouse (t | c) 19:23, 11 October 2007 (UTC)

:Actually they're both correct - the original minimum feedback arc set problem is APX-hard, as described in Kann's "On the Approximability of NP-Complete Optimization Problems" ([http://www.nada.kth.se/~viggo/papers/phdthesis.pdf pdf]), but Weighted Feedback Set on Tournaments has a PTAS. Another example of how a small variation can change the complexity of a problem. Dcoetzee 20:12, 11 October 2007 (UTC)