KAIST Discrete Math Seminar

A chordless cycle in a graph G is an induced subgraph of G which is a cycle of length at least four. We prove that the Erdős-Pósa property holds for chordless cycles, which resolves the major open question concerning the Erdős-Pósa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either k+1 vertex-disjoint chordless cycles, or ck² log k vertices hitting every chordless cycle for some constant c. It immediately implies an approximation algorithm of factor O(OPT log OPT) for Chordal Vertex Deletion. We complement our main result by showing that chordless cycles of length at least ℓ for any fixed ℓ≥ 5 do not have the Erdős-Pósa property.

We introduce the concept of low rank-width colorings, generalizing the notion of low tree-depth colorings introduced by Nešetřil and Ossona de Mendez in [Grad and classes with bounded expansion I. Decompositions. EJC 2008]. We say that a class ? of graphs admits low rank-width colorings if there exist functions N:ℕ→ℕ and Q:ℕ→ℕ such that for all p∈ℕ, every graph G∈? can be vertex colored with at most N(p) colors such that the union of any i≤p color classes induces a subgraph of rank-width at most Q(i).
Graph classes admitting low rank-width colorings strictly generalize graph classes admitting low tree-depth colorings and graph classes of bounded rank-width. We prove that for every graph class ? of bounded expansion and every positive integer r, the class {G^r: G∈?} of r-th powers of graphs from ?, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. All of these classes have unbounded rank-width and do not admit low tree-depth colorings. We also show that the classes of interval graphs and permutation graphs do not admit low rank-width colorings. In this talk, we provide the color refinement technique necessary to show the first result. This is joint work with Sebastian Sierbertz and Michał Pilipczuk.

It has long been known that Feedback Vertex Set can be solved in time 2^{O(w log w)}n^O(1) on graphs of treewidth w, but it was only recently that this running time was improved to 2^O(w)n^O(1), that is, to single-exponential parameterized by treewidth. We consider a natural generalization of this problem, which asks given a graph G on n vertices and positive integers k and d, whether there is a set S of at most k vertices of G such that each block of G-S has at most d vertices. The central question of this talk is: “Can we obtain an algorithm that runs in single-exponential time parameterized by treewidth, for every fixed d?” The answer is negative. But then, one may be curious which properties of Feedback Vertex Set that make it allow to have a single-exponential algorithm. To answer this question, we add an additional condition in the general problem, and provide a dichotomy result.
Formally, for a class ? of graphs, the Bounded ?-Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether there is a set S of at most k vertices of G such that each block of G-S has at most d vertices and is in ?. Assuming that ? is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d:

• if ? consists only of chordal graphs, then the problem can be solved in time 2^{O(wd^2)}n^O(1),
• if ? contains a graph with an induced cycle of length ℓ≥4, then the problem is not solvable in time 2^{o(w log w)} n^O(1) even for fixed d=ℓ, unless the ETH fails.

We further show that it is W[1]-hard parameterized by only treewidth, when ? consists of all graphs. This is joint work with Édouard Bonnet, Nick Brettell, and Daniel Marx.

Graph layout problems are a class of optimization problems whose goal is to find a linear ordering of an input graph in such a way that a certain objective function is optimized. The matrix rank function has been studied as an objective function. The linear rank-width of a graph G is the minimum integer k such that G admits a linear ordering satisfying that the maximum over all values $$ \operatorname{rank}A_G[\{v_1, v_2, \ldots, v_t\}, \{v_{t+1}, \ldots, v_n\}]$$ is k, where is the adjacency matrix of G and the rank is computed over the binary field.

In this talk, we present a result that for every graph G that is vertex-minor minimal with the property having linear rank-width larger than p, the number of vertices in G is at most doubly exponential in . The number of vertex-minor obstructions for linear rank-width at most p is of interest because the only known fixed parameter tractable algorithm to test whether linear rank-width is at most p is using the finiteness of the number of forbidden vertex-minor obstructions. Our result gives an upper bound of the complexity on this algorithm. Our basic tools are the algebraic operations on labelled graphs introduced by Kanté and Rao, and we extend the notion of vertex-minors in our purpose. This is joint work with Mamadou Moustapha Kanté.

A split of a graph is a partition (A,B) of the vertex set V(G) having subsets A₀ of A and B₀ of B such that |A|,|B| > 1 and a vertex a in A is adjacent to a vertex b in B if and only if a is in A₀ and b is in B₀. A graph is prime (with respect to the split decomposition) if it has no split.

We prove that for each n, there exists N such that every prime graph on at least N vertices contains a vertex-minor isomorphic to either a cycle of length n or a graph consisting of two disjoint cliques of size n joined by a matching.

In this talk, we plan to describe a main tool, which is called a blocking sequence in a prime graph, and we will describe two big steps of the proof. And we will pose some open problems behind this result.

This is a joint work with Sang-il Oum.