论文标题
在键多层
On the Bond Polytope
论文作者
论文摘要
给定图形$ g =（v，e）$，最大债券问题搜索最大切割$δ（s）\ subseteq e $带有$ s \ subseteq v $，因此连接$ g [s] $和$ g [v \ setminus s] $。此问题与众所周知的最大切割问题密切相关，并以各种名称，例如最大键，最小切割和最大连接（侧）切割而知。键多层是键的所有发生率向量的凸壳。与相应的优化问题的连接相似，键多层与切割多层密切相关。虽然已经深入研究了切割的多面体，但键多面没有结果。我们开始对后者的结构研究。 我们研究了切割和键多面体之间的关系，并研究了图修饰对键多型及其方面的影响。此外，我们研究了由键多面体的边缘和周期引起的方面定义不平等。特别是，这些产生了循环的债券多塔和$ 3 $连接的平面$（k_5-e）$的完整线性描述。此外，我们将任意图上最大债券问题的最大债券问题减少到$ 3 $连接的图表上的最大债券问题。这会产生$（k_5-e）$的最大债券的线性时间算法 - 较小的免费图。
Given a graph $G=(V,E)$, the maximum bond problem searches for a maximum cut $δ(S) \subseteq E$ with $S \subseteq V$ such that $G[S]$ and $G[V\setminus S]$ are connected. This problem is closely related to the well-known maximum cut problem and known under a variety of names such as largest bond, maximum minimal cut and maximum connected (sides) cut. The bond polytope is the convex hull of all incidence vectors of bonds. Similar to the connection of the corresponding optimization problems, the bond polytope is closely related to the cut polytope. While cut polytopes have been intensively studied, there are no results on bond polytopes. We start a structural study of the latter. We investigate the relation between cut- and bond polytopes and study the effect of graph modifications on bond polytopes and their facets. Moreover, we study facet-defining inequalities arising from edges and cycles for bond polytopes. In particular, these yield a complete linear description of bond polytopes of cycles and $3$-connected planar $(K_5-e)$-minor free graphs. Moreover we present a reduction of the maximum bond problem on arbitrary graphs to the maximum bond problem on $3$-connected graphs. This yields a linear time algorithm for maximum bond on $(K_5-e)$-minor free graphs.
