抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ほとんどのt頂点の集合がグラフから取り除くことができるかどうかは,グラフから,結果として得られるグラフが,ほとんどの2で木幅を持つかどうかを問う。グラフは,それがK_4マイナーを含んでいないならば,ほとんど2つで木幅を持つ。したがって,この問題は,F={K_4}を有するNP困難F-Minor Cover問題に対応する。F-Minor Cover問題の任意の変異体に対して,Fが平面グラフを含む場合,多項式カーネルが存在することが知られている。即ち,多項式時間での前処理ルーチンはサイズt ̄O(1)の等価インスタンスを出力する。しかしながら,この証明は,非構成的であり,この証明がカーネルサイズに明確な限界をもたらさないことを意味する。{K_4}-Minor Cover問題は,未知のカーネルサイズを有するF-Minor Cover問題の最も単純な変異体である。建設的カーネル化アルゴリズムを開発するために,著者らは,この新分解における近突出を基本縮小規則を用いて低減することができるように,グラフを近突出に分解するための新しい方法を示した。この方法は,van Bevern et al.[Algogorithica 2012]によって,ΔΨ近似とtidyingのフレームワークを拡張し,このフレームワークと規則的な突出分解の両方によって提供されるものよりも強い保証を提供する。さらに,Donkersら[IPEC 2021]によって導入された{K_4,K_2,3}-Minor Coverカーネル化アルゴリズムによって使用された基本縮小規則の拡張を提供した。新しい分解法と還元規則を用いて,著者らはO(t ̄41)頂点から成るカーネルを得て,それは最初の構成カーネルである。このカーネルは,Fが平面グラフを含むF-Minor Cover問題に対するより具体的なカーネル化限界に対するステップであり,この分解はこれらの新しい限界を達成するための潜在的方向を提供する。【JST・京大機械翻訳】
