Approximating clique-width and branch-width
Approximating clique-width and branch-width
复制标题
DOI：
10.1016/j.jctb.2005.10.006
复制
发表时间：
2006-07
期刊：
影响因子：
--
通讯作者：
Sang-il Oum;P. Seymour
中科院分区：
文献类型：
--
作者：
Sang-il Oum;P. Seymour
本文构造了一个多项式时间算法来逼近某些对称次模函数的分支宽度，并给出了两个应用。第一个是绘制“candle-width”。图的宽度是一种树结构中分解图的难度的度量，如果一个图的宽度最多为k，则该图的相应分解称为“k-表达式”。我们找到一个O（n9 logn）时间的算法，输入一个n顶点图，输出一个图的（23 k +2−1）-表达式，或者证明图的宽度至少为k+1。(The最佳早期算法，Johansson [1]。Johansson，logn-近似NLCk-分解在O（n2 k +1）时间（扩展摘要），在：图论概念在计算机科学，Boltengland，2001，在：讲义在计算.科学，vol. 2204，Springer，柏林，2001，pp. [229-240]，构造了一个2klogn-表达式，用于cn-width至多为k的图。我们已经知道，如果输入图配备了k-表达式（对于固定的k），那么在一般图上的几个NP-困难的图问题在多项式时间内是可解的。作为我们算法的结果，在较弱的假设下得出相同的结论，即输入图的candle-width至多为k（因此，我们不再需要提供显式的k-表达式）。另一个应用是拟阵的分支宽度。对于固定的k，我们找到一个O（n3.5）时间算法，输入一个n元拟阵，根据其秩预言，要么输出一个宽度至多为3 k −1的分支分解，要么证明该拟阵的分支宽度至少为k+1。Hlinyoung [P. Hlinyoung，A parametrized algorithm for matroid branch-width，SIAM J. Comput. 35（2）（2005）259-277]仅适用于有限域上表示的拟阵。
We construct a polynomial-time algorithm to approximate the branch-width of certain symmetric submodular functions, and give two applications. The first is to graph “clique-width.” Clique-width is a measure of the difficulty of decomposing a graph in a kind of tree-structure, and if a graph has clique-width at most k then the corresponding decomposition of the graph is called a “k-expression.” We find (for fixed k) an O(n9logn)-time algorithm that, with input an n-vertex graph, outputs either a (23k+2−1)-expression for the graph, or a witness that the graph has clique-width at least k+1. (The best earlier algorithm, by Johansson [Ö. Johansson, logn-approximative NLCk-decomposition in O(n2k+1) time (extended abstract), in: Graph-Theoretic Concepts in Computer Science, Boltenhagen, 2001, in: Lecture Notes in Comput. Sci., vol. 2204, Springer, Berlin, 2001, pp. 229–240], constructs a 2klogn-expression for graphs of clique-width at most k.) It was already known that several graph problems, NP-hard on general graphs, are solvable in polynomial time if the input graph comes equipped with a k-expression (for fixed k). As a consequence of our algorithm, the same conclusion follows under the weaker hypothesis that the input graph has clique-width at most k (thus, we no longer need to be provided with an explicit k-expression). Another application is to the area of matroid branch-width. For fixed k, we find an O(n3.5)-time algorithm that, with input an n-element matroid in terms of its rank oracle, either outputs a branch-decomposition of width at most 3k−1 or a witness that the matroid has branch-width at least k+1. The previous algorithm by Hliněný [P. Hliněný, A parametrized algorithm for matroid branch-width, SIAM J. Comput. 35 (2) (2005) 259–277] works only for matroids represented over a finite field.