カーネル化

コンピュータ サイエンスにおいて、カーネル化とは、アルゴリズムへの入力を「カーネル」と呼ばれるより小さな入力に置き換える前処理段階によって効率性を実現する効率的なアルゴリズムを設計する手法です。カーネルで問題を解いた結果は、元の入力と同じになるか、カーネルの出力を元の問題に対する望ましい出力に簡単に変換できる必要があります。

カーネル化は、多くの場合、インスタンスの扱いやすい部分を切り取る一連の削減規則を適用することによって実現されます。パラメータ化された複雑性理論では、カーネルのサイズに保証された境界を持つカーネル (問題に関連付けられた何らかのパラメータの関数として) を多項式時間で見つけることができることが証明できることがよくあります。これが可能な場合、実行時間が (多項式時間の) カーネル化ステップと (非多項式だがパラメータによって制限される) カーネルを解く時間の合計である、固定パラメータの扱いやすいアルゴリズムが得られます。実際、固定パラメータの扱いやすいアルゴリズムで解ける問題はすべて、このタイプのカーネル化アルゴリズムで解くことができます。これは、近似カーネル化にも当てはまります。

カーネル化アルゴリズムの標準的な例としては、S. Buss による頂点カバー問題のカーネル化が挙げられます。 ^[1] この問題では、入力は無向グラフ と数値です。出力は、グラフ内の各辺の端点を含む最大 個の頂点の集合(そのような集合が存在する場合) であり、そのような集合が存在しない場合は失敗例外となります。この問題はNP 困難です。ただし、次の削減規則を使用してカーネル化できます。 ${\displaystyle G}$${\displaystyle k}$${\displaystyle k}$

1. およびがより大きい次数の頂点である場合、 をグラフから削除して1 減らします。サイズ のすべての頂点カバーには が含まれている必要があります。そうでないと、接続エッジをカバーするために、その近傍をあまりに多く選択しなければならなくなります。したがって、元のグラフの最適な頂点カバーは、縮小された問題のカバーに を追加することで形成できます。${\displaystyle k>0}$${\displaystyle v}$${\displaystyle k}$${\displaystyle v}$${\displaystyle k}$${\displaystyle k}$${\displaystyle v}$${\displaystyle v}$
2. が孤立した頂点である場合は、それを削除します。孤立した頂点はどのエッジもカバーできないため、この場合はどの最小カバーの一部にもなりません。${\displaystyle v}$${\displaystyle v}$
3. グラフにより多くの辺が残っており、前の 2 つの規則のどちらも適用できない場合、グラフにはサイズ の頂点カバーを含めることができません。 より大きい次数の頂点をすべて除去した後、残っている各頂点は最大 の辺しかカバーできず、頂点の集合は最大 の辺しかカバーできないからです。 この場合、インスタンスは 2 つの頂点、1 つの辺、および を持つインスタンスに置き換えられますが、これも解がありません。${\displaystyle k^{2}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k^{2}}$${\displaystyle k=0}$

これらの規則を、削減ができなくなるまで繰り返し適用するアルゴリズムは、必然的に、最大で 個のエッジと(各エッジは最大で 2 つのエンドポイントを持ち、孤立した頂点は存在しないため) 最大で個の頂点を持つカーネルで終了します。このカーネル化は、線形時間で実装できます。カーネルが構築されると、カーネルの各サブセットがカーネルのカバーであるかどうかをテストする総当たり探索アルゴリズムによって、頂点カバー問題を解決できます。したがって、頂点とエッジを持つグラフでは、頂点カバー問題は で解決できるため、とが両方とも大きい場合でも、 が小さいときに効率的に解決できます。 ${\displaystyle k^{2}}$${\displaystyle 2k^{2}}$${\displaystyle O(2^{2k^{2}}+n+m)}$${\displaystyle n}$${\displaystyle m}$${\displaystyle k}$${\displaystyle n}$${\displaystyle m}$

この境界は固定パラメータで扱いやすいが、パラメータへの依存性は必要以上に高い。より複雑なカーネル化手順では、カーネル化ステップの実行時間が長くなることを犠牲にして、より小さなカーネルを見つけることでこの境界を改善できる。頂点カバーの例では、最大 の頂点を持つカーネルを生成するカーネル化アルゴリズムが知られている。この改善された境界を達成するアルゴリズムの 1 つは、 Nemhauserと Trotterによる頂点カバーの線形計画緩和の半整数性を利用する。^[2]その境界を達成する別のカーネル化アルゴリズムは、クラウン削減規則として知られるものに基づいており、交互パス引数を使用する。^[3]頂点の数の点で現在最もよく知られているカーネル化アルゴリズムは、Lampis (2011) によるもので、任意の固定定数 に対して頂点 を達成する。 ${\displaystyle 2k}$${\displaystyle 2k-c\log k}$${\displaystyle c}$

この問題では、 P = NPでない限り、サイズ のカーネルを見つけることはできません。そのようなカーネルは、NP困難な頂点カバー問題に対する多項式時間アルゴリズムにつながるからです。ただし、この場合はカーネルサイズに関するはるかに強い制限が証明できます。coNP NP/poly (複雑性理論家によってありそうにないと考えられている) でない限り、任意の に対して、エッジを持つカーネルを多項式時間で見つけることは不可能です。^[4]頂点カバーについては、いくつかの に対する頂点を持つカーネルが複雑性理論的に起こりそうにない結果をもたらす かどうかは不明です。${\displaystyle O(\log k)}$ ${\displaystyle \subseteq }$ ${\displaystyle \epsilon >0}$${\displaystyle O(k^{2-\epsilon })}$${\displaystyle (2-\epsilon )k}$${\displaystyle \epsilon >0}$

文献では、カーネル化を正式にどのように定義すべきかについて明確なコンセンサスはなく、その表現の使用法には微妙な違いがあります。

Downey & Fellows (1999) の表記法では、パラメータ化された問題は意思決定問題を記述するサブセットです。 ${\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }$

パラメータ化された問題のカーネル化とは、インスタンスを受け取り、それをインスタンス内の時間多項式にマッピングするアルゴリズムであり、 ${\displaystyle L}$${\displaystyle (x,k)}$${\displaystyle |x|}$${\displaystyle k}$${\displaystyle (x',k')}$

• ${\displaystyle (x,k)}$が である場合、かつが である場合に限ります。${\displaystyle L}$${\displaystyle (x',k')}$${\displaystyle L}$
• の大きさは内の計算可能な関数によって制限され、${\displaystyle x'}$${\displaystyle f}$${\displaystyle k}$
• ${\displaystyle k'}$は 内の関数によって制限されます。${\displaystyle k}$

カーネル化の出力はカーネルと呼ばれます。この一般的な文脈では、文字列のサイズは単にその長さを指します。グラフの問題の文脈では、頂点の数または辺の数をサイズの尺度として使用することを好む著者もいます。 ${\displaystyle (x',k')}$${\displaystyle x'}$

Flum & Grohe (2006, p. 4) の表記法では、パラメータ化された問題は、決定問題と関数(パラメータ化) で構成されます。インスタンスのパラメータは数値 です。 ${\displaystyle L\subseteq \Sigma ^{*}}$${\displaystyle \kappa :\Sigma ^{*}\to \mathbb {N} }$${\displaystyle x}$${\displaystyle \kappa (x)}$

パラメータ化された問題のカーネル化は、パラメータを持つインスタンスを受け取り、それを多項式時間でインスタンスにマッピングするアルゴリズムです。 ${\displaystyle L}$${\displaystyle x}$${\displaystyle k}$${\displaystyle y}$

• ${\displaystyle x}$がであり、 がであり、${\displaystyle L}$${\displaystyle y}$${\displaystyle L}$
• のサイズは内の計算可能な関数によって制限されます。${\displaystyle y}$${\displaystyle f}$${\displaystyle k}$

この表記法では、 のサイズの境界は、のパラメータも の関数によって境界が定められることを意味することに注意してください。 ${\displaystyle y}$${\displaystyle y}$${\displaystyle k}$

関数はカーネルのサイズと呼ばれることがよくあります。 の場合、問題は多項式カーネルを許容すると言われています。同様に、 の場合、問題は線形カーネルを許容します。 ${\displaystyle f}$${\displaystyle f=k^{O(1)}}$${\displaystyle L}$${\displaystyle f={O(k)}}$

問題が固定パラメータで扱いやすいのは、カーネル化可能かつ決定可能である場合のみです。

カーネル化可能かつ決定可能な問題が固定パラメータで扱いやすいことは、上記の定義からわかります。まず、ある c の時間で実行されるカーネル化アルゴリズムが呼び出され、サイズ のカーネルが生成されます。次に、問題が決定可能であることを証明するアルゴリズムによってカーネルが解かれます。この手順の合計実行時間はで、 はカーネルを解くために使用されるアルゴリズムの実行時間です。は計算可能であるため (たとえば、 が計算可能であるという仮定を使用して、長さ のすべての可能な入力をテストすることによって)、これは問題が固定パラメータで扱いやすいことを意味します。 ${\displaystyle O(|x|^{c})}$${\displaystyle f(k)}$${\displaystyle g(f(k))+O(|x|^{c})}$${\displaystyle g(n)}$${\displaystyle g(f(k))}$${\displaystyle f(k)}$${\displaystyle f(k)}$

固定パラメータで扱いやすい問題はカーネル化可能かつ決定可能であるというもう 1 つの方向性は、もう少し複雑です。問題が非自明であると仮定します。つまり、言語 と呼ばれるインスタンスが少なくとも 1 つあり、言語 と呼ばれるインスタンスが少なくとも 1 つあります。そうでない場合、インスタンスを空文字列に置き換えることは有効なカーネル化です。また、問題が固定パラメータで扱いやすいと仮定します。つまり、何らかの定数と何らかの関数について、インスタンス に対して最大 ステップで実行されるアルゴリズムがあります。入力をカーネル化するには、指定された入力に対してこのアルゴリズムを最大ステップで実行します。答えで終了する場合は、その答えを使用して、カーネルとしてまたはを選択します。代わりに、終了せずにステップ数の制限を超えた場合は、それ自体をカーネルとして返します。は の入力に対してのみカーネルとして返されるため、この方法で生成されたカーネルのサイズは最大 になります。このサイズの境界は、計算可能であるという固定パラメータの扱いやすさからの仮定によって計算可能です。 ${\displaystyle I_{はい}}$${\displaystyle I_{no}}$${\displaystyle f(k)\cdot |x|^{c}}$${\displaystyle (x,k)}$${\displaystyle c}$${\displaystyle f(k)}$${\displaystyle |x|^{c+1}}$${\displaystyle I_{はい}}$${\displaystyle I_{no}}$${\displaystyle |x|^{c+1}}$${\displaystyle (x,k)}$${\displaystyle (x,k)}$${\displaystyle f(k)\cdot |x|^{c}>|x|^{c+1}}$${\displaystyle \max\{|I_{はい}|,|I_{いいえ}|,f(k)\}}$${\displaystyle f(k)}$

• 頂点被覆は頂点被覆のサイズによってパラメータ化されます。頂点被覆問題には、最大で個の頂点と個の辺を持つカーネルがあります。^[5] さらに、任意の に対して、 でない限り、頂点被覆には辺を持つカーネルはありません。^[4] -一様ハイパーグラフ の頂点被覆問題には、ひまわりの補題を使用する辺を持つカーネルがあり、でない限り、サイズ のカーネルはありません。^[4]${\displaystyle 2k}$${\displaystyle O(k^{2})}$${\displaystyle \epsilon >0}$${\displaystyle O(k^{2-\varepsilon })}$${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$${\displaystyle d}$${\displaystyle O(k^{d})}$${\displaystyle O(k^{d-\varepsilon })}$${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$
• フィードバック頂点集合は、フィードバック頂点集合のサイズによってパラメータ化されます。フィードバック頂点集合問題には、頂点と辺を持つカーネルがあります。 ^[6]さらに、次の場合を除いて、辺を持つカーネルはありません。^[4]${\displaystyle 4k^{2}}$${\displaystyle O(k^{2})}$${\displaystyle O(k^{2-\varepsilon })}$${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$
• ${\displaystyle k}$-パス: -パス問題は、与えられたグラフに長さが少なくとも のパスがあるかどうかを判断する問題です。この問題には に指数サイズのカーネルがあり、でない限りに多項式サイズのカーネルはありません。^[7]${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$
• 2次元問題: 2次元問題の多くのパラメータ化されたバージョンは、平面グラフ上の線形カーネルを持ち、より一般的には、マイナーとしていくつかの固定グラフを除いたグラフ上に線形カーネルを持ちます。^[8]

上記の例では、パラメータは望ましい解のサイズとして選択されていますが、これは必須ではありません。入力の構造的複雑性の尺度をパラメータ値として選択することも可能で、いわゆる構造パラメータ化につながります。このアプローチは、解のサイズは大きいが、他の複雑性の尺度が制限されているインスタンスに適しています。たとえば、無向グラフのフィードバック頂点数は、削除すると非巡回になる頂点の集合の最小濃度として定義されます。入力グラフのフィードバック頂点数によってパラメータ化された頂点カバー問題には、多項式カーネル化があります。 ^[9]フィードバック頂点数が であるグラフが与えられた場合、 の最小頂点カバーが の最小頂点カバーに多項式時間で変換できるような頂点上のグラフを出力する多項式時間アルゴリズムがあります。したがって、カーネル化アルゴリズムは、フィードバック頂点数が小さいインスタンスが小さいインスタンスに削減されることを保証します。 ${\displaystyle k}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle k}$${\displaystyle G'}$${\displaystyle O(k^{3})}$${\displaystyle G'}$${\displaystyle G}$${\displaystyle k}$

• 反復圧縮、固定パラメータの扱いやすいアルゴリズムのための異なる設計手法
• 近似カーネル化、最適化問題の場合、カーネルは解の質において特定の要素を失う可能性がある。

• Abu-Khzam, Faisal N.; Collins, Rebecca L.; Fellows, Michael R .; Langston, Michael A .; Suters, W. Henry; Symons, Chris T. (2004)、頂点カバー問題のためのカーネル化アルゴリズム: 理論と実験(PDF)、テネシー大学。
• Bodlaender, Hans L. ; Downey, Rod G. ; Fellows, Michael R. ; Hermelin, Danny (2009)、「多項式カーネルのない問題について」、Journal of Computer and System Sciences、75 (8): 423–434、doi : 10.1016/j.jcss.2009.04.001。
• バス、ジョナサン F.;ゴールドスミス、ジュディ(1993)、「非決定性」、SIAM コンピューティングジャーナル、22 (3): 560–572、doi :10.1137/0222038、S2CID  43081484${\displaystyle P^{*}}$。
• チェン、ジャナー。カンジ、イヤド A. Jia、Weijia (2001)、「頂点カバー: さらなる観察とさらなる改善」、Journal of Algorithms、41 (2): 280–301、doi :10.1006/jagm.2001.1186、S2CID  13557005。
• Dell, Holger; van Melkebeek, Dieter (2010)、「多項式時間階層が崩壊しない限り、充足可能性は非自明なスパース化を許さない」(PDF)、第 42 回 ACM 計算理論シンポジウム (STOC 2010) の議事録(PDF)、pp. 251–260、doi :10.1145/1806689.1806725、ISBN 978-1-4503-0050-6、S2CID  1117711。
• Downey, RG ; Fellows, MR (1999)、「パラメータ化された複雑性」、Monographs in Computer Science、Springer、doi :10.1007/978-1-4612-0515-9、ISBN 0-387-94883-X、MR  1656112、S2CID  15271852。
• フルム、ヨルグ。Grohe、Martin (2006)、パラメータ化された複雑性理論、Springer、ISBN 978-3-540-29952-3、 2010年3月5日取得。
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. (2010)、「二次元性とカーネル」、第 21 回 ACM-SIAM 離散アルゴリズムシンポジウム (SODA 2010) の議事録、pp. 503–510。
• Jansen, Bart MP; Bodlaender, Hans L. (2013)、「頂点カバーカーネル化の再考 - 洗練されたパラメータの上限と下限」、Theory Comput. Syst.、53 (2): 263–299、arXiv : 1012.4701、doi : 10.1007/s00224-012-9393-4、
• ランプス、マイケル (2011)、「頂点カバーのための2 k  −  c  log  kオーダーのカーネル」、情報処理レター、111 (23–24): 1089–1091、doi :10.1016/j.ipl.2011.09.003。
• Thomassé, Stéphan (2010)、「フィードバック頂点セット用の4 k ^{2カーネル」、} ACM Transactions on Algorithms、6 (2): 1–8、doi :10.1145/1721837.1721848、S2CID  7510317。
• Niedermeier、Rolf (2006)、固定パラメーター アルゴリズムへの招待、オックスフォード大学出版局、CiteSeerX  10.1.1.2.9618、ISBN 0-19-856607-7、2008年9月24日にオリジナルからアーカイブされ、2017年6月1日に取得。

• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019)、カーネル化：パラメータ化された前処理の理論、ケンブリッジ大学出版局、p. 528、doi :10.1017/9781107415157、ISBN 978-1107057760
• Niedermeier、Rolf (2006)、固定パラメーター アルゴリズムへの招待、オックスフォード大学出版局、第 7 章、ISBN 0-19-856607-7、2007年9月29日にオリジナルからアーカイブされ、2017年6月1日に取得
• サイガン、マレック。フォミン、ヒョードル V.コワリク、ルカシュ。ロクシュタノフ、ダニエル。マルクス、ダニエル。ピリップチュク、マルシン。ピリチュク、ミハル。 Saurabh、Saket (2015)、Parameterized Algorithms、Springer、第 2 章および第 9 章、ISBN 978-3-319-21274-6