اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the Combinatorial Lower Bound for the Extension Complexity of the Spanning Tree Polytope
65
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with $n$ nodes. The best known lower bound is the trival (dimension) bound, $Omega(n^2)$, the best known upper bound is the extended formulation by Wong (1980) of size $O(n^3)$ (also Martin, 1991). In this note we give a nondeterministic communication protocol with cost $log_2(n^2log n)+O(1)$ for the support of the spanning tree slack matrix. This means that the combinatorial lower bounds can improve the trivial lower bound only by a factor of (at most) $O(log n)$.
قيم البحث
اقرأ أيضاً
In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with $n$ nodes. The best know
n lower bound is $Omega(n^2)$, the best known upper bound is $O(n^3)$. In this note we show that the venerable fooling set method cannot be used to improve the lower bound: every fooling set for the Spanning Tree polytope has size $O(n^2)$.
We prove that for every $n$-vertex graph $G$, the extension complexity of the correlation polytope of $G$ is $2^{O(mathrm{tw}(G) + log n)}$, where $mathrm{tw}(G)$ is the treewidth of $G$. Our main result is that this bound is tight for graphs contained in minor-closed classes.
We prove that, for an undirected graph with $n$ vertices and $m$ edges, each labeled with a linear function of a parameter $lambda$, the number of different minimum spanning trees obtained as the parameter varies can be $Omega(mlog n)$.
A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely
those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are $at$-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness $k$ is NP-hard for any fixed $k ge 3$. We show that the problem, for any $k ge 5$, remains NP-hard for graphs whose domination number is $O(k)$, but it is FPT in the vertex cover number.
The third author noticed in his 1992 PhD Thesis [Sim92] that every regular tree language of infinite trees is in a class $Game (D_n({bfSigma}^0_2))$ for some natural number $ngeq 1$, where $Game$ is the game quantifier. We first give a detailed expos
ition of this result. Next, using an embedding of the Wadge hierarchy of non self-dual Borel subsets of the Cantor space $2^omega$ into the class ${bfDelta}^1_2$, and the notions of Wadge degree and Veblen function, we argue that this upper bound on the topological complexity of regular tree languages is much better than the usual ${bfDelta}^1_2$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
