커널화

컴퓨터 과학에서 커널라이제이션은 알고리즘에 대한 입력이 "커널"이라고 불리는 더 작은 입력으로 대체되는 전처리 단계에 의해 효율을 달성하는 효율적인 알고리즘을 설계하는 기법이다.커널에서 문제를 해결한 결과는 원래 입력과 같거나, 커널의 출력을 원래 문제에 대해 원하는 출력으로 쉽게 변환할 수 있어야 한다.

커널화는 흔히 다루기 쉬운 인스턴스의 일부를 잘라내는 일련의 감소 규칙을 적용함으로써 이루어진다.매개 변수화된 복잡성 이론에서, (문제와 관련된 일부 매개 변수의 함수로서) 커널의 크기에 대한 한계가 보장된 커널을 다항식 시간에서 찾을 수 있다는 것을 증명할 수 있는 경우가 많다.이것이 가능하다면, 그것은 커널을 해결하기 위한 (폴리놈 시간) 커널화 단계와 (비폴리놈이지만 파라미터에 의해 경계된) 시간의 합인 고정 매개변수 추적 가능한 알고리즘을 낳는다.실제로 고정 매개변수 추적 가능한 알고리즘으로 해결할 수 있는 모든 문제는 이러한 유형의 커널화 알고리즘으로 해결할 수 있다.

예제: 꼭지점 커버

커널화 알고리즘의 표준 예로는 S에 의한 정점 커버 문제의 커널화가 있다.버스.^[1] 이 문제에서 입력은 숫자 $k{\displaystyle }$ ${\displaystyle k}$과(와$$) 함께 비방향 $그래프{\displaystyle }$ G ${\displaystyle G}$입니다$.$출력은 $최대{\displaystyle }$ k {\$displaystyle k}$ 정점$$ 집합으로, 이러한 집합이 있는 경우 그래프에 있는 모든 에지의 끝점을 포함하거나, 그러한 집합이 없는 경우 실패 예외를 포함한다$.$이 문제는 NP-hard이다.단, 커널라이징에는 다음과 같은 감소 규칙을 사용할 수 있다.

1. > ${\displaystyle k>0}$ 및 v ${\displaystyle v}$이(가) k ${\displaystyle k}$보다 큰 정도의 정점인 경우$$ $그래프$에서 v ${\displaystyle v}$을(를) 제거하고 $k{\displaystyle }$ ${\displaystyle$ k}을(를$)$ 하나씩$$ 감소시키십시오$.$k $크기{\displaystyle }$ ${\displaystyle k}$의 모든 꼭지점 커버에는 $v{\displaystyle }$ ${\displaystyle v}$이(가) 포함되어야$$ 하며 그렇지 않을 경우 사건 가장자리를 덮기 위해 인접 영역을 너무 많이 선택해야 하기 때문이다$$.따라서 $원래{\displaystyle }$ 그래프의 최적 꼭지점 $커버$는 v {\displaystyle $v}$을(를$)$ 커버에 다시$$ 추가함으로써 감소된 문제의 커버에서 형성될 수 있다.
2. $v{\displaystyle }$ ${\displaystyle v}$이(가) 분리된 꼭지점인 경우 제거하십시오.절연된 꼭지점은 가장자리를 덮을 수 없으므로 이 경우 $v{\displaystyle }$ ${\displaystyle v}$은(는) 최소 커버의 일부가 될 수 없다$$.
3. k ${\displaystyle {2\mathrm{}}^{}}$ ${\$개 이상의 가장자리가$$ 그래프에 남아 있고 앞의 두 규칙 중 어느 것도 적용할 수 없는 경우, 그래프에는 k $크기{\displaystyle }$ k ${\displaystyle k}$의 꼭지점 표지가 포함될 수 없다$.$ 왜냐하면,$$k {\$displaystyle k}$보다 큰 모든 정점을 제거한 후$,$ 남은 각 꼭지점은 최대치까지만 커버할 수 있다.${\displaystyle k}$ ${\displaystyle k}$ 가장자리와$$ $k{\displaystyle }${\$displaystyle k}$ 꼭지점$$ $집합$은 ${\displaystyle {최대\mathrm{}}^{}}$ k$$2 {\$displaystyle k^{$2}}개의$$ 가장자리만 포함할 수 있다.이 경우 인스턴스는 하나의 에지와 $k{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle k=0}$이($$가) 있는 인스턴스로 대체될 수 있으며, 이 인스턴스는 해결책이 없다.

$더{\displaystyle {}^{}}$ 이상 감소를 할 수 없을 때까지 이러한 규칙을 반복적으로 적용하는 알고리즘은 최대 2 k ${\$ k$^{2}}$개의 가장자리가$$ 있고 (각 가장자리의 끝점이 최대 2개 있고 분리된 정점이 없기 때문에) 최대 $2{\displaystyle \mathrm{}}$ ${\displaystyle {k\mathrm{}}^{}}$ 2 ${\$}}개의$$정점을 가진 커널로 종료해야 한다.이 커널화는 선형 시간에 구현될 수 있다.일단 커널이 구성되면, 꼭지점 커버 문제는 커널의 각 부분집합이 커널의 커버인지 여부를 테스트하는 짐승 같은 힘 검색 알고리즘에 의해 해결될 수 있다.따라서 정점 커버 문제는 시간 $O{\displaystyle ({\mathrm{}}^{}}$ k ${\displaystyle {{2\mathrm{}}^{}}^{}}$+ ${\displaystyle n}$+ m ${\displaystyle )}$에 $n{\displaystyle }$ ${\displaystyle n}$ 정점과$$ $m{\displaystyle }$ ${\displaystyle$ m$}$ $가장자리$가 있는 그래프의 $경우$$,$ 시간 O$(2^{2k^{2}}+n+m)$로 해결할 수 있어, $n{\displaystyle }$ ${\displaystyle$n}과$$ {$di$$}$이 작더라도$$ $효율적$으로 $해결할$수 있다.$splaystyle m}$은(는) 둘 다 크다.

이 경계는 고정 매개변수 추적 가능하지만 매개변수에 대한 의존도는 원하는 것보다 높다.보다 복잡한 커널화 절차는 커널화 단계에서 더 많은 실행 시간을 희생하면서 더 작은 커널을 찾아냄으로써 이러한 경계를 개선할 수 있다.꼭지점 커버 예에서 커널화 알고리즘은 최대 $(\displaystyle 2k})$ 정점을$$ 가진 커널을 생성하는 것으로 알려져 있다.이러한 개선된 경계를 달성하는 하나의 알고리즘은 Nemhauser와 Trotter로 인해 정점 커버의 선형 프로그램 완화의 절반의 무결성을 이용한다.^[2]이 바인딩을 달성하는 또 다른 커널화 알고리즘은 크라운 축소 규칙이라고 알려진 규칙에 기초하고 교대 경로 인수를 사용한다.^[3]정점 수 측면에서 현재 가장 잘 알려진 커널화 알고리즘은 Lampis(2011년)에 기인하며 고정 $상수{\displaystyle }$ c$$${\displaystyle \{\backslash }$$displaystyle$ $2k-c\$$log$ k$}$ $정점$을 ${\displaystyle \mathrm{2k}}$ ${\displaystyle -}$ c ${\displaystyle \mathrm{로그}}$에 달성한다$.$

P = NP가 아닌 한 이 문제에서 크기 O${\displaystyle (}log{\displaystyle \log }$ k$){\displaystyle O(\log$ k$)}$의 커널을 찾는 것은 불가능하며, 그러한 커널에 대해 NP-하드 꼭지점 커버 문제에 대한 다항 시간 알고리즘을 초래할 수 있다$.$지 않는 한 coNP NP/poly(가능성 복잡성 이론가들에 의해 믿어지), 모든 ϵ 을에{\displaystyle \subseteq}⊆ 하지만, 커널 크기에 훨씬 더 강한 경계를 이 경우에:;0{\displaystyle \epsilon>0}이 다항 시간에 O(k2− ϵ){\displaystyle O(k^{2-\epsilon}과 알맹이들을 찾는 것은 불가능하다 증명될 수 있다.)}${\displaystyle \mathrm{가장자리}}.$^[4] $\$$$> $0$ {\$displaystyle$ ($2-\$$epsilon$$)k}$의 정점을 가진 커널이 예상 밖의 복잡성-이론적 결과를 가져올지는 정점 커버에 대해서는 알 수 없다.

정의

문헌에서는 커널라이제이션이 어떻게 공식적으로 정의되어야 하는가에 대한 명확한 공감대가 없고 그 표현의 용도에 미묘한 차이가 있다.

다우니-펠로우즈 표기법

다우니 & 펠로우즈(1999년) 표기법에서 매개변수화된 문제는 의사결정 문제를 설명하는 $부분집합$ L${\displaystyle {\mathrm{}}^{}}$ ∗ ${\displaystyle {}^{}}$ ${\displaystyle N\mathbb{}}$ ${\$이다.

매개 변수화된 문제 $L{\displaystyle }$ ${\displaystyle L}$에 대한 커널라이징은 인스턴스$({\displaystyle x}$, k${\displaystyle }$) ${\displaystyle(x,k)}$을(를) 취하여$$ ${\displaystyle x}$ $displaystyle$ x ${\displaystyle {\}}^{}}$ 및$$ $k{\displaystyle }$ ${\displaystyk$의 시간 다항식$x,k)$으로 매핑하는 알고리즘이다$$.

• ${\displaystyle (}$ ${\displaystyle x}$, ${\displaystyle k}$) ${\displaystyle (x,$${\displaystyle {}^{}}$$)}$이$({\displaystyle {}^{}}$) $L{\displaystyle }$ ${\$$displaystyle L}($x$$ $only{\displaystyle }$${\displaystyle }$, k ${\displaystyle {\prime }^{}}$) ${\displaystyle (x',k')$인 경우에만$$ L {\$displaystyle$ L$}$에 $있다$
• $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ x$'}$의 크기는 $k{\displaystyle }$ ${\displaystyle k}$의 계산 가능한 함수 $f{\displaystyle }$ ${\displaystyle f}$에 의해 제한되며$,$
• ${\displaystyle k^{}}$ ${\displaystyle {\prime }^{}}$ ${\$은(는) $k{\displaystyle }$ ${\displaystyle k}$의 함수에 의해 제한된다$.$

커널화의 출력$$($($ , k ${\displaystyle {\prime }^{}}$) {\$displaystyle (x',k')$을 커널이라고 한다.이러한 일반적인 맥락에서 문자열 $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$의 크기는 문자열의 길이만$$ 가리킨다.일부 저자들은 그래프 문제의 맥락에서 크기를 측정할 때 정점의 수나 가장자리 수를 사용하는 것을 선호한다.

플럼-그로헤 표기법

In the notation of Flum & Grohe (2006, p. 4), a parameterized problem consists of a decision problem ${\displaystyle L\subseteq \Sigma ^{*}}$ and a function ${\displaystyle \kappa :\Sigma ^{*}\to \mathbb {N} }$, the parameterization.인스턴스 $x{\displaystyle }$ ${\displaystyle x}$의 매개 변수는 숫자 ${\displaystyle \kappa }$( x${\displaystyle }$) ${\displaystyle \kappa (x)}$ 입니다$.$

매개 변수화된 문제 $L{\displaystyle }$ ${\displaystyle L}$에 대한 커널라이징은 매개 $변수{\displaystyle }$ k ${\displaystyle k}$이(가) 있는 인스턴스 $x{\displaystyle }$ ${\displaystyle x}$을(를) 가져와서$$ 다항 시간 내에 인스턴스 $y{\displaystyle }$ ${\displaysty y}$에 매핑하는$$ 알고리즘이다$$.

• ${\displaystyle }$$y{\displaystyle }$ ${\\displaystyle y$}이(가) L$${\$displaystyle L$}에$$$$ 있는 경우에만$$ x ${\displaystyle$ $x$$}$이(가) $L$에 있고
• $y{\displaystyle }$ ${\displaystyle y}$의 크기는 $k{\displaystyle }$ ${\displaystyle k}$의 계산 가능한 $함수{\displaystyle }$ f ${\displaystyle f}$에 의해 제한된다$.$

이 표기법에서 $y{\displaystyle }$ ${\displaystyle y}$의 크기에 대한 바운드는 $y{\displaystyle }$ ${\displaystyle y}$의 매개 $변수$도 k ${\displaystyle$k$\}$의 함수에 의해 경계됨을$$ 의미한다는$$ 점에 유의하십시오.

$f{\displaystyle }$ ${\displaystyle f}$ 함수를$$ 커널 크기라고 부르는 경우가 많다.$f{\displaystyle }$${\displaystyle }$= ${\displaystyle {\mathrm{k}}^{}}$ ${\displaystyle O^{}}$( 1${\displaystyle {}^{}}$) ${\$$displaystyle$ $f=k^{O(1)}}}$이$($가$)$ 다항식 커널을 인정한다고$$ 한다.마찬가지로 $f{\displaystyle }$= ${\displaystyle O}$( $){\$ f$={O(k)}}}}}}$에 대해서도 문제는 선형 커널을 인정한다$.$

커널라이저성과 고정 매개변수 트랙터성이 동일함

문제는 커널링 가능하고 해독 가능한 경우에만 고정 매개변수가 추적 가능하다.

커널라이블 및 디커블이 가능한 문제가 고정 매개변수라는 사실은 위의 정의에서 확인할 수 있다.먼저 일부 c에 대해$$ 시간 $O{\displaystyle (}$ ${\displaystyle {}^{}}$ ${\displaystyle c{}^{}}$) ${\displaystyle O(x ^c})$로 실행되는 커널화 알고리즘을 호출하여 크기 $f{\displaystyle (k}$) ${\displaystyle f(k)}$의 커널을 생성한다$.$그리고 나서 그 커널은 문제가 디커블이 가능하다는 것을 증명하는 알고리즘에 의해 해결된다.이 절차의 총 실행 시간은 $g{\displaystyle }$( ${\displaystyle f}$(${\displaystyle k}$)${\displaystyle }$+ O${\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle c{}^{}}$) ${\displaystyle g(f(k)+O(x ^{c})}$이며$,$ 여기서 $g{\displaystyle }$(${\displaystyle n}$) ${\displaystyle g(n)}$은 커널을 해결하는 데 사용되는 알고리즘의 실행 시간이다$$.$g{\displaystyle }$( ${\displaystyle f}$ (${\displaystyle k}$)$${\$displaystyle$ g($k)}$을(를$)$ 연산할 수 있다는$$$$ 가정과 같은 $예$로서${\displaystyle }$f${\displaystyle }$( k$$) {\$displaystyle f($k$)\}$의 가능한 모든 입력 $길이$를 테스트함으로써, 이는 문제가 고정 매개변수 추적 가능하다는 것을 의미한다.

또 다른 방향은 고정 매개변수 추적 가능한 문제가 커널링 가능하고 디커블이 가능하다는 것이다.질문이 비경쟁적이라고 가정해 보십시오. 즉, $언어$에 I y ${\displaystyle e_{}}$ ${\displaystyle s_{}}$ ${\$라고 하는 인스턴스 하나와 언어에 없는 인스턴스 하나, $즉{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{In}}_{}}$ o$${\$displaystyle I_{no}$라고 하는 인스턴스 하나 이상이 있다고 가정해 보십시오$.$ 그렇지 않으면 빈 문자열로 인스턴스를 대체하는 것은 유효한 커널화입니다.Assume also that the problem is fixed-parameter tractable, i.e., it has an algorithm that runs in at most ${\displaystyle f(k)\cdot x ^{c}}$ steps on instances ${\displaystyle (x,k)}$, for some constant ${\displaystyle c}$ and some function ${\displaystyle f(k)}$. To kernelize입력, ${\displaystyle 최대}$ ${\displaystyle {}^{}}$c + ${\displaystyle 1^{}}${\$displaystyle x$^{$c+1$} 단계에$$ 대해 지정된 입력에서 이 알고리즘을 실행하십시오.응답과 함께 종료되는 경우, 이 대답을 사용하여 $I{\displaystyle {}_{}}$ y ${\displaystyle e_{}}$ s ${\$ 또는$$ ${\displaystyle {In}_{}}$ ${\displaystyle o_{}}$ ${\$ 중 하나를 커널로 선택하십시오$$.대신, 종료하지 않고 스텝 수에 따라$$ 바인딩된 ${\displaystyle {}^{}}$ ${\displaystyle c{}^{}}$+ ${\displaystyle 1^{}}$ ${\$x$^{c+1}$를 초과하면$,{\displaystyle }$ (x ,${\displaystyle k}$) ${\displaystyle (x,k)$ 자체를$$ 커널로 반환한다.왜냐하면(x, km그리고 4.9초 만){\displaystyle(x,k)}은 커널로 입력의 F, f.(k)⋅으로 돌아왔다)c>)댁+1{\displaystyle f(k)\cdot)^{c}>^^{c+1}}, 그것은 대부분의 정도 들 것에{나는 es, 나는시, f(k)의 스녀 y}{\displaystyle은 커널의 크기는 이 방법에서 생산된 것. \max\${ I_{yes}, I_{no},f(k$ $){\displaystyle f(k)}}$을(를) 계산할 수 있다는 고정-변수 추적성 가정으로 이 크기 바운드를 계산할 수 있다.

더 많은 예

• 꼭지점 커버의 크기에 따라 파라메트릭된 꼭지점 커버:정점 커버 문제에는 최대 ${\displaystyle \mathrm{2k}}$ ${\displaystyle 2k}$의 $정점$과 O${\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle O(k^{2})$의 가장자리가 있는 커널이 있다.^[5], > {\$displaystyle \varepsilon >0}$의 경우$,$ ${\displaystyle \text{coNP}}$ ${\displaystyle \subseteq }$ ${\displaystyle \text{NP/poly}}${\$displaystyle {\coNP}\subseteq${\$text}$이$($가)가 아닌 한 꼭지점 커버에 $(k$ 2${\displaystyle {}^{}}$-$ε)$가 있는 커널이 없다.$NP/폴리$^[4]The vertex cover problems in ${\displaystyle d}$-uniform hypergraphs has kernels with ${\displaystyle O(k^{d})}$ edges using the sunflower lemma, and it does not have kernels of size ${\displaystyle O(k^{d-\varepsilon })}$ unless ${\displaystyle {\text{coNP}}\subseteq {\t$$ext{NP/폴리}}}$^[4].
• 피드백 정점 집합의 크기로 파라메타된 피드백 정점 집합:피드백 정점 세트 문제에는 ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\$개의 정점과$$ $O{\displaystyle }$ ${\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle O(k^{2})$의 가장자리가$$ 있는 커널이 있다.^[6]또한, ${\displaystyle \text{coNP}}$ ${\displaystyle \subseteq }$ ${\displaystyle \text{NP/poly}}$ ${\${nP}\$text${\text$}$가 아닌 한, $O{\displaystyle ({k\mathrm{}}^{}}$ -${\displaystyle {\epsilon }^{}}$ ${\displaystystyle O(k^{2-\varepsilon }})$ 에지가$$ 있는 커널은 없다.$NP/폴리$^[4]
• ${\displaystyle k}$ ${\displaystyle k}$ -path$$:$k{\displaystyle }$ ${\displaystyle k}$ -path$$ 문제는 주어진 그래프의 길이가 $적어도{\displaystyle }$ k$${\$displaystyle$ k$}$인지 여부를 결정하는 것이다$.$이 문제는 $k{\displaystyle }$ ${\displaystyle k}$의 크기 지수화된 커널을 가지며$,$ ${\displaystyle \text{coNP}}$ ${\displaystyle \subseteq }$ ${\displaystyle \text{NP/폴리}}$ ${\$이(가) 아닌 한 k ${\displaysty k}$에 크기 다항식의 커널을 가지지 않는다.$NP/폴리$^[7]
• 입찰 차원의 문제:많은 매개변수화된 2차원 문제 버전은 평면 그래프에 선형 커널을 가지며, 더 일반적으로 일부 고정 그래프를 부차 그래프로 제외한 그래프에 선형 커널을 가진다.^[8]

구조 매개변수를 위한 커널화

위의 예에서 $매개$ 변수 k ${\displaystyle k}$을(를) 원하는 용액의 크기로 선택하지만, 이것은 필요하지 않다.입력의 구조적 복잡성 측도를 매개변수 값으로 선택할 수도 있어 이른바 구조 매개변수화(structural parameteration)로 이어진다.이 접근방식은 솔루션 크기가 크지만 다른 복잡성 측정이 제한되는 경우에 효과적이다.예를 들어, 비방향 $그래프{\displaystyle }$ G ${\displaystyle G}$의 피드백 정점 번호는 제거가 $G{\displaystyle }$ ${\displaystyle G}$을(를) 반복하는 정점 집합의 최소 카디널리티로 정의된다$$.입력 그래프의 피드백 정점 번호에 의해 파라미터화된 정점 커버 문제는 다항식 커널라이제이션:^[9]피드백 정점 번호가 $k{\displaystyle }$ ${\displaystyle$ $k$$}$인 $그래프$ G ${\displaystyle G}$을$($를) 지정하면$$$G{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$$displaystyle G$의 최소 정점 커버를 G${\displaystyle }$′ {\$displaystystyle$ G$'''$로 변환할$$ 수 있도록 $그래프{\displaystyle {}^{}}$ G ${\displaystyle {\prime }^{}}$ ${\$${\displaystyle {d\mathrm{}}^{}}$}을 출력하는 $다항식$ 알고리즘이 있다.다항식 시간에서$$ $G{\displaystyle }$ ${\displaystyle G}$에 대한 최소 꼭지점 커버.따라서 커널라이제이션 알고리즘은 피드백 정점 수 $k{\displaystyle }$ ${\displaystyle k}$이(가) 작은 인스턴스로 축소되도록$$ 보장한다.

참고 항목

• 반복 압축, 고정 매개변수 추적 가능한 알고리즘에 대한 다른 설계 기법

메모들

참조

• Abu-Khzam, Faisal N.; Collins, Rebecca L.; Fellows, Michael R.; Langston, Michael A.; Suters, W. Henry; Symons, Chris T. (2004), Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments (PDF), University of Tennessee.
• Bodlaender, Hans L.; Downey, Rod G.; Fellows, Michael R.; Hermelin, Danny (2009), "On problems without polynomial kernels", Journal of Computer and System Sciences, 75 (8): 423–434, doi:10.1016/j.jcss.2009.04.001.
• Buss, Jonathan F.; Goldsmith, Judy (1993), "Nondeterminism within ${\displaystyle P^{*}}$", SIAM Journal on Computing, 22 (3): 560–572, doi:10.1137/0222038, S2CID 43081484.
• Chen, Jianer; Kanj, Iyad A.; Jia, Weijia (2001), "Vertex cover: Further observations and further improvements", Journal of Algorithms, 41 (2): 280–301, doi:10.1006/jagm.2001.1186, S2CID 13557005.
• Dell, Holger; van Melkebeek, Dieter (2010), "Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses" (PDF), Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), pp. 251–260, doi:10.1145/1806689.1806725, S2CID 1117711.
• Downey, R. G.; Fellows, M. R. (1999), Parameterized Complexity, Monographs in Computer Science, Springer, doi:10.1007/978-1-4612-0515-9, ISBN 0-387-94883-X, MR 1656112, S2CID 15271852.
• Flum, Jörg; Grohe, Martin (2006), Parameterized Complexity Theory, Springer, ISBN 978-3-540-29952-3, retrieved 2010-03-05.
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. (2010), "Bidimensionality and kernels", Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 503–510.
• Jansen, Bart M. P.; Bodlaender, Hans L. (2013), "Vertex Cover Kernelization Revisited - Upper and Lower Bounds for a Refined Parameter", Theory Comput. Syst., 53 (2): 263–299, doi:10.1007/s00224-012-9393-4,
• Lampis, Michael (2011), "A kernel of order 2k − c log k for vertex cover", Information Processing Letters, 111 (23–24): 1089–1091, doi:10.1016/j.ipl.2011.09.003.
• Thomassé, Stéphan (2010), "A 4k² kernel for feedback vertex set", ACM Transactions on Algorithms, 6 (2): 1–8, doi:10.1145/1721837.1721848, S2CID 7510317.
• Niedermeier, Rolf (2006), Invitation to Fixed-Parameter Algorithms, Oxford University Press, ISBN 0-19-856607-7, archived from the original on 2008-09-24, retrieved 2017-06-01.

추가 읽기

• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019), Kernelization: Theory of Parameterized Preprocessing, Cambridge University Press, p. 528, doi:10.1017/9781107415157, ISBN 978-1107057760
• Niedermeier, Rolf (2006), Invitation to Fixed-Parameter Algorithms, Oxford University Press, Chapter 7, ISBN 0-19-856607-7, archived from the original on 2007-09-29, retrieved 2017-06-01
• Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), Parameterized Algorithms, Springer, Chapters 2 and 9, ISBN 978-3-319-21274-6