# Label coloring to maximize number of “balanced” triangles (NP-hardness)

Define a triangle in undirected graph $G$ is balanced if the edge labels in the triangle are $(+1, +1, +1)$, $(-1, -1, +1)$, $(+1, -1, -1)$ or $(-1, +1, -1)$ (social balance theory).

Problem definition:

Given undirected graph $G=(V, E)$, initial edge label function $f: E \rightarrow \{+1, 0, -1\}$ and $k \in \mathbb{Z}^{+}$, find another label coloring function $g: E \rightarrow \{+1, 0, -1\}$ that maximizes the number of "balanced triangles" in $G$

s.t.

1. $\forall e \in E \text{ such that } f(e) \neq 0, g(e)=f(e) \text{ holds}$ ($g$ conforms with $f$ for non-zero valued edges).
2. $|\{e \in E \mid g(e) \neq 0 \text{ and } g(e) \neq f(e)\}| \le k$ (up to $k$ unlabeled edges can be labeled.)

I am trying to prove the NP-hardness of this problem, failing to find an appropriate problem reduction.

Here is what I have thought:

First, the problem can be decomposed using recursion.

We consider assigning label to only one edge, then fix it and solve the sub-problem with updated $f$ and $k-1$ labelings. However, this approach runs in exponential time.

Second, this problem can be seen from the "set cover" perspective.

We can consider each edge as a set containing a subset of all triangles (the universe), triangles can be classified into three types:

1. 1st-order triangle which has only one unknown label edge ($f(e) = 0$)
2. 2nd-order triangle which has two unknown label edges
3. 3rd-oder triangle where all the labels in the triangle are unknown.

A triangle is considered covered if it's 1st-order and the labeled edge makes it balanced.

If we consider some greedy approach by labeling the best edge one by one, then whenever each edge is labeled, the triangle type information will change accordingly.

For example, some 1st-order triangles will no longer be 1st-order while some 2nd-order triangles will become 1st-order because of the newly-labeled edge.

The "chaining" effect actually couples edges together, which makes things more difficult.