Sandwiches missing two ingredients of order four

DOI10.1007/S10479-019-03174-6MaRDI QIDQ2288872zbMATH OpenOpenAlexFDO

Authors Simone Dantas, Dieter Rautenbach, José D. Alvarado

Publication date 20 January 2020

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

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)

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.

Recommendations

• scientific article; zbMATH DE number 6423755
• On the forbidden induced subgraph sandwich problem
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• The graph sandwich problem for P₄-sparse graphs
• Graph Sandwich Problems

Cites work

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

Cited in

(5)

• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• The graph sandwich problem for P₄-sparse graphs
• Sandwich and probe problems for excluding paths
• Structural properties and applications to sandwich problem of the two forbidden four-vertex graph classes
• 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)