A graph $G$ is an $\ell$-leaf power of a tree $T$ if $V(G)$ is equal to the set of leaves of $T$, and distinct vertices $v$ and $w$ of $G$ are adjacent if and only if the distance between $v$ and $w$ in $T$ is at most $\ell$. Given a graph $G$, 3-Leaf Power Deletion asks whether there is a set $S\subseteq V(G)$ of size at most $k$ such that $G\setminus S$ is a $3$-leaf power of some tree $T$. We provide a polynomial kernel for this problem. More specifically, we present a polynomial-time algorithm for an input instance $(G,k)$ to output an equivalent instance $(G',k')$ such that $k'\leq k$ and $G'$ has at most $O(k^{14}\log^{12}k)$ vertices.
주어진 트리 $T$의 $\ell$-leaf power란, $T$의 모든 리프들을 꼭짓점으로 가지고, $T$에서 거리가 $\ell$ 이하인 두 리프를 변으로 연결한 그래프를 말한다. 주어진 그래프 $G$에서 최대 $k$개의 꼭짓점을 제거해 어떤 트리의 $3$-leaf power가 되도록 하는 게 가능한지를 판별하는 문제를 3-Leaf Power Deletion이라고 한다. 그래프 $G$에서 그러한 최대 $k$개의 꼭짓점이 존재하면 $(G,k)$를 yes-instance라고 하자. 그리고 $(G,k)$가 yes-instance라는 조건과 $(G',k')$가 yes-instance라는 조건이 동치일 때, $(G,k)$와 $(G',k')$를 동치라고 하자. 우리는 주어진 $(G,k)$와 동치이며 최대 $O(k^{14}\log^{12}k)$개의 꼭짓점을 가지는 그래프 $G'$와 $k'\leq k$로 구성된 $(G',k')$을 다항식 시간 안에 생성하는 알고리즘을 제시했다.
