A recent technique in parameterized complexity theory, developed by Bodlaender $\emph{et al.}$ (On problems without polynomial kernels. $\emph{Journal of Computer and System Sciences}$, vol. 75, issue 8, pages 423-434, 2009.), can be used to provide evidence that a variety of parameterized problems do not have polynomial size kernels. Originally, this technique was only used for parameterizations of NP-complete languages. We are interested in extending it so that it yields similar results for parameterizations of languages that are not believed to be NP-complete. Specifically, we establish a kernel bounds framework for the Graph Isomorphism problem.
Using the strong interplay between the notions of composition and distillation, we show that AND-compositional parameterizations of Graph Isomorphism do not have polynomial size kernels, unless the unparameterized problem has an AND-distillation. Next, we develop some techniques for proving compositionality results for Graph Isomorphism, and using these, we prove that the parameterization of this problem is AND-compositional for the following parameters:
-rooted tree distance width for connected graphs (as originally defined in Yamazaki $\emph{et al.}$. Isomorphism for graphs of bounded distance width.$\emph{Algorithmica}$, 24(2):105-127. Springer, 1999.);
-rooted tree distance width (our generalization of this notion to arbitrary graphs);
-tree-width;
-maximum degree.
As a result, for these parameterizations of the Graph Isomorphism problem, the existence of polynomial size kernels is no more likely than the classical problem having an AND-distillation.
Parameterized complexity 분야의 최근 연구성과로서, Bodlaender, Downey, Fellows와 Hermelin은 파라메터가 주어진 다양한 문제가 다항식 크기의 커널(kernel)을 가질 수 없는 증거를 보이는 방법을 제시하였다. 하지만 원래 이 방법을 NP-complete 문제의 경우에만 이용 할 수 있었다. 본 논문에서는 파라메터가 주어진 문제가 다항식 크기의 커널이 없다는 것을 보이는 방법을 일반화하고, 특별히 Graph Isomorphism 문제의 경우에는 어느 파라메터가 주어지면 다항식 크기의 커널이 없는지 연구하였다.
이것을 위해 AND-composition과 AND-distillation이라는 두 개념의 관계를 이용한다. AND-distillation이란 어떤 문제의 여러 instance가 주어지면 이것들을 어느 의미로 압축하는 알고리즘을 말한다. P에 포함되지 않은 문제의 경우에는 이런 알고리즘이 존재하지 않는다고 추측할 수 있다. 한편 AND-composition이란 파라메터가 주어진 문제의 여러 instance가 주어지면 이것들을 합치는 알고리즘을 말한다. AND-distillation과 달리, 많은 경우에는 AND-composition 알고리즘이 존재한다는 것을 증명할 수 있다. 이 이론의 핵심은 파라메터가 주어진 문제는 AND-composition과 다항식 크기의 커널을 함께 가지면 AND-distillation도 가진다는 정리 이다.
본 논문에서는 Graph Isomorphism 문제가 연결된 그래프의 rooted tree distance width, 일반화된 rooted tree distance width, tree-width와 maximum degree를 파라메터로 갖는 각각의 경우에 AND-composition을 가진다는 것을 증명했다. 그러므로 이 문제가 AND-distillation이 없다는 추측이 맞다면, 위에 언급한 각 파라메터를 갖는 Graph Isomorphism 문제는 다항식 크기의 커널이 없다는 결론을 낼 수 있다.
