Node-Weighted Triangles: Faster and Simpler

Let $w$ be the unique vertex weight in $X$. Remove all edges $(y,z)\in Y\times Z$ with $w+\text{wt}(y)+\text{wt}(z)\ne 0$. The triangles in the remaining graph are exactly the triangles whose node weights sum to zero. So to solve NWT on $H$, it suffices to detect an unweighted triangle in the remaining graph in $\text{MM}(|X|,|Y|,|Z|)$ time. $◀$

With this simple lemma, we can now prove our main result.

Let $W=\{\text{wt}(x):x\in V\}$ be the set of node weights in $G$. For any weight $w\in W$, let $f(w)=|\{v\in V:\text{wt}(v)=w\}|$ denote its frequency. The set $W$ and all frequencies can be computed in $O(n)$ time by scanning through the vertices of the graph. Given this data, we run the following algorithm:

• 1

  for each $w\in W$ do

• 2

  Let $W^{\prime }=\{w^{\prime }\in W:f(w^{\prime })\le f(w)\}$

• 3

  Let $𝒫$ be a greedy partition of $W^{\prime }$ into parts $P$ with ${\sum }_{w^{\prime }\in P}f(w^{\prime })\le 2f(w)$

• 4

  for each $P\in 𝒫$ do

• 5

  Let $X=\{x\in V:\text{wt}(x)=w\}$

• 6

  Let $Y=\{y\in V:\text{wt}(y)\in P\}$

• 7

  Let $Z=\{z\in V:-(w+\text{wt}(z))\in P\}$

• 8

  Detect a solution in $X\times Y\times Z$ by Lemma 5

To elaborate on line 3 above: we scan through the set $W^{\prime }$ in some fixed order, and keep adding weights to our current part. Right before the sum of the frequencies of weights in our current part would exceed $2f(w)$, we set aside that part and start growing a new part. Once we have completed scanning through $W$ in this way, we have produced the partition $𝒫$. Since all weights in $W^{\prime }$ have frequency at most $f(w)$ and all frequencies are positive, each part we build is guaranteed to include at least one element, so this process terminates.

We claim that if $G$ has a solution $(x,y,z)$, then we will detect it in line 8. Without loss of generality, suppose $f(x)\ge f(y)$. Consider the iteration of the algorithm where we pick $w=\text{wt}(x)$ in line 1. Then $\text{wt}(y)\in W^{\prime }$ by definition, hence there is a part $P$ in the partition from line 3 with $\text{wt}(y)\in P$. By construction $x\in X$ and $y\in Y$. Since $(x,y,z)$ is a solution, we must have $z\in Z$. Thus we successfully detect the solution $(x,y,z)$ in line 8.

Fix an iteration of the algorithm where we pick weight $w$ in line 1. We compute $W^{\prime }$ and $𝒫$ in $O(n)$ time by scanning through $W$. Consider the loop in lines 4-8. Let $X_P,Y_P,Z_P$ be the sets $X,Y,Z$ constructed in the iteration of this inner loop when we pick part $P$ in line 4.

By construction $|X_P|=f(w)$ and $|Y_P|={\sum }_{w^{\prime }\in P}f(w^{\prime })\le 2f(w)$. Since $𝒫$ partitions a subset $W^{\prime }$ of weights in $G$, we have ${\sum }_{P\in 𝒫}|Z_P|\le n$. Moreover, as each weight in $W^{\prime }$ has frequency at most $f(w)$ and we form a new part in $𝒫$ only when the total frequency would exceed $2f(w)$, each part $P\in 𝒫$ has total frequency at least $f(w)$, so the partition has at most $|𝒫|\le n/f(w)$ parts.

Each call to Lemma 5 takes $O(\text{MM}(|X_P|,|Y_P|,|Z_P|))$ time. This means that overall, the total time spent in the loop is

The transition from the first to second line follows from the fact that in order to multiply an $f(w)\times f(w)$ matrix with an $f(w)\times |Z_P|$ matrix, if $|Z_P|>f(w)$ we can split the second matrix into the concatenation of $O(|Z_P|/f(w))$ many $f(w)\times O(f(w))$ matrices, and simply multiply the first $f(w)\times f(w)$ matrix with each of the new $f(w)\times O(f(w))$ matrices separately. If $|Z_P|\le f(w)$, then we can directly multiply the matrices in at most $\text{MM}(f(w))$ time. The transition from the second to third lines follows from ${\sum }_{P\in 𝒫}|Z_P|\le n$ and $|𝒫|\le n/f(w)$. The transition from the penultimate to final line follows from ▶ 4.

Summing over all possible choices of $w\in W$ in line 1, we get that the algorithm takes

time overall as claimed. $◀$

The only place we use matrix multiplication in our algorithm for NWT is in calls to Lemma 5. In the proof of Lemma 5, we only use matrix multiplication to detect unweighted triangles. This means that our algorithm for NWT can be interpreted as an efficient reduction to unweighted triangle detection. Concretely, if we let $\text{Tri}(n)$ denote the time complexity of detecting a triangle in an $n$-node graph, our arguments actually prove that NWT can be solved in $O(\text{Tri}(n))$ time. This is relevant in case it turns out that unweighted triangles actually can be detected in faster than matrix multiplication time. The previous algorithms of [8, 16] can also be formulated as reductions to unweighted triangle detection.

If instead of integer weights the graph has real node weights, our algorithm still applies unchanged. This is because we never use the fact that the weights are integers, only that we can add and compare weights in constant time. Previous algorithms for NWT handle this case as well.

The algorithms of [16] can solve the counting version of NWT, where we are tasked with returning the number of triangles $(x,y,z)$ whose sum of node weights is zero. Our approach can be adapted to solve this counting problem faster in $O(\text{MM}(n))$ time as well, with just two small changes.

The first change is to replace Lemma 5 with an algorithm that counts rather than just detects node-weighted triangles when one part has uniform weight. This follows from the standard fact that we can count unweighted triangles using matrix multiplication. In our algorithm we then keep a running count of solutions.

The second change is necessary to avoid overcounting triangles. Here we distinguish three types of triangles: (1) all three nodes have distinct weights, (2) exactly two nodes share the same weight, (3) all three nodes share the same weight. To count triangles of type (1), we first artificially ensure that the frequencies $f(w)$ of all weights are distinct. Then, by inspecting the correctness argument of Theorem 1, we see that a solution $(x,y,z)$ with distinct node weights will be counted three times by the algorithm (twice when the weight in the solution with highest frequency is selected in line 1 of the algorithm, and once when the weight in the solution with second-highest frequency is selected). The arguments for (2) and (3) are only easier. For instance, to count the triangles of type (2) we enumerate all weights $w$ of the first two nodes; the third node necessarily has weight $-2w$. Then we count the unweighted triangles in $X_w\times X_w\times Z_w$, where $X_w$ is the set of nodes with weight $w$ and $Z_w$ is the set of nodes with weight $-2w$. Each type-(2) triangle is counted exactly twice, and the total runtime is ${\sum }_w\text{MM}(|X_w|,|X_w|,|Z_w|)\le O(\text{MM}(n))$ by a similar analysis as in Theorem 1.

Suppose that instead of seeking a triangle whose sum of node weights is zero, we are tasked with finding a subgraph isomorphic to a fixed pattern graph $H$ on $k$ vertices whose sum of node weights is zero. Then combining Theorem 1 with standard reductions (see e.g., the discussion at the beginning of [16, Section 3]) shows that when $3\mid k$, we can solve this more general node-weighted $H$ detection problem in $O(\text{MM}(n^{k/3}))$ time. If instead $k\equiv 1(mod3)$ or $k\equiv 2(mod3)$, we have an additional $n$ or $n^2$ overhead on top of an $O(\text{MM}(n^{\lfloor k/3\rfloor }))$ runtime respectively.

It is well-known that we can find an unweighted triangle in an $m$-edge graph in $O(m^{2\omega /(\omega +1)})$ time, provided $\text{MM}(n)\le O(n^{\omega })$ [5, Theorem 3.5]. This is proved by reducing triangle detection in sparse graphs to triangle detection in dense graphs with fewer vertices. As observed in [8, Proof of Corollary 5], this argument generalizes to the NWT problem. In particular, if $\text{MM}(n)\le O(n^{\omega })$, previous work solves NWT in $m$-edge graphs in $O(m^{2\omega /(\omega +1)})$ time for $\omega >2$, but for $\omega =2$ only achieves a runtime of $m^{4/3}\cdot 2^{O(\sqrt{\log m})}$ [16]. With our new algorithm for NWT, we can remove the $2^{\mathrm{\Theta }(\sqrt{\log m})}$ factor in the runtime, and find node-weighted triangles as quickly as unweighted triangles in sparse graphs, for the full range of possible values of $\text{MM}(n)$.