2026-09-08T01:22:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26399 2026-08-27T14:38:40Z ddc:004 open_access

Node-Weighted Triangles: Faster and Simpler Akmal, Shyan Fischer, Nick fine-grained complexity triangle detection node-weighted triangle Weighted variants of triangle detection are an important object of study because of their prominence in fine-grained complexity. We revisit the Node-Weighted Triangle problem, where the goal is to decide if a vertex-weighted graph contains a triangle whose node weights sum to zero. This problem has been the focus of a celebrated line of work, beginning with a subcubic-time algorithm [Vassilevska, Williams; STOC '06], and culminating in algorithms running almost in matrix multiplication time, O(MM(n) + n²⋅2^O(√{log n})) [Czumaj, Lingas; SODA '07], [Vassilevska W., Williams; STOC '09]. This runtime is almost-optimal, since even detecting an unweighted triangle is conjectured to require matrix multiplication time MM(n). However, the superpolylogarithmic 2^Ω(√{log n}) overhead persists in a world where near-optimal matrix multiplication is possible (i.e., MM(n) ≤ n²poly(log n)). In this paper, we present a new algorithm solving Node-Weighted Triangle in O(MM(n)) time, closing the gap to unweighted triangle detection completely. Remarkably, our algorithm is much simpler than previous approaches, which use involved recursion schemes and communication protocols. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shyan Akmal and Nick Fischer 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.10 urn:nbn:de:0030-drops-263998 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.10 eng https://creativecommons.org/licenses/by/4.0/legalcode