# Node-Weighted Triangles: Faster and Simpler

Preprint · Shyan Akmal, Nick Fischer

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

## Abstract

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(\\textsf{MM}(n) + n^2\\cdot 2^{O(\\sqrt{\\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 $\\textsf{MM}(n)$. However, the superpolylogarithmic $2^{Ω(\\sqrt{\\log n})}$ overhead persists in a world where near-optimal matrix multiplication is possible (i.e., $\\textsf{MM}(n) \\leq n^2\\text{poly}(\\log n)$). In this paper, we present a new algorithm solving Node-Weighted Triangle in $O(\\textsf{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.

_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.