誘導パス
無向グラフG中の誘導パスは， Gの誘導グラフかつ道であるグラフのことである． つまり，誘導パスは そのパス上で隣接している任意の頂点対はG中で隣接しており， かつ， 隣接していない任意の頂点対はG中で隣接していないような，G中の頂点の列である． 誘導パスは，スネークとも呼ばれ， 超立方体上の最長誘導パスを発見する問題は， en:Snake-in-the-box問題として知られている．
また， 誘導サイクルは， en:閉路をなすGの誘導グラフのことである． また，誘導サイクルは， コードレスサイクルや，その長さが4以上のとき，ホールとも呼ばれる． アンチホールは， Gの補グラフにおけるホールである．
グラフ中の最長誘導パスの長さは， そのグラフのう回路数と呼ばれる．[1] 任意のen:疎グラフに対して， う回路数が固定された時は，w:tree-depthが固定されている時と等価である． [2] グラフGの誘導パス数とは， グラフを分割するのに必要な最小の誘導パスの数である． [3] また， Gのパス被覆は，Gのすべての頂点を覆うために必要な誘導パスの最小数である． [4] グラフGの内周は， G中の最小のサイクルの長さであるが， そのサイクルは，誘導サイクルである． 同様に，奇内周は， グラフにおける奇数長の最短な誘導サイクルの長さのことである．
例
図は， 8個の頂点と12本の辺からなるグラフと， このグラフにおける長さ4の誘導パスの例である． 図の超立方体は， これより長い誘導パスを持たないが， 長さ6の誘導サイクルを持つ． 超立方体上の最長誘導パスまたは，最長誘導サイクルを求める問題は， en:Snake-in-the-box問題として知られており， 符号理論や工学分野で広く研究されている．
グラフクラスの特徴付け
多くの重要なグラフクラスは， 誘導パスや誘導サイクルの観点で特徴づけする事ができる．
- 長さ2の誘導パスを持たない連結グラフは，完全グラフであり，誘導サイクルを持たない連結グラフは，木である．
- en:Triange-free graphは，長さ3の誘導サイクルを持たないグラフである．
- en:Cographは，長さ3の誘導パスを持たないグラフである．
- en:Chordal graphは，長さ4以上の誘導サイクルを持たないグラフである．
- en:Even-hole-free graphは，偶数個の頂点からなる誘導サイクルを持たないグラフである．
- en:Trivially perfect graphは， 長さ3の誘導パスと長さ4の誘導サイクルのいずれも持たないグラフである．
- en:Strong perfect theoremにより， パーフェクトグラフは， 奇数長のホールとアンチホールを持たないグラフであることが知られている．
- en:Distance-hereditary graphは，すべての誘導パスが最短路であり，かつ，同じ端点を持つ任意の2つの誘導パスは，その長さが等しくなるようなグラフである．
- en:ブロックグラフは，任意の2つの頂点間に高々1つしか誘導パスがないグラフである．また，連結ブロックグラフは，任意の2つの頂点間にちょうど1つ誘導パスがあるグラフである．
アルゴリズム
グラフGとパラメタkが与えられたとき， Gが少なくとも長さkの誘導パスが存在するかを決定する問題は，NP完全である． この結果は，Mihalis Yannakakisの未発表の結果としてGarey & Johnson (1979)が紹介している． しかし，この問題はGが特定のグラフクラスであるときに， たとえば，asteroidal-triple-free graphs[5] や長いホールのないグラフ[6]であるときに， 多項式時間で解けることが知られている．
また，グラフ中の頂点が2つの誘導パスや誘導サイクルに分割できるかどうかを決定する問題も， NP完全であることが知られている．[7] その系として， グラフの誘導パス数を求める問題はNP困難であることがわかる．
最長誘導パスや最長誘導サイクルの近似アルゴリズムは， 次に与える還元から， 最大独立点集合を求める問題と関係があることがわかる．[8] n個の頂点からなる任意のグラフGに対して， 2n個の頂点からなる別のグラフHを次のように構築する: 2個の隣接頂点をもつ，かつ，一方がG中の頂点であるような， n(n − 1)/2個の頂点をGに加える． 次に， Gがk個の独立点集合を持つならば， その独立点集合の頂点をIと入れ替えることで， Hは，必ず長さ2kの誘導パスまたは誘導サイクルを持つことがわかる． 一方， Hが長さkの誘導パスまたは誘導サイクルを持つならば， これらのパスまたはサイクルから得られる隣接していない頂点の極大集合から， Gは，サイズが少なくともk/3の独立点集合を持つことがわかる． よって，Gの最大独立点集合のサイズは，Hの最大誘導パスと最大誘導サイクルのサイズの定数倍以内である． Håstad (1996)による独立点集合の近似不可能性の結果から， NP=ZPPでない限り， 最適解のO(n1/2-ε)以内の最長誘導パスまたは最長誘導サイクルを求める多項式時間アルゴリズムは存在しない．
n個の頂点とm個の辺からなるグラフのホールと，長さ5の誘導サイクルを含まないグラフのアンチホールは， O(n+m2)時間で求められる．[9]
アトミックサイクル
アトミックサイクルは，n-弦を1つも持たないサイクルであり， 誘導サイクルの一般化である． ここで， n-弦とは， 与えられたあるサイクルに対して， そのサイクル上のある2頂点を結ぶ結ぶ長さnの道である． ただし，nは，そのサイクルにおけるそれらの頂点の距離よりも小さい値である． もし，サイクルがn-弦を持たなければ， そのサイクルは，より小さなサイクルに分割することができないため， そのサイクルをアトミックサイクルと呼ぶ．[10] mをグラフGの辺の数とすると， G中のすべてのアトミックサイクルを列挙するのに必要な時間は， O(m2)である．
脚注
- ^ Buckley & Harary (1988).
- ^ Nešetřil & Ossona de Mendez (2012), Proposition 6.4, p. 122.
- ^ Chartrand et al. (1994).
- ^ Barioli, Fallat & Hogben (2004).
- ^ Kratsch, Müller & Todinca (2003).
- ^ Gavril (2002).
- ^ Le, Hoàng-Oanh, Le, Van Bang & Müller, Haiko (2003).
- ^ Berman & Schnitger (1992).
- ^ Nikolopoulos & Palios (2004).
- ^ Gashler & Martinez (2012).
参考文献
- Barioli, Francesco; Fallat, Shaun; Hogben, Leslie (2004). “Computation of minimal rank and path cover number for certain graphs”. Linear Algebra Appl. 392: 289–303. doi:10.1016/j.laa.2004.06.019.
- Berman, Piotr; Schnitger, Georg (1992). “On the complexity of approximating the independent set problem”. Information and Computation 96 (1): 77–94. doi:10.1016/0890-5401(92)90056-L.
- Buckley, Fred; Harary, Frank (1988). “On longest induced paths in graphs”. Chinese Quart. J. Math. 3 (3): 61–65.
- Chartrand, Gary; McCanna, Joseph; Sherwani, Naveed; Hossain, Moazzem; Hashmi, Jahangir (1994). “The induced path number of bipartite graphs”. Ars Combin. 37: 191–208.
- Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness.. W. H. Freeman. p. 196
- Gashler, Michael; Martinez, Tony (2012). “Robust manifold learning with CycleCut”. Connection Science 24 (1): 57–69. doi:10.1080/09540091.2012.664122.
- Gavril, Fănică (2002). “Algorithms for maximum weight induced paths”. Information Processing Letters 81 (4): 203–208. doi:10.1016/S0020-0190(01)00222-8.
- Håstad, Johan (1996). "Clique is hard to approximate within n1-ε". Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. pp. 627–636. doi:10.1109/SFCS.1996.548522。
- Kautz, W. H. (1958). “Unit-distance error-checking codes”. IRE Trans. Elect. Comput. 7: 177–180.
- Kratsch, Dieter; Müller, Haiko; Todinca, Ioan (2003). "Feedback vertex set and longest induced path on AT-free graphs". Graph-theoretic concepts in computer science. Berlin: Lecture Notes in Computer Science, Vol. 2880, Springer-Verlag. pp. 309–321. doi:10.1007/b93953。
- Le, Hoàng-Oanh; Le, Van Bang; Müller, Haiko (2003). “Splitting a graph into disjoint induced paths or cycles” (The Second International Colloquium "Journées de l'Informatique Messine", Metz, 2000). Discrete Appl. Math. 131 (1): 199–212. doi:10.1016/S0166-218X(02)00425-0.
- Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012). “Chapter 6. Bounded height trees and tree-depth”. Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics. 28. Heidelberg: Springer. pp. 115–144. doi:10.1007/978-3-642-27875-4. ISBN 978-3-642-27874-7. MR2920058
- Nikolopoulos, Stavros D.; Palios, Leonidas (2004). "Hole and antihole detection in graphs". Proc. 15th ACM-SIAM Symposium on Discrete Algorithms. pp. 850–859..