论文标题
小树宽图的近似路径
Approximating pathwidth for graphs of small treewidth
论文作者
论文摘要
我们描述了一种多项式时间算法，该算法给定图形$ g $带有treewidth $ t $，近似于$ g $的路径在$ o（t \ sqrt {\ log log t}）$之比以内。这是第一个实现某些功能$ f $的$ f（t）$近似值的算法。 我们的方法基于以下关键见解：每个具有较大路径的图形都具有较大的树宽或包含大型完整二进制树的细分。具体而言，我们表明，每个图形至少$ th+2 $具有至少$ t $或包含一个完整的高度二进制树的细分$ h+1 $的细分。绑定的$ th+2 $最好是达到乘法常数。该结果的动机是由（$ c = 2 $）激励的，以下是Kawarabayashi和Rossman（Soda'18）的猜想：存在一个通用的常数$ C $，因此每个具有Pathwidth $ω（k^c）$的图表至少都有$ k $或至少$ k $或包含一个完整的binary bilary bilary bilary bilary barinie barine of bariny barinie bariny of bariny bariny of barinial bariny of barinial of y。 我们的主要技术算法在输入中采用$ g $的图形$ g $和一些（不一定是最佳的）树木分解$ g $ width $ t'$，并且在多项式时间内计算一个整数$ h $，证书$ g $至少具有$ h $的路径温度，至少是$ h $的$ g $ a $ g $ a $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ $ $ $ $（$ 1）该证书与（并暗示）存在一个完整的高度二进制树的细分密切相关。然后，通过将此算法与Feige，Hajiaghayi和Lee（Stoc'05）的近似算法相结合，以获得路径宽的近似算法。
We describe a polynomial-time algorithm which, given a graph $G$ with treewidth $t$, approximates the pathwidth of $G$ to within a ratio of $O(t\sqrt{\log t})$. This is the first algorithm to achieve an $f(t)$-approximation for some function $f$. Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least $th+2$ has treewidth at least $t$ or contains a subdivision of a complete binary tree of height $h+1$. The bound $th+2$ is best possible up to a multiplicative constant. This result was motivated by, and implies (with $c=2$), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant $c$ such that every graph with pathwidth $Ω(k^c)$ has treewidth at least $k$ or contains a subdivision of a complete binary tree of height $k$. Our main technical algorithm takes a graph $G$ and some (not necessarily optimal) tree decomposition of $G$ of width $t'$ in the input, and it computes in polynomial time an integer $h$, a certificate that $G$ has pathwidth at least $h$, and a path decomposition of $G$ of width at most $(t'+1)h+1$. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height $h$. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth.
