Tag: 안정호

An induced packing of cycles in a graph is a set of vertex-disjoint cycles such that the graph has no edge between distinct cycles of the set. The classic Erdős-Pósa theorem shows that for every positive integer $k$, every graph contains $k$ vertex-disjoint cycles or a set of $O(k\log k)$ vertices which intersects every cycle of $G$.

We generalise this classic Erdős-Pósa theorem to induced packings of cycles of length at least $\ell$ for any integer $\ell$. We show that there exists a function $f(k,\ell )=O(\ell k\log k)$ such that for all positive integers $k$ and $\ell$ with $\ell \ge 3$, every graph $G$ contains an induced packing of $k$ cycles of length at least $\ell$ or a set $X$ of at most $f(k,\ell )$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$.

Furthermore, we extend the result to long cycles containing prescribed vertices. For a graph $G$ and a set $S\subseteq V(G)$, an $S$-cycle in $G$ is a cycle containing a vertex in $S$. We show that for all positive integers $k$ and $\ell$ with $\ell \ge 3$, every graph $G$, and every set $S\subseteq V(G)$, $G$ contains an induced packing of $k$ $S$-cycles of length at least $\ell$ or a set $X$ of at most $\ell k^{O(1)}$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$.

Our proofs are constructive and yield polynomial-time algorithms, for fixed $\ell$, finding either the induced packing of the constrained cycles or the set $X$.

This is based on joint works with Pascal Gollin, Tony Huynh, and O-joung Kwon.

Let $\mathcal{F}$ be a family of graphs, and let $p$ and $r$ be nonnegative integers.
The $(p,r,\mathcal{F})$-Covering problem asks whether for a graph $G$ and an integer $k$, there exists a set $D$ of at most $k$ vertices in $G$ such that $G^p\setminus N_G^r[D]$ has no induced subgraph isomorphic to a graph in $\mathcal{F}$, where $G^p$ is the $p$-th power of $G$ and $N_G^r[D]$ is the set of all vertices in $G$ at distance at most $r$ from $D$ in $G$. The $(p,r,\mathcal{F})$-Packing problem asks whether for a graph $G$ and an integer $k$, $G^p$ has $k$ induced subgraphs $H_1,\dots ,H_k$ such that each $H_i$ is isomorphic to a graph in $\mathcal{F}$, and for distinct $i,j\in \{1,\dots ,k\}$, the distance between $V(H_i)$ and $V(H_j)$ in $G$ is larger than $r$. The $(p,r,\mathcal{F})$-Covering problem generalizes Distance-$r$ Dominating Set and Distance-$r$ Vertex Cover, and the $(p,r,\mathcal{F})$-Packing problem generalizes Distance-$r$ Independent Set and Distance-$r$ Matching. By taking $(p^{\prime },r^{\prime },{\mathcal{F}}^{\prime })=(pt,rt,\mathcal{F})$, we may formulate the $(p,r,\mathcal{F})$-Covering and $(p,r,\mathcal{F})$-Packing problems on the $t$-th power of a graph. Moreover, $(1,0,\mathcal{F})$-Covering is the $\mathcal{F}$-Free Vertex Deletion problem, and $(1,0,\mathcal{F})$-Packing is the Induced-$\mathcal{F}$-Packing problem.

We show that for every fixed nonnegative integers $p,r$ and every fixed nonempty finite family $\mathcal{F}$ of connected graphs, the $(p,r,\mathcal{F})$-Covering problem with $p\le 2r+1$ and the $(p,r,\mathcal{F})$-Packing problem with $p\le 2\lfloor r/2\rfloor +1$ admit almost linear kernels on every nowhere dense class of graphs, and admit linear kernels on every class of graphs with bounded expansion, parameterized by the solution size $k$. We obtain the same kernels for their annotated variants. As corollaries, we prove that Distance-$r$ Vertex Cover, Distance-$r$ Matching, $\mathcal{F}$-Free Vertex Deletion, and Induced-$\mathcal{F}$-Packing for any fixed finite family $\mathcal{F}$ of connected graphs admit almost linear kernels on every nowhere dense class of graphs and linear kernels on every class of graphs with bounded expansion. Our results extend the results for Distance-$r$ Dominating Set by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017), and the result for Distance-$r$ Independent Set by Pilipczuk and Siebertz (EJC 2021).

This is joint work with Jinha Kim and O-joung Kwon.

We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure, the leaves of which are of size one. Well-partitioned chordal graphs are a generalization of this concept in the following two ways. First, the cliques in the partition can be arranged in a tree structure, and second, each clique is of arbitrary size. We mainly provide a characterization of well-partitioned chordal graphs by forbidden induced subgraphs and give a polynomial-time algorithm that given any graph, either finds an obstruction or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal. We demonstrate the algorithmic use of this graph class by showing that two variants of the problem of finding pairwise disjoint paths between k given pairs of vertices are in FPT, parameterized by k, on well-partitioned chordal graphs, while on chordal graphs, these problems are only known to be in XP. From the other end, we introduce some problems that are polynomial-time solvable on split graphs but become NP-complete on well-partitioned chordal graphs.

This is joint work with Lars Jaffke, O-joung Kwon, and Paloma T. Lima.