MAX DICUT

Definition. MAX DICUT = MAXimum DIrected CUT: 给定有向图 G = (V, E), 找节点划分 (A, B) (即 k=2 二分) 最大化有向 cut \sum_{u \in A, v \in B, u \rightsquigarrow v} w(u,v)。等价于 Laenen-Sun 2020 flow ratio 在 k=2 时的退化。

复杂度

• NP-hard (Karp 1972)
• 0.878-近似: Goemans & Williamson (J. ACM 1995) 用 SDP relaxation + randomized rounding 在 MAX DICUT / MAX CUT 上达到 0.878 的近似比。
• 在有向图上, 0.858 简单近似也可达到 (Trevisan 1998); 0.874 via 更复杂 SDP。

与 Laenen-Sun 2020 的关系

当 k=2 时, flow ratio: \Phi_G(S_0, S_1) = \frac{w(S_1, S_0)}{\text{vol}(S_0) + \text{vol}(S_1)} + \frac{w(S_0, S_1)}{\text{vol}(S_1) + \text{vol}(S_0)} 仍等价于 MAX DICUT (NP-hard)。这意味着 Laenen-Sun 的 chain flow ratio 在 k=2 时无多项式精确解, 必须用 Hermitian Laplacian 的谱松弛 (近似保证由 Theorem 4.4 提供)。

邻近概念

• Flow Ratio (chain objective) — Laenen-Sun 链式目标
• Hermitian Laplacian — 谱松弛方案
• Hermitian Spectral Clustering — 父类

起源 / 标准文献

• Karp (1972) "Reducibility among combinatorial problems" — NP-hardness
• Goemans & Williamson (1995) J. ACM — 0.878 SDP 近似
• Laenen & Sun (NeurIPS 2020) — k=2 退化分析 (本 wiki 摘要)

Open Questions

• 对有向图 + 边权有噪声 的 MAX DICUT 鲁棒近似?
• MAX DICUT 的 quantum 近似算法 (e.g., 量子 SDP)?