技術的概要：4 円グラフを持たないグラフのスター被覆に関する最適化問題

問題定義

本論文は、対称非負行列の三乗分解（$A = BCB^\top$）の研究に動機づけられたパラメータである SNT-ランク（対称非負三乗分解ランク）をグラフに対して調査する。グラフ $G$ の SNT-ランク、$st^+(G)$ と表記されるものは、$G$ の支持パターンと一致する任意の対称非負行列を表現するために必要な非負因子行列 $B$ の列数の最小値として定義される。

本論文は、グラフのギャップ $gap(G) = |V(G)| - st^+(G)$ に焦点を当てる。ここで扱われる主要な最適化問題は、特定の種類のグラフ被覆である「集合結合被覆（set-join cover）」において必要な成分の数を最小化することである。従来のスター被覆問題がしばしばスターの総数を最小化するのに対し、本研究では被覆に使用される「成分（頂点集合）」の数を最小化する。

本研究は、特定の禁止部分グラフ（具体的には、論文の図 2 に示される閉じた 4-歩行に対応する $C_4$、$C_3^\circ$、および $P_{2}^{\circ,\circ}$）を含まないグラフの族 $\mathcal{G}_{\square \times}$ に制限されている。この族に属するグラフにおいて、集合結合被覆は「スター被覆」に簡略化され、ここで各成分は、一連の隣接頂点に結合された単一の頂点となる。

手法

著者らは、$\mathcal{G}_{\square \times}$ に属するグラフのギャップを計算するための多段階アルゴリズム的アプローチを開発した。

1. 重み付き多重グラフへの変換:
   著者らは、単純グラフ $G \in \mathcal{G}_{\square \times}$ を重み付き多重グラフ $\Gamma$ に変換する写像 $\kappa(G)$ を定義する。

   • $\Gamma$ の頂点は、$G$ の次数 2 以外の頂点に対応する。
   • $\Gamma$ の辺は、これらの頂点間の $G$ 内の経路を表す。
   • 辺の重みは二項的（0 または 1）であり、$G$ 内の経路長の偶奇を表す（偶数経路は重み 0、奇数経路は重み 1 に写像される）。
   • この変換の下でギャップは保存される：$gap(G) = gap^*(\kappa(G))$。ここで $gap^*$ は多重グラフに対して定義されたギャップである。

2. 簡約操作（$\tau$）:
   一連の操作が導入され、ギャップを保存しつつ（加法定数まで）重み付き多重グラフ $\Gamma$ をより単純な形に簡約する。これらの操作には以下が含まれる。

   • 頂点除去（$\Gamma - v$）: 接続されたループと葉を考慮した特殊な頂点除去。
   • 葉と次数 2 の除去: 葉と次数 2 の頂点を除去し、結果として生じる経路を適切な重みの単一の辺に置き換える。
   • 辺の縮約: 重み 1 の辺を縮約し、重み 0 の平行辺を除去する。
   • 成分の集約（$\tau_1, \tau_2, \tau_3$）:
     • $\tau_1$ は「1-成分」内の重み 1 の辺の全域木を縮約し、冗長な頂点の数（$t_1$）を記録する。
     • $\tau_2$ は葉とその隣接頂点を除去し、その数（$t_2$）を記録する。
     • $\tau_3$ は次数 0 の頂点を除去し、グラフを単純な形に再写像する。
   • アルゴリズムは、安定した簡約多重グラフ $\tau(\Gamma)$ に到達するまでこれらの操作を反復適用する。総ギャップは、簡約グラフのギャップと累積された数（$t(\Gamma)$）の和である。

3. 簡約グラフに対する帰納的頂点除去:
   最終的な簡約グラフ $\tau(\Gamma)$（次数 0 または次数 2 の頂点を持たず、重み 0 の辺のみを持つ）に対して、著者らは頂点除去に基づく帰納的手法を採用する。

   • 彼らは $gap^*(\Gamma) = \max\{0, \max_{v \in V(\Gamma)} (gap^*(\Gamma(v)) - 1)\}$ が成り立つことを確立する。
   • これにより、頂点を再帰的に除去し、結果として生じる部分グラフを分析することでギャップを計算できる。

主要な貢献と結果

• スター被覆の特性化: 本論文は、$\mathcal{G}_{\square \times}$ に属するグラフにおいて、任意の最適集合結合被覆が「ABC 被覆」であることを証明する。ここで、頂点は被覆における役割に基づいて 3 種類（A、B、C）に分類される。この構造的洞察は、最適化問題を著しく簡素化する。
• SNT-ランクのアルゴリズム的計算: 著者らは、$\mathcal{G}_{\square \times}$ に属する任意のグラフの SNT-ランク（したがってギャップ）を決定する構成アルゴリズムを提供する。このアルゴリズムは、問題を小さく単純化された多重グラフのギャップを計算することに帰着させる。
• 特定の族に対する厳密な公式:
  • 完全グラフ（$K_n$）: 全ての $n$ に対して $gap^*(K_n) = 0$。
  • 完全二部グラフ（$K_{m,n}$）: $gap^*(K_{m,n}) = |m - n|$。
  • ペーターセングラフ: ギャップは 0 として計算される。
  • クローバーグラフ: 中心頂点に様々な垂れ下がりのサイクルを持つグラフに対して公式が導出される。
• 限界と複雑性:
  • 本論文は、独立数 $\alpha(\Gamma)$ に基づく $gap^*$ の下限を確立する：$gap^*(\Gamma) \ge 2\alpha(\Gamma) - |V(\Gamma)|$。
  • この限界は、特定のグラフに対しては任意に緩いものであることが示される。
  • 本論文は、簡約アルゴリズムは効率的であるが、頂点除去による簡約グラフのギャップの計算という最終段階は高い計算複雑性を持つことを指摘している。ただし、このクラスに属する任意のグラフに対して解を保証するものである。

意義と主張

本論文は、対称非負行列の三乗分解の研究から自然に生じる組合せ最適化問題を解決すると主張している。定義域を 4 円グラフ（および関連する禁止部分グラフ）を持たないグラフに制限することで、著者らは SNT-ランクを決定するという複雑な問題が実行可能になることを示している。

その意義は以下の点にある。

1. 行列理論とグラフ理論の架け橋: 本作業は、スター被覆を通じて SNT-ランクの具体的な組合せ的解釈を提供し、行列分解のランクをグラフの構造的パラメータと結びつける。
2. アルゴリズム的解決: 理論的な限界を超えて厳密な計算へと進むため、非自明なクラスのグラフに対する SNT-ランクを計算する決定的な手法を提供する。
3. 構造的洞察: 「ABC 被覆」の導入と重み付き多重グラフへの簡約は、グラフ被覆と経路の偶奇および頂点次数との関係を分析するための新たな道具を提供する。

著者らは謙虚なトーンを維持しており、一般的な問題（$\mathcal{G}_{\square \times}$ 以外のグラフに対するもの）は依然として困難であり、簡約グラフに対する彼らの手法は厳密であるものの高い計算複雑性を伴うことを認めている。彼らは行列分解とグラフ被覆の文脈を超えて新たな応用を提案するものではないが、この特定のグラフ族に対するギャップの特性化の理論的価値を強調している。