chaoxu/testgust

## testgust
<p>We have a graph <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-1-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-1" style="width: 5.123em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.447em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.853em -0.384em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-2"><span class="mi" id="MathJax-Span-3" style="font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-4" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="mo" id="MathJax-Span-5" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">(</span><span class="mi" id="MathJax-Span-6" style="font-family: STIXGeneral-Italic;">V<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.099em;"></span></span><span class="mo" id="MathJax-Span-7" style="font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-8" style="font-family: STIXGeneral-Italic; padding-left: 0.196em;">E<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-9" style="font-family: STIXGeneral-Regular;">)</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.114em; vertical-align: -0.275em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-1">G=(V,E)</script>. Given cost(<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-2-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-10" style="width: 0.582em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.486em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-11"><span class="mi" id="MathJax-Span-12" style="font-family: STIXGeneral-Italic;">c</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.614em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-2">c</script>) on each edge and balance(<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-3-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-13" style="width: 0.63em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.534em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-14"><span class="mi" id="MathJax-Span-15" style="font-family: STIXGeneral-Italic;">b</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.892em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-3">b</script>) for each vertex. We want to solve the following LP. (To make things easier, there is no capacity constraint on the edges. We will show how to fix that problem.)</p>

<p><span class="MathJax_Preview"></span><div class="MathJax_Display" role="textbox" aria-readonly="true" style="text-align: center;"><span class="MathJax" id="MathJax-Element-4-Frame"><nobr><span class="math" id="MathJax-Span-16" style="width: 24.205em; display: inline-block;"><span style="display: inline-block; position: relative; width: 21.017em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(-1.06em 1000.002em 5.123em -0.287em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-17"><span class="mtable" id="MathJax-Span-18" style="padding-right: 0.147em; padding-left: 0.147em;"><span style="display: inline-block; position: relative; width: 20.679em; height: 0px;"><span style="position: absolute; clip: rect(2.176em 1000.002em 6.089em -0.432em); top: -4.587em; left: 0.002em;"><span style="display: inline-block; position: relative; width: 4.157em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -4.104em; right: 0.002em;"><span class="mtd" id="MathJax-Span-19"><span class="mrow" id="MathJax-Span-20"><span class="mtext" id="MathJax-Span-21" style="font-family: STIXGeneral-Regular;">minimize&nbsp;</span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; clip: rect(1.693em 1000.002em 2.901em -0.432em); top: -1.399em; right: 0.002em;"><span class="mtd" id="MathJax-Span-39"><span class="mrow" id="MathJax-Span-40"><span class="mtext" id="MathJax-Span-41" style="font-family: STIXGeneral-Regular;">subject to&nbsp;</span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="display: inline-block; width: 0px; height: 4.592em;"></span></span><span style="position: absolute; clip: rect(3.577em 1000.002em 9.761em -0.143em); top: -6.906em; left: 4.157em;"><span style="display: inline-block; position: relative; width: 11.693em; height: 0px;"><span style="position: absolute; clip: rect(0.775em 1000.002em 4.06em -0.143em); top: -4.104em; left: 0.002em;"><span class="mtd" id="MathJax-Span-22"><span class="mrow" id="MathJax-Span-23"><span class="munderover" id="MathJax-Span-24" style="padding-left: 0.244em; padding-right: 0.196em;"><span style="display: inline-block; position: relative; width: 1.307em; height: 0px;"><span style="position: absolute; clip: rect(1.838em 1000.002em 3.577em -0.336em); top: -2.944em; left: 0.002em;"><span class="mo" id="MathJax-Span-25" style="font-family: STIXSizeOneSym; vertical-align: -0.529em;">∑</span><span style="display: inline-block; width: 0px; height: 2.949em;"></span></span><span style="position: absolute; clip: rect(1.693em 1000.002em 2.708em -0.529em); top: -1.157em; left: 0.099em;"><span class="texatom" id="MathJax-Span-26"><span class="mrow" id="MathJax-Span-27"><span class="mi" id="MathJax-Span-28" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">j<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-29" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">=</span><span class="mn" id="MathJax-Span-30" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; clip: rect(1.742em 1000.002em 2.466em -0.432em); top: -3.524em; left: 0.389em;"><span class="mi" id="MathJax-Span-31" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">m</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="msubsup" id="MathJax-Span-32"><span style="display: inline-block; position: relative; width: 0.824em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-33" style="font-family: STIXGeneral-Italic;">c</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mi" id="MathJax-Span-34" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">j<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="msubsup" id="MathJax-Span-35"><span style="display: inline-block; position: relative; width: 0.775em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-36" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mi" id="MathJax-Span-37" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">j<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mtext" id="MathJax-Span-38" style="font-family: STIXGeneral-Regular;">&nbsp;</span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; clip: rect(1.403em 1000.002em 4.254em -0.143em); top: -1.399em; left: 0.002em;"><span class="mtd" id="MathJax-Span-42"><span class="mrow" id="MathJax-Span-43"><span class="munderover" id="MathJax-Span-44" style="padding-left: 0.244em; padding-right: 0.196em;"><span style="display: inline-block; position: relative; width: 2.853em; height: 0px;"><span style="position: absolute; clip: rect(1.838em 1000.002em 3.577em -0.336em); top: -2.944em; left: 0.775em;"><span class="mo" id="MathJax-Span-45" style="font-family: STIXSizeOneSym; vertical-align: -0.529em;">∑</span><span style="display: inline-block; width: 0px; height: 2.949em;"></span></span><span style="position: absolute; clip: rect(1.548em 1000.002em 2.756em -0.432em); top: -1.06em; left: 0.002em;"><span class="texatom" id="MathJax-Span-46"><span class="mrow" id="MathJax-Span-47"><span class="msubsup" id="MathJax-Span-48"><span style="display: inline-block; position: relative; width: 0.534em; height: 0px;"><span style="position: absolute; clip: rect(1.886em 1000.002em 2.466em -0.432em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-49" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">e</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.341em;"><span class="mi" id="MathJax-Span-50" style="font-size: 50%; font-family: STIXGeneral-Italic;">j<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span><span class="mo" id="MathJax-Span-51" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">∈</span><span class="msubsup" id="MathJax-Span-52"><span style="display: inline-block; position: relative; width: 0.824em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.466em -0.432em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-53" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">δ</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.558em; left: 0.341em;"><span class="texatom" id="MathJax-Span-54"><span class="mrow" id="MathJax-Span-55"><span class="mi" id="MathJax-Span-56" style="font-size: 50%; font-family: STIXGeneral-Italic;">i</span><span class="mi" id="MathJax-Span-57" style="font-size: 50%; font-family: STIXGeneral-Italic;">n</span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span><span class="mo" id="MathJax-Span-58" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">(</span><span class="msubsup" id="MathJax-Span-59"><span style="display: inline-block; position: relative; width: 0.534em; height: 0px;"><span style="position: absolute; clip: rect(1.886em 1000.002em 2.466em -0.432em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-60" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">v</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.341em;"><span class="mi" id="MathJax-Span-61" style="font-size: 50%; font-family: STIXGeneral-Italic;">i</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span><span class="mo" id="MathJax-Span-62" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">)</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="msubsup" id="MathJax-Span-63"><span style="display: inline-block; position: relative; width: 0.775em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-64" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mi" id="MathJax-Span-65" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">j<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-66" style="font-family: STIXGeneral-Regular; padding-left: 0.244em;">−</span><span class="munderover" id="MathJax-Span-67" style="padding-left: 0.244em;"><span style="display: inline-block; position: relative; width: 3.094em; height: 0px;"><span style="position: absolute; clip: rect(1.838em 1000.002em 3.577em -0.336em); top: -2.944em; left: 0.92em;"><span class="mo" id="MathJax-Span-68" style="font-family: STIXSizeOneSym; vertical-align: -0.529em;">∑</span><span style="display: inline-block; width: 0px; height: 2.949em;"></span></span><span style="position: absolute; clip: rect(1.645em 1000.002em 2.756em -0.432em); top: -1.109em; left: 0.002em;"><span class="texatom" id="MathJax-Span-69"><span class="mrow" id="MathJax-Span-70"><span class="msubsup" id="MathJax-Span-71"><span style="display: inline-block; position: relative; width: 0.534em; height: 0px;"><span style="position: absolute; clip: rect(1.886em 1000.002em 2.466em -0.432em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-72" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">e</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.341em;"><span class="mi" id="MathJax-Span-73" style="font-size: 50%; font-family: STIXGeneral-Italic;">j<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span><span class="mo" id="MathJax-Span-74" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">∈</span><span class="msubsup" id="MathJax-Span-75"><span style="display: inline-block; position: relative; width: 1.065em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.466em -0.432em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-76" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">δ</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.558em; left: 0.341em;"><span class="texatom" id="MathJax-Span-77"><span class="mrow" id="MathJax-Span-78"><span class="mi" id="MathJax-Span-79" style="font-size: 50%; font-family: STIXGeneral-Italic;">o</span><span class="mi" id="MathJax-Span-80" style="font-size: 50%; font-family: STIXGeneral-Italic;">u</span><span class="mi" id="MathJax-Span-81" style="font-size: 50%; font-family: STIXGeneral-Italic;">t<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span><span class="mo" id="MathJax-Span-82" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">(</span><span class="msubsup" id="MathJax-Span-83"><span style="display: inline-block; position: relative; width: 0.534em; height: 0px;"><span style="position: absolute; clip: rect(1.886em 1000.002em 2.466em -0.432em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-84" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">v</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.341em;"><span class="mi" id="MathJax-Span-85" style="font-size: 50%; font-family: STIXGeneral-Italic;">i</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span><span class="mo" id="MathJax-Span-86" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">)</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="msubsup" id="MathJax-Span-87" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.775em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-88" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mi" id="MathJax-Span-89" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">j<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-90" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="msubsup" id="MathJax-Span-91" style="padding-left: 0.292em;"><span style="display: inline-block; position: relative; width: 0.872em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-92" style="font-family: STIXGeneral-Italic;">b</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.534em;"><span class="mi" id="MathJax-Span-93" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">i</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mtext" id="MathJax-Span-94" style="font-family: STIXGeneral-Regular;">&nbsp;</span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="display: inline-block; width: 0px; height: 6.911em;"></span></span><span style="position: absolute; clip: rect(4.882em 1000.002em 5.413em -0.143em); top: -4.007em; left: 15.848em;"><span style="display: inline-block; position: relative; width: 1.017em; height: 0px;"><span style="position: absolute; clip: rect(2.273em 1000.002em 2.804em -0.143em); top: -1.399em; right: 0.002em;"><span class="mtd" id="MathJax-Span-95"><span class="mrow" id="MathJax-Span-96"><span class="mo" id="MathJax-Span-97" style="font-family: STIXGeneral-Regular; padding-left: 0.244em; padding-right: 0.244em;">,</span><span class="mtext" id="MathJax-Span-98" style="font-family: STIXGeneral-Regular;">&nbsp;</span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="display: inline-block; width: 0px; height: 4.012em;"></span></span><span style="position: absolute; clip: rect(4.302em 1000.002em 5.365em -0.336em); top: -4.007em; left: 16.862em;"><span style="display: inline-block; position: relative; width: 3.819em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.756em -0.336em); top: -1.399em; left: 0.002em;"><span class="mtd" id="MathJax-Span-99"><span class="mrow" id="MathJax-Span-100"><span class="mn" id="MathJax-Span-101" style="font-family: STIXGeneral-Regular;">1</span><span class="mo" id="MathJax-Span-102" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">≤</span><span class="mi" id="MathJax-Span-103" style="font-family: STIXGeneral-Italic; padding-left: 0.292em;">i</span><span class="mo" id="MathJax-Span-104" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">≤</span><span class="mi" id="MathJax-Span-105" style="font-family: STIXGeneral-Italic; padding-left: 0.292em;">n</span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="display: inline-block; width: 0px; height: 4.012em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 6.892em; vertical-align: -3.164em;"></span></span></nobr></span></div><script type="math/tex; mode=display" id="MathJax-Element-4">\begin{alignat*}{2}
    \text{minimize }   & \sum_{j=1}^m c_j x_j\  \\
    \text{subject to }   & \sum_{e_j\in \delta^{in}(v_i)} x_j - \sum_{e_j\in \delta^{out}(v_i)} x_j  = b_i\ &,\ & 1\leq i\leq n\\
  \end{alignat*}</script></p>

<p>Let <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-5-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-106" style="width: 6.959em; display: inline-block;"><span style="display: inline-block; position: relative; width: 6.041em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.645em 1000.002em 2.998em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-107"><span class="msubsup" id="MathJax-Span-108"><span style="display: inline-block; position: relative; width: 1.645em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-109" style="font-family: STIXGeneral-Italic;">g</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.534em;"><span class="texatom" id="MathJax-Span-110"><span class="mrow" id="MathJax-Span-111"><span class="mi" id="MathJax-Span-112" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-113" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-114" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-115" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">:</span><span class="msubsup" id="MathJax-Span-116" style="padding-left: 0.292em;"><span style="display: inline-block; position: relative; width: 1.258em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="texatom" id="MathJax-Span-117"><span class="mrow" id="MathJax-Span-118"><span class="mi" id="MathJax-Span-119" style="font-family: STIXGeneral-Regular;">ℝ</span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.703em; left: 0.775em;"><span class="mi" id="MathJax-Span-120" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">n</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-121" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">→</span><span class="texatom" id="MathJax-Span-122" style="padding-left: 0.292em;"><span class="mrow" id="MathJax-Span-123"><span class="mi" id="MathJax-Span-124" style="font-family: STIXGeneral-Regular;">ℝ</span></span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.336em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-5">g_{G,c}:\mathbb{R}^n\to \mathbb{R}</script>. <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-6-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-125" style="width: 3.287em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.853em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.998em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-126"><span class="msubsup" id="MathJax-Span-127"><span style="display: inline-block; position: relative; width: 1.645em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-128" style="font-family: STIXGeneral-Italic;">g</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.534em;"><span class="texatom" id="MathJax-Span-129"><span class="mrow" id="MathJax-Span-130"><span class="mi" id="MathJax-Span-131" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-132" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-133" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-134" style="font-family: STIXGeneral-Regular;">(</span><span class="mi" id="MathJax-Span-135" style="font-family: STIXGeneral-Italic;">b</span><span class="mo" id="MathJax-Span-136" style="font-family: STIXGeneral-Regular;">)</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.281em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-6">g_{G,c}(b)</script> denote the minimum value obtained for the above LP when the balance is <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-7-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-137" style="width: 0.63em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.534em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-138"><span class="mi" id="MathJax-Span-139" style="font-family: STIXGeneral-Italic;">b</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.892em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-7">b</script>. We are interested in represent the function <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-8-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-140" style="width: 6.621em; display: inline-block;"><span style="display: inline-block; position: relative; width: 5.751em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.5em 1000.002em 2.998em -0.577em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-141"><span class="msubsup" id="MathJax-Span-142"><span style="display: inline-block; position: relative; width: 1.403em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.853em -0.577em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-143" style="font-family: STIXGeneral-Italic;">f<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.147em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.292em;"><span class="texatom" id="MathJax-Span-144"><span class="mrow" id="MathJax-Span-145"><span class="mi" id="MathJax-Span-146" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-147" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-148" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-149" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">:</span><span class="msubsup" id="MathJax-Span-150" style="padding-left: 0.292em;"><span style="display: inline-block; position: relative; width: 1.21em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="texatom" id="MathJax-Span-151"><span class="mrow" id="MathJax-Span-152"><span class="mi" id="MathJax-Span-153" style="font-family: STIXGeneral-Regular;">ℝ</span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.703em; left: 0.775em;"><span class="mi" id="MathJax-Span-154" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-155" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">→</span><span class="texatom" id="MathJax-Span-156" style="padding-left: 0.292em;"><span class="mrow" id="MathJax-Span-157"><span class="mi" id="MathJax-Span-158" style="font-family: STIXGeneral-Regular;">ℝ</span></span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.503em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-8">f_{G,c}:\mathbb{R}^k\to \mathbb{R}</script>, where <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-9-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-159" style="width: 11.307em; display: inline-block;"><span style="display: inline-block; position: relative; width: 9.809em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.5em 1000.002em 2.998em -0.577em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-160"><span class="msubsup" id="MathJax-Span-161"><span style="display: inline-block; position: relative; width: 1.403em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.853em -0.577em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-162" style="font-family: STIXGeneral-Italic;">f<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.147em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.292em;"><span class="texatom" id="MathJax-Span-163"><span class="mrow" id="MathJax-Span-164"><span class="mi" id="MathJax-Span-165" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-166" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-167" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-168" style="font-family: STIXGeneral-Regular;">(</span><span class="mi" id="MathJax-Span-169" style="font-family: STIXGeneral-Italic;">b</span><span class="mo" id="MathJax-Span-170" style="font-family: STIXGeneral-Regular;">)</span><span class="mo" id="MathJax-Span-171" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="msubsup" id="MathJax-Span-172" style="padding-left: 0.292em;"><span style="display: inline-block; position: relative; width: 1.645em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-173" style="font-family: STIXGeneral-Italic;">g</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.534em;"><span class="texatom" id="MathJax-Span-174"><span class="mrow" id="MathJax-Span-175"><span class="mi" id="MathJax-Span-176" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-177" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-178" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-179" style="font-family: STIXGeneral-Regular;">(</span><span class="mi" id="MathJax-Span-180" style="font-family: STIXGeneral-Italic;">b</span><span class="mo" id="MathJax-Span-181" style="font-family: STIXGeneral-Regular; padding-left: 0.244em;">⊕</span><span class="msubsup" id="MathJax-Span-182" style="padding-left: 0.244em;"><span style="display: inline-block; position: relative; width: 1.79em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mn" id="MathJax-Span-183" style="font-family: STIXGeneral-Regular;">0</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.703em; left: 0.534em;"><span class="texatom" id="MathJax-Span-184"><span class="mrow" id="MathJax-Span-185"><span class="mi" id="MathJax-Span-186" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">n</span><span class="mo" id="MathJax-Span-187" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">−</span><span class="mi" id="MathJax-Span-188" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-189" style="font-family: STIXGeneral-Regular;">)</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.503em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-9">f_{G,c}(b)=g_{G,c}(b\oplus 0^{n-k})</script>. Basically, this says the first <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-10-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-190" style="width: 0.582em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.486em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-191"><span class="mi" id="MathJax-Span-192" style="font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.892em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-10">k</script> vertices of <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-11-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-193" style="width: 0.872em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.727em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-194"><span class="mi" id="MathJax-Span-195" style="font-family: STIXGeneral-Italic;">G</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.892em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-11">G</script> are the terminal vertices, and they “connect to the outside”, therefore can have non-zero balance.</p>

<p>Notice that <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-12-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-196" style="width: 2.998em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.611em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.998em -0.577em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-197"><span class="msubsup" id="MathJax-Span-198"><span style="display: inline-block; position: relative; width: 1.403em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.853em -0.577em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-199" style="font-family: STIXGeneral-Italic;">f<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.147em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.292em;"><span class="texatom" id="MathJax-Span-200"><span class="mrow" id="MathJax-Span-201"><span class="mi" id="MathJax-Span-202" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-203" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-204" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-205" style="font-family: STIXGeneral-Regular;">(</span><span class="mi" id="MathJax-Span-206" style="font-family: STIXGeneral-Italic;">b</span><span class="mo" id="MathJax-Span-207" style="font-family: STIXGeneral-Regular;">)</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.281em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-12">f_{G,c}(b)</script> is a <a href="http://inst.eecs.berkeley.edu/~ee127a/book/login/l_lqp_poly_fcns.html">polyhedral function</a>, because <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-13-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-208" style="width: 1.983em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.693em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.756em -0.432em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-209"><span class="msubsup" id="MathJax-Span-210"><span style="display: inline-block; position: relative; width: 1.645em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-211" style="font-family: STIXGeneral-Italic;">g</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.534em;"><span class="texatom" id="MathJax-Span-212"><span class="mrow" id="MathJax-Span-213"><span class="mi" id="MathJax-Span-214" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-215" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-216" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.003em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-13">g_{G,c}</script> is polyhedral and <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-14-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-217" style="width: 1.693em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.452em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.452em 1000.002em 2.756em -0.577em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-218"><span class="msubsup" id="MathJax-Span-219"><span style="display: inline-block; position: relative; width: 1.403em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.853em -0.577em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-220" style="font-family: STIXGeneral-Italic;">f<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.147em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.292em;"><span class="texatom" id="MathJax-Span-221"><span class="mrow" id="MathJax-Span-222"><span class="mi" id="MathJax-Span-223" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-224" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-225" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.281em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-14">f_{G,c}</script> is just a projection. Therefore epigraph <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-15-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-226" style="width: 15.51em; display: inline-block;"><span style="display: inline-block; position: relative; width: 13.481em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.5em 1000.002em 2.998em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-227"><span class="msubsup" id="MathJax-Span-228"><span style="display: inline-block; position: relative; width: 1.742em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-229" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.63em;"><span class="texatom" id="MathJax-Span-230"><span class="mrow" id="MathJax-Span-231"><span class="mi" id="MathJax-Span-232" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-233" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-234" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-235" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="mo" id="MathJax-Span-236" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">{</span><span class="mo" id="MathJax-Span-237" style="font-family: STIXGeneral-Regular;">(</span><span class="mi" id="MathJax-Span-238" style="font-family: STIXGeneral-Italic;">b</span><span class="mo" id="MathJax-Span-239" style="font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-240" style="font-family: STIXGeneral-Italic; padding-left: 0.196em;">t<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-241" style="font-family: STIXGeneral-Regular;">)</span><span class="mo" id="MathJax-Span-242" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">∈</span><span class="msubsup" id="MathJax-Span-243" style="padding-left: 0.292em;"><span style="display: inline-block; position: relative; width: 2.031em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="texatom" id="MathJax-Span-244"><span class="mrow" id="MathJax-Span-245"><span class="mi" id="MathJax-Span-246" style="font-family: STIXGeneral-Regular;">ℝ</span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.703em; left: 0.775em;"><span class="texatom" id="MathJax-Span-247"><span class="mrow" id="MathJax-Span-248"><span class="mi" id="MathJax-Span-249" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-250" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">+</span><span class="mn" id="MathJax-Span-251" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="texatom" id="MathJax-Span-252"><span class="mrow" id="MathJax-Span-253"><span class="mo" id="MathJax-Span-254" style="font-family: STIXGeneral-Regular;">|</span></span></span><span class="mi" id="MathJax-Span-255" style="font-family: STIXGeneral-Italic;">t<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-256" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">≥</span><span class="msubsup" id="MathJax-Span-257" style="padding-left: 0.292em;"><span style="display: inline-block; position: relative; width: 1.403em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.853em -0.577em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-258" style="font-family: STIXGeneral-Italic;">f<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.147em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.292em;"><span class="texatom" id="MathJax-Span-259"><span class="mrow" id="MathJax-Span-260"><span class="mi" id="MathJax-Span-261" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-262" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-263" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-264" style="font-family: STIXGeneral-Regular;">(</span><span class="mi" id="MathJax-Span-265" style="font-family: STIXGeneral-Italic;">b</span><span class="mo" id="MathJax-Span-266" style="font-family: STIXGeneral-Regular;">)</span><span class="mo" id="MathJax-Span-267" style="font-family: STIXGeneral-Regular;">}</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.503em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-15">P_{G,c} = \{   (b,t)\in \mathbb{R}^{k+1} | t\geq f_{G,c}(b) \}</script> is a polytope. We can represent <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-16-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-268" style="width: 2.08em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.79em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.452em 1000.002em 2.659em -0.432em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-269"><span class="msubsup" id="MathJax-Span-270"><span style="display: inline-block; position: relative; width: 1.742em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-271" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.63em;"><span class="texatom" id="MathJax-Span-272"><span class="mrow" id="MathJax-Span-273"><span class="mi" id="MathJax-Span-274" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-275" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-276" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.169em; vertical-align: -0.331em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-16">P_{G,c}</script> by <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-17-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-277" style="width: 2.659em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.321em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.853em -0.384em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-278"><span class="mo" id="MathJax-Span-279" style="font-family: STIXGeneral-Regular;">(</span><span class="mi" id="MathJax-Span-280" style="font-family: STIXGeneral-Italic;">A</span><span class="mo" id="MathJax-Span-281" style="font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-282" style="font-family: STIXGeneral-Italic; padding-left: 0.196em;">d<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.051em;"></span></span><span class="mo" id="MathJax-Span-283" style="font-family: STIXGeneral-Regular;">)</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.114em; vertical-align: -0.275em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-17">(A,d)</script>, such that <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-18-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-284" style="width: 9.229em; display: inline-block;"><span style="display: inline-block; position: relative; width: 8.022em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.901em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-285"><span class="msubsup" id="MathJax-Span-286"><span style="display: inline-block; position: relative; width: 1.742em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-287" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.63em;"><span class="texatom" id="MathJax-Span-288"><span class="mrow" id="MathJax-Span-289"><span class="mi" id="MathJax-Span-290" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-291" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-292" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-293" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="mo" id="MathJax-Span-294" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">{</span><span class="mi" id="MathJax-Span-295" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mtext" id="MathJax-Span-296" style="font-family: STIXGeneral-Regular;">&nbsp;</span><span class="texatom" id="MathJax-Span-297"><span class="mrow" id="MathJax-Span-298"><span class="mo" id="MathJax-Span-299" style="font-family: STIXGeneral-Regular;">|</span></span></span><span class="mtext" id="MathJax-Span-300" style="font-family: STIXGeneral-Regular;">&nbsp;</span><span class="mi" id="MathJax-Span-301" style="font-family: STIXGeneral-Italic;">A</span><span class="mi" id="MathJax-Span-302" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-303" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">≤</span><span class="mi" id="MathJax-Span-304" style="font-family: STIXGeneral-Italic; padding-left: 0.292em;">d<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.051em;"></span></span><span class="mo" id="MathJax-Span-305" style="font-family: STIXGeneral-Regular;">}</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.169em; vertical-align: -0.331em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-18">P_{G,c}=\{x~|~Ax\leq d\}</script>. The size of the representation is the number of rows in <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-19-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-306" style="width: 0.727em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.63em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-307"><span class="mi" id="MathJax-Span-308" style="font-family: STIXGeneral-Italic;">A</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.892em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-19">A</script>. </p>

<p>Now, assume we have two graphs <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-20-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-309" style="width: 5.123em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.447em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.853em -0.384em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-310"><span class="mi" id="MathJax-Span-311" style="font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-312" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="mo" id="MathJax-Span-313" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">(</span><span class="mi" id="MathJax-Span-314" style="font-family: STIXGeneral-Italic;">V<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.099em;"></span></span><span class="mo" id="MathJax-Span-315" style="font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-316" style="font-family: STIXGeneral-Italic; padding-left: 0.196em;">E<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-317" style="font-family: STIXGeneral-Regular;">)</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.114em; vertical-align: -0.275em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-20">G=(V,E)</script> and <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-21-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-318" style="width: 6.476em; display: inline-block;"><span style="display: inline-block; position: relative; width: 5.606em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.597em 1000.002em 2.853em -0.384em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-319"><span class="msup" id="MathJax-Span-320"><span style="display: inline-block; position: relative; width: 1.065em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-321" style="font-family: STIXGeneral-Italic;">G</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.703em; left: 0.727em;"><span class="mo" id="MathJax-Span-322" style="font-size: 70.7%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-323" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="mo" id="MathJax-Span-324" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">(</span><span class="msup" id="MathJax-Span-325"><span style="display: inline-block; position: relative; width: 1.114em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.336em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-326" style="font-family: STIXGeneral-Italic;">V<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.099em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.703em; left: 0.824em;"><span class="mo" id="MathJax-Span-327" style="font-size: 70.7%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-328" style="font-family: STIXGeneral-Regular;">,</span><span class="msup" id="MathJax-Span-329" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 1.017em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-330" style="font-family: STIXGeneral-Italic;">E<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.703em; left: 0.679em;"><span class="mo" id="MathJax-Span-331" style="font-size: 70.7%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-332" style="font-family: STIXGeneral-Regular;">)</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.225em; vertical-align: -0.275em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-21">G'=(V',E')</script>. Each has a cost function <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-22-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-333" style="width: 0.582em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.486em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-334"><span class="mi" id="MathJax-Span-335" style="font-family: STIXGeneral-Italic;">c</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.614em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-22">c</script> and <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-23-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-336" style="width: 1.017em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.872em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.355em 1000.002em 2.418em -0.384em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-337"><span class="msup" id="MathJax-Span-338"><span style="display: inline-block; position: relative; width: 0.824em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-339" style="font-family: STIXGeneral-Italic;">c</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.703em; left: 0.486em;"><span class="mo" id="MathJax-Span-340" style="font-size: 70.7%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.003em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-23">c'</script>. <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-24-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-341" style="width: 5.22em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.543em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.597em 1000.002em 2.756em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-342"><span class="mi" id="MathJax-Span-343" style="font-family: STIXGeneral-Italic;">E<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-344" style="font-family: STIXGeneral-Regular; padding-left: 0.244em;">∩</span><span class="msup" id="MathJax-Span-345" style="padding-left: 0.244em;"><span style="display: inline-block; position: relative; width: 1.017em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-346" style="font-family: STIXGeneral-Italic;">E<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.703em; left: 0.679em;"><span class="mo" id="MathJax-Span-347" style="font-size: 70.7%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-348" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="mi" id="MathJax-Span-349" style="font-family: STIXVariants; padding-left: 0.292em;">∅</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.114em; vertical-align: -0.164em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-24">E\cap E'=\emptyset</script>, <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-25-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-350" style="width: 5.606em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.882em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.597em 1000.002em 2.708em -0.336em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-351"><span class="mi" id="MathJax-Span-352" style="font-family: STIXGeneral-Italic;">V<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.099em;"></span></span><span class="mo" id="MathJax-Span-353" style="font-family: STIXGeneral-Regular; padding-left: 0.244em;">∩</span><span class="msup" id="MathJax-Span-354" style="padding-left: 0.244em;"><span style="display: inline-block; position: relative; width: 1.114em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.336em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-355" style="font-family: STIXGeneral-Italic;">V<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.099em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.703em; left: 0.824em;"><span class="mo" id="MathJax-Span-356" style="font-size: 70.7%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-357" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="mi" id="MathJax-Span-358" style="font-family: STIXGeneral-Italic; padding-left: 0.292em;">T<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.099em;"></span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.058em; vertical-align: -0.108em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-25">V\cap V'=T</script> (they share some terminals…)</p>

<p>Can we compute a representation of <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-26-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-359" style="width: 4.688em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.06em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.452em 1000.002em 2.756em -0.432em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-360"><span class="msubsup" id="MathJax-Span-361"><span style="display: inline-block; position: relative; width: 4.012em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-362" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.123em; left: 0.63em;"><span class="texatom" id="MathJax-Span-363"><span class="mrow" id="MathJax-Span-364"><span class="mi" id="MathJax-Span-365" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-366" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">∪</span><span class="msup" id="MathJax-Span-367"><span style="display: inline-block; position: relative; width: 0.775em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.466em -0.384em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-368" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.558em; left: 0.534em;"><span class="mo" id="MathJax-Span-369" style="font-size: 50%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span><span class="mo" id="MathJax-Span-370" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-371" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span><span class="mo" id="MathJax-Span-372" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">+</span><span class="msup" id="MathJax-Span-373"><span style="display: inline-block; position: relative; width: 0.582em; height: 0px;"><span style="position: absolute; clip: rect(1.886em 1000.002em 2.466em -0.432em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-374" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.461em; left: 0.341em;"><span class="mo" id="MathJax-Span-375" style="font-size: 50%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.225em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-26">P_{G\cup G',c+c'}</script>?</p>

<p>Let <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-27-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-376" style="width: 8.36em; display: inline-block;"><span style="display: inline-block; position: relative; width: 7.249em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.998em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-377"><span class="mi" id="MathJax-Span-378" style="font-family: STIXGeneral-Italic;">P</span><span class="mo" id="MathJax-Span-379" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="msubsup" id="MathJax-Span-380" style="padding-left: 0.292em;"><span style="display: inline-block; position: relative; width: 1.742em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-381" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.63em;"><span class="texatom" id="MathJax-Span-382"><span class="mrow" id="MathJax-Span-383"><span class="mi" id="MathJax-Span-384" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-385" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-386" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-387" style="font-family: STIXGeneral-Regular; padding-left: 0.244em;">⊕</span><span class="msubsup" id="MathJax-Span-388" style="padding-left: 0.244em;"><span style="display: inline-block; position: relative; width: 2.273em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-389" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.123em; left: 0.63em;"><span class="texatom" id="MathJax-Span-390"><span class="mrow" id="MathJax-Span-391"><span class="msup" id="MathJax-Span-392"><span style="display: inline-block; position: relative; width: 0.775em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.466em -0.384em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-393" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.558em; left: 0.534em;"><span class="mo" id="MathJax-Span-394" style="font-size: 50%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span><span class="mo" id="MathJax-Span-395" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="msup" id="MathJax-Span-396"><span style="display: inline-block; position: relative; width: 0.582em; height: 0px;"><span style="position: absolute; clip: rect(1.886em 1000.002em 2.466em -0.432em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-397" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.461em; left: 0.341em;"><span class="mo" id="MathJax-Span-398" style="font-size: 50%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.225em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-27">P= P_{G,c} \oplus P_{G',c'}</script>. <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-28-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-399" style="width: 4.688em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.06em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.452em 1000.002em 2.756em -0.432em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-400"><span class="msubsup" id="MathJax-Span-401"><span style="display: inline-block; position: relative; width: 4.012em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-402" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.123em; left: 0.63em;"><span class="texatom" id="MathJax-Span-403"><span class="mrow" id="MathJax-Span-404"><span class="mi" id="MathJax-Span-405" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-406" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">∪</span><span class="msup" id="MathJax-Span-407"><span style="display: inline-block; position: relative; width: 0.775em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.466em -0.384em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-408" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.558em; left: 0.534em;"><span class="mo" id="MathJax-Span-409" style="font-size: 50%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span><span class="mo" id="MathJax-Span-410" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-411" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span><span class="mo" id="MathJax-Span-412" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">+</span><span class="msup" id="MathJax-Span-413"><span style="display: inline-block; position: relative; width: 0.582em; height: 0px;"><span style="position: absolute; clip: rect(1.886em 1000.002em 2.466em -0.432em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-414" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.461em; left: 0.341em;"><span class="mo" id="MathJax-Span-415" style="font-size: 50%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.225em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-28">P_{G\cup G',c+c'}</script> can be written as a linear transform of <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-29-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-416" style="width: 0.727em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.63em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-417"><span class="mi" id="MathJax-Span-418" style="font-family: STIXGeneral-Italic;">P</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.892em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-29">P</script>. It would be easy to see by showing a sequence of transforms.</p>

<p>First, we sum the cost <br>
<span class="MathJax_Preview"></span><div class="MathJax_Display" role="textbox" aria-readonly="true" style="text-align: center;"><span class="MathJax" id="MathJax-Element-30-Frame"><nobr><span class="math" id="MathJax-Span-419" style="width: 34.012em; display: inline-block;"><span style="display: inline-block; position: relative; width: 29.568em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.548em 1000.002em 2.901em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-420"><span class="msup" id="MathJax-Span-421"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-422" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.751em; left: 0.63em;"><span class="mo" id="MathJax-Span-423" style="font-size: 70.7%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-424" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="mo" id="MathJax-Span-425" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">{</span><span class="mo" id="MathJax-Span-426" style="font-family: STIXGeneral-Regular;">(</span><span class="msubsup" id="MathJax-Span-427"><span style="display: inline-block; position: relative; width: 0.92em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-428" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mn" id="MathJax-Span-429" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-430" style="font-family: STIXGeneral-Regular;">,</span><span class="mo" id="MathJax-Span-431" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">…</span><span class="mo" id="MathJax-Span-432" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">,</span><span class="msubsup" id="MathJax-Span-433" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.872em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-434" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mi" id="MathJax-Span-435" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-436" style="font-family: STIXGeneral-Regular;">,</span><span class="msubsup" id="MathJax-Span-437" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-438" style="font-family: STIXGeneral-Italic;">y</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.486em;"><span class="mn" id="MathJax-Span-439" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-440" style="font-family: STIXGeneral-Regular;">,</span><span class="mo" id="MathJax-Span-441" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">…</span><span class="mo" id="MathJax-Span-442" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">,</span><span class="msubsup" id="MathJax-Span-443" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.92em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-444" style="font-family: STIXGeneral-Italic;">y</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.486em;"><span class="mi" id="MathJax-Span-445" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-446" style="font-family: STIXGeneral-Regular;">,</span><span class="msubsup" id="MathJax-Span-447" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-448" style="font-family: STIXGeneral-Italic;">c</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mn" id="MathJax-Span-449" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-450" style="font-family: STIXGeneral-Regular; padding-left: 0.244em;">+</span><span class="msubsup" id="MathJax-Span-451" style="padding-left: 0.244em;"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-452" style="font-family: STIXGeneral-Italic;">c</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mn" id="MathJax-Span-453" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">2</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-454" style="font-family: STIXGeneral-Regular;">)</span><span class="texatom" id="MathJax-Span-455"><span class="mrow" id="MathJax-Span-456"><span class="mo" id="MathJax-Span-457" style="font-family: STIXGeneral-Regular;">|</span></span></span><span class="mo" id="MathJax-Span-458" style="font-family: STIXGeneral-Regular;">(</span><span class="msubsup" id="MathJax-Span-459"><span style="display: inline-block; position: relative; width: 0.92em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-460" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mn" id="MathJax-Span-461" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-462" style="font-family: STIXGeneral-Regular;">,</span><span class="mo" id="MathJax-Span-463" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">…</span><span class="mo" id="MathJax-Span-464" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">,</span><span class="msubsup" id="MathJax-Span-465" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.872em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-466" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mi" id="MathJax-Span-467" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-468" style="font-family: STIXGeneral-Regular;">,</span><span class="msubsup" id="MathJax-Span-469" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-470" style="font-family: STIXGeneral-Italic;">c</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mn" id="MathJax-Span-471" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-472" style="font-family: STIXGeneral-Regular;">,</span><span class="msubsup" id="MathJax-Span-473" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-474" style="font-family: STIXGeneral-Italic;">y</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.486em;"><span class="mn" id="MathJax-Span-475" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-476" style="font-family: STIXGeneral-Regular;">,</span><span class="mo" id="MathJax-Span-477" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">…</span><span class="mo" id="MathJax-Span-478" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">,</span><span class="msubsup" id="MathJax-Span-479" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.92em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-480" style="font-family: STIXGeneral-Italic;">y</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.486em;"><span class="mi" id="MathJax-Span-481" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-482" style="font-family: STIXGeneral-Regular;">,</span><span class="msubsup" id="MathJax-Span-483" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-484" style="font-family: STIXGeneral-Italic;">c</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mn" id="MathJax-Span-485" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">2</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-486" style="font-family: STIXGeneral-Regular;">)</span><span class="mo" id="MathJax-Span-487" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">∈</span><span class="mi" id="MathJax-Span-488" style="font-family: STIXGeneral-Italic; padding-left: 0.292em;">P</span><span class="mo" id="MathJax-Span-489" style="font-family: STIXGeneral-Regular;">}</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.336em; vertical-align: -0.331em;"></span></span></nobr></span></div><script type="math/tex; mode=display" id="MathJax-Element-30">P'= \{ (x_1,\ldots,x_k,y_1,\ldots,y_k,c_1+c_2) | (x_1,\ldots,x_k,c_1,y_1,\ldots,y_k,c_2)\in P\}</script></p>

<p>Then, we start merging terminals that shows up in both <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-31-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-490" style="width: 0.872em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.727em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-491"><span class="mi" id="MathJax-Span-492" style="font-family: STIXGeneral-Italic;">G</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.892em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-31">G</script> and <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-32-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-493" style="width: 1.307em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.114em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.355em 1000.002em 2.418em -0.384em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-494"><span class="msup" id="MathJax-Span-495"><span style="display: inline-block; position: relative; width: 1.065em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-496" style="font-family: STIXGeneral-Italic;">G</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.703em; left: 0.727em;"><span class="mo" id="MathJax-Span-497" style="font-size: 70.7%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.058em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-32">G'</script>. Say, if <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-33-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-498" style="width: 3.722em; display: inline-block;"><span style="display: inline-block; position: relative; width: 3.239em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.645em 1000.002em 2.949em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-499"><span class="msubsup" id="MathJax-Span-500"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-501" style="font-family: STIXGeneral-Italic;">v</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mn" id="MathJax-Span-502" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-503" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="msubsup" id="MathJax-Span-504" style="padding-left: 0.292em;"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-505" style="font-family: STIXGeneral-Italic;">v</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; clip: rect(1.79em 1000.002em 2.466em -0.384em); top: -2.655em; left: 0.486em;"><span class="mo" id="MathJax-Span-506" style="font-size: 70.7%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; clip: rect(1.693em 1000.002em 2.466em -0.336em); top: -2.027em; left: 0.486em;"><span class="mn" id="MathJax-Span-507" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.281em; vertical-align: -0.386em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-33">v_1=v_1'</script>, then let <br>
<span class="MathJax_Preview"></span><div class="MathJax_Display" role="textbox" aria-readonly="true" style="text-align: center;"><span class="MathJax" id="MathJax-Element-34-Frame"><nobr><span class="math" id="MathJax-Span-508" style="width: 32.998em; display: inline-block;"><span style="display: inline-block; position: relative; width: 28.698em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.548em 1000.002em 2.901em -0.432em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-509"><span class="msubsup" id="MathJax-Span-510"><span style="display: inline-block; position: relative; width: 1.114em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-511" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; clip: rect(1.79em 1000.002em 2.466em -0.384em); top: -2.703em; left: 0.63em;"><span class="mo" id="MathJax-Span-512" style="font-size: 70.7%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; clip: rect(1.693em 1000.002em 2.466em -0.336em); top: -2.075em; left: 0.63em;"><span class="mn" id="MathJax-Span-513" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-514" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="mo" id="MathJax-Span-515" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">{</span><span class="mo" id="MathJax-Span-516" style="font-family: STIXGeneral-Regular;">(</span><span class="msubsup" id="MathJax-Span-517"><span style="display: inline-block; position: relative; width: 0.92em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-518" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mn" id="MathJax-Span-519" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-520" style="font-family: STIXGeneral-Regular; padding-left: 0.244em;">+</span><span class="msubsup" id="MathJax-Span-521" style="padding-left: 0.244em;"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-522" style="font-family: STIXGeneral-Italic;">y</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.486em;"><span class="mn" id="MathJax-Span-523" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-524" style="font-family: STIXGeneral-Regular;">,</span><span class="msubsup" id="MathJax-Span-525" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.92em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-526" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mn" id="MathJax-Span-527" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">2</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-528" style="font-family: STIXGeneral-Regular;">,</span><span class="mo" id="MathJax-Span-529" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">…</span><span class="mo" id="MathJax-Span-530" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">,</span><span class="msubsup" id="MathJax-Span-531" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.872em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-532" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mi" id="MathJax-Span-533" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-534" style="font-family: STIXGeneral-Regular;">,</span><span class="msubsup" id="MathJax-Span-535" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-536" style="font-family: STIXGeneral-Italic;">y</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.486em;"><span class="mn" id="MathJax-Span-537" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">2</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-538" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">…</span><span class="mo" id="MathJax-Span-539" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">,</span><span class="msubsup" id="MathJax-Span-540" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.92em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-541" style="font-family: STIXGeneral-Italic;">y</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.486em;"><span class="mi" id="MathJax-Span-542" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-543" style="font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-544" style="font-family: STIXGeneral-Italic; padding-left: 0.196em;">c</span><span class="mo" id="MathJax-Span-545" style="font-family: STIXGeneral-Regular;">)</span><span class="texatom" id="MathJax-Span-546"><span class="mrow" id="MathJax-Span-547"><span class="mo" id="MathJax-Span-548" style="font-family: STIXGeneral-Regular;">|</span></span></span><span class="mo" id="MathJax-Span-549" style="font-family: STIXGeneral-Regular;">(</span><span class="msubsup" id="MathJax-Span-550"><span style="display: inline-block; position: relative; width: 0.92em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-551" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mn" id="MathJax-Span-552" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-553" style="font-family: STIXGeneral-Regular;">,</span><span class="mo" id="MathJax-Span-554" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">…</span><span class="mo" id="MathJax-Span-555" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">,</span><span class="msubsup" id="MathJax-Span-556" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.872em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.659em -0.481em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-557" style="font-family: STIXGeneral-Italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.486em;"><span class="mi" id="MathJax-Span-558" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-559" style="font-family: STIXGeneral-Regular;">,</span><span class="msubsup" id="MathJax-Span-560" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-561" style="font-family: STIXGeneral-Italic;">y</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.486em;"><span class="mn" id="MathJax-Span-562" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-563" style="font-family: STIXGeneral-Regular;">,</span><span class="mo" id="MathJax-Span-564" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">…</span><span class="mo" id="MathJax-Span-565" style="font-family: STIXGeneral-Regular; padding-left: 0.196em;">,</span><span class="msubsup" id="MathJax-Span-566" style="padding-left: 0.196em;"><span style="display: inline-block; position: relative; width: 0.92em; height: 0px;"><span style="position: absolute; clip: rect(1.935em 1000.002em 2.853em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-567" style="font-family: STIXGeneral-Italic;">y</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.075em; left: 0.486em;"><span class="mi" id="MathJax-Span-568" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-569" style="font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-570" style="font-family: STIXGeneral-Italic; padding-left: 0.196em;">c</span><span class="mo" id="MathJax-Span-571" style="font-family: STIXGeneral-Regular;">)</span><span class="mo" id="MathJax-Span-572" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">∈</span><span class="msup" id="MathJax-Span-573" style="padding-left: 0.292em;"><span style="display: inline-block; position: relative; width: 0.969em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-574" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.751em; left: 0.63em;"><span class="mo" id="MathJax-Span-575" style="font-size: 70.7%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-576" style="font-family: STIXGeneral-Regular;">}</span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.336em; vertical-align: -0.331em;"></span></span></nobr></span></div><script type="math/tex; mode=display" id="MathJax-Element-34">P'_1= \{ (x_1+y_1,x_2,\ldots,x_k,y_2\ldots,y_k,c) | (x_1,\ldots,x_k,y_1,\ldots,y_k,c)\in P'\}</script> <br>
and so on.</p>

<p>Thus, if <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-35-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-577" style="width: 2.08em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.79em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.452em 1000.002em 2.659em -0.432em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-578"><span class="msubsup" id="MathJax-Span-579"><span style="display: inline-block; position: relative; width: 1.742em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-580" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.63em;"><span class="texatom" id="MathJax-Span-581"><span class="mrow" id="MathJax-Span-582"><span class="mi" id="MathJax-Span-583" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-584" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-585" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.169em; vertical-align: -0.331em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-35">P_{G,c}</script> and <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-36-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-586" style="width: 2.659em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.321em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.452em 1000.002em 2.756em -0.432em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-587"><span class="msubsup" id="MathJax-Span-588"><span style="display: inline-block; position: relative; width: 2.273em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-589" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.123em; left: 0.63em;"><span class="texatom" id="MathJax-Span-590"><span class="mrow" id="MathJax-Span-591"><span class="msup" id="MathJax-Span-592"><span style="display: inline-block; position: relative; width: 0.775em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.466em -0.384em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-593" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.558em; left: 0.534em;"><span class="mo" id="MathJax-Span-594" style="font-size: 50%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span><span class="mo" id="MathJax-Span-595" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="msup" id="MathJax-Span-596"><span style="display: inline-block; position: relative; width: 0.582em; height: 0px;"><span style="position: absolute; clip: rect(1.886em 1000.002em 2.466em -0.432em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-597" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.461em; left: 0.341em;"><span class="mo" id="MathJax-Span-598" style="font-size: 50%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.225em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-36">P_{G',c'}</script>’s representation has <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-37-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-599" style="width: 1.307em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.114em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.452em 1000.002em 2.563em -0.384em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-600"><span class="msubsup" id="MathJax-Span-601"><span style="display: inline-block; position: relative; width: 1.065em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-602" style="font-family: STIXGeneral-Italic;">T<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.099em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.582em;"><span class="mn" id="MathJax-Span-603" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.058em; vertical-align: -0.219em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-37">T_1</script> rows and <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-38-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-604" style="width: 1.307em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.114em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.452em 1000.002em 2.563em -0.384em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-605"><span class="msubsup" id="MathJax-Span-606"><span style="display: inline-block; position: relative; width: 1.065em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-607" style="font-family: STIXGeneral-Italic;">T<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.099em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.582em;"><span class="mn" id="MathJax-Span-608" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">2</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.058em; vertical-align: -0.219em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-38">T_2</script> rows, then one can obtain <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-39-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-609" style="width: 4.688em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.06em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.452em 1000.002em 2.756em -0.432em); top: -2.268em; left: 0.002em;"><span class="mrow" id="MathJax-Span-610"><span class="msubsup" id="MathJax-Span-611"><span style="display: inline-block; position: relative; width: 4.012em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.432em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-612" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.123em; left: 0.63em;"><span class="texatom" id="MathJax-Span-613"><span class="mrow" id="MathJax-Span-614"><span class="mi" id="MathJax-Span-615" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-616" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">∪</span><span class="msup" id="MathJax-Span-617"><span style="display: inline-block; position: relative; width: 0.775em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.466em -0.384em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-618" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.558em; left: 0.534em;"><span class="mo" id="MathJax-Span-619" style="font-size: 50%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span><span class="mo" id="MathJax-Span-620" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-621" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span><span class="mo" id="MathJax-Span-622" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">+</span><span class="msup" id="MathJax-Span-623"><span style="display: inline-block; position: relative; width: 0.582em; height: 0px;"><span style="position: absolute; clip: rect(1.886em 1000.002em 2.466em -0.432em); top: -2.316em; left: 0.002em;"><span class="mi" id="MathJax-Span-624" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span><span style="position: absolute; top: -2.461em; left: 0.341em;"><span class="mo" id="MathJax-Span-625" style="font-size: 50%; font-family: STIXVariants;">′</span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.273em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.225em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-39">P_{G\cup G',c+c'}</script> with representation size at most <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-40-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-626" style="width: 3.867em; display: inline-block;"><span style="display: inline-block; position: relative; width: 3.336em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.804em -0.384em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-627"><span class="msubsup" id="MathJax-Span-628"><span style="display: inline-block; position: relative; width: 1.065em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-629" style="font-family: STIXGeneral-Italic;">T<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.099em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.582em;"><span class="mn" id="MathJax-Span-630" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">1</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span><span class="mo" id="MathJax-Span-631" style="font-family: STIXGeneral-Regular; padding-left: 0.244em;">+</span><span class="msubsup" id="MathJax-Span-632" style="padding-left: 0.244em;"><span style="display: inline-block; position: relative; width: 1.065em; height: 0px;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.659em -0.384em); top: -2.51em; left: 0.002em;"><span class="mi" id="MathJax-Span-633" style="font-family: STIXGeneral-Italic;">T<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.099em;"></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span><span style="position: absolute; top: -2.171em; left: 0.582em;"><span class="mn" id="MathJax-Span-634" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">2</span><span style="display: inline-block; width: 0px; height: 2.321em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.514em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.058em; vertical-align: -0.219em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-40">T_1+T_2</script>. </p>

<p>Now, one just have to use this knowledge to do things on the tree decomposition… somehow…</p>

<blockquote>
  <p>Remark: If there are capacity constraints, say lower bound <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-41-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-635" style="width: 0.344em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.295em; height: 0px; font-size: 114%;"><span style="position: absolute; clip: rect(1.708em 1000.002em 2.683em -0.387em); top: -2.532em; left: 0.002em;"><span class="mrow" id="MathJax-Span-636"><span class="mi" id="MathJax-Span-637" style="font-family: STIXGeneral-Italic;">l<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span></span><span style="display: inline-block; width: 0px; height: 2.537em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.892em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-41">l</script> and upper bound <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-42-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-638" style="width: 0.636em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.538em; height: 0px; font-size: 114%;"><span style="position: absolute; clip: rect(1.952em 1000.002em 2.683em -0.387em); top: -2.532em; left: 0.002em;"><span class="mrow" id="MathJax-Span-639"><span class="mi" id="MathJax-Span-640" style="font-family: STIXGeneral-Italic;">u</span></span><span style="display: inline-block; width: 0px; height: 2.537em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.614em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-42">u</script>, then we have to define <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-43-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-641" style="width: 18.813em; display: inline-block;"><span style="display: inline-block; position: relative; width: 16.474em; height: 0px; font-size: 114%;"><span style="position: absolute; clip: rect(1.708em 1000.002em 3.024em -0.436em); top: -2.532em; left: 0.002em;"><span class="mrow" id="MathJax-Span-642"><span class="msubsup" id="MathJax-Span-643"><span style="display: inline-block; position: relative; width: 2.683em; height: 0px;"><span style="position: absolute; clip: rect(1.757em 1000.002em 2.683em -0.436em); top: -2.532em; left: 0.002em;"><span class="mi" id="MathJax-Span-644" style="font-family: STIXGeneral-Italic;">P</span><span style="display: inline-block; width: 0px; height: 2.537em;"></span></span><span style="position: absolute; top: -2.191em; left: 0.636em;"><span class="texatom" id="MathJax-Span-645"><span class="mrow" id="MathJax-Span-646"><span class="mi" id="MathJax-Span-647" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-648" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-649" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span><span class="mo" id="MathJax-Span-650" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-651" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">l<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-652" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-653" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">u</span></span></span><span style="display: inline-block; width: 0px; height: 2.342em;"></span></span></span></span><span class="mo" id="MathJax-Span-654" style="font-family: STIXGeneral-Regular; padding-left: 0.295em;">=</span><span class="mo" id="MathJax-Span-655" style="font-family: STIXGeneral-Regular; padding-left: 0.295em;">{</span><span class="mo" id="MathJax-Span-656" style="font-family: STIXGeneral-Regular;">(</span><span class="mi" id="MathJax-Span-657" style="font-family: STIXGeneral-Italic;">b</span><span class="mo" id="MathJax-Span-658" style="font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-659" style="font-family: STIXGeneral-Italic; padding-left: 0.197em;">t<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-660" style="font-family: STIXGeneral-Regular;">)</span><span class="texatom" id="MathJax-Span-661"><span class="mrow" id="MathJax-Span-662"><span class="mo" id="MathJax-Span-663" style="font-family: STIXGeneral-Regular;">|</span></span></span><span class="mi" id="MathJax-Span-664" style="font-family: STIXGeneral-Italic;">t<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-665" style="font-family: STIXGeneral-Regular; padding-left: 0.295em;">≥</span><span class="msubsup" id="MathJax-Span-666" style="padding-left: 0.295em;"><span style="display: inline-block; position: relative; width: 2.342em; height: 0px;"><span style="position: absolute; clip: rect(1.708em 1000.002em 2.878em -0.582em); top: -2.532em; left: 0.002em;"><span class="mi" id="MathJax-Span-667" style="font-family: STIXGeneral-Italic;">f<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.149em;"></span></span><span style="display: inline-block; width: 0px; height: 2.537em;"></span></span><span style="position: absolute; top: -2.093em; left: 0.295em;"><span class="texatom" id="MathJax-Span-668"><span class="mrow" id="MathJax-Span-669"><span class="mi" id="MathJax-Span-670" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-671" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-672" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">c</span><span class="mo" id="MathJax-Span-673" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-674" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">l<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-675" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-676" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">u</span></span></span><span style="display: inline-block; width: 0px; height: 2.342em;"></span></span></span></span><span class="mo" id="MathJax-Span-677" style="font-family: STIXGeneral-Regular;">(</span><span class="mi" id="MathJax-Span-678" style="font-family: STIXGeneral-Italic;">b</span><span class="mo" id="MathJax-Span-679" style="font-family: STIXGeneral-Regular;">)</span><span class="mo" id="MathJax-Span-680" style="font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-681" style="font-family: STIXGeneral-Italic; padding-left: 0.197em;">b</span><span class="mo" id="MathJax-Span-682" style="font-family: STIXGeneral-Regular; padding-left: 0.295em;">∈</span><span class="msubsup" id="MathJax-Span-683" style="padding-left: 0.295em;"><span style="display: inline-block; position: relative; width: 2.195em; height: 0px;"><span style="position: absolute; clip: rect(1.757em 1000.002em 2.683em -0.436em); top: -2.532em; left: 0.002em;"><span class="mi" id="MathJax-Span-684" style="font-family: STIXGeneral-Italic;">F<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.051em;"></span></span><span style="display: inline-block; width: 0px; height: 2.537em;"></span></span><span style="position: absolute; top: -2.191em; left: 0.636em;"><span class="texatom" id="MathJax-Span-685"><span class="mrow" id="MathJax-Span-686"><span class="mi" id="MathJax-Span-687" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-688" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-689" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">l<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-690" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-691" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">u</span></span></span><span style="display: inline-block; width: 0px; height: 2.342em;"></span></span></span></span><span class="mo" id="MathJax-Span-692" style="font-family: STIXGeneral-Regular;">}</span></span><span style="display: inline-block; width: 0px; height: 2.537em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.281em; vertical-align: -0.442em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-43">P_{G,c,l,u} = \{   (b,t) | t\geq f_{G,c,l,u}(b), b\in F_{G,l,u}\}</script>. Where <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-44-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-693" style="width: 2.585em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.244em; height: 0px; font-size: 114%;"><span style="position: absolute; clip: rect(1.513em 1000.002em 2.683em -0.436em); top: -2.288em; left: 0.002em;"><span class="mrow" id="MathJax-Span-694"><span class="msubsup" id="MathJax-Span-695"><span style="display: inline-block; position: relative; width: 2.195em; height: 0px;"><span style="position: absolute; clip: rect(1.757em 1000.002em 2.683em -0.436em); top: -2.532em; left: 0.002em;"><span class="mi" id="MathJax-Span-696" style="font-family: STIXGeneral-Italic;">F<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.051em;"></span></span><span style="display: inline-block; width: 0px; height: 2.537em;"></span></span><span style="position: absolute; top: -2.191em; left: 0.636em;"><span class="texatom" id="MathJax-Span-697"><span class="mrow" id="MathJax-Span-698"><span class="mi" id="MathJax-Span-699" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-700" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-701" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">l<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-702" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-703" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">u</span></span></span><span style="display: inline-block; width: 0px; height: 2.342em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.293em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.169em; vertical-align: -0.331em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-44">F_{G,l,u}</script> is the polytope of feasible flows with the balance constraints and lower bound <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-45-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-704" style="width: 0.344em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.295em; height: 0px; font-size: 114%;"><span style="position: absolute; clip: rect(1.708em 1000.002em 2.683em -0.387em); top: -2.532em; left: 0.002em;"><span class="mrow" id="MathJax-Span-705"><span class="mi" id="MathJax-Span-706" style="font-family: STIXGeneral-Italic;">l<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span></span><span style="display: inline-block; width: 0px; height: 2.537em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.892em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-45">l</script>, upper bound <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-46-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-707" style="width: 0.928em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.782em; height: 0px; font-size: 114%;"><span style="position: absolute; clip: rect(1.757em 1000.002em 2.683em -0.339em); top: -2.532em; left: 0.002em;"><span class="mrow" id="MathJax-Span-708"><span class="mi" id="MathJax-Span-709" style="font-family: STIXGeneral-Italic;">U<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.051em;"></span></span></span><span style="display: inline-block; width: 0px; height: 2.537em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.892em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-46">U</script>. Note that <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-47-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-710" style="width: 2.585em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.244em; height: 0px; font-size: 114%;"><span style="position: absolute; clip: rect(1.513em 1000.002em 2.683em -0.436em); top: -2.288em; left: 0.002em;"><span class="mrow" id="MathJax-Span-711"><span class="msubsup" id="MathJax-Span-712"><span style="display: inline-block; position: relative; width: 2.195em; height: 0px;"><span style="position: absolute; clip: rect(1.757em 1000.002em 2.683em -0.436em); top: -2.532em; left: 0.002em;"><span class="mi" id="MathJax-Span-713" style="font-family: STIXGeneral-Italic;">F<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.051em;"></span></span><span style="display: inline-block; width: 0px; height: 2.537em;"></span></span><span style="position: absolute; top: -2.191em; left: 0.636em;"><span class="texatom" id="MathJax-Span-714"><span class="mrow" id="MathJax-Span-715"><span class="mi" id="MathJax-Span-716" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-717" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-718" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">l<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-719" style="font-size: 70.7%; font-family: STIXGeneral-Regular;">,</span><span class="mi" id="MathJax-Span-720" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">u</span></span></span><span style="display: inline-block; width: 0px; height: 2.342em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.293em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.169em; vertical-align: -0.331em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-47">F_{G,l,u}</script> has a description size of <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-48-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-721" style="width: 1.172em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.026em; height: 0px; font-size: 114%;"><span style="position: absolute; clip: rect(1.269em 1000.002em 2.439em -0.387em); top: -2.288em; left: 0.002em;"><span class="mrow" id="MathJax-Span-722"><span class="msubsup" id="MathJax-Span-723"><span style="display: inline-block; position: relative; width: 0.977em; height: 0px;"><span style="position: absolute; clip: rect(1.708em 1000.002em 2.683em -0.387em); top: -2.532em; left: 0.002em;"><span class="mn" id="MathJax-Span-724" style="font-family: STIXGeneral-Regular;">2</span><span style="display: inline-block; width: 0px; height: 2.537em;"></span></span><span style="position: absolute; top: -2.727em; left: 0.538em;"><span class="mi" id="MathJax-Span-725" style="font-size: 70.7%; font-family: STIXGeneral-Italic;">k<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 2.342em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.293em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.114em; vertical-align: -0.053em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-48">2^k</script>, as shown in the max flow paper.</p>
</blockquote>