Scrumptious Sandwich Problems: A Tasty Retrospective for Before Lunch


Martin Golumbic


University of Haifa


Thu, 10/10/2019 - 11:00am


RC-2063, The Red Centre, UNSW


Graph sandwich problems are a prototypical example of checking consistency when faced with only partial data. A sandwich problem for a graph with respect to a graph property $\Pi$ is a partially specified graph, i.e., only some of the edges and non-edges are given, and the question to be answered is, can this graph be completed to a graph which has the property $\Pi$? The graph sandwich problem was investigated for a large number of families of graphs in a 1995 paper by Golumbic, Kaplan and Shamir, and over 200 subsequent papers by many researchers have been published since.
In some cases, the problem is NP-complete such as for interval graphs, comparability graphs, chordal graphs and others. In other cases, the sandwich problem can be solved in polynomial time such as for threshold graphs, cographs, and split graphs. There are also interesting special cases of the sandwich problem, most notably the probe graph problem where the unspecified edges are confined to be within a subset of the vertices. Similar sandwich problems can also be defined for hypergraphs, matrices, posets and Boolean functions, namely, completing partially specified structures such that the result satisfies a desirable property. In this talk, we will present a survey of results that we and others have obtained in this area during the past decade.

Sandwiches will be served after the seminar. Please send a quick email to if you intend to come so we have an idea of numbers.

School Seminar Series: