The Sandwich Problem for Decompositions and Almost Monotone Properties

Maria Chudnovsky, Celina M.H. de Figueiredo, Sophie Spirkl

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)3618-3645
Number of pages28
JournalAlgorithmica
Volume80
Issue number12
DOIs
StatePublished - Dec 1 2018

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Graph algorithms
  • Graph decompositions
  • Graph theory
  • Probe problem
  • Sandwich problem
  • Trigraphs

Fingerprint Dive into the research topics of 'The Sandwich Problem for Decompositions and Almost Monotone Properties'. Together they form a unique fingerprint.

  • Cite this