Title:Scrumptious Sandwich Problems: A Tasty Retrospective for After Lunch
Date: September 11, 2019 (Wednesday)
Time: 2:30 pm - 3:30 pm
Venue: Room 121, 1/F, Ho Sin-Hang Engineering Building, The Chinese University of Hong Kong, Shatin, N.T.
Speaker: Prof. Martin Charles Golumbic
University of Haifa


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.

Speaker’s Bio: 

Martin Charles Golumbic is Emeritus Professor of Computer Science and Founder of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of Haifa. He is the founding Editor-in-Chief of the journal “Annals of Mathematics and Artificial Intelligence” and is or has been a member of the editorial boards of several other journals including “Discrete Applied Mathematics”, “Constraints” and “AI Communications”. His current area of research is in combinatorial mathematics interacting with real world problems in computer science and artificial intelligence. 

Professor Golumbic received his Ph.D. in mathematics from Columbia University in 1975 under the direction of Samuel Eilenberg. He has held positions at the Courant Institute of Mathematical Sciences of New York University, Bell Telephone Laboratories, the IBM Israel Scientific Center and Bar-Ilan University. He has also had visiting appointments at the Université de Paris, the Weizmann Institute of Science, Ecole Polytechnique Fédérale de Lausanne, Universidade Federal do Rio de Janeiro, Rutgers University, Columbia University, Hebrew University, IIT Kharagpur and Tsinghua University.

He is the author of the book “Algorithmic Graph Theory and Perfect Graphs” and coauthor of the book “Tolerance Graphs”. He has written many research articles in the areas of combinatorial mathematics, algorithmic analysis, expert systems, artificial intelligence, and programming languages, and has been a guest editor of special issues of several journals. He is the editor of the books “Advances in Artificial Intelligence, Natural Language and Knowledge-based Systems”, and “Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications”. His most recent book is “Fighting Terror Online: The Convergence of Security, Technology, and the Law”, published by Springer-Verlag. 

Prof. Golumbic and was elected as Foundation Fellow of the Institute of Combinatorics and its Applications in 1995, and has been a Fellow of the European Artificial Intelligence society ECCAI since 2005. He is a member of the Academia Europaea, honoris causa -- elected 2013. Martin Golumbic has been the chairman of over fifty national and international symposia. He a member of the Phi Beta Kappa, Pi Mu Epsilon, Phi Kappa Phi, Phi Eta Sigma honor societies and is married and the father of four bilingual, married daughters and has seven granddaughters and five grandsons.

Enquiries: Ms. Shirley Lau at tel. 3943 8439

For more information, please refer to http://www.cse.cuhk.edu.hk/en/events