Tag: 권오정

A family $\mathcal{F}$ of graphs is said to satisfy the Erdős-Pósa property if there exists a function $f$ such that for every positive integer $k$, every graph $G$ contains either $k$ (vertex-)disjoint subgraphs in $\mathcal{F}$ or a set of at most $f(k)$ vertices intersecting every subgraph of $G$ in $\mathcal{F}$. We characterize the obstructions to the Erdős-Pósa property of $A$-paths in unoriented group-labelled graphs. As a result, we prove that for every finite abelian group $\mathrm{\Gamma }$ and for every subset $\mathrm{\Lambda }$ of $\mathrm{\Gamma }$, the family of $\mathrm{\Gamma }$-labelled $A$-paths whose lengths are in $\mathrm{\Lambda }$ satisfies the half-integral relaxation of the Erdős-Pósa property. Moreover, we give a characterization of such $\mathrm{\Gamma }$ and $\mathrm{\Lambda }\subseteq \mathrm{\Gamma }$ for which the same family of $A$-paths satisfies the full Erdős-Pósa property. This is joint work with Youngho Yoo.

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomassé, and Watrigant [FOCS 2020] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$, we define the reduced-$f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced-bandwidth, which implies and is stronger than bounded twin-width (reduced-maximum-degree).

We show that every proper minor-closed class has bounded reduced-bandwidth, which is qualitatively stronger than a result of Bonnet et al. for bounded twin-width. In many instances, we also make quantitative improvements. For example, all previous upper bounds on the twin-width of planar graphs were at least $2^{1000}$. We show that planar graphs have reduced-bandwidth at most $466$ and twin-width at most $583$; moreover, the witnessing reduction sequence can be constructed in polynomial time. We show that $d$-powers of graphs in a proper minor-closed class have bounded reduced-bandwidth (irrespective of the degree of the vertices).

This is joint work with Édouard bonnet and David Wood.

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\ne \mathrm{\varnothing }$ 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

The canonical tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper, we prove the analogous result for digraphs, the directed tangle tree-decomposition theorem. More precisely, we introduce directed tangles and provide a directed tree-decomposition of digraphs $G$ that distinguishes all maximal directed tangles in $G$. Furthermore, for any integer $k$, we construct a directed tree-decomposition that distinguishes all directed tangles of order $k$, for any integer $k$.

By relaxing the bound slightly, we can make the previous result algorithmic: for fixed $k$, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order $3k$ separated by some separation of order less than $k$.

We provide two direct applications of this tangle tree-decomposition theorem. First, we show that the family of directed odd cycles has the half-integral Erdős-Pósa property, that is, there is a function $f:\mathbb{N}\to \mathbb{R}$ such that for every digraph $G$ and every integer $k$, either $G$ contains a family of $k$ directed odd cycles where every vertex of $G$ is contained at most two cycles, or a vertex subset of size at most $f(k)$ hitting all directed odd cycles. This extends the half-integral Erdős-Pósa property for undirected odd cycles, shown by Reed [Mangoes and blueberries. Combinatorica 1999].

Second, for every fixed $k$ we show that there is a polynomial-time algorithm which, on input $G$, and source and sink vertices $(s_1,t_1),\dots ,(s_k,t_k)$, either finds a family of paths $P_1,\dots ,P_k$ such that each $P_i$ links $s_i$ to $t_i$ and every vertex of $G$ is contained in at most two paths, or determines that there is no set of pairwise vertex-disjoint paths each connecting $s_i$  to $t_i$. This result improves previous results (with “two” replaced by “three”), and given known hardness results, our result is best possible in a sense that we cannot hope for fixed parameter tractability or fully vertex-disjoint directed paths.

This is joint work with Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, and Qiqin Xie.

Vatshelle (2012) introduced a width parameter called mim-width. It is based on the following cut function : for a vertex partition (A,B) of a graph, the complexity of this partition is computed by the size of a maximum induced matching of the bipartite subgraph induced by edges between A and B. This parameter naturally extends the expressibility power of the graph parameters clique-width and rank-width, which have been well-developed in recent years. In a series of papers, we explored the computational complexity of several problems, parameterized by mim-width. We summarize known structural properties and algorithmic applications of mim-width, and give some open problems at the end. This is joint work with Lars Jaffke, Torstein Strømme, and Jan Arne Telle.