Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExtension Complexity of the Correlation Polytope
100
0
0.0
(
0
)
Added by
Marco Macchia
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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)$.
We study the dynamic and complexity of the generalized Q2R automaton. We show the existence of non-polynomial cycles as well as its capability to simulate with the synchronous update the classical version of the automaton updated under a block sequential update scheme. Furthermore, we show that the decision problem consisting in determine if a given node in the network changes its state is textbf{P}-Hard.
Correspondence homomorphisms are both a generalization of standard homomorphisms and a generalization of correspondence colourings. For a fixed target graph $H$, the problem is to decide whether an input graph $G$, with each edge labeled by a pair of permutations of $V(H)$, admits a homomorphism to $H$ `corresponding to the labels, in a sense explained below. We classify the complexity of this problem as a function of the fixed graph $H$. It turns out that there is dichotomy -- each of the problems is polynomial-time solvable or NP-complete. While most graphs $H$ yield NP-complete problems, there are interesting cases of graphs $H$ for which the problem is solved by Gaussian elimination. We also classify the complexity of the analogous correspondence {em list homomorphism} problems, and also the complexity of a {em bipartite version} of both problems. We emphasize the proofs for the case when $H$ is reflexive, but, for the record, we include a rough sketch of the remaining proofs in an Appendix.
Let $G$ be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of $k$ colors. Suppose that we are given two list edge-colorings $f_0$ and $f_r$ of $G$, and asked whether there exists a sequence of list edge-colorings of $G$ between $f_0$ and $f_r$ such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer $k ge 6$ and planar graphs of maximum degree three, but any complexity hardness was unknown for the non-list variant. In this paper, we first improve the known result by proving that, for every integer $k ge 4$, the problem remains PSPACE-complete even if an input graph is planar, bounded bandwidth, and of maximum degree three. We then give the first complexity hardness result for the non-list variant: for every integer $k ge 5$, we prove that the non-list variant is PSPACE-complete even if an input graph is planar, of bandwidth linear in $k$, and of maximum degree $k$.
The extension complexity $mathsf{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that affinely projects to $P$. Let $G$ be a bipartite graph with $n$ vertices, $m$ edges, and no isolated vertices. Let $mathsf{STAB}(G)$ be the convex hull of the stable sets of $G$. It is easy to see that $n leqslant mathsf{xc} (mathsf{STAB}(G)) leqslant n+m$. We improve both of these bounds. For the upper bound, we show that $mathsf{xc} (mathsf{STAB}(G))$ is $O(frac{n^2}{log n})$, which is an improvement when $G$ has quadratically many edges. For the lower bound, we prove that $mathsf{xc} (mathsf{STAB}(G))$ is $Omega(n log n)$ when $G$ is the incidence graph of a finite projective plane. We also provide examples of $3$-regular bipartite graphs $G$ such that the edge vs stable set matrix of $G$ has a fooling set of size $|E(G)|$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
