Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.17080 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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.