Talk:Cop-win graph

There is a problem with the paragraph about hereditarily cop-win graphs. If they are defined as the graphs in which every induced subgraph is cop-win (as it is now), then they do not correspond to bridged graphs (consider a cycle of length 6 plus a universal vertex). In the abstract of the paper of Anstee and Farber, it is written that "a connected graph is bridged if and only if every isometric subgraph is a cop-win graph".

So one need either to change the definition of hereditarily cop-win graphs by replacing induced by isometric, or to rephrase/remove the subsequent sentences.

Looking at ISGCI [1] it seems you are right, it should be isometric not just induced. —David Eppstein (talk) 20:20, 4 April 2018 (UTC)

The article states that the king's graph is cop-win, but that can't be true. The 2 by 2 version of the king's graph is the complete graph of order 4, which isn't cop win. 100.1.249.103 (talk) 02:10, 14 June 2018 (UTC)

Huh? Every complete graph is an immediate win for the cop. —David Eppstein (talk) 05:44, 14 June 2018 (UTC)

Something wrong...

In section Recognition algorithms and the family of all dismantling orders read:

Repeatedly find a vertex v that is an endpoint of an edge participating in a number of triangles equal to the degree of v, delete v, and decrement the triangles per edge of each remaining edge that formed a triangle with v.

Diamond graph has 2 triangles. 2 vertex has degree 2, but number of triangles equal 1. 2 vertex has degree 3, but number of triangles equal 2. So number of triangles equal to the degree of v never holds...

Another case. Take any path. There are no triangles at all. So number of triangles equal to the degree of v again does not held. Jumpow (talk) 09:54, 3 April 2019 (UTC)

There are two issues here, one with your article but the other with your misreading of it. (1) There's an off-by-one error; it should be degree minus one. (2) It's not the number of triangles v belongs to, and it's not the number of triangles in the whole graph; it's whether there's an edge vw that participates in deg(v)-1 triangles. —David Eppstein (talk) 17:01, 3 April 2019 (UTC)

Ok, 1. Agree 2. Not agree. What about missing triangles in graph? For example - lattice. So number of triangles equal to the degree of v minus one again does not held (triangles = 0, min degree = 2). It looks like I something missed... Every dismantling graph has triangles? And why exist vertex with property deg(v)-1 = # triangles? Jumpow (talk) 18:06, 3 April 2019 (UTC)

The square lattice is not a cop-win graph. The example in the article that looks like a lattice is actually a King's graph, a different graph with many triangles. And in a cop-win graph, if v is a dominated vertex, it must have a neighbor w that dominates it, in which case edge vw participates in exactly deg(v)-1 triangles, one with each other neighbor of v. —David Eppstein (talk) 19:23, 3 April 2019 (UTC)

GA Review

This review is transcluded from Talk:Cop-win graph/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Eviolite (talk · contribs) 05:11, 23 April 2022 (UTC)

I will review this nomination within the next ~2 days; please ping me if I do not get back by then. eviolite (talk) 05:11, 23 April 2022 (UTC)

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

1. It is reasonably well written.

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

   Prose comments below

2. It is factually accurate and verifiable.

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

   Passes spotchecks

3. It is broad in its coverage.

   a (major aspects): b (focused):

   Doesn't miss anything obvious

4. It follows the neutral point of view policy.

   Fair representation without bias:

   Tone is good

5. It is stable.

   No edit wars, etc.:

   No edits by other people in years (only bots)

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

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

   All free with clear pertinence to the article and captions

7. Overall:

   Pass/Fail:

Lead

• Citation should be removed per MOS:LEADCITE and that the information is present in the Definitions section

Definitions

• Very small issue, but be consistent with using hyphen vs en dash (there's an en dash in "pursuit–evasion" in the body and lead, but it's hyphenated in the heading)
  • Ok, done. I couldn't immediately change the hyphen in the category name but I listed it for speedy renaming. This was an annoying one: my browser edit window doesn't give me any way to find which ones are en-dashes and which ones are hyphens. I had to go into an external editor to find them. —David Eppstein (talk) 06:06, 27 April 2022 (UTC)
    • Update: the speedy category rename worked. —David Eppstein (talk) 07:38, 30 April 2022 (UTC)
• It may be helpful to link Pursuit–evasion again in the body (and perhaps graph (discrete mathematics))
  • Ok, done. —David Eppstein (talk) 06:06, 27 April 2022 (UTC)
• It should be noted that the cop gets to move first (at least in the specific case examined by the source)
  • Ok, done. —David Eppstein (talk) 06:06, 27 April 2022 (UTC)
• I'm not sure if "no matter where the two players start" is strictly true; the paper just says it's when the cop has a winning strategy, and the strategy also presumably includes the choice of the starting position for the cop.
  • Fair enough. One can prove that the starting position doesn't affect this: if the graph is disconnected it cannot be cop-win in either sense, and if it is connected then the cop can start anywhere and then walk to a preferred starting position before commencing the rest of a winning strategy. But if we don't have a source saying that, I guess it would be original research. —David Eppstein (talk) 06:10, 27 April 2022 (UTC)
• It might be clearer to remove the parenthetical about robber-win graphs and instead adding a sentence explaining that robber-win graphs are those graphs that are not cop-win.
  • Ok, done. —David Eppstein (talk) 06:10, 27 April 2022 (UTC)
• Italicize dismantlable for consistency
  • Ok, done. —David Eppstein (talk) 06:10, 27 April 2022 (UTC)
• n is not defined before it's first mentioned (maybe "For a larger graph with n vertices")
  • I defined it closer to where it is used. —David Eppstein (talk) 06:13, 27 April 2022 (UTC)
• Comma after "carefully"
  • Ok, done. —David Eppstein (talk) 06:13, 27 April 2022 (UTC)
• Change the one use of <math>v</math> to use {{mvar}}
  • Ok, done. Generally I prefer math to mvar formatting, but it's good to be consistent, especially since the math v looks more like a u. —David Eppstein (talk) 06:13, 27 April 2022 (UTC)

Closure properties

• Link Closure (mathematics) (or otherwise just explain it)
  • Linked and explained. —David Eppstein (talk) 02:03, 29 April 2022 (UTC)
• I wonder if the explanation for the strategy can be made more clear, but I tried for a bit and it was still worded awkwardly. Maybe just leaving it at that is fine, given the example.
  • I tried rewriting it. —David Eppstein (talk) 02:03, 29 April 2022 (UTC)
• The PDF in Ref 11 is a dead link for me, so should be archived
  • The correct fix is not to treat it as dead, but to find the replacement hostname for the server. I replaced emis.ams.org with emis.de and now it works again. —David Eppstein (talk) 02:03, 29 April 2022 (UTC)
• "factor strategy" may not be immediately obvious, and given the context just "strategy" should be fine
  • Changed to "product-based strategy". It wouldn't be correct to say simply "the strategy" because there is more than one winning strategy. —David Eppstein (talk) 05:35, 29 April 2022 (UTC)
• Delink the second use of "induced subgraph"
  • Done, good catch. —David Eppstein (talk) 05:35, 29 April 2022 (UTC)
• "each two adjacent vertices" might be more natural as "every pair of adjacent vertices"
  • Ok, done. —David Eppstein (talk) 07:33, 29 April 2022 (UTC)
• Not sure if "as they argue," is necessary here since it's not a particularly contentious claim, but if it's kept I suggest changing it to "they argue that"
  • Removed. —David Eppstein (talk) 07:33, 29 April 2022 (UTC)
• I think using "For," in this way may be slightly awkward; maybe "This is because" or similar
  • Ok, done. —David Eppstein (talk) 07:33, 29 April 2022 (UTC)

Recognition algorithms

• Link degree (graph theory) as the term may not be familiar to readers
  • Ok, done. —David Eppstein (talk) 07:44, 30 April 2022 (UTC)
• The whole decrementing thing seems equivalent to just re-calculating the number of triangles for each edge, so maybe remove "repeatedly" and that clause, instead saying "and repeat these steps for the now-smaller graph". I don't know if that constitutes OR, though, since it seems the original paper also used the "updating" wording, so it's your call.
  • Um, no, this would be a problem. Finding and counting all triangles is slow, so you don't want to do that over and over again every time you remove one vertex. Counting them once and updating the counts avoids this slow recalculation. —David Eppstein (talk) 07:44, 30 April 2022 (UTC)
• It's not immediately clear where the alternative time complexity comes from, perhaps because it's not made explicit where the original n^3/log n comes from either (without digging through the source), so I'd treat this as OR and fall back on the time from the paper, perhaps with an in-text attribution though.
  • The analysis parts of the bullet points in this section were more or less my notes to myself at trying to figure out where the n^3/log n comes from and concluding that the analysis was sloppy and it's really mn/log n. But I suppose without a source we can't actually say that; it's not simple enough for WP:CALC. So I jjust removed it and quoted the n^3/log n. It makes less difference than you might think, because this algorithm is only an improvement on the O(dm) one when mn is within a logarithmic factor of n^3 (another thing we probably shouldn't say without sourcing). —David Eppstein (talk) 08:05, 1 May 2022 (UTC)
• In the "In infinite graphs" section, it's not really clear to me what differentiates "algorithmically" from having unbounded computing power; is it that any finite algorithm can't beat the robber? A clarification might be warranted though I might just be missing something.
  • This is a basic point about computation rather than anything specific to this article's topic. Computers, even theoretical ones, are (like people) not omniscient. There are plenty of things we might want them to compute but we can prove are uncomputable. There is an answer but no algorithm can find one. Testing whether a given computer program contains an infinite loop, for instance. You can program up heuristics that sometimes find infinite loops, but there will always be an input that they fail on (by giving the wrong answer or getting into an infinite loop themselves). That background was the point of linking computability at the start of this section. Anyway, I changed "with unbounded computing power" to "omniscient" in hope that this will be less confusing. —David Eppstein (talk) 07:30, 1 May 2022 (UTC)

Related families of graphs

• "later neighbors"?
  • Neighbors of the vertex that are later in the ordering. —David Eppstein (talk) 07:41, 1 May 2022 (UTC)
• Link diameter (graph theory)
  • Ok, done. —David Eppstein (talk) 07:41, 1 May 2022 (UTC)

@David Eppstein: Placing on hold for now. eviolite (talk) 03:04, 25 April 2022 (UTC)

Thanks! My time is tight for the next few days but I'll see what I can do. —David Eppstein (talk) 05:31, 25 April 2022 (UTC)

@Eviolite: Ok, I think I've responded to everything — please take another look. —David Eppstein (talk) 16:42, 1 May 2022 (UTC)

Thank you for the response. I see you have also done some other copy-edits to the Recognition algorithms section, which I appreciate. Happy to promote now; great work. eviolite (talk) 05:19, 2 May 2022 (UTC)