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 -