Kernels in FPT

어떤 decision problem에 대해서, kernel은 그 decision problem의 답을 보존하는 작은 인스턴스다. 그러니까 f : Instance -> Instance인데

• $|f(x)| \leq g(k)$
• $Decision(x) = Decision(f(x))$
  같은 함수가 있으면, decision problem은 $g(k)$ 크기의 kernel이 있다고 함

자명한 theorem은, 모든 FPT 문제는 다항시간에 찾을 수 있는 kernel이 존재한다는 것이다.
구체적으로 decision problem을 $g(k) n^c$ 에 풀 수 있으면 poly time에 kernel을 찾을 수 있음. 방법은:

• $n \geq g(k)$ 면, 그냥 $n^{c+1}$에 풀고 trivial yes / no instance를 반환한다.
• $n < g(k)$ 면, 그냥 입력이 g(k) 크기의 kernel이다.

물론 poly-time에 찾을 수 있는 kernel이 존재하면 FPT이다. kernel을 찾고, 그 안에서 그냥 $f(k)$ 시간에 풀면 됨. 그러면 kernel 찾은 후 $f(g(k))$ 에 해결. 여기서 또 한가지 알 수 있는 건 kernel은 그냥 yes/no만 보존하면 되고 certificate를 줄 필요는 없음. 마치 NP-complete가 decision problem에 대해서만 정의되고 certificate랑 아무 상관 없는것과 동일 (물론 그 proof가 대개 certificate랑 일치하지만)

Takeaway는 "다항시간에 찾을 수 있는" kernel 은 그냥 FPT를 정의하는 여러 방법 중 하나라는 것이다. "지수시간에 찾을 수 있는" kernel은, 지수 시간 알고리즘만 있으면 FPT가 없어도 존재한다. 그냥 풀고 yes/no를 찍으면 됨. 비슷하게, $f(k)$ 크기의 kernel이 존재하냐는 자명하게 yes지만, $f(k) \leq poly(k)$ 크기의 kernel이 존재하냐는 어려운 문제일 수 있다. 예를 들어 길이 k의 simple path가 있는지는 FPT로 해결할 수 있지만 (color coding) $poly(k)$ 크기의 kernel이 존재하면 polynomial hierarchy가 무너진다고 들었다.

vertex cover는 $2k$ 크기의 kernel을 poly-time에 구할 수 있는데 이를 아래에 소개함

Theorem: k-vertex cover는 2k개 이하의 정점을 가지는 kernel이 존재한다.
Proof. min(sum x_v) st x_u + x_v >= 1 형태의 LP relaxation을 생각해보자. LP는 polytime에 풀 수 있다. 만약 LP의 값이 k 이상이면 당연히 NO instance. 그러니까 LP 값이 $k$ 이하라고 가정.

$P = {v | x_v > 1/2}, Z = {v | x_v = 1/2}, N = {v | x_v < 1/2}$ 로 정의하자. $|P \cup Z| \leq 2k$ 이다. 또한 $P \subseteq S \subseteq P \cup Z$ 인 minimum V.C 가 존재한다 (증명) 이제, $N$ 은 다 날리고, $P$ 는 다 선택한 그래프에서 minimum V.C 를 풀자. 원래 그래프의 MVC가 $k$ 이하면 저 그래프에서도 MVC가 $k$ 이하임을 보였다. 저 그래프의 MVC는 무조건 원래 그래프의 MVC인게, $N$ 에 인접한 모든 간선은 반대쪽 끝이 $P$ 에 있어서 항상 만족이 되기 때문이다. kernelization 끝.