Efficient reversal of transductions of sparse graph classes

技術要約：疎なグラフクラスの転置（Transduction）の効率的な逆転

問題提起
本論文は、疎なグラフクラスにおける一次（first-order）転置を「逆転」させるというアルゴリズム上の課題に取り組んでいる。一次転置とは、頂点のコピー、それらへの色の付与、および一次論理式を用いた新たな隣接関係の定義を通じて、グラフ $H$ をグラフ $G$ へと変換する一般的な操作である。ソースグラフ $H$ が良好な性質を持つ疎なクラス（例：有界拡大）に属する場合、結果として得られるグラフ $G$ も有用な構造的特性を保持することは確立されているが、逆問題、すなわち $G$ が $\mathcal{D}$ という疎なクラスから転置されたことが既知のクラス $\mathcal{C}$ のグラフであるとき、一回的な一次解釈（first-order interpretation）を通じて $G$ を復元できるような「疎な」表現 $H \in \mathcal{D}$ を効率的に計算できるか、という問題は依然として困難である。

先行研究では、構造的に有界な次数、パス幅、または木幅を持つ特定のサブクラスに対して、多項式時間の疎化（sparsification）手順が確立されていた。しかし、構造的に有界な拡大（有界拡大のクラスから転置されたクラス）を持つより広範なグラフクラスについては、標準的なテンプレートに従う効率的な疎化手順は知られていなかった。これらのクラスに対する既存の手法は、効率性に欠けるか、あるいは最近のモナディック安定（monadically stable）クラスに関する研究のように、出力が「ほとんどどこでも稠密ではない（almost nowhere dense）」だけであり、堅牢なアルゴリズム的応用に必要な構造的パラメータ（弱彩色数など）の定数的な境界を保証できないものであった。

手法
著者らは、固有の線形近傍複雑性を持つ任意のモナディック安定クラスの入力グラフ $G$ に対して、疎な表現 $H$ を構築する新しいアルゴリズム的フレームワークを提案している。この手法は、以下の3つの核心的な技術的コンポーネントに基づいている。

1. 二部グラフへの還元: アルゴリズムはまず、後続のステップが二部グラフの設定内で動作できるように、入力グラフ $G$ を、損失なく二部グラフ $G'$ へと変換する。
2. ニア・ツイン（Near-Twins）による反復的分岐: 中核となる技術的貢献は、二部グラフの「分岐（branching）」を効率的に計算する新しい補題（補題12）である。これは、二部グラフの一方の側を集合 $P_i$ に分割し、各 $P_i$ がもう一方の側の特定の「リーダー」頂点 $\ell_i$ によって支配されるようにするものである。決定的なのは、非支配側のすべての頂点が、高々定数個の集合 $k^*$ 内に隣接関係を持つことである。これは、Hausslerのパッキング補題と、ハーフグラフフリー（half-graph-free）グラフにおけるニア・ツイン（近接する隣接関係を持つ頂点）の推移性を利用して達成される。
3. 木構造の構築（疎化）: 分岐補題を用いて、アルゴリズムは根付き木 $T$ を再帰的に構築する。木の各ノード $p$ において、アルゴリズムは現在のグラフの誘導部分グラフまたはその補グラフである部分グラフ $G(p)$ を関連付ける。アルゴリズムは $G(p)$ の左または右の分岐を計算し、各分岐に対して木の子供を作成し、その分岐の二部補グラフを子ノードに割り当てる。このプロセスは、誘導部分グラフとその補グラフの間で交互に行われ、これにより、2ステップごとに「ラダー指数（ladder index）」（最大の誘導ハーフグラフのサイズ）を実質的に減少させる。入力クラスはモナディック安定であるため、ラダー指数は有界であり、これにより木 $T$ の高さが保証される。

最終的な出力グラフ $H$ は、元のグラフ $G$ の頂点（内部エッジなし）と、木 $T$ のノードとを結びつけたものである。頂点 $v \in V(G)$ は、頂点 $p \in T$ に接続される。これは、$v$ が $p$ に関連付けられた部分グラフに含まれる場合に限られる。

主要な貢献と結果
本論文は以下の主要な結果（定理1）を確立している。

• メイン定理: モナディック安定かつ固有の線形近傍複雑性を持つ任意のグラフクラス $\mathcal{C}$ に対して、グラフ $G \in \mathcal{C}$ を与えられたとき、固定された一次解釈を通じて $G$ を復元できるような、クラス $\mathcal{D}$（有界拡大のクラス）に属する彩色グラフ $H$ を計算する $O(n^4)$ 時間のアルゴリズムが存在する。
• 構造的に有界な拡大の特性付け: 著者らは、モナディック安定であることと固有の線形近傍複雑性を持つことは、構造的に有界な拡大を持つことと同値であることを証明した。これにより、これらのクラスに関する構造的特性付けに関する未解決問題が解決された。
• マージ幅（Merge-Width）に関する系: 本論文はさらに、これらの特性を「マージ幅」へと結びつけ、あるクラスが構造的に有界な拡大を持つための必要十分条件は、モナディック安定であり、かつ有界なマージ幅を持つことであることを示している。
• アルゴリズム的含意: この $O(n^4)$ の前処理により、構造的に有界な拡大クラスにおける一次（FO）モデル検査問題を、有界拡大クラスの設定へと還元することが可能になる。これにより、有界拡大クラスで知られている高度なアルゴリズム的結果（定数遅延列挙、解の計数、およびFOクエリのための動的データ構造など）を、より広範な構造的に有界な拡大グラフへと転用することが可能になる。
• 性質の保存: 疎化されたクラス $\mathcal{D}$ は、転置の下で閉じている性質を継承する。例えば、$\mathcal{C}$ が有界線形クリーク幅（bounded linear cliquewidth）を持つ場合、得られる $\mathcal{D}$ は有界パス幅を持つ。また、$\mathcal{C}$ が有界ツイン幅（bounded twin-width）を持つ場合、$\mathcal{D}$ は有界疎ツイン幅（bounded sparse twin-width）を持つ。

意義
本論文は、Gajarskýら [17] によって提起された、構造的に有界な拡大クラスのための効率的な疎化手順の存在に関する重要な未解決問題に回答するものである。以前のアプローチは、より弱い構造的保証（劣多項式的な境界）しか提供できなかったり、より狭いサブクラスに限定されたりしていたのに対し、本研究は、出力が有界拡大のクラスに属することを保証する手順を提供する。この区別は極めて重要である。なぜなら、有界拡大クラスは、一般的なモナディック安定クラスでは現在利用できない量化消去（quantifier elimination）やその他の強力なアルゴリズム的ツールを許容するためである。

著者らは、彼らの手法が自己完結的であり、先行研究で使用された複雑な「Flipper game」の仕組みを避け、主要な補題（補題12）と基本的なハーフグラフの議論を直接適用することに基づいていることを強調している。この結果は、疎なグラフの構造理論とアルゴリズムの効率性を統合し、モナディック安定かつ線形近傍複雑性を持つクラスの構造的特性が、有界拡大への効率的な疎化を保証するのに十分であることを示している。