# Witness-Sensitive Detection of Induced Diamonds

Preprint · Keren Censor-Hillel, Tomer Even, Virginia Vasillevska Williams, Nathan Wallheimer

- Archive id: arxiv:2605.09006
- Published: 2026-05-09
- arXiv: https://arxiv.org/abs/2605.09006
- Source URL: https://arxiv.org/abs/2605.09006
- PDF: https://arxiv.org/pdf/2605.09006
- Provenance: arxiv

## Abstract

We provide a fast \\emph{witness-sensitive} algorithm for detecting an induced diamond (a $K\_4$ minus an edge) in an $n$-vertex graph containing $t$ induced diamonds. Our algorithm runs in time $\\tilde{O}(\\min(n^{2.425}/t^{0.25}+n^2, n^ω))$ with high probability, improving upon the prior state of the art (witness-oblivious) algorithm that runs in time $O(n^ω\\log{n})$ \[Vassilevska Williams, Wang, Williams, Yu, SODA 2014\] whenever $t \\geq n^{(3-ω)/3}$, where $ω\< 2.372$ is the matrix multiplication exponent. Our key insight is that the size of a clique containing one of the triangles of an induced diamond plays a crucial role in detecting such a diamond. We say that a diamond is $r$-heavy if this size is at least $r$, and we provide a fast detection algorithm for $r$-heavy diamonds in $\\tilde{O}(r \\cdot (n/r)^ω+ (n/r)^3+ nr)$ time. When there are no $r$-heavy diamonds, we provide a different fast detection algorithm in $\\tilde{O}(\\mathsf{MM}(n,n,n\\sqrt{r/t}))$ time, where $\\mathsf{MM}(a,b,c)$ denotes the time to multiply an $a \\times b$ matrix by a $b \\times c$ matrix, which is conditionally optimal for $r=\\tilde{O}(1)$. Our main technical contribution is in designing a refinement framework for sampling vectors, which allows sampling vertices for detecting diamonds in a manner that is adaptive to the structure of graphs with no $r$-heavy diamonds. We establish that our technique is of a wide applicability, by showing how it also allows for faster witness-sensitive algorithms for $4$-SUM and for a special case of $4$-cycles.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.