Talk:Feedback arc set

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 [1] 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" (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)

GA Review

This review is transcluded from Talk:Feedback arc set/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: SnowFire (talk · contribs) 07:18, 15 November 2021 (UTC)

GA review (see here for what the criteria are, and here for what they are not)

---

Looks like people are gunshy on taking this one, as it's been sitting around for awhile. I'll give it a shot, with the usual "some of this is flying over my head" disclaimer.

1. It is reasonably well written.

   a (prose, spelling, and grammar): b (MoS for lead, layout, word choice, fiction, and lists):

   I suspect you knew this was coming - the biggest worry is accessibility to a general audience. Now yes, a truly general audience won't even find this article nor care about it. However, I think you can still make the article more accessible for people with a standard math background. The images are a great addition! But still a few nits... I'm mostly nitpicking the lede, as if there's any place that should be crystal-clear, it's that.

   The intent was to make the first part of the lead, and the applications section, more readable to a wider audience, while still keeping the technical detail for specialists in the later sections and summarizing those later sections appropriately in the lead. But it's entirely likely that parts can be made more accessible than they are already. —David Eppstein (talk) 21:23, 15 November 2021 (UTC)

   • "It is often desirable" -> I know this is math-ese, but for the lede, maybe a different phrasing? Either remove it or explain why it's desirable after the terminology explanation, IMO.
     • It was not so much math-ese, as a forward reference to the applications where this minimization is often the goal. But as you seem to prefer a dry style that just states the definition, I have removed the part about desirability. —David Eppstein (talk) 08:32, 16 November 2021 (UTC)
       • Nah, as per above I'm fine with being loose in the lede, but I do think "forward reference" can be tricky. It's the old adage in writing about show, don't tell - if it really is desirable, say "maximum acyclic subgraphs are awesome because they have properties X, Y, and Z". So I do think just removing it is better if there isn't space to show why it's useful. SnowFire (talk) 00:24, 17 November 2021 (UTC)
   • "Finding minimum feedback arc sets and maximum acyclic subgraphs is NP-hard, but can be solved in exponential time, or in fixed-parameter tractable time." -> Wait, why "but"? Lots of NP-Hard problems are exponential time, so there's no contrast, right? I'd just split into two sentences, or else make clear why this is a "but".
     • It's a contrast between a lower bound (it's hard) and an upper bound (we can still solve it). I don't think "and" makes sense as a connective, because it should connect clauses that all point in the same direction and these point in opposite directions. On the other hand, NP-hardness generally motivates the search for exponential time and FPT algorithms (if it's not a hard problem, those are not the kinds of algorithms you should be looking for), so they don't belong in separate sentences. I changed it to a semicolon, which is more neutral.
       • A semicolon works for me. I suppose I was just saying that contrast is already inherent in saying it's NP-Hard to me, so the old phrasing made me wonder if there was something deeper to it.
         • It's not immediate from being in NP that the problem has time exponential in #vertices. Brute force searches for sets of edges or topological orderings of vertices are slower, exponential in #edges or factorial in #vertices. So yes, the exponential time upper bound adds something to the hardness statement, but maybe it could be expressed more clearly. —David Eppstein (talk) 19:49, 17 November 2021 (UTC)
   • "If a feedback edge set is minimal (...) then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph." -> Nit: "also produces" perhaps, to make clear we're back where we started and producing a DAG a different way?
     • I tend to overuse the word "also" but I don't see the point of it here when we're already using "additional" to indicate that this is an addition to the previous property. "Then, also, it also has an additional property"? I could easily imagine accidentally writing that and only catching it later. —David Eppstein (talk) 08:32, 16 November 2021 (UTC)
       • Fair enough, that was just a thought. SnowFire (talk) 00:24, 17 November 2021 (UTC)
   • Approximated & Approximability in the lede: I think you're running into a clash between math-ese and English here. You can approximate anything, it just won't necessarily be very good ("The population of France is approximately 5 people"). The body of the article clarifies that we're really talking about efficiently approximating in polynomial time to within some known margin, so I'd see if that could be made clearer in the lede without making it too dense.
     • I think the lead is not the place for pedantically filling in details with full mathematical precision, but I threw in an "In polynomial time" lead-in. —David Eppstein (talk) 08:32, 16 November 2021 (UTC)
       • Yeah, it's clashing goals of making the lede both approachable, concise, and accurate, but I do feel that this is significant rather than pedantic. Anything can be approximated badly and/or slowly, the "interesting" part is when there's an approximation that's both efficient and reasonably accurate. SnowFire (talk) 00:24, 17 November 2021 (UTC)
2. It is factually accurate and verifiable.

   a (reference section): b (citations to reliable sources): c (OR): d (copyvio and plagiarism):

   I will mostly AGF the copyvio / plagarism aspects, as well as these being Real Journals and not sneaking in a fake journal somewhere. The prices for access to journal articles are crazy - I tried to spotcheck some of these sources, also for background, and they all charge crazy rates for the PDF. Sigh. At least I was able to read the three references with arxiv links. So while the second link to Karpinski & Schudy checks out, can you clarify why it's a valid reference the first time, i.e. "This can be formulated and solved as a minimum-weight feedback arc set problem, in which the vertices represent candidates, edges are directed to represent the winner of each head-to-head contest, and the cost of each edge represents the number of voters who would be made unhappy by giving a higher ranking to the head-to-head loser?" I CTRL-F'd through the paper and read parts, and it doesn't ever seem to quite say that, but maybe I missed something.

   The sentence in question concerns formulating Kemeny rank aggregation as a weighted feedback arc set problem in tournaments ("weighted FAST", in the terminology of Karpinsky and Schudy). One relevant paragraph of Karpinsky and Schudy is the one spanning pages 2-3 on the arXiv version: "An important application of weighted feedback arc set tournament is rank aggregation ... A natural notion of distance is the number of pairs of vertices that are in different orders ... This defines the Kemeny rank aggregation problem". —David Eppstein (talk) 21:23, 15 November 2021 (UTC)

3. It is broad in its coverage.

   a (major aspects): b (focused):

   AGF'ing here since you've clearly read the literature that you're not hiding some key aspect of this problem from the article.

4. It follows the neutral point of view policy.

   Fair representation without bias:

5. It is stable.

   No edit wars, etc.:

6. It is illustrated by images and other media, where possible and appropriate.

   a (images are tagged and non-free content have fair use rationales): b (appropriate use with suitable captions):

   Excellent images, they really do help the article! Licensing looks fine. My one request: Can you add an explanation for the numbers in File:Min-upset ranking MBV 2016 Pool F.svg to the image description (i.e. the 21-16, 21-16 annotations), and add a source for the results to show that it's real and not hypothetical? Yeah, I know the results are in the linked article too, but it can't hurt to have a link in the image as well.

   Added to the image file's description, and also expanded the caption somewhat. —David Eppstein (talk) 21:23, 15 November 2021 (UTC)

7. Overall:

   Pass/Fail:

   Looks good! If it is possible to make the lede slightly "friendlier" I think we're good to go, along with answering the two minor requests above that I can't imagine will be a problem at all. Nice work, an interesting read. SnowFire (talk) 07:18, 15 November 2021 (UTC)

Also, while I'm here, my one random question - is there a variant on this problem for when a graph is weakly connected, and the goal is to create a feedback arc set that is still weakly connected? Maybe it's in the article already, but I missed it. For example, if A->B->C->D->E and there's also a switch back from C->B, deleting C->B keeps the weak connectivity, but deleting B->C, while changing the graph into a DAG, breaks the weak connectivity of the graph. Not sure if that ever comes up. SnowFire (talk) 07:18, 15 November 2021 (UTC)

Interesting question, but the short answer is that I don't know of any research on such a variant and a quick search didn't find anything promising. Anyway, thanks for the review — I'll work on your other comments through the next few days. —David Eppstein (talk) 07:25, 15 November 2021 (UTC)

Now that I think about it, I'm not sure my example works anyway, I think it would still qualify as weakly connected looking at the definition again. But maybe there's another example that would work. Anyway, this is more a fun side-note, not a real issue with 3a. SnowFire (talk) 07:32, 15 November 2021 (UTC)

@SnowFire: I think I've responded to all comments here; please take another look. —David Eppstein (talk) 20:22, 16 November 2021 (UTC)

I checked the diff of your changes. I can't comment on the nowraps you added but they don't seem to detract at least, and I do think the lede reads slightly better now. This will always be a tough topic on accessibility for the level of detail it goes into (and I even liked graph theory in college!), but it does seem comprehensive and accurate, which are the most important criterions IMO. Nice work! SnowFire (talk) 00:24, 17 November 2021 (UTC)

Thanks! The nowraps are because if you have a math formula followed by punctuation, the browser will often put a line break between the formula and punctuation. Using nowrap prevents those bad line breaks, and should have no other visible effect. —David Eppstein (talk) 01:20, 17 November 2021 (UTC)

Did you know nomination

The following is an archived discussion of the DYK nomination of the article below. Please do not modify this page. Subsequent comments should be made on the appropriate discussion page (such as this nomination's talk page, the article's talk page or Wikipedia talk:Did you know), unless there is consensus to re-open the discussion at this page. No further edits should be made to this page.

The result was: promoted by Kavyansh.Singh (talk) 13:08, 25 November 2021 (UTC)

(

• Comment or view
• Article history

)

• ... 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? Source: Remage & Thompson, 1966, https://doi.org/10.2307/2334060 (paywalled); for the formulation of sports tournaments as a ranking problem, see p. 145, for the definition of the minimum-upset ranking, see "Slater's i" at the top of p. 145, and for the equivalence to the feedback arc set problem, see theorem 2, p. 146

• Reviewed: Noa Denmon

Improved to Good Article status by David Eppstein (talk). Self-nominated at 23:52, 17 November 2021 (UTC).

GA recent, article otherwise excellent. Hood directly cited. QPQ complete. GTG. Maury Markowitz (talk) 15:55, 18 November 2021 (UTC)

Promoting to Prep 5 – Kavyansh.Singh (talk) 13:08, 25 November 2021 (UTC)