Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
复制标题
用于小封闭类及其他类中的生成树多胞体的较小扩展公式
DOI：
10.37236/10522
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
D. Wood
中科院分区：
文献类型：
--
作者：
Manuel Aprile;Samuel Fiorini;T. Huynh;G. Joret;D. Wood
设G$是一个真次闭类$\mathcal G$中的连通$n$-顶点图。证明了G$的生成树多面体的扩张复杂性为O（n^{3/2}）$。这改进了Wong（1980）和Martin（1991）的O（n^2）$界。它还扩展了Fiorini，Huynh，Joset和Pashkovich（2017）的结果，他们获得了嵌入固定曲面的图的$O（n^{3/2}）$界。我们的证明更普遍地适用于所有承认强次线性平衡分隔符的图类：我们证明了：对于任意常数$\beta$，且$0<\beta<1$，如果$\mathcal G$是一个在导出子图下闭的图类，使得$\mathcal G$中的所有$n$-顶点图都有大小为$O（n^\beta）$的平衡分离子，则$\mathcal{G}$中每个连通$n$-顶点图的生成树多面体的扩张复杂度为$O（n^{1+\beta}）$.我们实际上给出了这个结果的两个证明，一个是直接构造扩展公式，另一个是通过通信协议。使用后一种方法，我们也给出了一个简短的证明，由于威廉姆斯（2002）的平面图的$O（n）$界。
Let $G$ be a connected $n$-vertex graph in a proper minor-closed class $\mathcal G$. We prove that the extension complexity of the spanning tree polytope of $G$ is $O(n^{3/2})$. This improves on the $O(n^2)$ bounds following from the work of Wong (1980) and Martin (1991). It also extends a result of Fiorini, Huynh, Joret, and Pashkovich (2017), who obtained a $O(n^{3/2})$ bound for graphs embedded in a fixed surface. Our proof works more generally for all graph classes admitting strongly sublinear balanced separators: We prove that for every constant $\beta$ with $0<\beta<1$, if $\mathcal G$ is a graph class closed under induced subgraphs such that all $n$-vertex graphs in $\mathcal G$ have balanced separators of size $O(n^\beta)$, then the extension complexity of the spanning tree polytope of every connected $n$-vertex graph in $\mathcal{G}$ is $O(n^{1+\beta})$. We in fact give two proofs of this result, one is a direct construction of the extended formulation, the other is via communication protocols. Using the latter approach we also give a short proof of the $O(n)$ bound for planar graphs due to Williams (2002).
扩展公式、非负分解和随机通信协议
影响因子：
2.7
作者：
Y. Faenza;S. Fiorini;R. Grappe;H.R. Tiwary
通讯作者：
H.R. Tiwary
影响因子：
2.1
作者：
Hamidreza Validi;Austin Buchanan
通讯作者：
Hamidreza Validi;Austin Buchanan
计数拟阵的子图多胞形和独立多胞形
DOI：
10.1016/j.orl.2015.06.011
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Michele Conforti;Volker Kaibel;Matthias Walter;Stefan Weltge
通讯作者：
Stefan Weltge