Sandwiches missing two ingredients of order four

DOI10.1007/S10479-019-03174-6zbMATH Open1494.68186arXiv1704.01922OpenAlexW2607186789MaRDI QIDQ2288872FDOQ2288872

Simone Dantas, José D. Alvarado, Dieter Rautenbach

Publication date: 20 January 2020

Published in: Annals of Operations Research (Search for Journal in Brave)

Abstract: For a set $calF$ of graphs, an instance of the $calF$-{sc free Sandwich Problem} is a pair $(G_1,G_2)$ consisting of two graphs $G_1$ and $G_2$ with the same vertex set such that $G_1$ is a subgraph of $G_2$, and the task is to determine an $calF$-free graph $G$ containing $G_1$ and contained in $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$-free graphs, we study the complexity of the $calF$-{sc free Sandwich Problem} for sets $calF$ containing two non-isomorphic graphs of order four. We show that if $calF$ is one of the sets $leftmdiamond,K_{4}ight$, $leftmdiamond,C_{4}ight$, $leftmdiamond,mpawight$, $left{K}_4,overline{K}_{4}ight$, $left{P}_4,C_{4}ight$, $left{P}_4,overlinemclawight$, $left{P}_4,overlinempawight$, $left{P}_4,overlinemdiamondight$, $leftmpaw,C_{4}ight$, $leftmpaw,mclawight$, $leftmpaw,overlinemclawight$, $leftmpaw,overlinempawight$, $left{C}_4,overline{C}_{4}ight$, $leftmclaw,overlinemclawight$, and $leftmclaw,overline{C}_{4}ight$, then the $calF$-{sc free Sandwich Problem} can be solved in polynomial time, and, if $calF$ is one of the sets $left{C}_4,K_{4}ight$, $leftmpaw,K_{4}ight$, $leftmpaw,overline{K}_{4}ight$, $leftmpaw,overline{C}_{4}ight$, $leftmdiamond,overline{C}_{4}ight$, $leftmpaw,overlinemdiamondight$, and $leftmdiamond,overlinemdiamondight$, then the decision version of the $calF$-{sc free Sandwich Problem} is NP-complete.

Full work available at URL: https://arxiv.org/abs/1704.01922

zbMATH Keywords

prime graphforbidden induced subgraphhomogeneous setgraph sandwich problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Graph Classes: A Survey
• Graph Sandwich Problems
• Threshold graphs and related topics
• Linear recognition of pseudo-split graphs
• Paw-free graphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• The homogeneous set sandwich problem
• The chain graph sandwich problem
• Two forbidden induced subgraphs and well-quasi-ordering
• Clique-width for 4-vertex forbidden subgraphs
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• The external constraint 4 nonempty part sandwich problem
• The graph sandwich problem for \(P_4\)-sparse graphs
• Matrix sandwich problems
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• The polynomial dichotomy for three nonempty part sandwich problems
• On the forbidden induced subgraph sandwich problem

This page was built for publication: Sandwiches missing two ingredients of order four

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2288872)