On Hilbert bases of cuts

详细信息    查看全文

• 作者：Luis Goddyn^a ; ^{goddyn@sfu.ca" class="auth_mail" title="E-mail the corresponding author} ; Tony Huynh^b ; ^{tony.bourbaki@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Tanmay Deshpande^a ; ^{tanmaydesh5886@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Hilbert basis ; Graph cut ; Combinatorial optimization
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：721-728
• 全文大小：419 K

文摘

A Hilbert basis   is a set of vectors X⊆R^d$X\subseteq {\mathbb{R}}^d$ such that the integer cone (semigroup) generated by X$X$ is the intersection of the lattice generated by X$X$ with the cone generated by X$X$. Let ℋ$\mathscr{H}$ be the class of graphs whose set of cuts is a Hilbert basis in R^E${\mathbb{R}}^E$ (regarded as {0,1}$\{0,1\}$-characteristic vectors indexed by edges). We show that ℋ$\mathscr{H}$ is not closed under edge deletions, subdivisions, nor 2-sums. Furthermore, no graph having K₆∖e$K_6\setminus e$ as a minor belongs to ℋ$\mathscr{H}$. This corrects an error in Laurent (1996).

For positive results, we give conditions under which the 2-sum of two graphs produces a member of ℋ$\mathscr{H}$. Using these conditions we show that all ebf389519dae4">$K_5^{\perp }$-minor-free graphs are in ℋ$\mathscr{H}$, where ebf389519dae4">$K_5^{\perp }$ is the unique 3-connected graph obtained by uncontracting an edge of K₅$K_5$. We also establish a relationship between edge deletion and subdivision. Namely, if G^′$G^{\prime }$ is obtained from G∈ℋ$G\in \mathscr{H}$ by subdividing e$e$ two or more times, then G∖e∈ℋ$G\setminus e\in \mathscr{H}$ if and only if G^′∈ℋ$G^{\prime }\in \mathscr{H}$.