Semitotal domination in unit disk graphs

技術要約：単位円盤グラフにおける半全域支配

問題定義
本論文は、**単位円盤グラフ（Unit Disk Graphs: UDGs）における最小半全域支配問題（Minimum Semitotal Domination problem）を扱う。グラフ $G=(V, E)$ において、集合 $S \subseteq V$ が以下の2つの条件を満たすとき、それは半全域支配集合（semitotal dominating set: STDS）**であると定義される：

1. 支配条件： $V \setminus S$ のすべての頂点は、$S$ の少なくとも1つの頂点と隣接している。
2. 半全域条件： $S$ のすべての頂点は、他の $S$ の頂点から距離2以内に存在する。

目的は、最小の基数を持つSTDSを見つけることであり、これを半全域支配数 $\gamma_{t2}(G)$ と表記する。この問題の決定版は、UDGsにおいてNP完全であることが知られている。本論文は、グラフの隣接構造を通じてグラフが提供され、明示的な幾何学的座標は利用できないグラフベースの入力モデルの下で動作する。

手法
著者らは、半全域条件を満たす極大独立集合（MIS）を構築する決定論的な5因子近似アルゴリズム（Algorithm 1）を提案している。その手法は、以下の構造的アプローチに基づいている：

1. 幅優先探索（BFS）による階層化： アルゴリズムは任意の根 $r$ を選択し、BFS木（$T_{BFS}$）を構築する。頂点集合 $V$ は、層 $L_0, L_1, \dots, L_R$ に分割される。ここで $L_i$ は、根からの距離が $i$ である頂点を含む。
2. 貪欲な構築：
   • アルゴリズムは、根 $r$ を解集合 $S$ に初期値として追加する。
   • 層を非減少順序（$i$ を 2 から $R$ まで）で処理する。
   • 各層について、未支配の頂点から残りの頂点 $v$ を反復的に選択し、$v$ を $S$ に加え、$v$ の閉近傍を候補集合から削除する。
   • このプロセスは、すべての頂点が $S$ に含まれるか、あるいは $S$ によって支配されるまで継続される。
3. 特殊なケースの処理： 最大距離 $R=1$ の場合、アルゴリズムは根とその隣接する任意の1つの頂点を選択する。これは最適であることが証明されている。

主な貢献と結果

• 近似保証： 著者らは、アルゴリズムによって返される集合 $S$ のサイズが $|S| \le 5 \cdot \gamma_{t2}(G)$ を満たすことを証明している。これは、任意のUDGにおいて、極大独立集合のサイズは支配数 $\gamma(G)$ の最大5倍であるという既知の補題を利用することで達成される。$\gamma(G) \le \gamma_{t2}(G)$ であるため、5近似が成立する。
• 正当性： 著者らは、構築された集合 $S$ が極大独立集合（したがって支配集合でもある）であるだけでなく、半全域条件も満たすことを示している。具体的には、層ごとの処理により、選択されたすべての頂点が距離2以内の「パートナー」を持つことが保証される（$L_2$ の頂点については根が、$i \ge 3$ の頂点については同一または前の層の頂点がパートナーとなる）。
• 計算量： アルゴリズムの実行時間は $O(n + m)$ である。ここで $n$ は頂点数、$m$ はエッジ数である。最悪の場合、これは $O(n^2)$ となる。

意義と主張
本論文は、グラフベースの入力モデルにおける単位円盤グラフの最小半全域支配問題において、最先端の技術を改善したと主張している。具体的には：

• 近似因子を、Henningらによって達成された 5.75 から 5 へと改善した。
• 実行時間を $O(n^3)$ から $O(n+m)$ へと短縮した。
• 本研究は、幾何学的座標を必要とせず、グラフの連結性のみが既知であるシナリオにも適した、より効率的でタイトな近似境界を提供している。

著者らは、この問題が一般のグラフや制限されたクラス（平面グラフ、スプリットグラフ、弦二部グラフ）においてNP完全であり、幾何学的モデルでは以前に6因子近似で解決されていたことに触れているが、本研究はグラフベースのモデルにおいて、既知の最高の決定論的近似を提供している。