TY - JOUR
T1 - The Sandwich Problem for Decompositions and Almost Monotone Properties
AU - Chudnovsky, Maria
AU - de Figueiredo, Celina M.H.
AU - Spirkl, Sophie
N1 - Funding Information:
Acknowledgements We are thankful to Paul Seymour for many helpful discussions. This material is based upon work supported in part by the U. S. Army Research Laboratory and the U. S. Army Research Office under Grant No. W911NF-16-1-0404.
Funding Information:
Maria Chudnovsky was supported by National Science Foundation Grant DMS-1550991 and US Army Research Office Grant W911NF-16-1-0404. Celina M. H. de Figueiredo was supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico CNPq Grant 303622/2011-3.
Publisher Copyright:
© 2018, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2018/12/1
Y1 - 2018/12/1
N2 - We consider the graph sandwich problem and introduce almost monotone properties, for which the sandwich problem can be reduced to the recognition problem. We show that the property of containing a graph in C as an induced subgraph is almost monotone if C is the set of thetas, the set of pyramids, or the set of prisms and thetas. We show that the property of containing a hole of length ≡jmodn is almost monotone if and only if j≡2modn or n≤ 2. Moreover, we show that the imperfect graph sandwich problem, also known as the Berge trigraph recognition problem, can be solved in polynomial time. We also study the complexity of several graph decompositions related to perfect graphs, namely clique cutset, (full) star cutset, homogeneous set, homogeneous pair, and 1-join, with respect to the partitioned and unpartitioned probe problems. We show that the clique cutset and full star cutset unpartitioned probe problems are NP-hard. We show that for these five decompositions, the partitioned probe problem is in P, and the homogeneous set, 1-join, 1-join in the complement, and full star cutset in the complement unpartitioned probe problems can be solved in polynomial time as well.
AB - We consider the graph sandwich problem and introduce almost monotone properties, for which the sandwich problem can be reduced to the recognition problem. We show that the property of containing a graph in C as an induced subgraph is almost monotone if C is the set of thetas, the set of pyramids, or the set of prisms and thetas. We show that the property of containing a hole of length ≡jmodn is almost monotone if and only if j≡2modn or n≤ 2. Moreover, we show that the imperfect graph sandwich problem, also known as the Berge trigraph recognition problem, can be solved in polynomial time. We also study the complexity of several graph decompositions related to perfect graphs, namely clique cutset, (full) star cutset, homogeneous set, homogeneous pair, and 1-join, with respect to the partitioned and unpartitioned probe problems. We show that the clique cutset and full star cutset unpartitioned probe problems are NP-hard. We show that for these five decompositions, the partitioned probe problem is in P, and the homogeneous set, 1-join, 1-join in the complement, and full star cutset in the complement unpartitioned probe problems can be solved in polynomial time as well.
KW - Graph algorithms
KW - Graph decompositions
KW - Graph theory
KW - Probe problem
KW - Sandwich problem
KW - Trigraphs
UR - http://www.scopus.com/inward/record.url?scp=85040646863&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85040646863&partnerID=8YFLogxK
U2 - 10.1007/s00453-018-0409-6
DO - 10.1007/s00453-018-0409-6
M3 - Article
AN - SCOPUS:85040646863
SN - 0178-4617
VL - 80
SP - 3618
EP - 3645
JO - Algorithmica
JF - Algorithmica
IS - 12
ER -