Min-Max Theorems for Packing and Covering Odd (u, v)-trails
Min-Max Theorems for Packing and Covering Odd (u, v)-trails
复制标题
包装和覆盖奇数 (u, v) 轨迹的最小-最大定理
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Chaitanya Swamy
中科院分区：
文献类型：
--
作者：
Sharat Ibrahimpur;Chaitanya Swamy
我们调查了包装和覆盖奇数$（u，v）$ - trails trails的问题。 $（u，v）$ - trail是$（u，v）$ - 允许重复的顶点但没有重复的边缘的步行。如果步道中的边缘数为奇数，我们将其称为奇数。让$
u（u，v）$表示边缘 - 划线奇数$（u，v）$ - trails和$ au（u，v）$的最大数量u，v）$ - 步道。
我们证明$ au（u，v）leq 2
u（u，v）+1 $。我们的结果是紧密的---有例子表明$ au（u，v）= 2
u（u，v）+1 $ ---，并在[Charchley等人2016]中获得的$ 8 $的限制大大改善，以$ au（u，v）/
u（u，v）$。我们的证明还产生了一个多项式时间算法，用于查找满足上述边界的盖子和一系列小径。
我们的证明很简单，有两种主要成分。我们表明（宽松地说）问题可以简化为包装和覆盖奇数$（紫外线，紫外线）$的问题 - 步道失去了2倍（在找到的步道数量或封面的大小中） 。补充这一点，我们表明，可以通过利用[Chudnovsky et al 2006]的功能强大的Min-Max结果来解决奇怪的 - $（UV，UV）$ - 可以解决oxping vertex-disjoint nonzero $ a $ a $ - 可以解决问题。组标记图中的路径。
We investigate the problem of packing and covering odd $(u,v)$-trails in a graph. A $(u,v)$-trail is a $(u,v)$-walk that is allowed to have repeated vertices but no repeated edges. We call a trail odd if the number of edges in the trail is odd. Let $
u(u,v)$ denote the maximum number of edge-disjoint odd $(u,v)$-trails, and $ au(u,v)$ denote the minimum size of an edge-set that intersects every odd $(u,v)$-trail.
We prove that $ au(u,v)leq 2
u(u,v)+1$. Our result is tight---there are examples showing that $ au(u,v)=2
u(u,v)+1$---and substantially improves upon the bound of $8$ obtained in [Churchley et al 2016] for $ au(u,v)/
u(u,v)$. Our proof also yields a polynomial-time algorithm for finding a cover and a collection of trails satisfying the above bounds.
Our proof is simple and has two main ingredients. We show that (loosely speaking) the problem can be reduced to the problem of packing and covering odd $(uv,uv)$-trails losing a factor of 2 (either in the number of trails found, or the size of the cover). Complementing this, we show that the odd-$(uv,uv)$-trail packing and covering problems can be tackled by exploiting a powerful min-max result of [Chudnovsky et al 2006] for packing vertex-disjoint nonzero $A$-paths in group-labeled graphs.