Talk:Feedback arc set/GA1

GA Review

Article (edit | visual edit | history) · Article talk (edit | history) · Watch

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

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.

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)[reply]
- "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)[reply]
    - 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)[reply]
- "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)[reply]
- "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)[reply]
    - Fair enough, that was just a thought. SnowFire (talk) 00:24, 17 November 2021 (UTC)[reply]
- 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)[reply]
    - 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)[reply]
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)[reply]
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.
It follows the neutral point of view policy.
Fair representation without bias:
It is stable.
No edit wars, etc.:
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)[reply]
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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]