CanaDAM 2021
En ligne, 25 - 28 mai 2021

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

AKANKSHA AGRAWAL, Indian Institute of Technology Madras
Polynomial Kernel for Interval Vertex Deletion  [PDF]

Given a graph $G$ and an integer $k$, Interval Vertex Deletion (IVD) asks whether there exists $S \subseteq V(G)$ of size at most $k$, such that $G–S$ is an interval graph. The existence of polynomial kernel for IVD remained a well-known open problem in Parameterized Complexity. In this talk we will look at a sketch of polynomial kernel for IVD. We will mainly focus on a kernel for IVD, when parameterized by the vertex cover number. The ideas that will be presented are (some of the) key ingredients in our kernel for IVD, when parameterized by the solution size.

FLAVIA BONOMO, University of Buenos Aires
Algorithms for k-thin and proper k-thin graphs  [PDF]

The (proper) thinness of a graph is a with parameter generalizing (proper) interval graphs, which are exactly the (proper) 1-thin graphs. A wide family of problems (including list matrix partition with bounded size matrix) can be polynomially solved for graphs with bounded thinness, and it can be enlarged in the proper case. We will survey these results, along with some structural characterizations and algorithmic problems related to recognition, which is open. We will also describe the behavior of both parameters under some graph operations, and relate them to other graph invariants in the literature.

DEREK G. CORNEIL, University of Toronto
Early days of interval graph algorithms  [PDF]

This talk presents a low teck, personal voyage into interval graphs and related graph families. The talk starts with needed definitions of various graph families and early interval graph recognition algorithms leading to a discussion of the Lekkerkerker Boland Theorem and Asteroidal Triple-free graphs. The voyage continues into the role played by graph searches, most notably LexBFS. Along the way, we encounter surprising observations, false steps and shifting perspectives.

GUILLAUME DUCOFFE, University of Bucharest, Romania
Faster computation of graph diameter by using one (or two) properties of the interval graphs  [PDF]

For communication networks, and many others, important characteristics such as maximum communication delays, and centralities of nodes, can be derived from the computation of classic graph parameters, such as diameter, radius, average distance and median. One can solve all these problems in linear time on interval graphs, but which of these properties of this graph class are the true reason? We will review whether similar computational results can be achieved by relaxing the definition of interval graphs and/or keeping only a few of their nice properties (say, Helly property of the balls, chordality, AT-freeness, bounded VC-dimension, etc.).

FRANCISCO SOULIGNAC, University of Buenos Aires
Representation problems for unit interval and unit circular-arc graphs  [PDF]

The last decade saw an increasing research on numerical representation problems for unit circular-arc models (UCA) and related classes. In these problems we are given a proper circular-arc model $\mathcal{M}$ and we have to find a UCA model $\mathcal{U}$, related to $\mathcal{M}$, that satisfies certain numerical constraints. In the classical representation problem, for instance, we are given a proper circular-arc model and we have to find an equivalent unit circular-arc model whose extremes are all integer and have a polynomial size. In this talk I present a common framework to efficiently solve different numerical representation problems for UCA models.