2026-07-20T09:00:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26441 2026-07-01T07:16:10Z ddc:004 open_access

Witness-Sensitive Detection of Induced Diamonds Censor-Hillel, Keren Even, Tomer Vassilevska Williams, Virginia Wallheimer, Nathan Induced diamond detection Witness-sensitive algorithms Matrix multiplication Subgraph detection Fine-grained complexity We provide a fast witness-sensitive algorithm for detecting an induced diamond (a K₄ minus an edge) in an n-vertex graph containing t induced diamonds. Our algorithm runs in time Õ(min(n^2.425/t^0.25 + n², 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 ≥ 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 Õ(r⋅(n/r)^ω + (n/r)³+ nr) time. When there are no r-heavy diamonds, we provide a different fast detection algorithm in Õ(MM(n,n,n√{r/t})) time, where MM(a,b,c) denotes the time to multiply an a × b matrix by a b × c matrix, which is conditionally optimal for r = Õ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Keren Censor-Hillel and Tomer Even and Virginia Vassilevska Williams and Nathan Wallheimer 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.52 urn:nbn:de:0030-drops-264419 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.52 eng https://creativecommons.org/licenses/by/4.0/legalcode