A separator theorem for graphs with an excluded minor and its applications
A separator theorem for graphs with an excluded minor and its applications
复制标题
含排除次要图的分隔定理及其应用
DOI：
10.1145/100216.100254
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
R. Thomas
中科院分区：
文献类型：
--
作者：
N. Alon;P. Seymour;R. Thomas
letg是具有非负权重的n-vertex图，其总和为1分配给其顶点，并且对给定的H-vertex Graph H没有较小的同构。删除创建一个图表，其中每个连接的组件的总重量最多为1/2。 n-vertex图G具有上述权重和H-Vertex图H，是这样的X集或G偶像的h-vertex Graph g。加上我们的结果的数量例如，在任何固定的图H中，给定具有N顶点的图G，没有H-Minor的G g可以将G的最大独立集的最大独立集的大小近似于多项式时间的1/√logn ，找到该大小，并在时间2√n）中找到G的色数，并在n个未知数中求解n线性方程的任何稀疏系统，其稀疏结构0对应于时间O（n）。我们的结果将图的树宽度与其中的KH-Minor的最大大小相关联。
LetG be an n-vertex graph with nonnegative weights whose sum is 1 assigned to its vertices, and with no minor isomorphic to a given h-vertex graph H. We prove that there is a set X of no more than hn vertices of G whose deletion creates a graph in which the total weight of every connected component is at most 1/2. This extends significantly a well-known theorem of Lipton and Tarjan for planar graphs. We exhibit an algorithm which finds, given an n-vertex graph G with weights as above and an h-vertex graph H, either such a set X or a minor of G isomorphic to H. The algorithm runs in time O(hnm), where m is the number of edges of G plus the number of its vertices. Our results supply extensions of the many known applications of the Lipton-Tarjan separator theorem from the class of planar graphs (or that of graphs with bounded genus) to any class of graphs with an excluded minor. For example, it follows that for any fixed graph H , given a graph G with n vertices and with no H-minor one can approximate the size of the maximum independent set of G up to a relative error of 1/ √ log n in polynomial time, find that size exactly and find the chromatic number of G in time 2 √ n) and solve any sparse system of n linear equations in n unknowns whose sparsity structure 0 corresponds to G in time O(n). We also describe a combinatorial application of our result which relates the tree-width of a graph to the maximum size of a Kh-minor in it.