Basic Concepts

branch 有两条规则:

• reduction rule. 用来简化问题或者停止算法.
• branching rule. 通过递归地求解更小的问题的实例来解决一个问题.

因此设计一个 branch 算法很大程度上是设计 reduction 和 branching rule.

Upper Bound Analysis

要分析 branching 算法需要一些假设:

• polynomial time.
• Simplifying produces simpler problem.

在上面的假设下, 复杂度为 搜索树结点 一个多项式.

研究 branch 算法时, 问题的输入参数往往不是输入的长度, 而是一个可以描述问题规模的很自然的参数, 比如图的结点数, 称这样的参数为问题的 instance.

设 是 instance 数目为 的一个问题的分支树的叶子节点个数. 给定一个 branching 规则 , 设 , , 规则 将当前的 instance 分成了 个子问题且每个子问题的 instance 数量至多为 , 那么称向量 称为 branching vector. 根据树的递归结构, 有 这是一个线性递推不等式, 考虑用特征方程来解, 等式 的特征方程为 , 而显然有 , 为特征方程的所有根的 次幂的线性组合(系数为 的多项式), 可以写成 为方程的唯一正根, 称作 的 branching factor, 这就意味着 .

书上写的是 unique positive real root, 个人感觉应该是最大正根.

对于 branching vector , 定义其 branching factor 为 . 有如下性质:

• , 其中 为 的任意排列.
• .
• .
• .

Addition of Branching Vectors

设有两个分支规则 , branching vector 分别为 , 且 的 分支恰好符合实施 分支规则的条件, 那么可以把这两次分支并在一起, 得到新的 branching vector , 有时候会减少 branching factor.

-SAT

令变量集合 有下面的概念:

• literal 以及 被称为 literal, 与 有关的 literal 的集合记作 .
• clause 一个 clause 是若干 literal 的 disjunction . 要求一个 clause 不含有两个相同的 literal 或者 一个 literal 和它的非. 用集合 来表示一个 clause.
• CNF formula 是若干 clause 的conjunction , 用集合 来表示一个 CNF formula. 若 的每个 clause 都含有至多 个 literal, 则称其为 -CNF formula. 如果 CNF formula 满足 的每个 clause 都是 的每个 clause 的子集, 则称 是 的 subformula.

称 CNF formula 是 satisfiable 的当且仅当存在对 的 literal 的合法赋值使得 . 以此定义 SAT 和 -SAT 问题:

• Satisfiability Problem. 给定一个含有 个变量和 个 clause 的的 CNF formula , 要求判断是否能找到对变量的合法赋值(对每个变量赋值得到 的一个结果的过程称为 truth assignment)使 .
• -Satisfiability Problem. 在 SAT 的基础上, 要求 是 -CNF formula.

-SAT 的一个 branch 算法

考虑到对于 的任意 clause , 当 时便有 , 同时可以得到 , 其中 相比 少了一个变量 . 以这种方式作为分支规则, 可以得到 个 subformula:

于是若 之中至少要有一个是可满足的, 便可得到 是可满足的.

复杂度分析

由于 有 个变量即 个instance, 于是经过赋值, 有 个 instances, 其 branching vector 为 , 对应的特征方程为 , 利用等比数列求和化简得 , 设其 branching factor 为 , 序列 是单调递增的 , 那么上述 branch 算法的复杂度为 , 且 , 故复杂度上界为 . 这个复杂度不算很优秀, 因为对于有线性时间复杂度的 2-SAT 而言, branch 算法得到的复杂度为 .

基于 autark 的改进

第一个改进的技巧是每次选择最小的 clause 做分支, 这通过复杂度 就能体现出来.

同时还能注意到一个事实: 若 -CNF formula 存在 的 clause , 那么在 上做分支, 那么复杂度为 , 此时对于 2-SAT 变为 , 已经是多项式复杂度了.

若 都满足 , 考虑通过下面的称作 autark 的技巧做进一步改进:

定义 partial truth assignment 是对部分变量的赋值, 如果这样的赋值可以满足 的一个 subformula ( 还要满足 与 没有相同的变量) , 就称这个赋值为 autark, 称为autark subset.

举个例子, 对于 是一个对部分变量的赋值同时也是一个 autark, 它使 得到满足, 且赋值过后得到的 subformula 为 , 只需再判断 是否是可满足的, 便可得到 是否是可满足的.

autarky 即 autarchy 本身是“自给自足”的含义.

在前述的简单分支规则的基础上, 设 经过一个赋值后得到的 subformula 为 , 有下面两种情况:

• 若该赋值为 autark, 那么 可满足当且仅当 可满足, 因此递归地解决 的可满足性即可.
• 若该赋值不是 autark, 那么存在一个被赋值的 literal , 它出现在某一个 clause 中, 在赋值之后, 一定有 , 那么直接在赋值之后的 上做分支即可(事实上还是在最小的 clause 上做分支).

在上面的例子中, 不是一个 autark, 那么 是一个值为 的literal, 它出现在 clause 中, 赋值之后, 该 clause 变成了 , 大小从 变成了 .

在这个改进的基础上, 3-SAT 的复杂度为 .

最大独立集

一个简单的 branching

独立集一些简单的结论:

• 若 , 则 .
• 若 是 MIS, 则对于 , 中至少有一个点在 中即 , 如若不然, 可成为新的独立集.

这些结论实际上是在说, 想得到最大独立集, 对任意点 , 只能在它的闭邻域 中选择一个点.

下面是递推关系式: 对于度数最小的点 , 枚举 中的点 , 然后删去 , 得到若干子图 , 再重复这个过程求这些子图中独立集的最大值.

复杂度为 , 时为 是最大值. 设最小度数的点为 , 中的点的度数分别为 , 有 , 于是 不断由 递推得 .

可以证明下面的最大独立集的个数的定理:

一个有 个顶点的图 的最大独立集个数至多为 即 , 构造很容易, 只需要让 由 个不相交的 组成, 那么每个 只能取一个点, 有三种取法, 就得到了结论.

一个复杂的 branching

这个 branching 算法基于下面的引理.

Lemma 1 (domination rule) 设 , 则 .

PROOF 相当于证明 存在不包括 的最大独立集. 设某个最大独立集 满足 , 那么 即 . 由于 与 相邻, 因此可以将 替换成 而不违反独立集需要满足的要求, 那么 是一个不包括 的最大独立集.

Lemma 2 (standard branching) 求解最大独立集时, 要么选择 舍弃其邻域, 要么直接舍弃 , 于是 . 它的 branching vector 为 .

Lemma 3 对于 , 若 的所有最大独立集都不含 , 那么 的每一个最大独立集都至少含有 中的两个顶点.

PROOF 假设存在一个最大独立集 使得 , 分为两种情况:

• 不含有 中的任何点, 此时 可以成为新的最大独立集, 矛盾.
• 仅含有 中的一个顶点, 此时设 , 于是 不含有 中的顶点也不含有 中的顶点, 于是 也是一个最大独立集, 这与所有最大独立集都不含有 相矛盾.

定义 表示 的邻居的邻居的集合(不包括 中的点), 若 满足 是团, 则称 为 的 mirror. 设 是 在 中的所有的 mirror 点的集合. 定义 .

Lemma 4 (mirror branching) .

PROOF 如果 存在一个包括 的最大独立集, 那么 则命题为真; 反之若所有最大独立集都不包括 , 那么由引理 3 可得所有最大独立集都包括 中的至少两个顶点, 设某个 mirror 为 , 由 mirror 的定义知 为 clique, 而一个 clique 中至多有一个点在最大独立集中, 于是 中的点至少有一个在所有的最大独立集中, 这意味所有的最大独立集都不可能包含 , 因此可以丢弃掉 的所有 mirror 而不影响最大独立集的大小.

Lemma 5 (simplicial rule) 设 是一个 clique, 则 .

Lemma 6 (seperator branching) 设 是 的 (small) seperator 且 是 的所有子集中为 的独立集的那些子集的集合, 那么

seperator 的定义是 不连通.

PROOF 这个公式还算好理解, 就是将图分为两部分分别计算两部分的最大独立集(其中有一部分比较小, 在这里是 , 可以快速处理出最大独立集) , 其中 为 再去除掉 中最大独立集的邻接点的子图防止直接算 的最大独立集时出现冲突, 枚举 所有的最大独立集即可.

只对较小的 应用 Lemma 6, 防止分支数目过多, 在本算法中会确保 .

Lemma 7 对于不连通的图 , 设 是它的连通分量, 则 .

也许设所有连通分量的集合为 , 可以写成下面的公式

具体的算法

当 时每次选择度数最小的结点 做 branch, 当 时每次选择度数最大的结点 做 branch, 有如下分类讨论:

• 或 时, 直接选 , 并递归地求解 的最大独立集.

• 时, 设 的邻接顶点为

  • 若 相邻则 是一个 clique, 则 递归求 . (Lemma 5)

  • 若 不相邻:

    (i) 若 , 则应用 seperator branching,

    

    其中 是除了 以外剩下的子图, 那么此时的 seperator , 于是 , 那么 移除 后左边的图十分简单, 因此 , 以及 , 那么 branching vector 为 , 这至少是 .

    (2) 若 , 则应用 mirror branching. 若丢弃 则所有最大独立集都不会包括 , 那么 的两个邻接顶点 都要被选择(引理3)并递归求解 ; 如果选择 , 则需要丢弃 和所有的 mirror, 递归求解 . 因此 branching factor 为 , 至少是 . 此时上界是 .

• 时, 设 的邻接顶点为 , 则

  • 若 是一个独立集, 假设 都有在 中的邻接顶点, 如若不然, 应用 domination rule 可以删掉 , 这样就退化为了 的情况. 若 与 中的至少两个点相连, 则 有一个或两个顶点, 一定是 clique, 也就是说这样的 为 mirror.

    若 有 mirror 则直接 mirror branching, branching factor 为 , 至少为 ;

    若 没有 mirror, 中的每一个点都恰与 中的一个顶点相连, 同时 中的每个结点的度数都至少是 , 那么 至少与 的两个点相连. 直接做分支:

    • 选 丢 , 至少丢 个点
    • 丢 选 中的至少两个点, 即 (分别代表 ), 为了方便将 并入某个情况, 减少一个分支. 有两个分支至少丢弃了 个点, 有一个分支至少丢了 个点.

    那么 branch factor 为 .

  • 若 有 或 条边:

    • 条边. 不妨设 , 那么 至少连了 中的两个点, 且 是一个 clique, 于是 中与 相连的点都是 的 mirror, 至少两个, 实施 mirror branching, 故 , .
    • 条边. 不妨在上面的基础上设 , 那么很容易验证 所有的在 中的邻居都是 的 mirror, 于是实施 mirror branching, 在丢弃 和所有的 mirror 点之后, , 根据 的情况可以直接选 , 故 factor 至少为 .

  • 若 是个 clique (3条边), 直接 simplicial rule.

• 时, 直接选最大的点 branch 就可, .

• 若 是 或 -regular (每个点的度数都为 4 或 5 ) , 选任意点做分支, 但是不考虑它对时间复杂度的影响. 因为对任意正则图做分支只会增加分支树上叶子节点的数目.

• 若 , 一定存在 , 直接对 实施 mirror branching, 有 mirror 的话就是 , 没有 mirror 的话就是 , 这个是最劣情况, 显然有点太大了. 考虑用 Addition of Branching Vectors 做改良. 由于选 或丢弃 之后 , 于是在 上做 branch 之后分支 就可以立刻在 上做 branch, 此时相当于要把 或者 加到 上, 得到 或 .

最终得到的复杂度为 , 算法描述就是下面这个样子:

Exact algorithms for maximum independent set - ScienceDirect