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!
|
| _version_ | 1866917504937361408 |
|---|---|
| author | Lin, Luciano Norberto Grippo Min Chih |
| author_facet | Lin, Luciano Norberto Grippo Min Chih |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_17080 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Structural characterization and efficient recognition of probe diamond-free graphs Lin, Luciano Norberto Grippo Min Chih Combinatorics 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. |
| title | Structural characterization and efficient recognition of probe diamond-free graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.17080 |