隐含参数分支(implicit branching),理学-计算机科学技术-计算机科学理论-算法-参数算法,一种算法设计技术,在参数计算领域得到广泛应用(见参数算法)。分支法(branching)是设计参数算法的一个重要技术。利用分支法对FPT(见固定参数易解性)问题求解时有些分支情况中参数并未明显减少。这时,可以考虑用隐含参数的概念对算法时间复杂度进行分析。该方法主要基于如下观察:在参数没有明显减少时, 问题实例中的某些与参数相关的隐含结构量发生了改变。此外,这些隐含结构量的变化对问题求解产生影响,即当其增加或减少到一定值B,问题实例可以在多项式时间内求解。基于此,可以用参数k和界值B限定分支树高度。进一步讲,如果隐含结构量的初始值和B的绝对值差可以由参数限定,就得到一个FPT算法。下面以反馈顶点集(feedback vertex set)问题为例阐述隐含参数分支法的应用。首先介绍一个相关问题。森林二分反馈顶点集输入:一个图G=(V, E),V的一个划分(V1, V2) 满足G[V1]和G[V2]是森林,一个正整数h。