On 1-skeleton of the cut polytopes
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911933218684928 |
|---|---|
| author | Nikolaev, Andrei V. |
| author_facet | Nikolaev, Andrei V. |
| contents | Given an undirected graph $G = (V,E)$, the cut polytope $\mathrm{CUT}(G)$ is defined as the convex hull of the incidence vectors of all cuts in $G$. The 1-skeleton of $\mathrm{CUT}(G)$ is a graph whose vertex set is the vertex set of the polytope, and the edge set is the set of geometric edges or one-dimensional faces of the polytope. We study the diameter and the clique number of 1-skeleton of cut polytopes for several classes of graphs. These characteristics are of interest since they estimate the computational complexity of the max-cut problem for certain computational models and classes of algorithms. It is established that while the diameter of the 1-skeleton of a cut polytope does not exceed $|V|-1$ for any connected graph, the clique number varies significantly depending on the class of graphs. For trees, cacti, and almost trees (2), the clique number is linear in the dimension, whereas for complete bipartite and $k$-partite graphs, it is superpolynomial. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_13591 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On 1-skeleton of the cut polytopes Nikolaev, Andrei V. Combinatorics 52B05, 52B12, 90C57 Given an undirected graph $G = (V,E)$, the cut polytope $\mathrm{CUT}(G)$ is defined as the convex hull of the incidence vectors of all cuts in $G$. The 1-skeleton of $\mathrm{CUT}(G)$ is a graph whose vertex set is the vertex set of the polytope, and the edge set is the set of geometric edges or one-dimensional faces of the polytope. We study the diameter and the clique number of 1-skeleton of cut polytopes for several classes of graphs. These characteristics are of interest since they estimate the computational complexity of the max-cut problem for certain computational models and classes of algorithms. It is established that while the diameter of the 1-skeleton of a cut polytope does not exceed $|V|-1$ for any connected graph, the clique number varies significantly depending on the class of graphs. For trees, cacti, and almost trees (2), the clique number is linear in the dimension, whereas for complete bipartite and $k$-partite graphs, it is superpolynomial. |
| title | On 1-skeleton of the cut polytopes |
| topic | Combinatorics 52B05, 52B12, 90C57 |
| url | https://arxiv.org/abs/2402.13591 |