ICALP Workshop: Constrained Recognition Problems
Monday 9-July-2018. Prague, Czech Republic.
-- to occur during the 45th International Colloquium on Automata, Languages, and Programming (ICALP).
Recognition is fundamental class of algorithmic problems in the study of discrete structures. Classical examples include testing planarity and testing whether a graph is an interval graph. Often, the goal of such a recognition problem is to construct a representation certifying membership in the class, e.g., a planar embedding or intersection representation by intervals of the real number line. For the past 15 years, this fundamental class of problems has attained a renaissance period where several generalizations have gained prominence. Two primary examples are the classes of graph editing problems and partial representation extension problems. The former widens the class of graphs by allowing k modification operations which can be applied to an input graph in order to fit it into the class. The latter constrains the sought representation by prescribing the exact representation for a subgraph. Recently, there has been significant progress on the editing problems for several standard classes of graphs, e.g., interval graphs [SODA 2016], chordal graphs [SODA 2017, Algorithmica 2016], H-minor free graphs [FOCS 2012], and planar graphs [SODA 2017]. The partial representation extension problem has also been studied for various graph classes, among others planar graphs [TALG 2015], level-planar graphs [SODA 2017], interval graphs [TALG 2015, Algorithmica 2017], and bar visibility graphs [Algorithmica 2017]. The purpose of this workshop is to describe the main techniques employed to obtain recent significant results as well as to highlight the key challenges in these areas.
To be determined.