编辑推荐：
核化是一个用于分析对NP难问题（NP-hard problems）可证明高效且可证明有效的数据约简的框架，它起源于90年代初。它使用参数化复杂性理论（parameterized complexity theory）的术语来表述，这有助于根据输入实例的复杂性参数
核化是一个用于分析对NP难问题（NP-hard problems）可证明高效且可证明有效的数据约简的框架，它起源于90年代初。它使用参数化复杂性理论（parameterized complexity theory）的术语来表述，这有助于根据输入实例的复杂性参数对获得的数据约简量提供保证。本综述回顾了该领域的早期历史和发展、其动机、其开放问题的状态和相关性，以及其未来展望。
1. 引言
1.1. 有保证的高效数据约简
预处理步骤在算法分析前清理输入数据具有广泛优势，尤其在组合优化问题中，可将求解时间从数天缩短至数秒。核化（kernelization）领域在过去三十年中研究了可证明有效且可证明高效的数据约简。以3-着色问题（3-Coloring）为例，提出了约简规则1（删除度数不超过2的顶点）和更复杂的规则2（删除满足特定邻域条件的顶点），并证明了规则2可确保在顶点覆盖数（vertex cover number）为k的输入图中，经过穷举应用后所得图至多包含k+k3个顶点，实现了高效性（多项式时间）和有效性（规模受参数多项式函数约束）的保证。
1.2. 核化的起源
核化起源于参数化算法理论（parameterized algorithmics）。参数化问题（parameterized problem）中每个实例关联一个非负整数参数k，提供除输入长度外的第二维复杂性度量。固定参数可处理性（FPT）指存在算法在f(k)·|x|^c时间内判定实例。核化最初被引入作为获得FPT算法的方法：一个多项式时间算法将实例(x,k)转化为等价实例(x',k')，满足|x'|,k'≤f(k)，称为核（kernel）。核化直接导致FPT算法：先计算核，再对其暴力搜索。
1.3. 早期历史
早期论文中，Downey和Fellows将核化应用于k-叶生成树（k-Leaf Spanning Tree）和k-顶点覆盖（k-Vertex Cover），并提出了两个开放问题：平面支配集（Planar Dominating Set）和无向图反馈顶点集（Feedback Vertex Set）是否具有核化？前者于2002年被Alber等人解决，得到O(k)顶点的核；后者于2006年被一组作者解决，得到O(k^11)顶点的核，后经Bodlaender改进至O(k3)。这些发现催生了强大且实用的约简规则，推动了领域快速发展，包括元核化理论（meta-kernelization）、下界工具（lower-bound tools）和参数生态学（parameter ecology）等。
1.4. 本综述的范围、目标和视角
本综述明确考察核化研究的各种动机如何经受时间考验，并重新审视六个长期开放问题，评估其相关性。作者选择从核化作为严格分析数据约简的框架这一视角，反思其理论成果对实践的影响，并探讨超越核化概念的可证明有效预处理的新方向。
1.5. 组织结构
综述其余部分组织如下：第2节给出形式化定义；第3节讨论研究动机；第4节包含对六个开放问题的讨论和反思；第5节提出参数化预处理的未来研究方向；第6节总结。
2. 基本定义
2.1. 核化与FPT
参数化决策问题定义为P?Σ*×N。核化（kernelization）是一个多项式时间算法，将实例(x,k)映射为(x',k')，满足等价性和|x'|,k'≤f(k)。多项式核（polynomial kernel）指f为多项式函数。广义核化（generalized kernelization）允许输出为另一问题Q的实例。命题4指出可判定参数化问题属于FPT当且仅当它存在核化。多项式参数变换（polynomial-parameter transformation, ppt）用于关联核的存在性，常用于下界证明。NP?coNP/poly假设是许多核化下界的基础。
2.2. 图
本文考虑有限无向图和有向图。定义了邻域、顶点集、边集、诱导子图等基本概念，以及完全图K_n、完全二分图K_{n,m}等。
3. 研究核化的动机
列出了八项动机：作为构建FPT算法的手段；发现强大约简规则；严格分析多项式时间数据约简的能力；提供新颖有趣的问题；研究哪些问题具有多项式核；与数学技术的联系；成熟的研究领域提供确定答案；触发对高效编码的理论问题。反思指出，现代核化研究已偏离早期动机，许多高级结果（如基于近似解的结构性映射、算法非构造性、大多项式次数）在实践中的应用有限，但仍有实际影响，如参数化算法与计算实验挑战赛（PACE）中预处理步骤的关键作用。
4. 开放问题及其相关性
基于2023年FPT Fest上对44位参与者的投票，按重要性顺序讨论六个最突出的开放问题。
4.1. 有向反馈顶点集（Directed Feedback Vertex Set, DFVS）
问题：DFVS在参数为解大小k时是否具有多项式核？该问题源于2008年Chen等人的FPT算法。相关性在于基础性和激发新工具。最难封闭情况包括在竞赛图（tournament）和有界独立数（independence number）的有向图中已有多项式核，以及使用较大参数（如无向反馈顶点集大小、树宽（treewidth））的参数化。最简单开放情况包括平面有向图、欧拉有向图以及2对终端的斜多割（Skew Multicut）问题。前景：目前无解，研究人员尝试了组合和代数方法均未成功。
4.2. 顶点多路割（Vertex Multiway Cut）
问题：参数为解大小k时是否具有多项式核？输入包含无向图G、整数k和终端集T，要求删除至多k个非终端使得每个连通分量最多包含一个终端。相关性包括计算机视觉等应用，但更主要来自理论兴趣。最难封闭情况：平面图已有O(k^{1486})顶点的核；允许删除终端时已有随机多项式核（O(k3)）；边删除变体Edge Multiway Cut有随机拟多项式核（O(k log3 k)边）。最简单开放情况包括终端度数有界（如最大度3）或放宽核大小要求。前景：社区期望通过代数技术（如matroid工具）取得进展。
4.3. 顶点平面化（Vertex Planarization）
问题：参数为解大小k时是否具有多项式核？输入要求删除至多k个顶点使图变为平面图。该问题源于F-Minor-Free Deletion的核化研究，当禁止子图集包含平面图时已有多项式核，但{ K?, K?,? }（即平面性）的情况仍开放。相关性包括图绘制应用，以及其神秘复杂性状态。最难封闭情况：以顶点覆盖数或树深度（treedepth）为参数时已有多项式核；存在损失性核化（lossy kernelization）得到多项式大小核（因子510近似）。最简单开放情况包括边删除变体Edge Planarization、有界度输入图，以及从k个平面子图构造的图。前景：社区普遍认为存在多项式核，但需结合多路割和损失性核化技术。
4.4. 图灵核下界（Turing Kernel Lower Bounds）
问题：开发框架证明某些参数化问题（如CNF-SAT参数化变量数n、Min-Ones 3CNF-SAT参数化k、连通顶点覆盖参数化k）不存在多项式图灵核（Turing kernel）。图灵核允许算法通过多次查询小规模实例的oracle来判定原实例。现有下界技术（如基于组合的框架）因信息论局限而无法处理图灵核。相关性：从复杂性理论角度挑战性极高，但从预处理角度，由于多数问题已被推测为WK[1]-难，价值有限。最难封闭情况：已有无条件下界（针对人工问题）和基于指数时间假设的下界（针对双指数问题），但目标问题未解决。最简单开放情况：限制为析取图灵核，或考虑电路可满足性（Circuit Satisfiability）参数化n。前景：只有少数问题被发现具有多项式图灵核，下界问题仍艰巨。
4.5. d-击中集（d-Hitting Set）的线性元素核
问题：d-Hitting Set（参数为解大小k）是否存在具有f(d)·k个宇宙元素的核？现有核通过向日葵引理（Sunflower lemma）得到O(k^d)个集合和O(k^d)个元素，通过冠约简（crown reduction）改进至O(k^(d-1))个元素。但下界已证明比特大小最优，元素数下界未知。相关性：d-Hitting Set的通用性，其特例包括三角形击中集、竞赛图反馈顶点集、簇顶点删除（Cluster Vertex Deletion）等。线性元素核将证明核化是解决d-Hitting Set的最优策略。最难封闭情况：簇顶点删除已有O(k)顶点的核（基于彩虹匹配（rainbow matching））；平面图上的H-Free Vertex Deletion有O(k)顶点核。最简单开放情况：3-Hitting Set（如三角形击中集）仍无次二次元素数核。前景：多数研究者预期否定结果，但现有下界工具无法证明。
4.6. k-路径的图灵核化（Turing Kernelization for k-Path）
问题：k-Path（参数为路径长度k）是否存在多项式图灵核？该问题源于k-Path不存在多项式标准核（因或组合（or-composition）），但图灵核可能绕过。相关性主要来自智力好奇。最难封闭情况：在平面图、有界度图、无爪图、排除拓扑子式图（H-topological-minor-free）中已有多项式图灵核，但弦图（chordal graph）等仍开放。最简单开放情况：弦图（因周长可很小）。前景：作者倾向于肯定答案，但重要性可能有限。
4.7. 讨论
六个开放问题主要关注精确数据压缩的极限，而非直接加速后续计算。作者呼吁在保持智力挑战的同时，关注能对预处理实践产生更大影响的算法问题。
5. 参数化预处理的一些未来研究方向
5.1. 近期趋势提示的方向
新模型如边界核化（boundaried kernelization）、计数核化（counting kernelization）、NP预言机核化（NP-oracle kernelization）提供了新角度。计算受限信息压缩（computationally-bounded information compression）通过编码为有界秩系统（如线性delta-matroid）实现压缩，例如匹配模拟网络（matching-mimicking network）问题（问题7：是否存在多项式大小的匹配模拟网络？）。约束满足问题（CSP）的稀疏化（sparsification）研究，如BCK谓词下的线性稀疏化问题。工程化约简规则（engineering reduction rules）涉及并行化、算法顺序、线性时间实现等实际挑战。
5.2. 通过预处理减少搜索空间
作者提出预处理应致力于减少搜索空间（即降低参数值），而非仅压缩数据。例如，冠规则（crown rule）和花规则（flower rule）能识别属于最优解的部分顶点。核化定义恰好发现了这些规则，但并非所有核都如此。因此需要研究能保证搜索空间减少的理论问题。
5.3. 最优性的简单证书
以顶点覆盖的冠分解（crown decomposition）和反馈顶点集的鹿角分解（antler decomposition）为例，展示了如何通过简单证书（如匹配或循环集）证明某些顶点属于某个最优解，从而减少参数。对于反馈顶点集，存在算法在2^{O(k?)}·n^{O(1)}时间内检测到大小为k的鹿角头（head）。问题8：对于顶点覆盖，是否存在f(k)·n^{O(1)}时间的算法，能从存在独立集C且其邻域H为G[C∪H]的最优顶点覆盖的图中，输出至少k个属于某个最优解的顶点？
5.4. 本质顶点（Essential Vertices）
定义c-本质顶点（c-essential vertex）为属于所有c-近似可行解的顶点。对于最小化问题，提出c-本质检测问题（c-Essential Detection），要求输出包含所有c-本质顶点的集合S，且S包含于某个最优解（若最优解大小≤k）。该检测可结合FPT算法实现搜索空间缩减，减少量为c-本质顶点数。例如，奇环横贯（Odd Cycle Transversal, OCT）存在2-本质检测的多项式时间算法，利用Erd?s-Pósa定理的变体。问题9：是否存在常数c使得OCT的c-本质检测可在近线性时间内解决？
6. 结论
过去二十年核化领域蓬勃发展，但作者希望未来研究能产生既有深刻见解又能在实践中产生影响的算法，并引用Guo和Niedermeier的话，期待核化研究的下一个时代能像早期结果一样对实践产生重大影响。
