O-joung Kwon (권오정), Classes of intersection digraphs with good algorithmic properties

An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v, T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_v\cap T_v\neq \emptyset$ for every vertex $v$. Compared to well-known undirected intersection graphs like interval graphs and permutation graphs, not many algorithmic applications on intersection digraphs have been developed.

Motivated by the successful story on algorithmic applications of intersection graphs using a graph width parameter called mim-width, we introduce its directed analogue called `bi-mim-width’ and prove that various classes of reflexive intersection digraphs have bounded bi-mim-width. In particular, we show that as a natural extension of $H$-graphs, reflexive $H$-digraphs have linear bi-mim-width at most $12|E(H)|$, which extends a bound on the linear mim-width of $H$-graphs [On the Tractability of Optimization Problems on $H$-Graphs. Algorithmica 2020]

For applications, we introduce a novel framework of directed versions of locally checkable problems, that streamlines the definitions and the study of many problems in the literature and facilitates their common algorithmic treatment. We obtain unified polynomial-time algorithms for these problems on digraphs of bounded bi-mim-width, when a branch decomposition is given. Locally checkable problems include Kernel, Dominating Set, and Directed $H$-Homomorphism.

This seminar is a part of the
“Round the World Relay in Combinatorics”
on June 8, 2021.

http://people.maths.ox.ac.uk/scott/relay.htm

• 2:00 UTC, 11:00 KST Melbourne (Australia) Monash University
  David Wood (Monash University), Universality in Minor-Closed Graph Classes
• 3:00 UTC, 12:00 KST Shanghai (China) Shanghai Center for Mathematical Sciences
  Baogang Xu (Nanjing Normal University, China), On coloring of graphs of girth 2l+1 without longer odd holes
• 4:00 UTC, 13:00 KST Auckland (New Zealand) The University of Auckland
  Jeroen Schillewaert (University of Auckland), Constructing highly regular expanders from hyperbolic Coxeter groups
• 5:00 UTC, 14:00 KST Sydney (Australia) Combinatorial Mathematics Society of Australasia
  Gordon Royle (University of Western Australia (UWA)), Real chromatic roots of planar graphs
• 6:00 UTC, 15:00 KST Daejeon (Korea) IBS Discrete Mathematics Group
  O-joung Kwon (Incheon National University and IBS Discrete Mathematics Group), Classes of intersection digraphs with good algorithmic properties
• 7:00 UTC, 16:00 KST Krakow (Poland) Jagiellonian University
  Bartosz Walczak (Jagiellonian), Coloring polygon visibility graphs and their generalizations
• 8:00 UTC, 17:00 KST Glasgow (UK) University of Glasgow
  Heng Guo (University of Edinburgh), A Markov chain approach towards the sampling Lovász local lemma
• 9:00 UTC, 18:00 KST London (UK) London School of Economics
  Annika Heckel (LMU), How does the chromatic number of a random graph vary?
• 10:00 UTC, 19:00 KST Moscow (Russia) Moscow Institute of Physics and Technology
  Noga Alon (Princeton and Tel Aviv)
• 11:00 UTC, 20:00 KST Budapest (Hungary) Hungarian Academy of Sciences + Eötvös Loránd University
  László Lovász (Eotvos University, Budapest)
• 12:00 UTC, 21:00 KST Bordeaux (France) LaBRI
  Carla Groenland (Utrecht University), Universal Graphs and Labelling Schemes
• 13:00 UTC, 22:00 KST New York (USA) City University of New York + Montclair State University + Hofstra University
  Deepak Bal (Montclair State University)
• 14:00 UTC, 23:00 KST Prague (Czech) Czech Academy of Sciences + Czech Technical University + London School of Economics
  Dhruv Mubayi (University of Illinois at Chicago), The feasible region of hypergraphs
• 15:00 UTC, 00:00 KST Brno (Czech) Masaryk University
  James Davies (University of Waterloo), Colouring circle graphs and their generalisations
• 16:00 UTC, 01:00 KST Oxford (UK) University of Oxford
  Jacob Fox (Stanford University), Removal lemmas
• 17:00 UTC, 02:00 KST Columbus (USA) Ohio State University
  Allan Sly (Princeton University)
• 18:00 UTC, 03:00 KST Rio (Brazil) Instituto de Matemática Pura e Aplicada
  Marcelo Campos (IMPA), The singularity probability of a random symmetric matrix is exponentially small
• 19:00 UTC, 04:00 KST Atlanta (USA) Georgia Institute of Technology
  Jim Geelen (University of Waterloo), Homomorphisms and colouring for graphs and binary matroids
• 20:00 UTC, 05:00 KST Santiago (Chile) Universidad de Chile
  David Conlon (Caltech)
• 21:00 UTC, 06:00 KST Burnaby (Canada) Simon Fraser University
  Fan Chung (UCSD), Trees and forests in Green’s functions of a graph
• 22:00 UTC, 07:00 KST Victoria (Canada) University of Victoria
  Andrew Suk (UCSD), Turán-type problems for point-line incidences
• 23:00 UTC, 08:00 KST Fairbanks (USA) University of Alaska
  Ron Gould (Emory), Chorded cycles