グラフサンドイッチ問題

グラフ理論とコンピュータサイエンスにおいて、グラフサンドイッチ問題とは、特定のグラフファミリーに属し、2 つの他のグラフに「挟まれている」グラフを見つける問題であり、そのうちの 1 つは目的のグラフのサブグラフで、もう 1 つは目的のグラフのスーパーグラフである必要があります。

グラフサンドイッチ問題は、与えられたグラフがグラフの族に属するかどうかをテストする問題を一般化したものであり、その応用と認識問題の自然な一般化として注目を集めています。^[1]

より正確には、頂点集合V、必須の辺集合E ¹、およびより大きな辺集合E ²が与えられたとき、グラフG  = ( V ,  E ) は、 E 1 ⊆ E ⊆ E ^{2のとき、} G ¹  = ( V ,  E ¹ )、G ²  = ( V ,  E ² ) のペアに対して サンドイッチグラフと呼ばれます。特性 Π のグラフサンドイッチ問題は次のように定義されます: ^{[ 2] [3]}

特性Πのグラフサンドイッチ問題:

インスタンス:頂点集合Vと辺集合E ¹ ⊆ E ² ⊆ V × V。

質問: E ¹ ⊆ E ⊆ E ^2かつGが性質 Π を満たすようなグラフG = ( V , E ) は存在しますか?

グラフのクラス（プロパティ Π を満たすもの）の認識問題は、E 1 = E 2 、つまりオプションのエッジ セットが空である特定 のグラフサンドイッチ^問題 と 同等^です。

グラフサンドイッチ問題は、Π が弦グラフ、比較グラフ、順列グラフ、弦二部グラフ、または連鎖グラフのいずれかの性質を持つ場合、 NP完全である。^{[2] [4]}この問題に対しては、分割グラフ、^{[2] [5]}閾値グラフ、^{[2] [5]}および 5 頂点ごとに最大で 1 つの 4 頂点誘導パスが含まれるグラフに対して多項式時間で解くことができる。^{[6] 4 頂点グラフ}Hのそれぞれに対して、Hフリーグラフサンドイッチ問題 の計算量も解決されている。^[7]

• ダンタス、シモーネ。デ・フィゲイレド、セリーナ・MH。ダ・シルバ、ムリロVG。 Teixeira、Rafael B. (2011)、「禁止された誘導サブグラフ サンドイッチ問題について」、離散応用数学、159 (16): 1717–1725、doi : 10.1016/j.dam.2010.11.010。