【読書メモ】Parameterized Algorithms 第2章 Kernelization

\def\middlemid{\;\middle|\;}
\def\set#1{\left\{{#1}\right\}}
\def\setin#1#2{\left\{{#1} \middlemid {#2}\right\}}
\def\sub#1#2{{#1}_{#2}}

Parameterized Algorithms (Cygan et al., 2015) を読んでいます。各節の備忘録と、特に理解に時間がかかったところについて、理解するためのポイントをまとめます。

現在更新中です。下書きのため、未定義の用語が使われている部分や誤った引用、不正確な記述／表現が含まれる可能性があります。

Chapter 2 Kernelization

最初に、Felix Reidl によるリスが硬い殻を割って中の柔らかい実を食べている挿絵があります。これはカーネル化をとても美しく表現した比喩だと思います。我々が本当に興味を持つべきなのは問題の本質的な部分、すなわちカーネルであり、それを覆う殻は問題サイズを削減する前処理によって取り除かれるべきものです。本章では、その殻をどのように取り除くのか、そして取り除いた後に得られるカーネルがどのような性質を持つのかについて、いくつかの例を通して説明されています。

前処理の起源は Quine が 1950 年に真理関数を簡略化するために還元規則を定義したことにまで遡ります。それ以降、商用ソルバーの成功によって裏付けられる形で、その重要性が認識されていきました。しかしながら、後述するように前処理の枠組みの構築が困難であったという背景があり、その理論的な理解は、パラメータ化された計算量の枠組みの中で、体系的に研究されるようになりました。Mike Fellows は、この期間を「多項式時間前処理の失われた大陸」と呼んでいます。

前処理の枠組みの構築の難しさの一端が垣間見える例が紹介されていました。好きな $\mathcal{NP}$ 完全な問題を頭に思い浮かべながら、メタ的に「有用な前処理アルゴリズム」とは何か考えてみることにしましょう。例えば、入力サイズの多項式時間で動作し、入力サイズを 1 ビットでも削減し、同値な（変換前後で Yes/No が変化しない）インスタンスを出力するものと定義してみます。残念ながら、$\mathcal{P} \neq \mathcal{NP}$ を信じるならば、この定義は破綻します。なぜなら、もしそのような前処理アルゴリズムが存在するならば、$\mathcal{NP}$ 完全な問題のインスタンスを多項式時間で簡略化できることになり、このアルゴリズムを繰り返し適用すれば、最終的には定数サイズのインスタンスにまで削減できることになるからです。定数サイズのインスタンスは、定数時間で解くことができるため、$\mathcal{NP}$ 完全な問題を多項式時間で解くことができることになってしまいます。これは $\mathcal{P} = \mathcal{NP}$ を意味します。

パラメータ化問題の文脈の中で、ようやく「有用な前処理アルゴリズム」の定義に成功し、前処理アルゴリズムが理論的にも日の目を見るようになりました。直感的には、パラメータ $k$ を用いて、出力されたインスタンスのサイズを $k$ の関数で抑えることを試みます。興味深い点は、$k$ が定数であるならば、入力されたインスタンスのサイズがどれほど巨大でも、ある一定のサイズまで削減できることが保証されるという点です。これがカーネル化アルゴリズムの基本的なアイデアです。

2.1 形式的な定義

問題固有の還元規則 (reduction rule) と呼ばれる、あるインスタンスを同値なインスタンスに変換するルールを定義します。これらのルールを組み合わせて、前処理アルゴリズムを構成します。

形式的に、還元規則とは、あるパラメータ化問題 $Q$ のインスタンス $(I, k)$ を、$|I|$ と $k$ の多項式時間で $Q$ の同値なインスタンス $(I', k')$ に変換するルールのことを指します。ここで $(I, k)$ と $(I', k')$ が同値であるとは、$(I, k)$ が Yes インスタンスのとき、$(I', k')$ も Yes インスタンスであり、$(I, k)$ が No インスタンスのとき、$(I', k')$ も No インスタンスであることを意味します。最後の同値性の要件は、「還元規則の安全性・健全性 (soundness)」と呼ばれます。変換前後でインスタンスの同値性が保たれているか確認したいときは「この還元規則は本当に安全なんですか？」と尋ねることができます。

この還元規則をコンポーネント的に組み合わせて、前処理アルゴリズムを構成します。当然ながら、還元規則そのものも前処理アルゴリズムといえますが、ここではいくつかの還元規則を、定められたルールに従って適用するアルゴリズムを前処理アルゴリズムと呼ぶことを指すようです。

さて、前処理アルゴリズム $\mathcal{A}$ の出力サイズというものを定義します。「計算量はパラメータの観点から測定されるべきである」というパラメータ化複雑性理論の哲学に従って、この出力サイズは $k$ の関数として次式のように定義されます。$$\text{size}_{\mathcal{A}}(k) = \sup \set{|I'| + k' : (I', k') = \mathcal{A}(I, k), I \in \Sigma^*}$$ 与えられた $k$ に対して、任意の $I$ に対して $\mathcal{A}$ を適用したときの出力インスタンス $(I', k')$ のサイズ $|I'| + k'$ の上限を取ることで、前処理アルゴリズムの出力サイズを定義しています。入力はパラメータ $k$ ですが、出力はインスタンスのサイズが絡むということに注意してください。例えば、前処理アルゴリズムとして、与えられたインスタンスをそのまま返すだけのアルゴリズムを考えます。このアルゴリズムの出力サイズは、入力インスタンスのサイズに依存するため、$k$ の関数として定義された出力サイズは無限大になります。よって、関数の値域は $\mathbb{N} \cup {\infty}$ であり、上限（supremum）を用いる必要があるわけです。

そのようなものが存在すること自体が非常に興味深いですが、カーネル化アルゴリズム (kernelization algorithm) と定義されるものでは、上の定義に加えて、出力サイズが $k$ の関数で抑えられることを要求します。つまり、ある計算可能関数 $g \colon \mathbb{N} \to \mathbb{N}$ が存在して、前処理アルゴリズム $\mathcal{A}$ の出力サイズが $g(k)$ 以下であることを要求します。どんなに莫大なインスタンスを与えたとしても、同時に与えた $k$ に対して $g(k)$ 以下のサイズのインスタンスに削減できることが保証されるわけです。これがカーネル化アルゴリズムの定義です。

上の定義は、計算可能な関数 $g$ が存在して、$(I', k')$ が $(I, k)$ に対する出力であるとき、$|I'| + k' \le g(k)$ を満たすことと同値です。

2.2 いくつかの単純なカーネル

2.2.1 頂点被覆

Fellows ら¹ によれば、パラメータ複雑性の中でショウジョウバエ的な位置付けにある問題であり、また著者の Fedor Fomin² のお気に入りでもある NP 完全問題が頂点被覆です。

この節では、Buss と Goldsmith³ による頂点数 $O(k^2)$ のカーネルが説明されています。

2.2.2 トーナメントにおけるフィードバック弧集合

Feedback Arc Set in Tournaments (FAST) 問題は、トーナメントにおいて、フィードバック弧集合のサイズを最小化する問題です。Charbit ら⁴ によって NP 困難であることが知られています。

• トーナメント：完全グラフの各辺を適当に向き付けたもの
• フィードバック弧集合：有向グラフの弧集合であって、任意の有向閉路の弧を少なくとも 1 つ含むもの

ここでは、これのパラメータ化された問題を考えます。すなわち、トーナメントと整数 $k$ が与えられたとき、$k$ 以下のサイズのフィードバック弧集合が存在するかどうかを判定する問題です。

FAST の応用

全チームの総当たり戦の結果はトーナメントとして表現でき、もしそれが非巡回であれば、トポロジカル順序によって全チームのランキングを決定できます。ですが、トーナメントに巡回がある場合、ランキングを決定することはできません。

しかし、有向グラフからフィードバック弧集合を削除することで、その有向グラフが非巡回になることが知られています。したがって、トーナメントからフィードバック弧集合を削除することで、ランキングを決定できるようになり、そのフィードバック弧集合のサイズが小さいほど、ランキングの信頼性が高いと考えられます。

前準備

FAST のカーネル化アルゴリズムの説明に先立ち、いくつかの（トーナメントに限定しない）グラフの有向非巡回性とフィードバック弧集合に関わる補題が紹介されます。

補題 2.5. では、グラフが有向非巡回であることとトポロジカル順序を持つことが同値であることを示します。直感的には、有向非巡回であるならば、左から右に向かって流れるようなグラフの描画ができるので、トポロジカル順序を持つことは明らかです。反対方向も同様に、トポロジカル順序で頂点を並べて、実際に辺を描画してやれば、左から右に伸びる辺はあれど、右から左に伸びる辺は決してないので非巡回であることが容易に言えます。

補題 2.5. は次の観察 2.6. を導きますが、その前に少し定義をします。

有向グラフ $G$ とその辺部分集合 $F \subseteq E(G)$ が与えられた時、$G \circledast F$ を、$G$ の各辺のうち、$F$ に含まれるものを反転して得られるグラフとして定義します。

図中のオレンジの辺を $F$ と定めると、右側が $F$ の辺が反転された $G \circledast F$ になります。

観察 2.6. $G$ を有向グラフ、$F$ を $G$ の辺の部分集合とする。$G \circledast F$ が有向非巡回グラフならば、$F$ は $G$ のフィードバック弧集合である。

$\circledast$ というのがグラフの一部の辺を反転させる操作で、それによって非巡回にできるのなら、フィードバック弧集合の定義では、それらの辺を取り除くというより強い操作を行うわけですから、当然取り除かれたグラフも非巡回であることは直感的に理解できます。

より形式的な証明は補題 2.5. から導けます。

$G \circledast F$ は非巡回なので、補題 2.5 により頂点のトポロジカル順序 $\sigma$ が存在します。すなわち、$G \circledast F$ の任意の辺 $(u, v)$ について $\sigma(u) < \sigma(v)$ です。

$G \circledast F$ の辺集合は $(E(G) \setminus F) \cup \text{rev}(F)$ ですから、

• $E(G) \setminus F$ の辺 $(u, v)$ はそのまま $G \circledast F$ の辺なので、$\sigma(u) < \sigma(v)$
• $F$ の辺 $(u, v)$ は $G \circledast F$ 内では反転されて $(v, u)$ となっており、$\sigma(v) < \sigma(u)$

ここで $G$ の任意の有向閉路 $C$ を考えます。$C$ の辺をたどると、$\sigma$ の値は各辺で増加するか減少します。もし $C$ の全ての辺が $E(G) \setminus F$ に属するなら、全ての辺で $\sigma$ が増加するので、一周して元の頂点に戻ったとき $\sigma$ の値が厳密に増加し続けたことになり矛盾します。

したがって $C$ は $F$ の辺を少なくとも 1 つ含みます。$G$ の任意の有向閉路についてこれが成り立つので、$F$ はフィードバック弧集合です。$\square$

この観察の逆は成り立つでしょうか？（演習 2.2）これは成り立ちません。3-サイクルにて、$F$ を $3$ 本の辺すべてと定めた場合が反例になります。（下図では、$G \setminus F$ をグラフから $F$ に含まれる辺を除いたグラフとしています）

しかし興味深いことに、$F$ が包含関係の下で極小であるという条件を付け加えると、この逆が成立します。上の例であれば、$G$ から任意の 1 辺からなる集合が極小なフィードバック弧集合になりますが、確かに $G \circledast F$ も非巡回になっています。よって、この条件の下ではこれらは同値であるというのが次の補題です。

補題 2.7. $G$ を有向グラフ、$F$ を $E(G)$ の部分集合とする。$F$ が $G$ の包含関係の下で極小なフィードバック弧集合であることと、$F$ が $G \circledast F$ を非巡回有向グラフにする包含関係の下で極小な辺集合であることは同値である。

($\Rightarrow$) 証明は背理法により行われます。$F$ を極小なフィードバック弧集合とし、$G \circledast F$ が有向閉路 $C$ を持つと仮定して矛盾を導きます。まず $F$ はフィードバック弧集合なので、定義により $E(G) \setminus F$ にはいかなる有向閉路も含まれません。よって $C \nsubseteq E(G) \setminus F$ がいえます。$f_1, f_2, \ldots, f_{\ell}$ を $C \cap \text{rev}(F)$ の辺の閉路 $C$ 上の出現順とし、それぞれの $f_i$ に対して、対応する $F$ の辺（反転させる前の $G$ の辺）を $e_i$ とします。

$F$ は包含関係の下で極小なので、各 $e_i$ に対して、$G$ 中に $F \cap C_i = \set{e_i}$ を満たす有向閉路 $C_i$ が存在します。

先述の通り $C \nsubseteq E(G) \setminus F$ なので、任意の $C_i$ について $F \cap C_i \neq \emptyset$ です。もし任意の有向閉路 $C_i$ に対して $F \cap C_i = \set{e_i}$ を満たさないような $e_i$ があれば（つまり、$F \cap C_i$ で $e_i$ が含まれているものは、必ず他の辺 $e_j \space (i \neq j)$ も一緒に含まれているとすると）、それは $F$ から取り去ってもフィードバック弧集合の定義を満たすことになります。

$G \circledast F$ における有向閉路 $C$ のうち、$f_1, f_2, \ldots, f_{\ell}$ の部分を、対応する閉路 $C_1, C_2, \ldots, C_{\ell}$ のそれぞれ $e_1, e_2, \ldots, e_{\ell}$ を取り去ったパスで置き換えた閉歩道を考えます（下図参照）。この閉歩道は $E(G) \setminus F$ の辺しか使っていないので（各有向閉路 $C_i$ は $F$ の辺を 1 つしか使わないことに注意してください）、$F$ がフィードバック弧集合であることに矛盾します。

よって、$F$ が極小なフィードバック弧集合であるならば、$G \circledast F$ は有向閉路 $C$ を持たないことが示せました。

最後に、$F$ の極小性（$G \circledast F$ は有向閉路 $C$ を持たないだけでなく、$F$ のどの辺を削除しても $G \circledast F$ が有向閉路を持つようになること）を示します。この $F$ が $G \circledast F$ を有向閉路を持たないようにするための極小な $F$ でないと仮定すると、いくつかの辺を取り去った $F'$ について、$G \circledast F'$ も有向閉路を持ちません。観察 2.6. によれば この $F'$ は $G$ のフィードバック弧集合ですが、$F' \subset F$ なので、$F$ の極小なフィードバック弧集合という条件に矛盾します。よって、順方向が証明できました。

($\Leftarrow$) $F$ を $G \circledast F$ を非巡回にする包含関係の意味で極小な辺集合とする。再び観察 2.6. から、$F$ はフィードバック弧集合です。そして、$F$ は包含関係の意味で極小なフィードバック弧集合であることが示せます。なぜならもし $F$ が極小でないとすると、$F$ の極小な真部分集合 $F'$ であって、$F'$ もフィードバック弧集合であるものが存在します。既に示したこの補題の順方向によって、$G \circledast F'$ は非巡回になりますが、これは $F$ の極小性に矛盾します。$\square$

FAST のカーネル化

補題 2.7. から、トーナメント $T$ がサイズ高々 $k$ のフィードバック弧集合を持つことと、高々 $k$ 本の弧の向きを反転して非巡回トーナメントにできることが同値であることがわかります。順方向については、サイズ $k$ 以下のフィードバック弧集合 $F$ があったとして、その部分集合であって極小な $F'$ は $T \circledast F'$ を非巡回にすることが補題 2.7. からいえます。逆方向については、観察 2.6. を用いて同じサイズのフィードバック弧集合が存在することがいえます。

これを用いて FAST に対する $k^2 + 2k$ 頂点のカーネルを導きます。

還元規則 FAST.1. 弧 $e$ が少なくとも $k+1$ の三角形に含まれるなら、$e$ を反転し $k$ を $1$ 減らす。

還元規則 FAST.2. 頂点 $v$ がいかなる三角形にも含まれないなら、$T$ から $v$ を削除する。

頂点被覆のところの還元規則 VC.1. が今回の FAST.2. に、VC.2. が FAST.1. に対応するイメージです。

FAST.1. について、弧 $e$ をフィードバック弧集合に含めないとすると、$e$ を含むそれぞれの三角形について $e$ 以外の計 $k+1$ 本以上の弧をフィードバック弧集合に含めなければいけないことになります。$k$ 以下のフィードバック弧集合しか許されないので、$e$ をフィードバック弧集合に含める必要があるわけです。

$e$ を含む 2 つの三角形について、$e$ 以外の単一の弧であって、それぞれの三角形を非巡回にできるものは存在しないことに注意してください。もしあれば、それらは同一の三角形です。よって $e$ を含むいくつかの三角形を非巡回にするために、$e$ を使わないとすると、各三角形から $e$ 以外の別個の弧をフィードバック弧集合に含める必要があります。

あくまで、$e$ を含む三角形に着目しているのであり、この反転操作によって有向閉路が新たに生まれる可能性はあります。

さて、FAST.1. の安全性を示します。インスタンス $(T, k)$ に対して、還元規則を適用して $(T \circledast \set{e}, k-1)$ が得られたとします。このとき、$k + 1$ 以上の三角形に含まれていた弧 $e$ を反転して $k$ を $1$ 減らすという操作を行ったとします。

まず $(T, k)$ が Yes インスタンスであれば、$(T \circledast \set{e}, k-1)$ も Yes インスタンスであることを示します。今、$T$ に対して、サイズ $k$ 以下のフィードバック弧集合が存在します。ここで、補題 2.7. の帰結から、サイズ $k$ 以下の弧部分集合 $F$ であって、$T \circledast F$ が非巡回であるものが存在します。もし $e \notin F$ であるとすると、観察 2.6. から $F$ は $T$ のフィードバック弧集合であるので、サイズが $k$ 以下の $e$ を含まないフィードバック弧集合が存在することになります。これは先の議論に矛盾するので、$e \in F$ であることがいえます。以上より、$(T \circledast \set{e}) \circledast (F \setminus \set{e}) = T \circledast F$ は非巡回なので、$(T \circledast \set{e})$ に対するサイズ $|F \setminus \set{e}| \le k - 1$ のフィードバック弧集合が存在することが示せました。

続けて $(T \circledast \set{e}, k-1)$ が Yes インスタンスなら、$(T, k)$ も Yes インスタンスであることを示します。これは $T \circledast \set{e}$ に対するサイズ $k-1$ 以下のフィードバック弧集合に $e$ を加えることで、$T$ に対するサイズ $k$ 以下のフィードバック弧集合が得られることからいえます。

以上より、FAST.1. の安全性が示せました。

次に、FAST.2. の安全性を示します。インスタンス $(T, k)$ に対して、還元規則を適用して $(T \setminus \set{v}, k)$ が得られたとします。このとき、頂点 $v$ がいかなる三角形にも含まれていないため、$v$ を削除するという操作を行ったとします。

$v$ がいかなる三角形にも属していないことから、$X := N^{+}(v)$ から $Y := N^{-}(v)$ への弧は存在しません。なぜなら、もし $x \in X$, $y \in Y$ について $x \to y$ なる弧があれば、$v \to x \to y \to v$ が三角形になってしまうからです。

このことから次の二つが従います。

• $T[X]$ の任意のフィードバック弧集合 $A_1$ と $T[Y]$ の任意のフィードバック弧集合 $A_2$ について、$A_1 \cup A_2$ は $T$ の フィードバック弧集合。なぜなら、$v$ から出る弧の行き先は $X$ のみ、$v$ に入る弧の出発元は $Y$ のみであり、$X$ から $Y$ への弧もないため、$v$ を経由する有向閉路は存在しません。$v$ を経由しない有向閉路も、$X$ から $Y$ への弧がないことから $T[X]$ または $T[Y]$ に完全に含まれます。
• 逆に $T$ の任意のフィードバック弧集合 $A$ について、$A \cap E(T[X])$ は $T[X]$ の フィードバック弧集合、$A \cap E(T[Y])$ は $T[Y]$ のフィードバック弧集合。

よって、$(T, k)$ が Yes インスタンスであることと $(T \setminus \set{v}, k)$ が Yes インスタンスであることは同値であることが示せました。

最後に、以上の還元規則が適用できないトーナメント $T$ について、Yes インスタンスなら $T$ の頂点数が $k^2 + 2k$ 以下になることを示します。インスタンス $T$ のサイズ高々 $k$ のフィードバック弧集合を $A$ とします。

還元規則 FAST.2. が適用できないことから、$T$ の任意の頂点は少なくとも 1 つの三角形に含まれていることがいえます。また、還元規則 FAST.1. が適用できないことから、各弧 $e \in A$ について、$e$ を含む三角形は高々 $k$ 個しかないことがいえます。よって、弧 $e$ を底辺と見做したとき、$k$ 個の三角形の（底辺に対しての）頂点と、底辺の両端点を合わせて高々 $k + 2$ 個の頂点が存在します。$A$ の各弧についてこのような集合が存在するので、$T$ の頂点数は高々 $k(k + 2) = k^2 + 2k$ 個であることが示せました。

この主張の対偶から、$T$ の頂点数が $k^2 + 2k + 1$ 個以上であるならば、即座に No インスタンスであることがわかります。以上によって FAST に対する $k^2 + 2k$ 頂点のカーネル化アルゴリズムが示せました。

2.2.3 辺クリーク被覆

多項式カーネルを持たない問題の例として、辺クリーク被覆問題 (Edge Clique Cover, ECC) が取り上げられました。下界の証明は後の章で説明するとして、ここでは指数関数のカーネルが存在することが示されました。

• クリーク：グラフの頂点集合の部分集合であって、任意の 2 頂点が隣接しているもの
• 辺クリーク被覆：グラフの全ての辺が、いずれかのクリークによって誘導される（完全）部分グラフの辺集合に含まれるように、高々 $k$ 個のクリークを選ぶ問題

ここで、ある辺がクリークによって被覆されるとは、その辺の両端点がクリークに含まれることを意味します。

辺のいずれか片方の端点が含まれていればいいわけではありません。つまり、この問題は頂点被覆問題（選べるクリークのサイズが 1 という意味での）の一般化ではありません。

ECC の応用

要調査！

ECC のカーネル化

孤立辺の両端点も同じ閉近傍を持つため、ECC.2. を適用できる状況では、代わりに ECC.3. も適用できるわけですが、ECC.2. を先に適用した方がより多くの頂点数と $k$ を減らせるので、それで今回は還元規則の優先順位が設定されていたということです。

• $N(v)$：頂点 $v$ に隣接する頂点の集合
• $N[v]$：頂点 $v$ とその隣接する頂点の集合

証明は還元規則を適用し尽くした後に、グラフの頂点数が $2^k + 1$ 個以上の Yes インスタンスが存在することを仮定する背理法を用いて行います。Yes インスタンスなので、$k$ 個のクリーク $C_1, C_2, \ldots, C_k$ が存在して、グラフの全ての辺がこれらのクリークのいずれかによって被覆されることになります。ここで、グラフの（$2^k + 1$ 個以上の）各頂点に対して、サイズ $k$ のベクトルを割り当てます。ベクトルの $i$ 番目の要素は、頂点がクリーク $C_i$ に含まれるかどうかを表す 0 または 1 になります。ベクトルとしてあり得るのは $2^k$ 通りしかないため、鳩の巣原理から、同じベクトルを割り当てられる頂点が少なくとも 2 つ存在し、それらを $u$ と $v$ とします。

まず、$u$ と $v$ に割り当てられたベクトルが共に非零要素をもつことを示します。還元規則を適用し尽くしているので $u$ と $v$ は孤立点でなく、少なくとも 1 つの辺に隣接していることになります。その辺は $C_1, C_2, \ldots, C_k$ のいずれかによって被覆されることになるため、$u$ と $v$ に割り当てられたベクトルの少なくとも 1 つの要素は 1 でなければなりません。

上の議論から、$u$ と $v$ が共に含まれるクリークが少なくとも 1 つ存在します。そのクリーク内では任意の 2 頂点が隣接するため、グラフに辺 ${u, v}$ が含まれます。

次に、$N[u] = N[v]$ であることを示します。$u$ と $v$ に割り当てられたベクトルは同じなので $u \in C_i \Leftrightarrow v \in C_i$ が成り立ちます。ここで、ある $u$ の隣接頂点 $w \in N(u)$ について、辺 ${u, w}$ は $C_1, C_2, \ldots, C_k$ のいずれかによって被覆されており、被覆したクリークには $v$ も属している ($u \in C_i \Leftrightarrow v \in C_i$ より) ので $w \in N(v)$ です。よって $N(u) \subseteq N(v)$ がいえるので、対称性から $N(v) \subseteq N(u)$ も成り立ちます。先の議論から、${u, v} \in E$ なので、$N[u] = N[v]$ がいえました。

しかしながら、$N[u] = N[v]$ であることは、ECC.3. が適用し尽くされていることに矛盾します。よってグラフの頂点数は $2^k$ 以下であることが示されました。$\square$

2.3 クラウン分解

各問題に対するアドホックなテクニックというよりは、もう少し一般的な多くの問題に対して適用できるカーネル化のテクニックの一つとしてクラウン分解があります。
この節では、クラウン分解の応用として頂点被覆と最大充足可能性問題が扱われています。

Kőnig の定理と Hall の定理が引かれた後、続いて Hopcroft-Karp のアルゴリズムが引用されています。Hopcroft-Karp の二つ目の主張は、二部グラフ $G = (V_1 \sqcup V_2, E)$ において、多項式時間で $V_1$ を飽和するマッチングを見つけるか、$|N(X)| < |X|$ を満たす包含関係のもとで極小な $V_1$ の部分集合 $X$ を見つけることができるというものです。

この主張は、次のクラウン補題の証明では用いられず、その後の最大充足可能性問題で使うことになります。なぜ極小であることが必要かという点もそこで明らかになります。

さて、これらを踏まえた上で、クラウン補題とは、頂点数 $3k + 1$ 個以上のグラフに対して、多項式時間でサイズ $k+1$ のマッチングかクラウン分解のいずれかを見つけることができるというものです。

アルゴリズムとしては、まず、貪欲法により極大マッチング $M$ を求めます。これがサイズ $k+1$ 以上であれば、そのマッチングを返して終了なので、以下 $|M| \le k$ を仮定できます。$V_M$ を $M$ の端点集合とすると、$|V_M| \le 2k$ で、さらに $I := V(G) \setminus V_M$ は独立集合になります。

$I$ と $V_M$ の頂点間の辺のみを取り出した $G$ の部分二部グラフ $G_{I,V_M}$ を考えます。$G_{I,V_M}$ に対して、Hopcroft-Karp のアルゴリズムを用いて、多項式時間で最大マッチング $M'$ と最小点被覆 $X$ を求めます。もし $|M'| \ge k + 1$ ならそのマッチングを返して終了なので、以降 $|M'| \le k$ を仮定します。Kőnig の定理から $|X| = |M'|$ なので、$|X| \le k$ がいえます。

ここで、$G_{I, V_M}$ において、$I$ の頂点であって孤立点であるものは存在しないことに注意します。なぜならば、$I$ は独立集合であり、また $G$ は孤立点を持たないので、$I$ の任意の頂点は少なくとも 1 つの $V_M$ 内の頂点と隣接していなければならないからです。よって、もし $X \subseteq I$ ならば、$X = I$ が自明に成り立ち、$|X| = |I| \ge 3k + 1 - 2k = k + 1$ となってしまい、$|X| \le k$ と矛盾してしまいます。以下、$X$ の頂点のうち、少なくとも 1 つが $V_M$ に含まれることを仮定します。

次のグラフは $X = I$ であって一見問題なさそうですが、マッチング（点線）$M$ のサイズが大きく、$k$ 以下に矛盾するので、やはりあり得ない例ということになります（$|V(G)| = 14 \ge 3 \times k + 1$ が必要なので、$k \le 4$ ですが、$|M| = 5 \ge 4 + 1 \ge k + 1$ の時点でアルゴリズムは終了しているはず）。

あり得るグラフの例（オレンジが頂点被覆 $X$）：

ここまできたら、クラウン分解が得られたも同然です。$M^*$ を $M'$ のうち、$X \cap V_M (\neq \emptyset)$ にちょうど 1 つの端点を持つ辺の部分集合とし、$V_{M^*}$ をその端点の集合とします。$V_{M^*} \cap I$ を $C$、$V_{M^*} \cap V_M$ を $H$、それ以外の $V(G)$ の頂点を $R$ とすると、$(C, H, R)$ はクラウン分解になります。なぜならば、$C$ の頂点は、$I \setminus C$ の頂点とは隣接せず、また $V_M \setminus H$ の頂点とも隣接しないため（もし $u \in C$ と $v \in V_M \setminus H$ とが隣接していたら、$v$ は $X$ に含まれるが、$u$ は含まれないため、$M^*$ の構成から $u$ と $v$ はそれぞれ $C$ と $H$ に入るはず）$H$ によって $C$ と $R$ が分離されており、$C$ と $H$ の間の辺集合 $M^*$ には $H$ を飽和するマッチングが含まれるからです。$\square$

2.3.1 頂点被覆

任意のマッチングのサイズが、最小点被覆のサイズの下界になっていることを利用します。

2.3.2 最大充足可能性問題

例えば 3 変数 5 節 の CNF 論理式とは
$$(x_1) \land (x_2 \lor \lnot x_3) \land (x_1 \lor x_2 \lor x_3) \land (\lnot x_1 \lor x_3) \land (\lnot x_1 \lor \lnot x_2 \lor x_3)$$ のようなものです。$(x_1, x_2, x_3) = (0, 0, 0)$ を割り当てると、2, 4, 5 番目の節が充足されます。

ある変数の割り当て $\psi$ で充足されなかった節は、リテラルの真偽を反転させた割り当て $\lnot \psi$ で充足されます。よって、ある割り当てで充足される節の集合を $S_{\psi}$ とすると、
$$\max(|S_{\psi}|, |S_{\lnot \psi}|) \ge (|S_{\psi}| + |S_{\lnot \psi}|) / 2 \ge |S_{\psi} \cup S_{\lnot \psi}|/2 = m/2$$ が成り立つので、任意の CNF 論理式に対して、充足される節の数が $m/2$ 以上になる割り当てが存在することになります。したがって、$k \le m/2$ の場合は Yes インスタンスであることがわかります。

ここで、以下のような二部グラフを考えます。変数と節を頂点とし、変数がその節に現れる（正または負のリテラルとして）場合に辺を張ります。

...

2.4 Expansion lemma

二部グラフ $G = (A \sqcup B, E)$ に対して、辺集合 $M \subseteq E$ が $q$-expansion であるとは、$A$ の全ての頂点が $M$ のちょうど $q$ 本の辺に接続し、$M$ が $B$ のちょうど $q|A|$ 頂点を飽和するものです（下図参照）。

$M$ によって誘導される $G$ の部分グラフは $|A|$ 個の点素な $q$-star から構成されることになります。

ここで、$A$ から $B$ への $q$-expansionが存在することと、すべての $X \subseteq A$ に対して $|N(X)| \ge q|X|$ が成り立つことが同値であることを示します。 確かに $1$-拡張がマッチングであることに注意すれば、この主張は Hall の定理の一般化であることがわかります。

($\Rightarrow$) については q-expansion の定義から明らかです。以下、($\Leftarrow$)について示します。つまり、任意の $X \subseteq A$ に対して $|N(X)| \ge q|X|$ が成り立つなら $A$ から $B$ への $q$-expansion が存在することを示します。

$A$ のすべての頂点を $B$ との隣接関係を維持したまま、それぞれ $q-1$ 個ずつコピーします。そうして得られた二部グラフを $G' = (A' \sqcup B, E')$ とします。$G'$ における $A'$ を飽和するマッチングは、$G$ における $A$ から $B$ への $q$-expansionに対応します。

そのため、十分性を示すには $G'$ において $A'$ から $B$ へのマッチングの存在を示せばよく、これは Hall の定理によれば、任意の $X \subseteq A'$ に対して $|X| \le |N_{G'}(X)|$ を示すことと同値です。そうでないと仮定して、$|N_{G'}(X')| < |X'|$ を満たす集合 $X' \subseteq A'$ が存在すると仮定します。ある頂点 $v$ が $X'$ に含まれているとして、そのコピー $v'$ を $X'$ に追加しても $N_{G'}(X')$ は変化しないため、一般性を失わず $X'$ には $v$ の全てのコピーが含まれていると仮定できます。よって、$X'$ はサイズ $|X'|/q$ の $A$ の部分集合 $X_A$ に自然に対応しますが、$|N_G(X_A)| = |N_{G'}(X')| < |X'| = q|X_A|$ となり、$N(X) \ge q|X|$ に矛盾します。よって $A'$ から $B$ へのマッチングを持ち、したがって $A$ は $B$ への q-expansion を持つことが示されました。$\square$

この補題から Expansion lemma が得られます。$q \ge 1$ を正の整数、$G = (A \sqcup B, E)$ を二部グラフとします。もし、$|B| \ge q|A|$ であって、$B$ に孤立点が存在しないとします。すると、空でない頂点集合 $X \subseteq A$ と $Y \subseteq B$ が存在して、$N(Y) \subseteq X$ であって、$X$ から $Y$ への $q$-expansionが存在することが示されます。

2.5 線形計画法に基づくカーネル

頂点被覆問題を 01 整数計画問題として定式化し、整数制約を実数にまで緩和した問題 LPVC($G$) を考えます。

整数制約を緩和することで最適値が下がる例が 3 サイクルを通して紹介されていました。整数制約の下では任意の 2 頂点を選ぶしかないので最適値は 2 ですが、実数制約の下では、例えば全ての頂点に 1/2 を割り当てることで目的関数値が下がることが確認できます。制約式を足し合わせると $2(x_1 + x_2 + x_3) \ge 3$ という目的関数の下界が得られますが、先の割り当てから計算される目的関数値に一致するので、最適解であることがいえました。

面白いことに、任意の最適解のうち、少なくとも 1 つの解において各変数に割り当てられた値が $0, 1, 1/2$ のいずれかであるものが存在することが示せます（命題 2.24）。

任意の最適解において、変数の取り得る値は $0$ か $1$ か $1/2$ しかないのではないかということが頭を過りましたが、これは誤りですね。$2$ 頂点のパスにおいて、$x_1$ を $[0, 1]$ の範囲で任意に値を割り当て、$x_2 = 1 - x_1$ を割り当てれば、これが明らかに最適解になります。

---

1. Fellows, Michael R., et al. "What is known about vertex cover kernelization?." Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday. Cham: Springer International Publishing, 2018. 330-356. ↩

2. Fomin, Fedor. "DAY2 1 7: Basic Kernels I." Parameterized Complexity, YouTube, 5 Jan. 2018, https://youtu.be/NMLVXJmyGbQ?si=pPSaG1CPfeXRM-d2. ↩

3. Buss, Jonathan F., and Judy Goldsmith. "Nondeterminism within p^." SIAM Journal on Computing 22.3 (1993): 560-572. ↩

4. Charbit, Pierre, Stéphan Thomassé, and Anders Yeo. "The minimum feedback arc set problem is NP-hard for tournaments." Combinatorics, Probability and Computing 16.1 (2007): 1-4. ↩