Sandwiches missing two ingredients of order four

José D. Alvarado (), Simone Dantas () and Dieter Rautenbach ()
Additional contact information
José D. Alvarado: Universidade Federal Fluminense
Simone Dantas: Universidade Federal Fluminense
Dieter Rautenbach: Ulm University

Annals of Operations Research, 2019, vol. 280, issue 1, No 3, 47-63

Abstract: Abstract For a set $$\mathcal{F}$$ F of graphs, an instance of the $$\mathcal{F}$$ F -free Sandwich Problem is a pair $$(G_1,G_2)$$ ( G 1 , G 2 ) consisting of two graphs $$G_1$$ G 1 and $$G_2$$ G 2 with the same vertex set such that $$G_1$$ G 1 is a subgraph of $$G_2$$ G 2 , and the task is to determine an $$\mathcal{F}$$ F -free graph G containing $$G_1$$ G 1 and contained in $$G_2$$ G 2 , or to decide that such a graph does not exist. Initially motivated by the graph sandwich problem for trivially perfect graphs, which are the $$\{ P_4,C_4\}$$ { P 4 , C 4 } -free graphs, we study the complexity of the $$\mathcal{F}$$ F -free Sandwich Problem for sets $$\mathcal{F}$$ F containing two non-isomorphic graphs of order four. We show that if $$\mathcal{F}$$ F is one of the sets $$\left\{ \mathrm{diamond},K_4\right\} $$ diamond , K 4 , $$\left\{ \mathrm{diamond},C_4\right\} $$ diamond , C 4 , $$\left\{ \mathrm{diamond},\mathrm{paw}\right\} $$ diamond , paw , $$\left\{ K_4,\overline{K_4}\right\} $$ K 4 , K 4 ¯ , $$\left\{ P_4,C_4\right\} $$ P 4 , C 4 , $$\left\{ P_4,\overline{\mathrm{claw}}\right\} $$ P 4 , claw ¯ , $$\left\{ P_4,\overline{\mathrm{paw}}\right\} $$ P 4 , paw ¯ , $$\left\{ P_4,\overline{\mathrm{diamond}}\right\} $$ P 4 , diamond ¯ , $$\left\{ \mathrm{paw},C_4\right\} $$ paw , C 4 , $$\left\{ \mathrm{paw},\mathrm{claw}\right\} $$ paw , claw , $$\left\{ \mathrm{paw},\overline{\mathrm{claw}}\right\} $$ paw , claw ¯ , $$\left\{ \mathrm{paw},\overline{\mathrm{paw}}\right\} $$ paw , paw ¯ , $$\left\{ C_4,\overline{C_4}\right\} $$ C 4 , C 4 ¯ , $$\left\{ \mathrm{claw},\overline{\mathrm{claw}}\right\} $$ claw , claw ¯ , and $$\left\{ \mathrm{claw},\overline{C_4}\right\} $$ claw , C 4 ¯ , then the $$\mathcal{F}$$ F -free Sandwich Problem can be solved in polynomial time, and, if $$\mathcal{F}$$ F is one of the sets $$\left\{ C_4,K_4\right\} $$ C 4 , K 4 , $$\left\{ \mathrm{paw},K_4\right\} $$ paw , K 4 , $$\left\{ \mathrm{paw},\overline{K_4}\right\} $$ paw , K 4 ¯ , $$\left\{ \mathrm{paw},\overline{C_4}\right\} $$ paw , C 4 ¯ , $$\left\{ \mathrm{diamond},\overline{C_4}\right\} $$ diamond , C 4 ¯ , $$\left\{ \mathrm{paw},\overline{\mathrm{diamond}}\right\} $$ paw , diamond ¯ , and $$\left\{ \mathrm{diamond},\overline{\mathrm{diamond}}\right\} $$ diamond , diamond ¯ , then the decision version of the $$\mathcal{F}$$ F -free Sandwich Problem is NP-complete.

Keywords: Graph sandwich problem; Forbidden induced subgraph; Prime graph; Homogeneous set (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03174-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:280:y:2019:i:1:d:10.1007_s10479-019-03174-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-019-03174-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().