Finding Dominating Induced Matchings in $P_9$-Free Graphs in Polynomial Time

Andreas Brandst\"adt; Raffaele Mosca

REVIEW 3 major objections 6 minor 14 references

Finding Dominating Induced Matchings in $P_9$-Free Graphs in Polynomial Time

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that for every graph with no induced path on nine vertices, the existence of a dominating induced matching can be decided in polynomial time.

desk verdict A substantial P9 extension with a real gap: Lemma 3's "Case 2.2 appears only once" assertion is load-bearing and unproved, and Observation 4 is false as stated. read the letter →

arxiv 1908.00978 v3 pith:SRYGTQ5T submitted 2019-08-02 cs.DM math.CO

Andreas Brandstädt , Raffaele Mosca This is my paper · ORCID

classification cs.DMmath.CO MSC 05C8505C6968R10

keywords dominatinginducedmatchingefficientedgedominationP9-freegraphspolynomial-timealgorithmpathdistancelayersblack-whitecoloringgraphalgorithms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper extends the known polynomial-time boundary for Dominating Induced Matching (DIM) from P8-free graphs to P9-free graphs: in every connected graph that contains no induced path on nine vertices, one can decide in polynomial time whether some set of pairwise disjoint edges dominates every edge exactly once. The algorithm fixes a central vertex, tests each candidate matching edge incident to it by computing distance layers and forcing black-white colorings, and when no edge works, removes the central vertex as white and recurses on the remaining components. The result matters because DIM is NP-complete on general graphs, so each extension to a broader hereditary class shows where the hardness starts. If the proof is right, it also gives a constructive polynomial-time decision procedure, not merely an existence statement.

What carries the argument

The central machinery is the distance-level decomposition of a candidate d.i.m. edge xy, with layers $N_i = \{z : \mathrm{dist}(z, xy) = i\}$. In a P9-free graph, $N_5$ is empty, so only four layers can contain anything. The argument uses a black-white feasible coloring model: black vertices are the endpoints of the matching edges, white vertices are the independent remainder, and the rules force colors layer by layer (white neighbors force black, black vertices force white neighbors, each $T_i$ must contain exactly one black vertex). The key structural lemmas bound the number of feasible colorings per component, using forbidden objects such as P5s with special endpoints, C6s and C7s in $G[S_2 \cup N_3]$, and C9s involving N4.

What would settle it

Exhibit a connected P9-free graph with a central vertex v and an edge uv such that (i) uv lies in no induced P3, (ii) every d.i.m. contains uv, and (iii) no other edge incident to v can belong to a d.i.m.; then Step (B) finds no candidate edge and the algorithm terminates with the wrong answer. A concrete candidate is a triangle (u,v,w) with two length-2 tails attached at w, which has a unique d.i.m. using uv and appears to satisfy the failure conditions.

Watch

Extended reading notes

Core claim

Theorem 3 is the central claim: DIM is solvable in polynomial time for P9-free graphs. Concretely, the algorithm takes a connected P9-free graph and a central vertex x whose distance to every other vertex is at most four, then for each edge xy incident to x it computes the distance layers N_i of xy and tries to extend xy to a full d.i.m. by a feasible black-white coloring. The structural analysis shows that N1 is an independent white set, N2 consists of forced black isolated vertices plus forced matching edges, N3 splits into private sets T_i attached to N2, and N4 components are paths or cycles with only few feasible colorings. The reductions force colors outward, and P9-freeness rules out the long induced paths that would allow too many colorings, so each candidate edge can be checked in polynomial time. If every incident edge fails, the central vertex is forced white and removed, and the process repeats on the components.

Load-bearing premise

The load-bearing premise is Observation 4: every edge incident to a central vertex in a P9-free graph lies in an induced P3, so testing only those edges in Step (B) cannot miss the unique d.i.m.; if that premise fails, the polynomial loop over candidate edges can skip the only edge that can carry the d.i.m.

Editorial extensions

If this is right

For every connected P9-free graph, the existence of a d.i.m. is decidable in time polynomial in the number of vertices, rather than being NP-complete.
The polynomial-time frontier for DIM moves one step further along the induced-path hierarchy, from P8-free to P9-free graphs, supporting the conjecture that DIM is tractable for every fixed Pk-free class.
The algorithm is constructive: when a d.i.m. exists it returns one, expressed as a feasible black-white coloring built from distance layers.
The reduction rules imply that any d.i.m. in a P9-free graph admits a forced layered structure, which could be used to enumerate or certify all d.i.m.s in polynomial time.
A direct consequence of Theorem 3 is that DIM is polynomial for every connected graph whose every component is P9-free, since the problem decomposes componentwise.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural testable extension is to attempt the same distance-layer strategy for P10-free graphs, where $N_5$ can be nonempty and new ambient structures enter the coloring analysis.
The layered coloring framework suggests a possible uniform approach for all fixed Pk-free classes via bounded-depth distance layers, though the current proof is specialized to depth four.
If the algorithm were implemented, the practical bottleneck would likely be the branching over feasible colorings of N4 components; small exhaustive checks on generated P9-free graphs could test where that branching actually appears.
The paper's low-level lemmas may be reusable for other domination-type problems on P9-free graphs, since the distance-layer decomposition is tied to the path bound rather than to the matching objective itself.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my read. The paper is a genuine extension of the Pk-free DIM line: P9 is not in the cited literature, and the Section 3 machinery — distance levels, private-neighbor sets Ti, forcing rules, the component decomposition — is substantial original work, not a mechanical rerun of the P8 paper. Reuse of earlier published lemmas, such as Lemma 1 from [5], is legitimate citation, not circularity. If the proof were complete, Theorem 3 would be a solid increment in a well-known program.

As written, it is not complete. I agree with the stress-test note on Observation 4: the observation is false, and the triangle-with-two-tails example is a genuine counterexample. The proof's "dist(w,y) < dist(v,y)" is not a contradiction to centrality. But I also agree that this alone is probably patchable: in that example another central vertex satisfies the needed condition, so Step (A) could in principle still work. I would not rest a rejection on Observation 4 alone.

The load-bearing gap is Lemma 3, Section 3, case N4 = empty. The proof ends with a two-sentence assertion: if t2 does not completely color T3, we can "add a possible coloring of T3" that completely colors every neighbor, and "Case 2.2 appears only once" in the component because G is P9-free. This is exactly the claim that makes the search in Step (B.2) polynomial. No argument is supplied for either part: no proof that the added coloring is compatible with already forced colors, and no proof that a second occurrence of Case 2.2 contains an induced P9. If that assertion fails, the branching is not bounded polynomially and Theorem 3 does not follow. This is a major gap in the central argument, not a routine missing detail.

The paper reads honestly; the structural work is mostly careful, and the failure is an omitted proof step rather than an obviously wrong idea. But that is not enough for acceptance. Researchers working on DIM/EED and hereditary graph classes are the right audience, and the paper deserves a serious referee — the problem is natural, the extension is real, and the case analysis is large enough to pressure-test usefully. My recommendation is major revision, not acceptance: the authors need to prove the "only once" claim, or restructure Step (B.2) so it does not depend on it, and they need to fix Observation 4's statement and proof.

Referee Report

3 major / 6 minor

Summary. The paper claims to solve the Dominating Induced Matching (DIM) problem in polynomial time for P9-free graphs, extending the previously known P7-free linear-time and P8-free polynomial-time results. The approach follows the established framework for DIM: for a candidate matching edge xy contained in an induced P3, it partitions the graph into distance levels Ni(xy), applies a series of reduction rules (Vertex Reduction, Edge Reduction, assumptions (A1)-(A6), forcing rules (R1)-(R4)), and then attempts to complete a feasible black-white coloring. The main technical work is in Lemma 3, which claims that in the case N4 = empty set, each component of G[S2 ∪ N3] can be colored in polynomial time, and in Section 4, which extends the argument to N4 nonempty using a structural analysis of components in G[N4]. The final theorem (Theorem 3) asserts polynomial-time solvability of DIM on P9-free graphs.

Significance. If the main theorem is correct, it is a natural and meaningful advance in the study of dominating induced matchings in hereditary graph classes, supporting the conjecture that DIM is polynomial for Si,j,k-free graphs. The paper builds systematically on the authors' earlier work on P7- and P8-free graphs and does not merely reduce the P9 case to those results; the P9 arguments are new. The case analysis is extensive and several claims are carefully structured around explicit forbidden P9 configurations. No machine-checked proofs or code are supplied, so the contribution rests entirely on the correctness of the structural proof. Unfortunately, two load-bearing gaps prevent me from verifying the polynomial-time claim: Observation 4 is false as stated, and Lemma 3 contains an unproved assertion that is essential for the polynomial bound.

major comments (3)

[Section 2.3, Observation 4; Algorithm Step (A)] Observation 4 is false. Consider the P9-free graph consisting of a triangle (u,v,w) with two length-2 tails w-a-a' and w-b-b'. Vertices u and v are central, but the edge uv is contained in no induced P3, while the unique d.i.m. of this graph is {uv, aa', bb'}. The proof's assertion that dist(w,y) < dist(v,y) contradicts centrality is a non sequitur: a central vertex is defined by an absolute eccentricity bound, not by being closer to every vertex than v. Since Algorithm Step (A) requires a central vertex x such that every incident edge xy is contained in a P3, and the only justification for the existence of such an x is Observation 4, the preprocessing step is not justified as written. The example itself has another central vertex, w, with the required property, so a weaker existence statement may be true, but it is neither stated nor proved.
[Section 3, Lemma 3, final paragraph] The proof of Lemma 3 concludes: 'Since G is P9-free, Case 2.2 appears only once in component K.' This is load-bearing with no proof. Step (B.2) of the algorithm needs the search over feasible xy-colorings to be polynomial; if Case 2.2 can occur in more than one Ti, the procedure would need to branch again, and the number of colorings is no longer bounded by the initial |T1| choices. Claims 7-11 handle a single unfinished T3 under the implicit assumption that all other neighbor sets are already colored; they do not rule out a second occurrence of Case 2.2 after T3 has been colored. The preceding sentence, 'we can add a possible coloring of T3 which leads to a complete coloring of every neighbor Ti of T3', also asserts compatibility with already forced colors without proof. A complete proof of the uniqueness of Case 2.2, or an alternative polynomial enumeration, is required for the polynomial-time claim.
[Section 4, general structure] Section 4's argument for the case N4 nonempty depends repeatedly on the polynomial-time coloring of components of G[S2 ∪ N3] that is supposed to be established by Lemma 3. For example, the text after Claim 18 states that 'for every Qi, it can be independently checked in polynomial time whether Qi has a feasible coloring or a contradiction.' If Lemma 3 is not repaired, the N4 nonempty case is unsupported as well. The paper should state explicitly where Lemma 3 is invoked and verify that after fixing a feasible coloring of the N4-component D, the remaining graph still satisfies the assumptions (A1)-(A6) and the reduction rules used in Lemma 3.

minor comments (6)

[Section 2.3, after Theorem 2] The phrase 'a central vertex in G has shortest distance to every other vertex in G' is ambiguous; Theorem 2 only guarantees the existence of a vertex with dist(v,w) <= floor(t/2) for all w. Please rephrase to avoid suggesting that v is a distance-minimizer among all vertices.
[Section 2.3, proof of Observation 4] The sentence 'w has more neighbors than v in G since G itself is no C3' is irrelevant to the claimed distance inequality and should be removed or replaced by a precise argument.
[Section 3, Claim 2] The proof says 'Let P be any induced path in G between u1 and u3 through N1 ∪ {x,y}'; it is not obvious that such an induced path with the required properties exists, and the subsequent construction of a P9 depends on it. Please provide a short justification or a more precise definition of P.
[Section 4, first paragraph] The statement 'If there is a P5 (t,a,b,c,d) with endpoint t and four vertices a,b,c,d in N4 (such that only one of them, say a contacts t)' should specify whether the P5 is induced and what 'contacts' means; otherwise the claimed conclusion that t is the midpoint of a P9 is hard to verify.
[Section 2.2, Observation 1(iii)] Observation 1(iii) says 'for each C6 either exactly two or none of its edges are in M'; this is likely intended to count the C6 edges that belong to M, but the wording could be clarified to avoid confusion with domination of C6 edges by M-edges outside the cycle.
[Algorithm Step (C)] Step (C) applies the Vertex Reduction to x after all incident edges fail; this is only valid if the algorithm has indeed established that x is forced white. The link between exhaustively testing all incident edges and the forced-white conclusion should be stated explicitly, especially in view of the problem with Observation 4.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the P9-free DIM proof is a self-contained case analysis over central vertices and edges, and the cited P7/P8 results are independent published theorems rather than inputs to the P9 claim.

full rationale

I walked the derivation chain of Theorem 3. The algorithm reduces DIM on a connected P9-free graph to (A) choosing a central vertex, (B) trying each incident edge xy contained in a P3, and (B.2) checking for a d.i.m. containing xy by distance-level forcing. None of these steps defines the target object in terms of itself: the distance levels Ni(xy) are defined from graph distances, the colorings are defined by feasibility conditions, and the reduction rules are justified by the partition V = V(M) ∪ I. No fitted parameter is renamed as a prediction, and the polynomial-time claim does not rely on assuming DIM for P9-free graphs. The structural facts imported from the authors' earlier papers — Observation 1 and Lemma 1 in particular — are published results with independent proofs, and they do not contain the P9-free conclusion, so self-citation is not load-bearing. The only cited 'central vertex' theorem is due to Bacsó and Tuza, not to the present authors. I also checked the two places a reader could mistake for circularity. Observation 4's proof is incorrect as written, but the error is a false inferential step, not a definitional identification of the conclusion with the premise. The sentence in Lemma 3, 'Since G is P9-free, Case 2.2 appears only once in component K,' is an unsupported assertion and is a genuine gap in the proof, but again it is an omitted argument rather than a circular one. The paper is not renaming a known result: the P9-free case is a genuinely new extension of prior work, and its proof is not equivalent to the P7/P8 input by construction. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The argument depends on prior structural lemmas and on a new but false observation about central vertices. The false observation is the main unproved premise.

assumptions (4)

standard math Every connected P_t-free graph has a vertex with eccentricity at most floor(t/2) (Theorem 2, Bacsó-Tuza).
Invoked in Section 2.3 to fix a central vertex and conclude N_k(xy)=empty for k>=5; proven in [1].
standard math Observation 1 from [4]: in a d.i.m., every triangle has exactly one chosen edge, no C4 edge is chosen, and every C6 has zero or two chosen edges.
Used throughout for forcing edges (e.g., Observation 2, Claims 4-6); cited from the authors' own earlier work.
standard math Lemma 1 from [5]: structure of the distance-layer sets T_i, including bipartiteness of G[N3] and private-neighbor properties.
Basis for assumptions (A1)-(A6); published in [5].
ad hoc to paper Observation 4: every central vertex has all incident edges contained in an induced P3.
Load-bearing for Algorithm step (A), but false as stated (counterexample: triangle with two length-2 tails) and the proof is invalid.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Finding Dominating Induced Matchings in $P_9$-Free Graphs in Polynomial Time." pith.science (2026). https://pith.science/paper/SRYGTQ5T

@misc{pith2026190800978,
  author       = {Pith},
  title        = {Pith review of: Finding Dominating Induced Matchings in $P_9$-Free Graphs in Polynomial Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SRYGTQ5T}},
  note         = {Machine review of arXiv:1908.00978}
}

abstract

Let $G=(V,E)$ be a finite undirected graph. An edge subset $E' \subseteq E$ is a {\em dominating induced matching} ({\em d.i.m.}) in $G$ if every edge in $E$ is intersected by exactly one edge of $E'$. The \emph{Dominating Induced Matching} (\emph{DIM}) problem asks for the existence of a d.i.m.\ in $G$. The DIM problem is \NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for $P_7$-free graphs and in polynomial time for $P_8$-free graphs. In this paper, we solve it in polynomial time for $P_9$-free graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[5]

Brandst¨ adt and R

A. Brandst¨ adt and R. Mosca, Finding Dominating Induced Matchings in P8-Free Graphs in Polyno- mial Time, Algorithmica 77 (2017) 1283-1302

work page 2017
[1]

Bacs´ o and Zs

G. Bacs´ o and Zs. Tuza, A characterization of graphs with out long induced paths, J. Graph Theory 14, 4 (1990) 455-464

work page 1990
[2]

Biggs, Perfect codes in graphs, Journal of Combinatorial Theory, Series B 15 (1973) 289-296

N. Biggs, Perfect codes in graphs, Journal of Combinatorial Theory, Series B 15 (1973) 289-296

work page 1973
[3]

Brandst¨ adt, C

A. Brandst¨ adt, C. Hundt, and R. Nevries, Eﬃcient Edge Do mination on Hole-Free graphs in Poly- nomial Time, Conference Proceedings LATIN 2010, Lecture Notes in Computer Science 6034 (2010) 650-661

work page 2010
[4]

Brandst¨ adt and R

A. Brandst¨ adt and R. Mosca, Dominating Induced Matchin gs for P7-Free Graphs in Linear Time, Algorithmica 68 (2014) 998-1018

work page 2014
[6]

Dominating Induced Matchings in $S_{1,2,4}$-Free Graphs

A. Brandst¨ adt and R. Mosca, Dominating Induced Matchin gs in S1,2,4-Free Graphs, CoRR arXiv:1706.09301, 2017. Available online in Discrete Applied Math

work page Pith review arXiv 2017
[7]

Finding Dominating Induced Matchings in $(S_{2,2,3})$-Free Graphs in Polynomial Time

A. Brandst¨ adt and R. Mosca, Finding Dominating Induced Matchings in S2,2,3-Free Graphs, CoRR arXiv:1706.04894, 2017. Available online in Discrete Applied Math. 20

work page Pith review arXiv 2017
[8]

Finding Dominating Induced Matchings in $S_{1,1,5}$-Free Graphs in Polynomial Time

A. Brandst¨ adt and R. Mosca, Finding Dominating Induced Matchings in S1,1,5-Free Graphs, CoRR arXiv:1905.05582, 2019. Accepted for Discrete Applied Math

work page Pith review arXiv 1905

Show all 14 references

[9]

Cardoso, N

D.M. Cardoso, N. Korpelainen, and V.V. Lozin, On the comp lexity of the dominating induced match- ing problem in hereditary classes of graphs, Discrete Applied Math. 159 (2011) 521-531

2011
[10]

Grinstead, P.L

D.L. Grinstead, P.L. Slater, N.A. Sherwani, and N.D. Ho lmes, Eﬃcient edge domination problems in graphs, Information Processing Letters 48 (1993) 221-228

1993
[11]

Hertz, V.V

A. Hertz, V.V. Lozin, B. Ries, V. Zamaraev, and D. de Werr a, Dominating induced matchings in graphs containing no long claw, Journal of Graph Theory 88, no. 1 (2018) 18-39

2018
[12]

Korpelainen, V.V

N. Korpelainen, V.V. Lozin, and C. Purcell, Dominating induced matchings in graphs without a skew star, J. Discrete Algorithms 26 (2014) 45-55

2014
[13]

Lu, M.-T

C.L. Lu, M.-T. Ko, and C.Y. Tang, Perfect edge dominatio n and eﬃcient edge domination in graphs, Discrete Applied Math. 119 (2002) 227-250

2002
[14]

Lu and C.Y

C.L. Lu and C.Y. Tang, Solving the weighted eﬃcient edge domination problem on bipartite permu- tation graphs, Discrete Applied Math. 87 (1998) 203-211. 21

1998

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [5]

Brandst¨ adt and R

A. Brandst¨ adt and R. Mosca, Finding Dominating Induced Matchings in P8-Free Graphs in Polyno- mial Time, Algorithmica 77 (2017) 1283-1302

work page 2017

[2] [1]

Bacs´ o and Zs

G. Bacs´ o and Zs. Tuza, A characterization of graphs with out long induced paths, J. Graph Theory 14, 4 (1990) 455-464

work page 1990

[3] [2]

Biggs, Perfect codes in graphs, Journal of Combinatorial Theory, Series B 15 (1973) 289-296

N. Biggs, Perfect codes in graphs, Journal of Combinatorial Theory, Series B 15 (1973) 289-296

work page 1973

[4] [3]

Brandst¨ adt, C

A. Brandst¨ adt, C. Hundt, and R. Nevries, Eﬃcient Edge Do mination on Hole-Free graphs in Poly- nomial Time, Conference Proceedings LATIN 2010, Lecture Notes in Computer Science 6034 (2010) 650-661

work page 2010

[5] [4]

Brandst¨ adt and R

A. Brandst¨ adt and R. Mosca, Dominating Induced Matchin gs for P7-Free Graphs in Linear Time, Algorithmica 68 (2014) 998-1018

work page 2014

[6] [6]

Dominating Induced Matchings in $S_{1,2,4}$-Free Graphs

A. Brandst¨ adt and R. Mosca, Dominating Induced Matchin gs in S1,2,4-Free Graphs, CoRR arXiv:1706.09301, 2017. Available online in Discrete Applied Math

work page Pith review arXiv 2017

[7] [7]

Finding Dominating Induced Matchings in $(S_{2,2,3})$-Free Graphs in Polynomial Time

A. Brandst¨ adt and R. Mosca, Finding Dominating Induced Matchings in S2,2,3-Free Graphs, CoRR arXiv:1706.04894, 2017. Available online in Discrete Applied Math. 20

work page Pith review arXiv 2017

[8] [8]

Finding Dominating Induced Matchings in $S_{1,1,5}$-Free Graphs in Polynomial Time

A. Brandst¨ adt and R. Mosca, Finding Dominating Induced Matchings in S1,1,5-Free Graphs, CoRR arXiv:1905.05582, 2019. Accepted for Discrete Applied Math

work page Pith review arXiv 1905