Abstract

研究 hypergraph 中的连通性的的算法与结构特性. 给一个 hypergraph , , 在 uncapacitated case 时计算 中的一个 global min cut 的最快算法是 的; 在 capacitated case 时是 的.

• 计算 global min cut, 是 min cut 的值.

先略

Intro and Preliminaries

研究 hypergraph 的连通性. hypergraph 的定义是 , 其中 是有限顶点集, 是 hyperedge 的集合, 每个 hyperedge 是 的子集.

无向无 loop 的图是一个特殊的 hypergraph, 满足 .

basic def

• , 有容量的情况是 .

• , 可以注意到 . 是一个很自然的表示连通 hypergraph 的大小的量. 定义二部图 , , 则 即 是 边的数量.

• 是 的 rank.

• 设 , 表示同时与 和 相交的边的集合(对 , 有端点在 和 里). 我们只用 表示 cut , 且 .

• 是 edge-cut-set; 如果 是 min-cut, 则 是 min edge-cut-set.

• 是一个 上的函数, 是一个对称次模函数.

• 是 的 global min-cut. cut 的含义就不过多解释了.

• 一个 称为 - cut 如果 . 或者 定义为 , 是 之间的边连通性.

• 上述定义可以推广到 capacitated hypergraph, 每个边 有个 capacity . 对于 cut , . 如果 capacity 都是 就是 uncapacitied hypergraph, 在这种情况下允许重边的出现.

• 称 cross 如果 都非空.

• 如果 , 则称 是 -edge-connected 的.

• 对 , 是 induced subhypergraph. (subhypergraph of induced by .) 的 subhypergraph 是 , 其中 .

• 两两不相交 (pairwise disjoint), . .

• 对不相交的 , .

• 对于只有一个点的集合, 用 来简化符号. 这里 是上面定义的 .

• 收缩: 将某 收缩得到 : 中所有顶点缩为一个点 , 移除所有 , 用 代替 . 用 表示这样的 .

然后研究计算 时出现的算法与结构的问题.

先略去已有的结果.

Equivalent digraphs

定义为:

• , , 同理. 这里加上 表示?
• 如果 且 那么 中的 和 的容量是
• 对每个 , 的容量为 .

先略去仙人掌相关的结果.

vertex orderings

设 是一个对称次模函数. 如果 , 称 是 normalized. 的非平凡 minimizer . 是 的 domain. 定义:

• , . 这块和前面的 的定义类似.
• 是 的非平凡 minimizer 的函数值.
• 定义为 的 mincut 的值, 是 的 cut function
• 序偶 定义为 的 pendant pair 若 . 然后 hypergraph 的 pendant pair 就是它的 cut 函数的 pendant pair.

单调一致映射

通过 Nagamochi-Ibaraki 通过 找一对 pendant pair-收缩-递归 的方法, 有三种算 hypergraph 的 global mincut 的方法. Queyranne 推广了这种方法¹, 得到了一个一般的找一个对称次模函数的非平凡 minimizer 的算法. Rizzi 继续推广, 提到了单调一致映射的概念:

单调一致映射: 被称为 order inducing 的, 如果 满足下面的条件:

• 对称性: 对任意不相交 ,
• 单调性: 对 且不相交 ,
• 一致性: 若 且 不相交, 则 .

一个 vertex ordering 是 , 在这个 ordering 下, . 若对任意 有 , 称 realizes .

Rizzi 考虑了一个 max-back ordering of 即对任意 都满足 的 .

有这样一些关于这个 max-back ordering 的定理, 下面的 以及 都是上面定义出来的那些.

Theorem 2.1 .

根据 的 max-back ordering 可以很容易找到 的一个 pendant pair. Brinkmeier 加强了上面的定义.

Theorem 2.2 对 , .

Theorem 2.3 设 都 realize 了 , 则 的凸组合 realizes .

次模函数的 connectivity function

设 是对称次模函数. 定义在所有不相交的 上, 称为 的 connectivity function. 容易验证若 , 则 realizes . 我们给关于 的 max-back ordering 一个新名字是 的 Queyranne ordering.

Lemma 2.4 设 是一个 hypergraph 的 cut function, 则 , 对任意不相交 .

这里的 是前文定义的 . 是 .

Omit proof.

vertex orderings for hypergraph

给一个 和一个 ordering , 可以导出其他的 ordering. 有一些定义:

• 一条边 的 head 定义为 , 其实就是在给定的 ordering 下的 中的第一个 vertex
• 一个 edge 的 ordering 称为 head ordering, 如果 , 就是在给定的点的 ordering 中, 前一条边的 head 要比后一条边的 head 靠前.
• 称 是 的 backward edge 如果 且 . 就是 是 中非 head 顶点的 backward edge.

下面有个 -ordering.

-ordering

如果对 , 对任意 , 成立, 则称 是一个 -ordering. 对于特殊的 , 还有不同的叫法:

• 时, -ordering 又称为 MA-ordering (maximum adjacency ordering)
• 时, -ordering 又称为 tight ordering
• 时, -ordering 就是前面提到的 Queyranne ordering.

下面的引理叙述了 -ordering 具有的共同的性质. 每一个 -ordering 都是一个 realize 了 hypergraph 上的 cut function 的 order inducing function.

Lemma 2.5 和 都是一个 realize 了 hypergraph 上的 cut function 的 order inducing function.

下面是 Theorem 2.2 的推论.

Lemma 2.6 设 是一个 hypergraph 的 -ordering, 则 是一个 min --cut.

解决的问题

• hypergraph 上的 min-cut 有没有更快的 (近似) 算法?
• 一个 hypergraph 上有多少不同的 mincut?
• 有没有快速的对 hypergraph 稀疏化并近似地保留 cuts 的算法?