Label coloring to maximize number of "balanced" triangles (NP-hardness)

Question

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.

Answer 1

Reduce from 2-Lin(2):


Start with a star that has one edge per variable, and let those initial-labels all be 0.
For each equation ​ ​ ​ x_i + x_j ​ = ​ b ​ , ​ ​ ​ create an edge from the outer vertex of x_i's edge to the outer vertex of x_j's edge, and let that edge's initial-weight be (-1)^b.
That will produce the output weighted-graph. ​ Just let k be the number of variables, so the cardinality constraint doesn't matter.

Triangles whose weights are all forced are forced to be good or bad, so their existence affects approximation quality but not which g's are optimal. ​ Other triangles use at least one variable-edge, and so exactly 2 variable-edges, since being a variable-edge is equivalent to being incident with the central vertex. ​ Thus no unintended triangles affect which g's are optimal, so those g's are exactly the g's for which composing with log_-1 yields an optimal solution to the input 2-Lin(2) instance.

Your problem is obviously in W[P]O, and I have no other clue regarding its parameterized complexity.