Data: 14/05/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: The complexity of hard graph problems forty years later
Palestrante: Celina Miraglia Herrera de Figueiredo (UFRJ)


Abstract: The book Computers and Intractability, A Guide to the Theory of NP-completeness, by Michael R. Garey and David S. Johnson, was published 40 years ago, and despite its age, it is considered by the computational complexity community the single most important book, as NP-completeness is considered the single most important concept to come out of theoretical computer science. The popularity of the NP-completeness concept and of its guide book increased when the P versus NP problem was selected by the Clay Mathematics Institute as one of the seven Millennium Problems to motivate research on important classic questions that have resisted solution over the years. The P versus NP problem is considered a central problem in theoretical computer science, and aims to classify the possible existence of efficient solutions to combinatorial and optimization problems. In the sixteenth edition of his NP-Completeness Column: An Ongoing Guide, David S. Johnson focused on graph restrictions and their effect, with emphasis on the restrictions to graph classes and how they affect the complexity of various hard problems. Graph classes were selected because of their broad algorithmic significance. The presentation consisted of a summary table with 30 rows containing the selected classes of graphs, and 11 columns the first devoted to the complexity of determining whether a given graph is in the specified class followed by ten of the more famous NP-complete graph problems. We discuss several surprising complexity dichotomies and the concepts of separating problem proposed by David S. Johnson and the dual concept of separating class, by updating his summary table.