和音補完

数学の一分野であるグラフ理論において、与えられた無向グラフ $Gの$ 弦完備化とは、同じ頂点集合上にあり、 $G を$ 部分グラフとして持つ弦グラフのことである。最小弦完備化とは、辺を削除して形成されるグラフが弦完備化ではなくなるような弦完備化である。最小弦完備化とは、可能な限り辺の少ない弦完備化である。

異なるタイプの弦補完、つまり結果の弦グラフの最大クリークのサイズを最小化する補完を使用して、 $G$ のツリー幅を定義できます。弦補完は、 AT フリーグラフ、クローフリーAT フリーグラフ、コグラフなど、他のいくつかのグラフクラスを特徴付けるためにも使用できます。

最小弦補完は、1979 年の書籍「Computers and Intractability」で複雑性が未解決とされた 12 の計算問題のうちの 1 つです。弦補完の応用には、疎対称行列でガウス消去法を実行するときにフィルインを最小化する問題のモデル化や、系統樹の再構築などがあります。

グラフの弦完備化は三角形分割と呼ばれることもありますが^[1]、この用語はグラフ理論の文脈においても曖昧であり、最大平面グラフを指すこともあります。

アプリケーション

Computers and Intractabilityで説明されている弦補完の元々の応用には、疎行列のガウス消去法が含まれます。ガウス消去法のプロセスでは、最初はゼロであったが後に非ゼロになる行列の係数であるフィルインを最小化することが望まれます。これは、これらの係数の値を計算する必要があるためにアルゴリズムが遅くなるためです。疎対称行列の非ゼロのパターンは、無向グラフ (行列を隣接行列として持つ) で記述できます。フィルインされた行列の非ゼロのパターンは常に弦グラフであり、任意の最小弦補完はこのようにフィルインパターンに対応します。グラフの弦補完が与えられた場合、結果として得られる弦グラフの消去順序を計算することによって、このフィルインパターンを実現するためにガウス消去法を実行する一連の手順を見つけることができます。このように、最小フィルイン問題は、最小弦補完問題と同等と見なすことができます。^[4]この応用では、2次元有限要素システムの解法で平面グラフが出現することがある。平面分離定理から $、$ $n$ 頂点を持つすべての平面グラフは最大で $O$ $($ $nlogn$ $)辺を持つ弦完備$ $性$ を持つことが分かる。^[5]

もう 1 つの応用は、系統発生、つまり進化の樹木を再構築する問題から来ています。たとえば、遺伝子変異の影響を受ける生物の樹木や、筆写者の誤りの影響を受ける古代の写本のセットの樹木などです。遺伝子変異や筆写者の誤りはそれぞれ 1 回だけ発生すると仮定すると、完全な系統発生、つまり特定の特性を持つ種または写本が常に接続したサブツリーを形成する樹木が得られます。Buneman (1974) が説明しているように、完全な系統発生の存在は、弦補完問題としてモデル化できます。頂点が属性値 (種または写本のある特性の特定の選択) であり、辺が少なくとも 1 つの種によって共有される属性値のペアを表す「オーバーラップグラフ」 $G を$ 描画します。グラフの頂点は、各属性値の由来となる特性のアイデンティティによって色分けすることができ、色の総数は系統樹を導くために使用された特性の数と等しくなります。そして、 $Gが$ 色分けを尊重する弦完備性を持つ場合にのみ、完全な系統樹が存在します。^[6]

計算の複雑さ

1979 年の書籍Computers and Intractabilityでは未解決問題として挙げられていたものの、^{[7]最小弦補完問題 (}最小フィルイン問題とも呼ばれる) の計算複雑性はすぐに解決されました。Yannakakis (1981) はそれがNP 完全であることを示しました。^[8]最小弦補完がグラフ $Gに$ $k$ 本の辺を追加する場合、最大で $8$ $k$ $2 個$ の追加された辺を使用して多項式時間で弦補完を見つけることが可能です。^{[9]追加する} $k$ 本の辺の最適なセットを見つける問題は、固定パラメータの扱いやすいアルゴリズムによって、グラフサイズに対して多項式時間で、 $k$ に対して指数関数的に解くこともできます。^[10]

木幅（弦補完の最小クリークサイズ）とパス幅や木の深さなどの関連パラメータもNP完全で計算可能であり、（P=NPでない限り）最適値の定数倍以内で多項式時間で近似することはできない。しかし、対数近似比を持つ近似アルゴリズムが知られている。 ^[11]

最小充填問題と木幅問題はどちらも指数時間で解くことができます。より正確には、 $n$ 頂点グラフの場合、時間は $O （1.9601 n ）$ です。^[12]

参考文献

^ ab Parra, Andreas; Scheffler, Petra (1997)、「弦グラフ埋め込みの特性とアルゴリズム的応用」、第 4 回 Twente グラフおよび組み合わせ最適化ワークショップ (Enschede、1995)、離散応用数学、79 (1–3): 171–188、doi :10.1016/S0166-218X(97)00041-3、MR 1478250。
^ Kaplan, Haim; Shamir, Ron (1996)、「小さなクリークを持つ適切な区間グラフへのパス幅、帯域幅、および完了問題」、SIAM Journal on Computing、25 (3): 540–561、doi :10.1137/S0097539793258143、MR 1390027。
^ Eppstein, David (2012年11月15日)、グラフパラメータとスーパーグラフのクリーク。
^ ローズ、ドナルド J. (1972)、「スパース正定値線形方程式の数値解のグラフ理論的研究」、グラフ理論とコンピューティング、アカデミックプレス、ニューヨーク、pp. 183–217、MR 0341833。
^ Chung, FRK ; Mumford, David (1994)、「平面グラフの弦補完」、Journal of Combinatorial Theory、シリーズ B、62 (1): 96–106、doi : 10.1006/jctb.1994.1056、MR 1290632。
^ ブネマン、ピーター（1974）、「剛性回路グラフの特徴づけ」、離散数学、9（3）：205–212、doi：10.1016/0012-365X（74）90002-8、MR 0357218。
^ ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)。コンピュータとイントラクタビリティ：NP完全性理論ガイド。数学科学シリーズ（第1版）。ニューヨーク：WHフリーマンアンドカンパニー。ISBN 9780716710455. MR 0519066. OCLC 247570676.、[OPEN4]、p. 286; 更新、p. 339。
^ Yannakakis, Mihalis (1981)、「最小フィルインの計算はNP完全である」、SIAM Journal on Algebraic and Discrete Methods、2 (1): 77–79、CiteSeerX 10.1.1.128.192、doi :10.1137/0602010、hdl :10338.dmlcz/140775、MR 0604513 。
^ Natanzon, Assaf; Shamir, Ron; Sharan, Roded (2000)、「最小充填問題に対する多項式近似アルゴリズム」、SIAM Journal on Computing、30 (4): 1067–1079、doi :10.1137/S0097539798336073、MR 1786752。
^ Fomin, Fedor V.; Villanger, Yngve (2013)、「最小フィルインのための準指数パラメータ化アルゴリズム」、SIAM Journal on Computing、42 (6): 2197–2216、arXiv : 1104.2230、doi :10.1137/11085390X、MR 3138120。
^ ハンス・L・ボドレンダー;ギルバート、ジョン R.ハフスタインソン、ヤールムティール。 Kloks, Ton (1995)、「ツリー幅、パス幅、フロントサイズ、および最短エリミネーションツリーの概算」、Journal of Algorithms、18 (2): 238–255、doi :10.1006/jagm.1995.1009、MR 1317666。
^ Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan (2004)、「ツリー幅と最小フィルインのための正確な（指数）アルゴリズム」、オートマタ、言語とプログラミング：第31回国際コロキウム、ICALP 2004、フィンランド、トゥルク、2004年7月12日～16日、議事録、コンピュータサイエンスの講義ノート、vol. 3142、Springer-Verlag、pp. 568～580、doi :10.1007/978-3-540-27836-8_49。

[ps97-1] Parra, Andreas; Scheffler, Petra (1997)、「弦グラフ埋め込みの特性とアルゴリズム的応用」、第 4 回 Twente グラフおよび組み合わせ最適化ワークショップ (Enschede、1995)、離散応用数学、79 (1–3): 171–188、doi :10.1016/S0166-218X(97)00041-3、MR 1478250。

[2] Kaplan, Haim; Shamir, Ron (1996)、「小さなクリークを持つ適切な区間グラフへのパス幅、帯域幅、および完了問題」、SIAM Journal on Computing、25 (3): 540–561、doi :10.1137/S0097539793258143、MR 1390027。

[3] Eppstein, David (2012年11月15日)、グラフパラメータとスーパーグラフのクリーク。

[4] ローズ、ドナルド J. (1972)、「スパース正定値線形方程式の数値解のグラフ理論的研究」、グラフ理論とコンピューティング、アカデミックプレス、ニューヨーク、pp. 183–217、MR 0341833。

[5] Chung, FRK ; Mumford, David (1994)、「平面グラフの弦補完」、Journal of Combinatorial Theory、シリーズ B、62 (1): 96–106、doi : 10.1006/jctb.1994.1056、MR 1290632。

[6] ブネマン、ピーター（1974）、「剛性回路グラフの特徴づけ」、離散数学、9（3）：205–212、doi：10.1016/0012-365X（74）90002-8、MR 0357218。

[7] ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)。コンピュータとイントラクタビリティ：NP完全性理論ガイド。数学科学シリーズ（第1版）。ニューヨーク：WHフリーマンアンドカンパニー。ISBN 9780716710455. MR 0519066. OCLC 247570676.、[OPEN4]、p. 286; 更新、p. 339。

[8] Yannakakis, Mihalis (1981)、「最小フィルインの計算はNP完全である」、SIAM Journal on Algebraic and Discrete Methods、2 (1): 77–79、CiteSeerX 10.1.1.128.192、doi :10.1137/0602010、hdl :10338.dmlcz/140775、MR 0604513 。

[9] Natanzon, Assaf; Shamir, Ron; Sharan, Roded (2000)、「最小充填問題に対する多項式近似アルゴリズム」、SIAM Journal on Computing、30 (4): 1067–1079、doi :10.1137/S0097539798336073、MR 1786752。

[10] Fomin, Fedor V.; Villanger, Yngve (2013)、「最小フィルインのための準指数パラメータ化アルゴリズム」、SIAM Journal on Computing、42 (6): 2197–2216、arXiv : 1104.2230、doi :10.1137/11085390X、MR 3138120。

[11] ハンス・L・ボドレンダー;ギルバート、ジョン R.ハフスタインソン、ヤールムティール。 Kloks, Ton (1995)、「ツリー幅、パス幅、フロントサイズ、および最短エリミネーションツリーの概算」、Journal of Algorithms、18 (2): 238–255、doi :10.1006/jagm.1995.1009、MR 1317666。

[12] Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan (2004)、「ツリー幅と最小フィルインのための正確な（指数）アルゴリズム」、オートマタ、言語とプログラミング：第31回国際コロキウム、ICALP 2004、フィンランド、トゥルク、2004年7月12日～16日、議事録、コンピュータサイエンスの講義ノート、vol. 3142、Springer-Verlag、pp. 568～580、doi :10.1007/978-3-540-27836-8_49。

関連グラフファミリー

アプリケーション

計算の複雑さ

参考文献