Structural characterization and efficient recognition of probe diamond-free graphs

Luciano Norberto Grippo Min Chih Lin

arxiv: 2605.17080 · v1 · pith:E2FI5HIMnew · submitted 2026-05-16 · 🧮 math.CO

Structural characterization and efficient recognition of probe diamond-free graphs

Luciano Norberto Grippo Min Chih Lin This is my paper

Pith reviewed 2026-05-20 14:50 UTC · model grok-4.3

classification 🧮 math.CO

keywords probe graphsdiamond-free graphsstructural characterizationrecognition algorithmcertificate producingforbidden induced subgraphsO(nm) time

0 comments

The pith

Probe diamond-free graphs admit a local split-union characterization that directly produces an O(nm)-time recognition algorithm with explicit certificates.

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

The paper shows that a graph is probe diamond-free precisely when it satisfies a local condition called the union-of-complete-split property relative to some auxiliary bipartite graph. This structural test replaces the need to search for forbidden induced subgraphs and immediately supplies a linear-time procedure in the size of the edge set. The procedure returns either a probe partition together with the edges that must be added among the nonprobes, or a minimal forbidden subgraph presented as an ordered vertex sequence. The ordered certificate makes verification straightforward: one simply checks the induced subgraph against the fixed degree-lexicographic ordering rule.

Core claim

A graph is probe diamond-free if and only if its vertices can be partitioned into probes and an independent set of nonprobes such that the graph satisfies the locally union of complete split property with respect to an auxiliary bipartite graph that encodes the admissible completions; this equivalence yields a recognition algorithm running in O(nm) time that outputs a probe partition and completion set for yes-instances or a degree-lexicographically ordered minimal forbidden induced subgraph for no-instances.

What carries the argument

the locally union of complete split property together with an auxiliary bipartite graph that records candidate nonprobe edges and their completion status

If this is right

Membership can be decided and certified in O(nm) time without enumerating all possible forbidden subgraphs.
A positive instance is accompanied by an explicit probe partition and a set of edges to add among nonprobes.
A negative instance is accompanied by an ordered vertex sequence that induces a minimal forbidden subgraph, making verification a simple local check.
The same framework supplies an alternative to both sandwich-problem reductions and exhaustive induced-subgraph searches for this class.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The ordered-certificate technique may transfer to recognition algorithms for other probe classes whose minimal forbidden subgraphs admit a canonical ordering.
The auxiliary bipartite graph construction could be reused to obtain polynomial-time solutions for related partition problems that involve independent-set completions.
Because the local property is checkable by examining small neighborhoods, the method may admit parallel or distributed implementations for large sparse graphs.

Load-bearing premise

The locally union of complete split property together with the auxiliary bipartite graph supplies a complete and correct characterization of probe diamond-free graphs.

What would settle it

A concrete graph that satisfies the local split-union condition and auxiliary bipartite graph for some partition yet whose completion still contains an induced diamond, or a probe diamond-free graph for which no such auxiliary graph exists.

Figures

Figures reproduced from arXiv: 2605.17080 by Luciano Norberto Grippo Min Chih Lin.

**Figure 2.** Figure 2: Some graphs equipped with a degree–lexicographic ordering. The last three are [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: The forbidden subgraphs Ti for probe diamond-free graphs, each endowed with a degree–lexicographic ordering. • set N ϕ G ← N ϕ G ∪ SCv . • add edges joining avw to every vertex s ∈ SCv . The following observation follows directly from the definition. Remark 11. Let G be a LUCS graph and let v ∈ V (G). If Cv is a nonspecial component of G[N(v)], then the clique KCv ∪ {v} is represented by exactly one verte… view at source ↗

**Figure 4.** Figure 4: The forbidden subgraphs Si for probe diamond-free graphs, whose vertices are labeled according to a degree–lexicographic ordering. Subgraphs S4 and S3 correspond to the unpartitioned versions of H4 and H5, respectively. For S2 and S3, all degree– lexicographic orderings are equivalent The next result will be useful to detect subgraphs isomorphic to P3 + K2. Lemma 14. Let G be a LUCS graph such that NG is a… view at source ↗

**Figure 5.** Figure 5: For each graph Ti, vertices with nonzero t-value are shown in blue, and the ρ-values of its two diamonds are shown in brown. 20 [PITH_FULL_IMAGE:figures/full_fig_p020_5.png] view at source ↗

read the original abstract

A graph is probe diamond-free if its vertex set admits a partition into probes and nonprobes, where the set of nonprobes is independent, such that adding edges only between pairs of nonprobes yields a diamond-free graph. Although this class admits a characterization by forbidden induced subgraphs, such a characterization does not directly lead to an efficient recognition algorithm. In this work we introduce a new structural characterization of probe diamond-free graphs based on a local condition, called the \emph{locally union of complete split} property, together with an auxiliary bipartite graph. Using this framework, we obtain an $O(nm)$-time recognition algorithm for (nonpartitioned) probe diamond-free graphs. A distinctive feature of our algorithm is that it is certificate-producing. When the input graph does not belong to the class, the algorithm outputs a negative certificate in the form of a sequence of vertices inducing a minimal forbidden subgraph, ordered according to a fixed degree--lexicographic rule. This ordered representation enables particularly simple and efficient certificate verification. When the input graph is probe diamond-free, the algorithm outputs a positive certificate consisting of a probe partition and a completion set. To the best of our knowledge, this is the first $O(nm)$-time recognition algorithm for probe diamond-free graphs that produces explicit certificates, providing an alternative to both sandwich-based approaches and exhaustive forbidden subgraph testing.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a new local characterization via the union-of-complete-split property and an auxiliary bipartite graph that directly supports an O(nm) certificate-producing recognition algorithm for probe diamond-free graphs.

read the letter

Colleague, the main takeaway is that the authors replace the known forbidden-subgraph characterization with a local condition they call the locally union of complete split property, together with an auxiliary bipartite graph whose bipartition tracks allowable completions among nonprobes. This equivalence yields an O(nm) algorithm that outputs either a probe partition plus completion set or an ordered minimal forbidden induced subgraph. The ordering rule makes the negative certificate easy to verify, which is a practical plus. The work is positioned as the first efficient certificate-producing method, avoiding both sandwich reductions and exhaustive forbidden-subgraph enumeration. That part reads as a genuine algorithmic improvement for this specific class. The characterization appears derived from direct structural analysis rather than fitted parameters, and the stress-test note found no internal inconsistency between the local condition and diamond-freeness after completion. Soft spots are limited. The central equivalence still needs the full proofs to confirm it is both sound and complete; the abstract alone leaves that step unverified. The O(nm) claim also rests on the implementation details of the auxiliary-graph construction and search steps, so those should be checked for hidden quadratic factors. Overall the argument structure looks clean and the contribution is concrete. This paper is for people working on probe versions of hereditary classes or on recognition algorithms that produce short certificates. A reader focused on structural graph theory or practical forbidden-subgraph problems would get usable details from the characterization and the algorithm description. It deserves a serious referee because the result is specific, the certificate feature adds value, and the approach differs from prior sandwich or exhaustive methods. I would send it to peer review.

Referee Report

1 major / 2 minor

Summary. The paper defines probe diamond-free graphs via a probes/nonprobes partition (nonprobes independent) such that some completion of edges among nonprobes yields a diamond-free graph. It introduces an equivalent structural characterization based on the locally union of complete split property together with an auxiliary bipartite graph whose bipartition encodes allowable nonprobe completions. From this equivalence the authors derive an O(nm)-time recognition algorithm that outputs explicit certificates: an ordered sequence of vertices inducing a minimal forbidden subgraph (degree-lexicographic order) for negative instances, and a probe partition plus completion set for positive instances.

Significance. If the claimed equivalence holds, the result is significant: it supplies the first O(nm)-time certificate-producing recognition procedure for this probe class, together with particularly simple verification of the negative certificates. The approach avoids both exhaustive forbidden-subgraph enumeration and sandwich-problem reductions, and the explicit certificates constitute a concrete algorithmic contribution beyond mere complexity classification.

major comments (1)

[Characterization theorem (around the auxiliary bipartite graph construction)] The central claim rests on the completeness of the locally union of complete split property plus auxiliary bipartite graph as a characterization (see the statement following the definition of the auxiliary graph and the equivalence theorem). The provided argument sketch does not explicitly address whether every diamond-free completion corresponds to a valid auxiliary-graph matching; a concrete counter-example or missing case analysis here would falsify the O(nm) algorithm's correctness.

minor comments (2)

[Section introducing the auxiliary graph] Notation for the auxiliary bipartite graph (bipartition and edge set) is introduced without a dedicated figure or small illustrative example; adding one would clarify how allowable nonprobe completions are encoded.
[Certificate verification subsection] The degree-lexicographic ordering rule for negative certificates is stated but its uniqueness or canonicity is not proved; a short remark on why this ordering guarantees a minimal forbidden subgraph would strengthen the verification claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the thorough review and for recognizing the significance of our O(nm)-time certificate-producing recognition algorithm for probe diamond-free graphs. We address the major comment point by point below.

read point-by-point responses

Referee: [Characterization theorem (around the auxiliary bipartite graph construction)] The central claim rests on the completeness of the locally union of complete split property plus auxiliary bipartite graph as a characterization (see the statement following the definition of the auxiliary graph and the equivalence theorem). The provided argument sketch does not explicitly address whether every diamond-free completion corresponds to a valid auxiliary-graph matching; a concrete counter-example or missing case analysis here would falsify the O(nm) algorithm's correctness.

Authors: We appreciate the referee highlighting the need for explicit verification of the converse direction in the equivalence. Theorem 3.5 proves both directions: given a valid probe partition and diamond-free completion, the auxiliary bipartite graph is constructed precisely from the nonprobe pairs whose addition is compatible with the locally union of complete split property and does not induce diamonds. Conversely, any matching in the auxiliary graph defines a completion that respects the local conditions, thereby yielding a diamond-free supergraph. While the manuscript sketch outlines these arguments, we agree that a more granular case analysis—enumerating how arbitrary diamond-free completions among nonprobes map onto matchings without omission—would strengthen the presentation. In the revised version we will insert this expanded case analysis immediately after the statement of the auxiliary-graph construction, including verification that no allowable completion is excluded by the matching requirement. This addition clarifies the completeness of the characterization without altering the algorithm or its complexity. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines probe diamond-free graphs via an explicit partition and completion condition, then derives an equivalent structural characterization (locally union of complete split property plus auxiliary bipartite graph) through direct analysis of induced subgraphs and forbidden configurations. The O(nm) recognition algorithm and certificate production follow from this equivalence via standard graph traversal and verification steps. No step reduces a claimed prediction or uniqueness result to a fitted parameter, self-citation chain, or definitional renaming; the central claims rest on independent structural proofs rather than circular inputs. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The work rests on standard graph-theoretic definitions and introduces one new local property to support the recognition procedure.

axioms (2)

standard math Graphs are finite, undirected, and simple.
Basic assumption underlying all definitions of induced subgraphs and partitions.
domain assumption A graph is diamond-free if it contains no induced diamond as a subgraph.
Core definition used to define the probe version of the class.

invented entities (1)

locally union of complete split property no independent evidence
purpose: To serve as the local structural condition in the new characterization of probe diamond-free graphs.
Newly introduced concept whose correctness is central to the algorithm.

pith-pipeline@v0.9.0 · 5775 in / 1439 out tokens · 70110 ms · 2026-05-20T14:50:20.906904+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[1]

Daniel Bayer, Van Bang Le, and H. N. de Ridder. Probe threshold and probe trivially perfect graphs.Theoret. Comput. Sci., 410(47-49):4812– 4822, 2009

work page 2009
[2]

Rec- ognizing chordal probe graphs and cycle-bicolorable graphs.SIAM J

Anne Berry, Martin Charles Golumbic, and Marina Lipshteyn. Rec- ognizing chordal probe graphs and cycle-bicolorable graphs.SIAM J. Discrete Math., 21(3):573–591, 2007

work page 2007
[3]

Flavia Bonomo, Celina M. H. de Figueiredo, Guillermo Durán, Lu- ciano N. Grippo, Martín D. Safe, and Jayme L. Szwarcfiter. On probe 2-clique graphs and probe diamond-free graphs.Discrete Math. Theor. Comput. Sci., 17(1):187–199, 2015. 34

work page 2015
[4]

Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, and Sheng-Lung Peng

David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, and Sheng-Lung Peng. Partitioned probe comparability graphs.Theoret. Comput. Sci., 396(1-3):212–222, 2008

work page 2008
[5]

Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, and Sheng-Lung Peng

David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, and Sheng-Lung Peng. On probe permutation graphs.Discrete Appl. Math., 157(12):2611–2619, 2009

work page 2009
[6]

G. J. Chang, T. Kloks, J. Liu, and S.-L. Peng. The PIGs full monty – a floor show of minimal separators. In V. Diekert and B. Durand, editors, Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS 2005), volume 3403 ofLecture Notes in Computer Science, pages 521–532, Heidelberg, 2005. Springer

work page 2005
[7]

Recognition of probe distance-hereditary graphs.Discrete Appl

Maw-Shang Chang, Ling-Ju Hung, and Peter Rossmanith. Recognition of probe distance-hereditary graphs.Discrete Appl. Math., 161(3):336– 348, 2013

work page 2013
[8]

Dabrowski, Tala Eagling-Vose, Matthew Johnson, Giacomo Paesani, and Daniël Paulusma

Konrad K. Dabrowski, Tala Eagling-Vose, Matthew Johnson, Giacomo Paesani, and Daniël Paulusma. Finding d-cuts in probe h-free graphs. In Artur Jez and Jan Otop, editors,Fundamentals of Computation Theory - 25th International Symposium, FCT 2025, Wrocław, Poland, Septem- ber 15-17, 2025, Proceedings, volume 16106 ofLecture Notes in Com- puter Science, page...

work page 2025
[9]

Simone Dantas, Celina M. H. de Figueiredo, Murilo V. G. da Silva, and Rafael B. Teixeira. On the forbidden induced subgraph sandwich problem.Discrete Appl. Math., 159(16):1717–1725, 2011

work page 2011
[10]

Van Bang Le and H. N. de Ridder. Characterisations and linear-time recognition of probe cographs. In Andreas Brandstädt, Dieter Kratsch, and Haiko Müller, editors,Graph-Theoretic Concepts in Computer Sci- ence, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers, volume 4769 ofLecture Notes in Computer Science, pages ...

work page 2007
[11]

Van Bang Le and H. N. de Ridder. Probe split graphs.Discrete Math. Theor. Comput. Sci., 9(1):207–238, 2007

work page 2007
[12]

Characterizing and recognizing probe block graphs.Theoret

Van Bang Le and Sheng-Lung Peng. Characterizing and recognizing probe block graphs.Theoret. Comput. Sci., 568:97–102, 2015

work page 2015
[13]

Soulignac, and Jayme L

Min Chih Lin, Francisco J. Soulignac, and Jayme L. Szwarcfiter. Ar- boricity,h-index, and dynamic algorithms.Theoret. Comput. Sci., 426/427:75–90, 2012. 35

work page 2012
[14]

McConnell and Yahav Nussbaum

Ross M. McConnell and Yahav Nussbaum. Linear-time recognition of probe interval graphs. InAlgorithms—ESA 2009, volume 5757 ofLec- ture Notes in Comput. Sci., pages 349–360. Springer, Berlin, 2009

work page 2009
[15]

Recognition of probe proper interval graphs.Discrete Appl

Yahav Nussbaum. Recognition of probe proper interval graphs.Discrete Appl. Math., 167:228–238, 2014

work page 2014
[16]

An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA.Computer Applications in the Biosciences, 10(3):309–317, 1994

P.Zhang, E.Schön, S.Fischer, E.C., J.Weiss, S.Kistler, andP.Bourne. An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA.Computer Applications in the Biosciences, 10(3):309–317, 1994. 36

work page 1994

[1] [1]

Daniel Bayer, Van Bang Le, and H. N. de Ridder. Probe threshold and probe trivially perfect graphs.Theoret. Comput. Sci., 410(47-49):4812– 4822, 2009

work page 2009

[2] [2]

Rec- ognizing chordal probe graphs and cycle-bicolorable graphs.SIAM J

Anne Berry, Martin Charles Golumbic, and Marina Lipshteyn. Rec- ognizing chordal probe graphs and cycle-bicolorable graphs.SIAM J. Discrete Math., 21(3):573–591, 2007

work page 2007

[3] [3]

Flavia Bonomo, Celina M. H. de Figueiredo, Guillermo Durán, Lu- ciano N. Grippo, Martín D. Safe, and Jayme L. Szwarcfiter. On probe 2-clique graphs and probe diamond-free graphs.Discrete Math. Theor. Comput. Sci., 17(1):187–199, 2015. 34

work page 2015

[4] [4]

Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, and Sheng-Lung Peng

David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, and Sheng-Lung Peng. Partitioned probe comparability graphs.Theoret. Comput. Sci., 396(1-3):212–222, 2008

work page 2008

[5] [5]

Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, and Sheng-Lung Peng

David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, and Sheng-Lung Peng. On probe permutation graphs.Discrete Appl. Math., 157(12):2611–2619, 2009

work page 2009

[6] [6]

G. J. Chang, T. Kloks, J. Liu, and S.-L. Peng. The PIGs full monty – a floor show of minimal separators. In V. Diekert and B. Durand, editors, Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS 2005), volume 3403 ofLecture Notes in Computer Science, pages 521–532, Heidelberg, 2005. Springer

work page 2005

[7] [7]

Recognition of probe distance-hereditary graphs.Discrete Appl

Maw-Shang Chang, Ling-Ju Hung, and Peter Rossmanith. Recognition of probe distance-hereditary graphs.Discrete Appl. Math., 161(3):336– 348, 2013

work page 2013

[8] [8]

Dabrowski, Tala Eagling-Vose, Matthew Johnson, Giacomo Paesani, and Daniël Paulusma

Konrad K. Dabrowski, Tala Eagling-Vose, Matthew Johnson, Giacomo Paesani, and Daniël Paulusma. Finding d-cuts in probe h-free graphs. In Artur Jez and Jan Otop, editors,Fundamentals of Computation Theory - 25th International Symposium, FCT 2025, Wrocław, Poland, Septem- ber 15-17, 2025, Proceedings, volume 16106 ofLecture Notes in Com- puter Science, page...

work page 2025

[9] [9]

Simone Dantas, Celina M. H. de Figueiredo, Murilo V. G. da Silva, and Rafael B. Teixeira. On the forbidden induced subgraph sandwich problem.Discrete Appl. Math., 159(16):1717–1725, 2011

work page 2011

[10] [10]

Van Bang Le and H. N. de Ridder. Characterisations and linear-time recognition of probe cographs. In Andreas Brandstädt, Dieter Kratsch, and Haiko Müller, editors,Graph-Theoretic Concepts in Computer Sci- ence, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers, volume 4769 ofLecture Notes in Computer Science, pages ...

work page 2007

[11] [11]

Van Bang Le and H. N. de Ridder. Probe split graphs.Discrete Math. Theor. Comput. Sci., 9(1):207–238, 2007

work page 2007

[12] [12]

Characterizing and recognizing probe block graphs.Theoret

Van Bang Le and Sheng-Lung Peng. Characterizing and recognizing probe block graphs.Theoret. Comput. Sci., 568:97–102, 2015

work page 2015

[13] [13]

Soulignac, and Jayme L

Min Chih Lin, Francisco J. Soulignac, and Jayme L. Szwarcfiter. Ar- boricity,h-index, and dynamic algorithms.Theoret. Comput. Sci., 426/427:75–90, 2012. 35

work page 2012

[14] [14]

McConnell and Yahav Nussbaum

Ross M. McConnell and Yahav Nussbaum. Linear-time recognition of probe interval graphs. InAlgorithms—ESA 2009, volume 5757 ofLec- ture Notes in Comput. Sci., pages 349–360. Springer, Berlin, 2009

work page 2009

[15] [15]

Recognition of probe proper interval graphs.Discrete Appl

Yahav Nussbaum. Recognition of probe proper interval graphs.Discrete Appl. Math., 167:228–238, 2014

work page 2014

[16] [16]

An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA.Computer Applications in the Biosciences, 10(3):309–317, 1994

P.Zhang, E.Schön, S.Fischer, E.C., J.Weiss, S.Kistler, andP.Bourne. An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA.Computer Applications in the Biosciences, 10(3):309–317, 1994. 36

work page 1994