Talk:Matroid parity problem

Matroid parity problem has been listed as one of the Mathematics good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it. Review: August 15, 2025. (Reviewed version).

This article is rated GA-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. Mid This article has been rated as Mid-priority on the project's priority scale. Computer science This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. ??? This article has not yet received a rating on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

GA review

Latest comment: 12 days ago49 comments2 people in discussion

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

GA toolbox
AI detector Authorship Citation bot Copyvio detector External links
Reviewing
Templates Criteria Instructions

This review is transcluded from Talk:Matroid parity problem/GA1. The edit link for this section can be used to add comments to the review.

Nominator: David Eppstein (talk · contribs) 07:53, 14 January 2025 (UTC)Reply

Reviewer: Gramix13 (talk · contribs) 04:33, 30 July 2025 (UTC)Reply

Hello! I want to preface that this will be my first review of a Good Article. If you prefer to have a more experienced GA reviewer look at this article, I won't mind "failing" this article to allow for a different reviewer, or asking for a second opinion. My goal will be to finish this review within a week, but if I need more time I will communicate that here. Gramix13 (talk) 04:33, 30 July 2025 (UTC)Reply

Summary of review

Rate	Attribute	Review Comment
1. Well-written:
	1a. the prose is clear, concise, and understandable to an appropriately broad audience; spelling and grammar are correct.
	1b. it complies with the Manual of Style guidelines for lead sections, layout, words to watch, fiction, and list incorporation.
2. Verifiable with no original research, as shown by a source spot-check:
	2a. it contains a list of all references (sources of information), presented in accordance with the layout style guideline.
	2b. reliable sources are cited inline. All content that could reasonably be challenged, except for plot summaries and that which summarizes cited content elsewhere in the article, must be cited no later than the end of the paragraph (or line if the content is not in prose).	There's at least one citation per paragraph, which I find sufficent for this criteria.
	2c. it contains no original research.
	2d. it contains no copyright violations or plagiarism.
3. Broad in its coverage:
	3a. it addresses the main aspects of the topic.
	3b. it stays focused on the topic without going into unnecessary detail (see summary style).
	4. Neutral: it represents viewpoints fairly and without editorial bias, giving due weight to each.
	5. Stable: it does not change significantly from day to day because of an ongoing edit war or content dispute.	According to Xtools, this article has only 3 editors (excluding bots), one of which being David Eppstein the nominator, and the other two having made only single edits each in 2017. In short, this article is (vacuously) stable from the absence of any other major contributor other than Eppstein.
6. Illustrated, if possible, by media such as images, video, or audio:
	6a. media are tagged with their copyright statuses, and valid non-free use rationales are provided for non-free content.	Both images are uploaded by the nominator with CC0 1.0 Universal license.
	6b. media are relevant to the topic, and have suitable captions.
	7. Overall assessment.	Congradulations on the GA pass!

Discussion

Here's an outline of how I plan to handle the review. I'll first do an initial read of the article to check criteria 1a (ensuring the prose is understandable), 2b (ensuring citations are included for anything that could be challenged), 4 (which as a non-BLP mathematics article, I doubt this would fail), and 6 (since I want to judge the illustrations as I understand the article to see if I find them useful and relevant). This would be followed by a second read for criteria 1b as I check the MOS against the article. I'll then be performing a spot check of the articles (I'll try to include a good number of the open access sources in that spot check) to ensure the article meets criteria 2 in being verifiable, while also checking if it satisfies criteria 3 in being broad. Once that is completed, I'll be able to give my overall assessment if there are no pending changes that should be made. I have already rated criteria 5 as a pass, with my rationale written above. Gramix13 (talk) 04:33, 30 July 2025 (UTC)Reply

Prose comments

Below are my (threaded) comments on the prose as I'm doing a first pass. Feel free to comment on each individual one if you prefer that over making one message addressing each of these points. Gramix13 (talk) 04:42, 30 July 2025 (UTC)Reply

In terms of the lead, I noticed that the main subject of this problem, Matroids, aren't defined (even loosely) in the leading paragraphs. The lead currently is on the shorter side in my view, so I don't think a brief explanation (even if not precise) on matroids would cause issues in terms of length. There are other terms here that aren't defined, but as the lead is supposed to be a summary, I don't really think those other terms provide an issue in the goal of summarizing. I mainly bring up Matroid since, without an idea as to what it is, its difficult to understand the question posed by the problem.

I also want to bring up early some things I've noticed per MOS:LEADREL. I noticed that matroid oracle isn't mentioned outside of the lead, which might be significant enough to warrant a mention in the body. This goes for the compactly-represented matroids as well, mentioned in the same sentence as the oracle. Also not mentioned outside the lead is Lawler's formulation of the problem (his name is only written in the article in the lead and his citation), so a short mention of this in the Formulation section would suffice. Gramix13 (talk) 05:03, 30 July 2025 (UTC)Reply

After reading MOS:INTRO, I now think the article should make a better effort to briefly explain some of the terminologies used in the lead section. To quote the guideline, Make the lead section accessible to as broad an audience as possible. Where possible, avoid difficult-to-understand terminology, symbols, mathematical equations and formulas. Where uncommon terms are essential, they should be placed in context, linked, and briefly defined. The subject should be placed in a context familiar to a normal reader... Readers should not be dropped into the middle of the subject from the first word; they should be eased into it. If you are to rewrite the lead in a way that concisely defines the terms used in the lead, that would greatly help the article meet criteria 1 of being a Good Article. Gramix13 (talk) 01:04, 2 August 2025 (UTC)Reply

The image in the lead does illustrate the problem, but I do think the caption could elaborate on what a graphic matroid is so the reader can recognize the matroid evident in the problem (which I presume is represented as the colored edges of this graph). I think a small elaboration of a forest being a collection of trees would be helpful, especially since the image only shows a tree as the solution, when the reader should keep in mind we allow for multiple trees in the solution to the problem if necessary. Gramix13 (talk) 05:19, 30 July 2025 (UTC)Reply

A matroid can be defined from a finite set of elements and from a notion of what it means for subsets of elements to be independent... I think this particular wording is fine as an introductory definition of a matroid, but I do think a more formal definition of a matroid should be included, in particular, what is the finite set we want to consider the matroid over, and what do we label as the set of independent sets. The main article has a good formulation of this under the independent sets definition that could be borrowed or modeled after. Gramix13 (talk) 05:28, 30 July 2025 (UTC)Reply

Another seemingly more general variation, in which the allowable pairs form a graph rather than having only one pair per element, is equivalent: an element appearing in more than one pair could be replaced by multiple copies of the element, one per pair. This wording is admittedly confusing to me. What exactly do we mean by replacing an element with multiple copies? How exactly is this graph formed in the generalization, and could it be more precise as to what makes up this graph? Gramix13 (talk) 05:34, 30 July 2025 (UTC)Reply

I think the terms "minimum-weight solution" and "maximum-weight paired independent set" need further clarification, its unclear as to what is being weighted in these solutions and why we would want to find them. Gramix13 (talk) 23:32, 30 July 2025 (UTC)Reply

I think "indeterminate" should be replaced with "variable" since the later term is what's primarily used to describe each ${\displaystyle t_{i}}$ , and the former term threw me off when I was trying to understand what it was referring to before I realized that the variables are in correspondence to each pair. Making that correspondence more clear would also help alleviate that issue I experienced. Gramix13 (talk) 23:45, 30 July 2025 (UTC)Reply

I would appreciate adding an example demonstrating the use of an algorithm to solve the matroid parity problem. It doesn't need to be the state-of-the-art algorithm, just something that's relatively easy to explain to the reader so they have an idea of how it would be solved in practice. Gramix13 (talk) 23:52, 30 July 2025 (UTC)Reply

The same problem can also be described as one of finding the largest Berge-acyclic sub-hypergraph of a 3-uniform hypergraph. Lots of jargon being used here that I feel a reader might not immediately know. Taking some time to define what Berge-acyclic and 3-uniform mean would be helpful for them, and possibly also defining the term hypergraph if it feels necessary. Gramix13 (talk) 03:13, 31 July 2025 (UTC)Reply

I feel like there needs to be more background information explaining what rigid bars are in the combinatorial rigidity, I find that the section makes no effort to explain what rigid bars are, and it makes it difficult to understand what some of the vague terms used in the paragraph refer to. Gramix13 (talk) 03:26, 31 July 2025 (UTC)Reply

The optimal embedding can then be obtained by pairing edges within each component and embedding each pair in such a way that it increases the genus by one. I feel like this could be elaborated on how this is creating a cellular embedding. That term should also probably be explained (if briefly) as well. Gramix13 (talk) 03:34, 31 July 2025 (UTC)Reply

To formulate the problem of finding a Xuong tree as a matroid parity problem, first subdivide each edge ${\displaystyle e}$  of the given graph into a path, with the length of the path equal to the number of other edges incident to ${\displaystyle e}$ . I'm struggling to understand how this is formed, could this be clarified to explain the path in more detail, as well as how the subdivision is occurring? Gramix13 (talk) 03:43, 31 July 2025 (UTC)Reply

In cubic graphs, this problem is closely related to connected domination. Both terms should be defined.

There is a linear equation relating the number of vertices, cyclomatic number, number of connected components, size of a minimum connected dominating set, and size of a minimum feedback vertex set. Sounds significant, is there a reasonable way to include this linear equation onto the article?

The same expansion of each vertex and each edge into a two-edge path, used for connected dominating sets, produces an expanded graph with paired edges. I feel like this would benefit from explaining what we mean by a graph expansion, as well as dominating sets. Gramix13 (talk) 03:54, 31 July 2025 (UTC)Reply

The paving matroid should probably be defined when explaining hardness, its a new type of matroid to the reader. Maybe also define what a randomly-permuted graph is (what is being permuted to justify its name?). Gramix13 (talk) 03:59, 31 July 2025 (UTC)Reply

That concludes my first read of the article. Overall, I mainly want to point out ways the article could better explain the subject and results, especially any terms that might be unfamiliar. My perspective has been of someone who is unfamiliar with matroids (which I admit that I was before reading this article). I also think some advanced terminology relating to graph theory could be explained more clearly, since I also wouldn't expect a reader to fully grasp some of those concepts. I'll wait to hear from you addressing these points before I considering passing criteria 1a.

As for the illustrations, I will wait to see if the caption on the lead image can be improved as I suggested above before passing criteria 6b. I do think additional illustrations might be helpful in the applications section so the reader can see visualization of how we are creating these matroids to solve those problems, but I think such a request would go beyond a GA review, so I won't hold the review against this suggestion. Gramix13 (talk) 04:09, 31 July 2025 (UTC)Reply

Thanks for the in-depth review! It looks like responding properly will take a chunk of time that I might not have until Sunday or Monday (I am at a conference, giving a talk tomorrow, in transit all day Saturday, and late for reviewing a paper that I promised to get done by Saturday), so please don't be surprised if I don't do much about it until then. —David Eppstein (talk) 04:00, 1 August 2025 (UTC)Reply

That sounds good to me! Sunday should probably give me enough time to review the MOS criteria for this article, as well as time to look at some of the sources for the spot check. If you see any further comments from me, don't worry about them until Sunday/Monday, when you do have time for the review. I hope your talk goes well by the way! Gramix13 (talk) 04:12, 1 August 2025 (UTC)Reply

MOS comments

Here are my comments relating to the MOS criteria for this article. Gramix13 (talk) 23:54, 1 August 2025 (UTC)Reply

This might not be necessary, but I noticed this article is lacking a See Also section, so I think some though should be put into adding one for this article. Maybe it could lead to other articles related to matroids perhaps, or maybe it can lead to articles related to the applications of the problem. I won't make this a requirement since MOS doesn't do so, but its worth considering. Gramix13 (talk) 23:58, 1 August 2025 (UTC)Reply

I'm not sure if I agree with the use of the {{glossary}} template in the applications section, since to me it reads less like definitions of the problems and more like detailed explanations of how those problems can be transformed into matroid parity problems. Each of them is roughly a paragraph. If we can make those subsections of the Applications section instead of glossary terms, I think it would also improve the navigability of the article as the reader to jump to a specific application they might be interested in. This is the first time I've encountered this template, so if there is precedent for using the template in this fashion, please let me know and I can reconsider this suggestion if it is reasonable to use it in this context. Gramix13 (talk) 00:13, 2 August 2025 (UTC)Reply

It might also be worth consider the use of {{See also}} in these new subsections as an easy way for the reader to jump to the main article of that application. Yes, most of the applications have the main article linked at the start, but since there's more to these subjects than what can be said in this article, I think being helpful to the reader by pointing them to their respective articles does more good than the harm of redundancy, but feel free to challenge me on this. Gramix13 (talk) 00:22, 2 August 2025 (UTC)Reply

Putting a {{Further}} template in the Formulation section towards Matroids could help the reader find more information about matroids if they so wish, or if they need to see more about matroids before they feel reader to understand the parity problem. Gramix13 (talk) 00:25, 2 August 2025 (UTC)Reply

I think having the lead image with upright=1.35 might be too large per WP:IMGSIZE since it just displays a graph, which I would argue does not have fine detail that would justify the large size. Per MOS:LAYIM, this size is at the limit of what's acceptable for a lead image size, so while the article might satisfy the size limit, it might be safe to make it smaller even if it already meets the MOS. Gramix13 (talk) 00:43, 2 August 2025 (UTC)Reply

Overall, I think MOS:LAYOUT is met for this article, but as I elaborated above, there might be some room for improvement in this regard. Gramix13 (talk) 00:45, 2 August 2025 (UTC)Reply

Per MOS:LEADCITE, the citations used in the last paragraph in the lead are unneeded if that information is also stated in the Applications section. The citation in the first sentence of the lead also could be safely removed since the definition of the problem is explained in the Formulation section. Now the same guideline doesn't necessarily prohibit those citations, so leaving the citations as is would be fine. Gramix13 (talk) 00:57, 2 August 2025 (UTC)Reply

There are no concerns I have about MOS:LEAD other than what I have mentioned above, mainly in regards to making some of the terminology accessible. Gramix13 (talk) 19:59, 3 August 2025 (UTC)Reply

the problem of finding triangular cactus graphs forms the basis for the best known approximation algorithm to the problem of finding the largest planar subgraph of a given graph [emphasis added] per MOS:PUFFERY, this sentence should give facts to justify why this is currently the best known algorithm, and more specifically what metrics are being used to judge this as the best algorithm. I would imagine its due to time complexity (I am now curious what that would be in big O), but that should be stated explicitly for the reader to remove all doubt. Gramix13 (talk) 20:08, 3 August 2025 (UTC)Reply

Aside from the above, I think MOS:WTW is met for this article. With that, I think as long as the lead is also able to be clarified, criteria 1 will be achieved. I don't have any other notes to add relating to the MOS. Gramix13 (talk) 20:26, 3 August 2025 (UTC)Reply

Some updates for today and answers to some of your initial points:

Re definition of matroids in lead, I copied the gloss of matroids from the lead of matroid into this lead. I also copied the claims of hardness from the lead into the algorithms section where they were already mentioned more briefly, and added there a gloss of the oracle model. Additionally, I expanded on the lead statement about being formulated by Lawler in the formulation section. As for "rewrite the lead in a way that concisely defines the terms used in the lead": I do not think the lead is the place for precise and detailed definitions. A brief gloss to give the sense of the words is appropriate. A definition is not. That would go against WP:TECHNICAL, by overwhelming the lead with difficult-to-read detail and formulas. If a reader is not familiar with what "polynomial time" or "planar graph" means, for instance, they are likely not ready to get much out of the rest of the article, and so glossing that level of term is just going to bore and annoy the actual readers of the article. Rewrote the lead image caption to make it more clear that it already defined the graphic matroid. And again, if a reader is unfamiliar with the idea that a forest = a set of trees, then this may not be the article for them.

Re "I do think a more formal definition of a matroid should be included" in the Formulation section: This is a completely formal and complete definition. In mathematics, one does not need to know that we are talking about sets of numbers or sets of edges or sets of fruits, in order to have a definition that is valid for any finite set. The nature of the elements is completely irrelevant.

Expanded confusing wording re the equivalence between the versions requiring only one pairing per element or allowing multiple pairs per element. Added a clarification that the weighted problems are instances where each element has a real number weight. Re ' "indeterminate" should be replaced with "variable" ': done.

More to come later. —David Eppstein (talk) 00:58, 5 August 2025 (UTC)Reply

Ok, I agree with your suggestion that those terms should just be glossed briefly in the lead rather than defined just to make sure the reader has an idea of what it means without being overwhelmed (I should also start adding "gloss" to my vocabulary here on Wikipedia to better communicate a brief mention of a term rather than a full fledged definition that could have been implied by some of my use of the word "definition"). And I certainly would not expect explaining "polynomial time", "planar graph" or even "forest" (although I admit I had to look that last one up since I never saw it before in the context of graph theory, but its definition is self evident after the fact), since I find them to be basic enough relative to what this article cover as you pointed out, so its completely fair not to touch on those terms here (and I probably should have excluded them from consideration for glossing over).

I was expecting a definition of matroid to involve sets, specifically labeling the ground and empty sets of the matroid, which is what I meant by "formal". Looking back at the sentence now, I think my previous request may have been too much as what's here is looks sufficient, so I think it is fine to leave it as is since it gets the general idea across for what a matroid is.

I'm agreeing with all the edits being done so far, looking forward to seeing the remainder of your responses. Gramix13 (talk) 01:42, 5 August 2025 (UTC)Reply

Spot check

This section will be for checking some of the citations and refrences for the spot check. Just to avoid spamming this section of every source I'm check, I will only mention issues I might find with citations. If you want more details about the references I am checking, feel free to ask and I will break that down. Gramix13 (talk) 22:54, 5 August 2025 (UTC)Reply

I see that in Cheung, Ho Yee et. al. that they require the empty set to be independent. Obviously this holds if the family of independent sets is non-empty (i.e. there is at least one independent set) due to the fact that it is closed under subsets, but it is still necessary to include the empty set as independent in order to eliminate the example of a "matroid" with no independent sets. If other sources include this pathological example of a matroid, I would be fine with a citation to confirm that . Gramix13 (talk) 23:05, 5 August 2025 (UTC)Reply

Cheung, Ho Yee et al. doesn't seem to call ${\displaystyle r}$  the rank of the linear matroid for the runtime ${\displaystyle O(nr^{\omega -1})}$ , rather they call it the number of rows of the matrix involved in the linear matroid, while calling ${\displaystyle n}$  (labeled as ${\displaystyle m}$  in the paper) the number of columns (or more accurately the pairs of columns). I think describing ${\displaystyle r}$  that way, rather than the rank, would be closer to how its described in the paper and might be more immediately intuitive rather than as the rank. Gramix13 (talk) 01:38, 6 August 2025 (UTC)Reply

I can't seem to find a mention of the fact that For simple graphs, ${\displaystyle m}$  is ${\displaystyle O(n^{2})}$  in Cheung, Ho Yee et al. as it doesn't directly mention simple graphs, it only mentions multigraphs in the colorful spanning tree (which goes unmentioned in that part, but I'm unsure if its even relevant to this article), and I can't seem to relocate where this ${\displaystyle O(n^{2})}$ -time is mentioned at the article.

As a general note, I do find it a bit difficult to spot check Cheung, Ho Yee et al. since no page numbers are associated with the citations for that source. If you wouldn't mind giving page number (at the very least in this review page) for each citation that would be helpful for me to confirm those citations really do verify what's being said in the article. For the most part I was able to find the material I needed that supports the article, I think the citation above and the one for the paragraph mentioning the Schwartz–Zippel lemma are the two I feel I need the pages the most on. Gramix13 (talk) 04:43, 6 August 2025 (UTC)Reply

Lawler seems to use the term "nonbipartite matching problem" to describe the graph matching problem, my interpretation is that this might be an older term to describe the same problem, so perhaps a brief mention of that name might be somewhat useful, but I'm not sure if its necessary. I figured I mention it here in case its actually a different problem, but I doubt that. Gramix13 (talk) 04:47, 6 August 2025 (UTC)Reply

I'm not quite sure if I see where the run time on the graph matching problem comes from in Lawler, although this might just be an application of the previously established run time in the linear matroid parity problem. Gramix13 (talk) 05:01, 6 August 2025 (UTC)Reply

Today's update, still working through your comments in sequential order:

Re the request for a worked example of an algorithm solving this problem on a specific matroid: small examples can be ok, but large worked examples can be problematic with respect to WP:NOTTEXTBOOK. In this case, the only algorithm described explicitly is the matrix rank algorithm; turning the example problem in the lead figure into an explicit matrix for the matrix rank based algorithm would produce a matrix M of size 6 x 10, expanded by the algorithm into a larger block matrix of size 16 x 16. I'm not entirely convinced that displaying this big matrix and saying that it has a certain rank would be illuminating, or would be an easy enough calculation to be able to include this example without sources under WP:CALC. And then instead of displaying just this matrix, following the full steps of the greedy algorithm while it zeros out some of the variables and maintains additional data to check the rank as it does, would definitely be too much for WP:NOTTEXTBOOK.

Expanded the Berge cycle paragraph with some more brief definitions.

Re "explaining what rigid bars are in the combinatorial rigidity": You know, a solid thing in the shape of a bar (longer than it is thick) that is rigid meaning that it cannot bend or stretch or compress, like you would make out of metal or wood. Like a two-by-four or a crowbar or a chopstick or a shishkebab skewer. The words "rigid" and "bar" are used here pretty much in their colloquial meanings in English, not with some strange and different technical meaning. You could model it mathematically as a line segment, but I think that is too abstract to convey the meaning effectively.

Expanded the Xuong tree paragraph with an explanation of cellular embeddings and of the edge-pair insertion process. —David Eppstein (talk) 01:39, 7 August 2025 (UTC)Reply

Your description of the algorithm on matrices definitely makes it sound too tedious to apply and thereby undue, so I'll retract that request now seeing how it would be infeasible for this article without violating policy.

I should have mentioned that I understand the colloquial meaning of a rigid bar, what I meant to have asked was how exactly that kind of theory is modeled in mathematics which was the main intent of my message, so apologies for failing to clarify that in my question. I was expecting some kind of elaboration of the math in Geometric rigidity for rigorously defining rigidity, but upon reflecting on what's there, that might be a bit undue. If we are relying here on colloquial definitions of rigidity for that paragraph (which I find acceptable), then my only complaint is a lack of definition on what an infinitesimally rigid set of joints is, since that isn't a term I think is colloquially well-known (and I admit I was not aware of what it means prior to this article). If we are using it to define a pinning set, I do think defining what infinitesimally rigid means would be helpful for that so a reader doesn't get stuck on trying to figure out what it even means for joint to be infinitesimal rigid and thereby doesn't reach understandability of a pinning set.

The additions to the Berge cycle and Xuong tree paragraphs look great, I appreciate your work to expand on those two. Gramix13 (talk) 02:07, 7 August 2025 (UTC)Reply

After reading Lovász, I think I am convinced that this article passes a spot check. There are only a couple concerns with some of the wording in the sources not entirely matching the material in the article, but I don't really think these situations I found impact the verification of the article. None of what I brought up during the spot check really compromises on the validity of the content within the article, which is why I feel its safe to pass the spot check. I'll go ahead and mark criteria 2 and 3 as a pass.

Once the remainder of my comments have been addressed, I think I will pass the article, but for now I will mark this review as on hold to give you some time to look over what I've said in the review. Gramix13 (talk) 22:39, 8 August 2025 (UTC)Reply

Today's comments (I think covering everything before the spot check):

Re the definition of bars in combinatorial rigidity: I added an illustration which I hope helps clarify the meaning.

Re "both terms [cubic graphs and connected domination] should be defined": this section had an error (now fixed) where it talked about dominating sets when it should have been talking about vertex covers. (They are very similar concepts but not the same.) Anyway, both connected vertex covers and cubic graphs are now defined, in the subsection about connected vertex covers. I think the sentence you quoted was from the next subsection, about feedback vertex sets, where readers can be assumed to have read the preceding subsection.

Linear equation now included, in the simpler case where there is only one connected component. I also swapped out the 1986 source for a 1988 source by the same author; I think the 1988 source is the journal version of the 1986 conference paper, so it's the more definitive version, but also I was able to find it online when I searched for what it said about the linear equation, and was unable to find the 1986 version, so the 1988 one is better for verifiability.

Re "I feel like this would benefit from explaining what we mean by a graph expansion, as well as dominating sets.": the expansion of vertices and edges into paths is now explained a bit more, and a new illustration of the expansion added. Again, vertex covers have already been defined; we don't need to keep redefining them every time we see them.

Re "The paving matroid should probably be defined": I moved the statement that it's a paving matroid after the definition of the specific matroid, because it's more an observation than part of the definition, with a gloss of what it means to be a paving matroid.

Re a see also section: I tend to think of that as a waiting list for topics that are relevant and could be discussed within the article itself but are not yet. So if it is empty, it merely means that the relevant discussion has already been included.

Re the glossary format: I changed it to use subsections instead, with see-also links.

Lead image size reduced. Redundant lead citations removed. "Best known approximation algorithm" changed to "largest known approximation ratio" for greater specificity, since obviously "best" was misinterpretable. —David Eppstein (talk) 23:29, 9 August 2025 (UTC)Reply

I think the GIF for the bars helps illustrate them for this section, I think it'll suffice for a more detailed definition of rigidity that might be too much for the article at this point. I do want to mention that the GIF is 6.8 seconds and MOS:ANIMATION recommends that GIFs go under 5 seconds in length or have control functions. I know this same GIF is used in The Peaucellier–Lipkin linkage article, and this MOS guideline isn't required for GA, so I wouldn't worry about addressing it right away for this article, but it is something to consider. I could also see one arguing that 6.8 seconds is pretty close to 5 seconds to not make this a notable issue.

All of the rest of the changes look great! Only thing I noticed that wasn't addressed was adding a {{Further}} template in the Formulation section pointing to Matroid, so I went to boldly add it myself, feel free to revert it if you disagree. I'll mark the remaining criteria as passed, and I will wait for a response on the spot check section before passing this GA review just in case you raise anything I might need to respond to. Gramix13 (talk) 00:24, 10 August 2025 (UTC)Reply

Sorry for being so slow to get back to this; I've been traveling again (and still am for a couple more days).

I rewrote the gloss of matroids to require the family of independent sets to be nonempty.

Re whether r should be the number of rows of the matrix (Cheung et al) or the rank of the matroid (Iwata&Kobayashi): I am following the notation and formulation of Iwata&Kobayashi. It is technically slightly stronger since the rank could be less than the number of rows and in that case this interpretation gives a lower time bound. But I think this is not really a significant difference since the matrix could be rewritten with a different basis to have #rows = rank. Iwata&Kobayashi cite Cheung et al as giving the time bounds in the form given here.

Re: "For simple graphs, m is O(n^2)": This is not a claim about matroid parity. It is the basic and obvious fact that (n choose 2) (the maximum number of edges in a simple graph) is O(n^2). I think it falls under WP:CALC, although probably many unrelated algorithms textbooks mention somewhere that simple graphs always have O(n^2) edges. The part about multigraphs sometimes having larger numbers of edges is in Cheung et al, though (on page A:5 in the "colorful spanning tree" paragraph).

Re spot checking page numbers: It is not common to provide page numbers for journal articles. The Wikipedia citation format does not provide a mechanism to do so: the page parameter of a citation should be the full page range of the article. (Do not talk to me about {{rp}}; it is an abomination and I will not use it.) This reference is only 26 pages long. But text search is your friend: it finds the Schwarz-Zippel lemma on page A:6, for instance.

Re "nonbipartite matching": in the graph matching literature, bipartite graphs are an important and often much easier special case. Here, "nonbipartite" just means that we are not in that special case. Since this article doesn't anywhere mention the special case, it is an unnecessary technicality to explain that case and then say that we're not in it. The statement that matching is polynomial is earlier in the same book; the implication (that matroid parity for partition matroids is polynomial) is obvious from this chapter's observation that matching and matroid parity for partition matroids are merely different ways of expressing the same problems. —David Eppstein (talk) 03:20, 15 August 2025 (UTC)Reply

Good to hear from you Eppstein, and all good on the replies, I was actually planning to reach out at some point tomorrow about the review, and I can understand how travels can make it difficult to communicate. Hope those travels are going well.

Do not talk to me about {{rp}}; it is an abomination and I will not use it. Oh god, just a look at the source and result of the template was enough for me to see how awful this template is, I have never seen this template before and I too am convinced never to use this ever. I fully retract my page number request then. I did do word searches to try to find the information, but I think searching for different terms probably lead me to different spots of the article which is what caused me to get confused, so I'll need to read the source more carefully next time that occurs.

With that, I believe that should cover all my main points I raised for the article, and I don't see a reason to keep this review going on for longer. I shall give this a pass as it meets all of the GA criteria from what I have seen. Hopefully your travels don't interfere with getting this article through DYK if you plan to do so. If you have anything else you want me to check in the article, or have any questions about the review, feel free to reach out. Gramix13 (talk) 04:02, 15 August 2025 (UTC)Reply

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.