Gráfszendvics-probléma

A matematika, azon belül a gráfelmélet, valamint a számítástudomány területén a gráfszendvics-probléma (graph sandwich problem) azon gráf megkeresésének a problémája, ami egy bizonyos gráfcsaládba tartozik és két másik gráf „szendvics”-ként közrefogja; az egyik a keresett gráf részgráfja, a másiknak pedig a keresett gráf a részgráfja..

A gráfszendvics-problémák az adott gráf valamely gráfcsaládba tartozása tesztelésének problémáját általánosítják, érdekességüket alkalmazási lehetőségeik mellett az adja, hogy felismerési problémák általánosításaként tekinthetők.^[1]

A particionált próbagráf-osztályok felismerési problémája a gráfszendvics-probléma alesetének tekinthető.^[2]

Problémafelvetés

Precízebben, vegyünk egy V csúcshalmazt, az E¹ kötelező élhalmazt és a nagyobb E² élhalmazt, ekkor a G = (V, E) gráfot akkor nevezzük a G¹ = (V, E¹), G² = (V, E²) pár „szendvicsgráfjának”, ha E¹ ⊆ E ⊆ E².

A Π tulajdonságra vonatkozó gráfszendvics-probléma a következőképp határozható meg:^[3][4]

Gráfszendvics-probléma a Π tulajdonságra:

Példány: V csúcshalmaz, E¹ és E² élhalmazok, melyekre igaz, hogy E¹ ⊆ E² ⊆ V × V.

Kérdés: létezik-e olyan G = (V, E) gráf, melyre E¹ ⊆ E ⊆ E² és G teljesíti a Π tulajdonságot?

A valamely gráfosztályra (a Π tulajdonságot teljesítő gráfokra) vonatkozó felismerési probléma megegyezik azzal a gráfszendvics-problémával, ahol E¹ = E², tehát az opcionális élhalmaz üres.

Számítási bonyolultság

A gráfszendvics-probléma NP-teljes, ha Π az a tulajdonság, hogy a gráf merev körű, összehasonlíthatósági gráf, permutációgráf, gyengén merev körű páros gráf vagy láncgráf (irányított kör-mentes vegyes gráf).^[3][5] Polinom időben oldható meg split gráfokra,^[3][6] küszöbgráfokra^[3][6] és olyan gráfokra, melyekben bármely öt csúcs tartalmaz legalább egy négy csúcs között futó feszített utat.^[7] A bonyolultsági osztályba sorolás eldőlt a H-mentességre vonatkozó gráfszendvics-problémákra, ahol H a négy csúcsból álló gráfok egyike.^[8]

Fordítás

• Ez a szócikk részben vagy egészben a Graph sandwich problem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

1. Golumbic, Martin Charles & Trenk, Ann N. (2004), "Chapter 4. Interval probe graphs and sandwich problems", Tolerance Graphs, Cambridge, pp. 63–83.
2. David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, Sheng-Lung Peng: Probe Graph Classes (October 17, 2012)
3. Golumbic, Martin Charles; Kaplan, Haim & Shamir, Ron (1995), "Graph sandwich problems", J. Algorithms 19: 449–473, DOI 10.1006/jagm.1995.1047.
4. Golumbic, Martin Charles (2004), Algorithmic Graph Theory and Perfect Graphs, vol. 57 (2nd ed.), Annals of Discrete Mathematics, Elsevier, p. 279, <https://books.google.com/books?id=8xo-VrWo5_QC&pg=PA279>.
5. de Figueiredo, C. M. H.; Faria, L. & Klein, S. et al. (2007), "On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs", Theoretical Computer Science 381 (1-3): 57–67, DOI 10.1016/j.tcs.2007.04.007.
6. Mahadev, N.V.R. & Peled, Uri N. (1995), Threshold Graphs and Related Topics, vol. 57, Annals of Discrete Mathematics, North-Holland, pp. 19–22, <https://books.google.com/books?id=nWfGo_VX5M8C&pg=PA19>.
7. Dantas, S.; Klein, S. & Mello, C.P. et al. (2009), "The graph sandwich problem for P₄-sparse graphs", Discrete Mathematics 309: 3664–3673, DOI 10.1016/j.disc.2008.01.014.
8. Dantas, Simone; de Figueiredo, Celina M.H. & Maffray, Frédéric et al. (2013), "The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem", Discrete Applied Mathematics: Available online 11 October 2013, DOI 10.1016/j.dam.2013.09.004.

Irodalom

• Dantas, Simone; de Figueiredo, Celina M.H. & da Silva, Murilo V.G. et al. (2011), "On the forbidden induced subgraph sandwich problem", Discrete Applied Mathematics 159: 1717-1725, DOI 10.1016/j.dam.2010.11.010.