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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=b435561ef964ffde07f77aca55f847bf" title="Click to view the MathML source">X⊆R^dclass="mathContainer hidden">class="mathCode">$X\subseteq {\mathbb{R}}^d$ such that the integer cone (semigroup) generated by class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=89c3c6c07683e3160c54792ab6bb0354" title="Click to view the MathML source">Xclass="mathContainer hidden">class="mathCode">$X$ is the intersection of the lattice generated by class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=89c3c6c07683e3160c54792ab6bb0354" title="Click to view the MathML source">Xclass="mathContainer hidden">class="mathCode">$X$ with the cone generated by class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=89c3c6c07683e3160c54792ab6bb0354" title="Click to view the MathML source">Xclass="mathContainer hidden">class="mathCode">$X$. Let class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si8.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=5b00ec8123b6ba9bd4a722f0f3ffd47f" title="Click to view the MathML source">ℋclass="mathContainer hidden">class="mathCode">$\mathscr{H}$ be the class of graphs whose set of cuts is a Hilbert basis in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si9.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=6f78ac7977a4fe2a470aae8cf269487d" title="Click to view the MathML source">R^Eclass="mathContainer hidden">class="mathCode">${\mathbb{R}}^E$ (regarded as class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si10.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=4854a3393cde6dcf748121e3af98e2f9" title="Click to view the MathML source">{0,1}class="mathContainer hidden">class="mathCode">$\{0,1\}$-characteristic vectors indexed by edges). We show that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si8.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=5b00ec8123b6ba9bd4a722f0f3ffd47f" title="Click to view the MathML source">ℋclass="mathContainer hidden">class="mathCode">$\mathscr{H}$ is not closed under edge deletions, subdivisions, nor 2-sums. Furthermore, no graph having class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si12.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=848aa952678e3c3adfdccfc68021be5c" title="Click to view the MathML source">K₆∖eclass="mathContainer hidden">class="mathCode">$K_6\setminus e$ as a minor belongs to class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si8.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=5b00ec8123b6ba9bd4a722f0f3ffd47f" title="Click to view the MathML source">ℋclass="mathContainer hidden">class="mathCode">$\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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si8.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=5b00ec8123b6ba9bd4a722f0f3ffd47f" title="Click to view the MathML source">ℋclass="mathContainer hidden">class="mathCode">$\mathscr{H}$. Using these conditions we show that all class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=69e62aeb8269593ea14ebf389519dae4">class="imgLazyJSB inlineImage" height="19" width="22" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003428-si1.gif">class="mathContainer hidden">class="mathCode">$K_5^{\perp }$-minor-free graphs are in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si8.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=5b00ec8123b6ba9bd4a722f0f3ffd47f" title="Click to view the MathML source">ℋclass="mathContainer hidden">class="mathCode">$\mathscr{H}$, where class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=69e62aeb8269593ea14ebf389519dae4">class="imgLazyJSB inlineImage" height="19" width="22" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003428-si1.gif">class="mathContainer hidden">class="mathCode">$K_5^{\perp }$ is the unique 3-connected graph obtained by uncontracting an edge of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si18.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=7270fdad0831188fb3fe0e250cae7317" title="Click to view the MathML source">K₅class="mathContainer hidden">class="mathCode">$K_5$. We also establish a relationship between edge deletion and subdivision. Namely, if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si19.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=98a06e38af76bd8372c47f56a5f7e95b" title="Click to view the MathML source">G^′class="mathContainer hidden">class="mathCode">$G^{\prime }$ is obtained from class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si20.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=bb27505092668b7e03b4f8d6c5b329c2" title="Click to view the MathML source">G∈ℋclass="mathContainer hidden">class="mathCode">$G\in \mathscr{H}$ by subdividing class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si21.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=fb3b3841861cc2f54f758ebb5baafe09" title="Click to view the MathML source">eclass="mathContainer hidden">class="mathCode">$e$ two or more times, then class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si22.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=23ce2ce00c83100ab90ba2bcc7a2e237" title="Click to view the MathML source">G∖e∈ℋclass="mathContainer hidden">class="mathCode">$G\setminus e\in \mathscr{H}$ if and only if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003428&_mathId=si23.gif&_user=111111111&_pii=S0012365X15003428&_rdoc=1&_issn=0012365X&md5=ecbe4445e1db56f135b1584758b43307" title="Click to view the MathML source">G^′∈ℋclass="mathContainer hidden">class="mathCode">$G^{\prime }\in \mathscr{H}$.