View source for 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 tournament|round-robin sports tournaments]], finding a [[Group tournament ranking system|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|
{{WikiProject Mathematics|priority=Low}}
{{WikiProject Computer science|importance=Low}}
}}

Taken from 

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

- homework problems. [[User:Charles Matthews|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. [[User:129.240.70.72|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. --[[User:Mellum|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. [[User:Taemyr|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. [[User:Dcoetzee|Dcoetzee]] 18:51, 14 September 2007 (UTC)
::Thanks.  [[User:Taemyr|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.

[[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 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. [[User:Dcoetzee|Dcoetzee]] 20:12, 11 October 2007 (UTC)

{{Talk:Feedback arc set/GA1}}

==Did you know nomination==
{{Did you know nominations/Feedback arc set}}