CanaDAM 2021
En ligne, 25 - 28 mai 2021

Algorithms for interval graphs and related families - Part II
Org: Yixin Cao (Hong Kong Polytechnic University) et Derek G. Corneil (University of Toronto)

YIXIN CAO, Hong Kong Polytechnic University
Recognizing (unit) interval graphs by zigzag graph searches  [PDF]

Corneil, Olariu, and Stewart [SODA1998; SIDMA2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [DMTCS2014] simplified it to only four. The great simplicity of the latter algorithm is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly shorter proof for Li and Wu's algorithm, as well as a simpler implementation. We also give a self-contained presentation of the recognition of unit interval graphs, based on three sweeps of graph searches. We make several new structural observations that might be of independent interests.

CELINA DE FIGUEIREDO, Universidade Federal do Rio de Janeiro
Maximum cut and Steiner tree restricted to interval graphs and related families  [PDF]

We consider Column 16 -- Graph Restrictions and Their Effect -- of D. S. Johnson's Ongoing guide, where several puzzles were proposed in a summary table with 30 graph classes as rows and 11 problems as columns, and several of the 330 entries remain unclassified into Polynomial or NP-complete after 35 years. We focus on columns MaxCut and StTree, where there are recent resolved entries for interval graphs and related families.

MICHEL HABIB, Paris University
Grounded intersection graphs and forbidden patterns on 4 vertices  [PDF]

In the 90s Damaschke noticed that classic graph classes, such as interval and chordal can be characterized by the existence of an ordering of the nodes avoiding some of ordered subgraphs, called patterns. Hell, Mohar and Rafiey 2014 showed that all the classes corresponding to set of patterns on three vertices can be recognized polynomially. Very recently we list all the classes corresponding to set of patterns on three vertices. For patterns on four nodes we may have graph classes that are NP-complete to recognize (example 3-colorable graphs). In this work, we study grounded intersection graphs, and their forbidden patterns.

PAVOL HELL, Simon Fraser University
Variants of interval graphs and related families  [PDF]

In this survey talk I will explore the best analogues of interval graphs (and of closely related families) for digraphs, bigraphs, and for graphs with loops allowed. I will focus on interval graphs, while mentioning other families, including strongly chordal graphs fully discussed in a talk by Cesar Hernandez-Cruz in another session. Most of the results are joint work with Jing Huang, Cesar Hernandez-Cruz, Jephian Lin, Ross McConnell, Arash Rafiey, and others; I will also mention other work by Akbar Rafiey and Arash Rafiey.

LALLA MOUATADID, University of Toronto and Google
$(\alpha, \beta)$-Modules in Graphs  [PDF]

We introduce the notion of an $(\alpha, \beta)$-module, a relaxation that allows a bounded number of errors in each node and maintains some of the algebraic structures. This leads to a new combinatorial decomposition with very interesting properties. In this talk, we'll discuss minimal $(\alpha, \beta)$-modules, $(\alpha, \beta)$-modular decomposition trees, $(\alpha, \beta)$-cographs, and other new findings and interesting conjectures on this new decomposition.

Joint work with Michel Habib, Eric Sopena, and Mengchuan Zou.