关于一般图与三分图中最小三角形问题等价性的技术问询

Hey folks, I've been working through a graph theory textbook and ran into a claim about simplifying the minimum weighted triangle problem that I want to unpack. Let me start by laying out the core problem clearly.

原问题：最小加权三角形 #

Given a weighted directed graph $G = (V, E, w)$ with $|V| = n$ and edge weights $w : E \to { -n^c, \ldots, n^c }$ for some $c > 0$, our goal is to find the minimum weighted triangle:
$$\min_{(i,j,k)} w(i, j) + w(j, k) + w(k, i)$$
where $(i,j,k)$ are distinct nodes ($i \neq j, j \neq k, i \neq k$) forming a directed triangle.

教材中的简化假设 #

The textbook states that we can assume without loss of generality that $G$ is a 3-partite directed graph with partitions $I, J, K$, satisfying:

• No edges exist within any partition (meaning no edges from $I$ to $I$, $J$ to $J$, or $K$ to $K$)
• All edges only go in the directions $I \to J$, $J \to K$, and $K \to I$

为什么这个简化是合理的？ #

Here's the key reasoning behind this equivalence that I've pieced together: we can transform any general directed graph into such a 3-partite graph while perfectly preserving the weight of every possible triangle, and vice versa. Here's how the transformation works:

• For each original node $v \in V$, create three copies: $v_I$ in partition $I$, $v_J$ in $J$, and $v_K$ in $K$.
• For every original edge $u \to v$ with weight $w(u,v)$, we add three directed edges in the 3-partite graph:
  • $u_I \to v_J$ with weight $w(u,v)$
  • $u_J \to v_K$ with weight $w(u,v)$
  • $u_K \to v_I$ with weight $w(u,v)$
• Now, any triangle in the original graph $(i \to j, j \to k, k \to i)$ corresponds exactly to a triangle in the 3-partite graph: $i_I \to j_J \to k_K \to i_I$, with the exact same total weight.
• Conversely, any valid triangle in the 3-partite graph has to cross all three partitions (since there are no intra-partition edges), so it directly maps back to a triangle in the original graph with the same weight.

This transformation guarantees that the minimum weighted triangle in the original graph is identical to the one in the 3-partite version. That's why the textbook says we can make this assumption— it doesn't change the problem's outcome, but it can simplify later analysis or algorithm design by restricting the graph structure we need to consider.

I'm double-checking to make sure I fully grasp every detail of this equivalence, so if anyone has clarifications or additional insights to share, I'd really appreciate it!

备注：内容来源于stack exchange，提问作者ninaPh99