<h1>Context</h1>
<p>I am reading <a href="https://web.eecs.umich.edu/%7Epettie/matching/Gabow-Tarjan-scaling-bipartite-matching.pdf" rel="nofollow noreferrer">Faster scaling algorithms for network problems</a> by Gabow and Tarjan where I am researching part 2: &quot;Matching and extensions&quot;. However, I am a bit confused with the algorithm at the bottom of page 6. On page 7 there a claim that throughout this algorithm the matching <span class="math-container">$M$</span> remains 1-feasible, without much further explanation. I found a counterexample but I might have missed something. If so, can someone give some pointers?</p>
<h1>Counterexample</h1>
<p>Take the following weighted bipartite graph.</p>
<pre><code>    2
A1 --- B1
  1\ /4
   / \
A2 --- B2
    2
</code></pre>
<p>The costs of the edges are integers of at least <span class="math-container">$-1$</span>, so the input is OK.</p>
<p>The algorithm starts by initializing all dual variables to <span class="math-container">$0$</span>.</p>
<h2>Iteration 1</h2>
<p>The first step of the loop of the algorithm is searching a maximal set of vertex-disjoint augmenting paths of eligible edges. There are no eligible edges so now we go to step 2.
In step 2 of the algorithm we search a forest <span class="math-container">$\mathcal{F}$</span> of eligible edges, with roots <span class="math-container">$V_0 \setminus M$</span>. The forest is <span class="math-container">$\mathcal{F} = \{(A_1), (A_2)\}$</span>. Now a dual adjustment is done with the adjustment quantity <span class="math-container">$\delta = cl(A_1, B_2) - y(A_1) - y(B_2) = 1 + 1 - 0 - 0 = 2$</span> which gives the following dual variables:</p>
<pre><code>2 A1   B1 0

2 A2   B2 0
</code></pre>
<p>Now <span class="math-container">$\mathcal{F} = \{(A_1, (B_2)), (A_2)\}$</span> and <span class="math-container">$(A_1, B_2)$</span> is a free eligible edge so we can go back to step 1</p>
<h2>Iteration 2</h2>
<p>After the first step we have <span class="math-container">$M = \{(A_1, B_2)\}$</span> and the duals are</p>
<pre><code>2 A1   B1 0

2 A2   B2 -1
</code></pre>
<p>For step 2 $\mathcal{F} = {(A_2)}$ so $\delta = cl(A_2, B_2) - y(A_2) - y(B_2) = 2$. Adjusting the duals gives</p>
<pre><code>2 A1   B1 0

4 A2   B2 -1
</code></pre>
<p>The edge <span class="math-container">$(A_2, B_2)$</span> can now be added to <span class="math-container">$\mathcal{F}$</span> so <span class="math-container">$\mathcal{F}$</span> becomes <span class="math-container">$\{(A_2, (B_2))\}$</span> but <span class="math-container">$B_2$</span> is not a free vertex, so another dual adjustment is necessary. There is only one edge to take into account for <span class="math-container">$\delta$</span>, so <span class="math-container">$\delta = 1$</span>. Now, all duals that are in <span class="math-container">$\mathcal{F}$</span> must be adjusted with <span class="math-container">$1 \cdot \delta$</span> if the vertex is in <span class="math-container">$V_0$</span> and <span class="math-container">$-1 \cdot \delta$</span> if the vertex is in <span class="math-container">$V_1$</span>.</p>
<p>The weights, matching and duals now look like this</p>
<pre><code>\\ -&gt; edge in matching
      2
2 A1 --- B1 0
   1\\ /4
     / \\
5 A2 --- B2 -2
      2
</code></pre>
<p>Now <span class="math-container">$M$</span> is not a 1-feasible matching anymore.</p>

CC BY-SA 4.0
2024-08-18T14:29:18.750Z
It may be a good idea to contact Hal Gabow. https://home.cs.colorado.edu/~hal/ He is generally quite forthcoming.
Chandra Chekuri
CC BY-SA 4.0
2024-08-21T09:32:36.980Z
@ChandraChekuri I have done that a few of days ago together with two more questions. He has pointed me to [this paper](https://ieeexplore.ieee.org/document/6375337) with follow-up work, but I still have to look at all the details
genzee
<ds.algorithms><graph-algorithms><linear-programming><matching><bipartite-graphs>
Counterexample for the 1-optimal matching algorithm in Gabow's and Tarjan's paper on scaling algorithms for networks
genzee
# Counterexample for the 1-optimal matching algorithm in Gabow's and Tarjan's paper on scaling algorithms for networks

(Asked by: username_0 on 2024-08-06)

Context
I am reading Faster scaling algorithms for network problems by Gabow and Tarjan where I am researching part 2: "Matching and extensions". However, I am a bit confused with the algorithm at the bottom of page 6. On page 7 there a claim that throughout this algorithm the matching $M$ remains 1-feasible, without much further explanation. I found a counterexample but I might have missed something. If so, can someone give some pointers?
Counterexample
Take the following weighted bipartite graph.
    2
A1 --- B1
  1\ /4
   / \
A2 --- B2
    2

The costs of the edges are integers of at least $-1$, so the input is OK.
The algorithm starts by initializing all dual variables to $0$.
Iteration 1
The first step of the loop of the algorithm is searching a maximal set of vertex-disjoint augmenting paths of eligible edges. There are no eligible edges so now we go to step 2.
In step 2 of the algorithm we search a forest $\mathcal{F}$ of eligible edges, with roots $V_0 \setminus M$. The forest is $\mathcal{F} = \{(A_1), (A_2)\}$. Now a dual adjustment is done with the adjustment quantity $\delta = cl(A_1, B_2) - y(A_1) - y(B_2) = 1 + 1 - 0 - 0 = 2$ which gives the following dual variables:
2 A1   B1 0

2 A2   B2 0

Now $\mathcal{F} = \{(A_1, (B_2)), (A_2)\}$ and $(A_1, B_2)$ is a free eligible edge so we can go back to step 1
Iteration 2
After the first step we have $M = \{(A_1, B_2)\}$ and the duals are
2 A1   B1 0

2 A2   B2 -1

For step 2 $\mathcal{F} = {(A_2)}$ so $\delta = cl(A_2, B_2) - y(A_2) - y(B_2) = 2$. Adjusting the duals gives
2 A1   B1 0

4 A2   B2 -1

The edge $(A_2, B_2)$ can now be added to $\mathcal{F}$ so $\mathcal{F}$ becomes $\{(A_2, (B_2))\}$ but $B_2$ is not a free vertex, so another dual adjustment is necessary. There is only one edge to take into account for $\delta$, so $\delta = 1$. Now, all duals that are in $\mathcal{F}$ must be adjusted with $1 \cdot \delta$ if the vertex is in $V_0$ and $-1 \cdot \delta$ if the vertex is in $V_1$.
The weights, matching and duals now look like this
\\ -> edge in matching
      2
2 A1 --- B1 0
   1\\ /4
     / \\
5 A2 --- B2 -2
      2

Now $M$ is not a 1-feasible matching anymore.

**Tags:** ds.algorithms, graph-algorithms, linear-programming, matching, bipartite-graphs

> **Comments:**
> **username_1**: It may be a good idea to contact Hal Gabow. https://home.cs.colorado.edu/~hal/ He is generally quite forthcoming.  
> **username_0**: @ChandraChekuri I have done that a few of days ago together with two more questions. He has pointed me to [this paper](https://ieeexplore.ieee.org/document/6375337) with follow-up work, but I still have to look at all the details  

---

## 0 answers

