<p>Attention: This is a partial answer based on conjecture and hearsay! Whereas David Eppstein's more general problem is NP-complete, maybe this one is in P.</p>

<p>Let us say that a bipartite graph $(A \cup B, E)$ with $|A|=|B|=n$ is "UPMX" if it is extendable to a graph with a unique perfect matching. Here are some necessary conditions for UPMX:</p>

<ul>
<li>it must not contain 2 perfect matchings, </li>
<li>the degree sequence of A, when sorted in increasing order, must be componentwise $\le (1, 2, ..., n)$, and likewise for B. I'll call this the "degree condition."</li>
</ul>

<p>So far, I haven't been able to find any example where a graph meets these conditions, but fails to be UPMX. In that case, maybe they are sufficient. One might prove this by the following algorithm: </p>

<ol>
<li>if the graph has >1 perfect matchings, return "not UPMX"</li>
<li>if the graph fails the degree condition, return "not UPMX"</li>
<li>if the graph has =1 perfect matching, return "UPMX"</li>
<li>otherwise, maybe we can show it is UPMX. Perhaps the following algorithm could prove it:
<ul>
<li>while the graph has $\le \tbinom{n+1}{2} - 2$ edges,</li>
<li>find some new edge e whose addition does not create a perfect matching and does not violate the degree condition; add e to the graph</li>
</ul></li>
<li>now the graph has $\tbinom{n+1}{2} - 1$ edges and no perfect matching, and satisfies the degree condition. I think it's not too hard to show it is UPMX, hence so was the original graph.</li>
</ol>

<p>You can characterize which new edges would create a perfect matching by using Hall's theorem, and it is not hard to characterize which new edges would violate the degree bound. Unfortunately, even if it's true that an edge of the right type always exists, I have not been able to prove it.</p>

CC BY-SA 2.5
2010-10-05T20:30:56.590Z
Not a bad approach, I wonder if it is true.
domotorp
CC BY-SA 2.5
2010-10-05T18:21:24.533Z
2010-10-05T18:21:24.533Z
daveagp
<p>This paper, <a href="https://hal.archives-ouvertes.fr/hal-01189621/document" rel="nofollow">Obtaining a triangular matrix by independent row-column permutations</a> Fertin, Rusu, and Vialette, shows that the problem is NP-complete for binary square matrices.</p>

CC BY-SA 3.0
2016-08-27T19:53:02.447Z
This is quite unfortunate that they've also proved the same result independently from us, I guess we should have communicated better. Anyhow, I'll email them.
domotorp
CC BY-SA 3.0
2016-08-27T22:32:30.267Z
@domotorp The same problem have been asked on MathOverflow and the best answer was that it is in "NP-limbo". http://mathoverflow.net/questions/191963/transforming-a-binary-matrix-into-triangular-form-using-permutation-matrices/248432#248432
Mohammad Al-Turkistany
CC BY-SA 3.0
2016-08-27T19:27:48.393Z
2016-08-27T19:27:48.393Z
Mohammad Al-Turkistany
<p>The problem is NP-complete but where is the algorithm to solve it ? I have one algorithm that works on many examples, but I can't demonstrate its going to work all the time.</p>

CC BY-SA 4.0
2019-01-14T18:18:47.350Z
Can you characterize an interesting class of graphs on which your algorithm is correct?
R B
CC BY-SA 4.0
2019-01-14T17:04:18.510Z
2019-01-14T17:04:18.510Z
ORILL_Code
<p>The problem turned out to be NP-complete. You can read more in detail <a href="http://www.sciencedirect.com/science/article/pii/S0020019016300552" rel="noreferrer">here</a> and <a href="https://hal.archives-ouvertes.fr/hal-01189621/document" rel="noreferrer">here</a>. Short summary:</p>

<p>The reduction is from a problem was shown to be NP-complete by Dasgupta, Jiang, Kannan, Li, and Sweedyk: given a bipartite graph G and an integer k, decide if G has an induced subgraph on 2k nodes that can be extended to be uniquely matchable. It was observed by Stéphane Vialette that this reduces to the bipartite unique matching version of this problem if we add n-k isolated nodes to both classes. </p>

CC BY-SA 2.5
2010-11-22T11:57:46.270Z
Thanks for the link to EGRES. I really enjoy the open problems especially the ones related to (perfect) matching.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-22T12:17:12.243Z
What are the other quality open problems sites (related to computational complexity)?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-22T17:49:02.670Z
@turkistany, I don't know any others, I think this is also more about operations research/graph theory.
domotorp
CC BY-SA 3.0
2010-11-22T08:37:11.790Z
2016-08-28T07:59:30.750Z
2016-08-28T07:59:30.750Z
domotorp
<p>Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix?</p>

<p>This question is motivated by this problem:
<a href="https://cstheory.stackexchange.com/questions/1346/positive-topological-ordering">Positive topological ordering</a></p>

<p>The original decision problem is at least as hard as this one, so an NP-completeness result would solve that too.</p>

<p>Edit:
Laszlo Vegh and Andras Frank called my attention to an equivalent problem asked by Gunter Rote:
<a href="http://lemon.cs.elte.hu/egres/open/Graphs_extendable_to_a_uniquely_matchable_bipartite_graph" rel="nofollow noreferrer">http://lemon.cs.elte.hu/egres/open/Graphs_extendable_to_a_uniquely_matchable_bipartite_graph</a></p>

<p>Edit:
The reduction to the original problem is as follows. Suppose that the DAG has only two levels, these will correspond to the rows and columns of the matrix. Also, we have one single node with weight +1. Everyone else in the lower level has weight -1 and on the upper level +1.</p>

CC BY-SA 2.5
2010-10-01T11:50:34.993Z
How do you reduce this to the original problem?  By the way, this problem looks interesting in itself.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-01T21:21:22.793Z
Are you looking for one permutation to apply to both the rows and columns, or two separate permutations? I'm guessing two, since with only one the problem seems equivalent to topological sort.
Warren Schudy
CC BY-SA 2.5
2010-10-01T21:28:50.720Z
Thinking of it as a bipartite graph (like in the elte link), they give the necessary condition that it has no subgraph made out of copies of K2, C4, C6, C8, etc. Another necessary condition is that the degree sequence of both parts is dominated by (1, 2, 3, ..., n) --- I think this is stronger than the other clique-based condition in the link.
daveagp
<ds.algorithms><np-hardness><matrices><open-problem><topological-sorting>
Positive topological ordering, take 3
domotorp
# Positive topological ordering, take 3

(Asked by: username_0 on 2010-10-01)

Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix?

This question is motivated by this problem:
[Positive topological ordering](https://cstheory.stackexchange.com/questions/1346/positive-topological-ordering)

The original decision problem is at least as hard as this one, so an NP-completeness result would solve that too.

Edit:
Laszlo Vegh and Andras Frank called my attention to an equivalent problem asked by Gunter Rote:
<http://lemon.cs.elte.hu/egres/open/Graphs_extendable_to_a_uniquely_matchable_bipartite_graph>

Edit:
The reduction to the original problem is as follows. Suppose that the DAG has only two levels, these will correspond to the rows and columns of the matrix. Also, we have one single node with weight +1. Everyone else in the lower level has weight -1 and on the upper level +1.

**Tags:** ds.algorithms, np-hardness, matrices, open-problem, topological-sorting
> **Comments:**
> **username_1**: How do you reduce this to the original problem?  By the way, this problem looks interesting in itself.  
> **username_2**: Are you looking for one permutation to apply to both the rows and columns, or two separate permutations? I'm guessing two, since with only one the problem seems equivalent to topological sort.  
> **username_3**: Thinking of it as a bipartite graph (like in the elte link), they give the necessary condition that it has no subgraph made out of copies of K2, C4, C6, C8, etc. Another necessary condition is that the degree sequence of both parts is dominated by (1, 2, 3, ..., n) --- I think this is stronger than the other clique-based condition in the link.  

---

## 4 answers

### Answer by username_0 on 2010-11-22. Score: 12 | Accepted answer

The problem turned out to be NP-complete. You can read more in detail [here](http://www.sciencedirect.com/science/article/pii/S0020019016300552) and [here](https://hal.archives-ouvertes.fr/hal-01189621/document). Short summary:

The reduction is from a problem was shown to be NP-complete by Dasgupta, Jiang, Kannan, Li, and Sweedyk: given a bipartite graph G and an integer k, decide if G has an induced subgraph on 2k nodes that can be extended to be uniquely matchable. It was observed by Stéphane Vialette that this reduces to the bipartite unique matching version of this problem if we add n-k isolated nodes to both classes.

> **Comments:**
> **username_4**: Thanks for the link to EGRES. I really enjoy the open problems especially the ones related to (perfect) matching.  
> **username_4**: What are the other quality open problems sites (related to computational complexity)?  
> **username_0**: @turkistany, I don't know any others, I think this is also more about operations research/graph theory.  

---

### Answer by username_3 on 2010-10-05. Score: 3

Attention: This is a partial answer based on conjecture and hearsay! Whereas David Eppstein's more general problem is NP-complete, maybe this one is in P.

Let us say that a bipartite graph $(A \cup B, E)$ with $|A|=|B|=n$ is "UPMX" if it is extendable to a graph with a unique perfect matching. Here are some necessary conditions for UPMX:

* it must not contain 2 perfect matchings,
* the degree sequence of A, when sorted in increasing order, must be componentwise $\le (1, 2, ..., n)$, and likewise for B. I'll call this the "degree condition."

So far, I haven't been able to find any example where a graph meets these conditions, but fails to be UPMX. In that case, maybe they are sufficient. One might prove this by the following algorithm:

1. if the graph has >1 perfect matchings, return "not UPMX"
2. if the graph fails the degree condition, return "not UPMX"
3. if the graph has =1 perfect matching, return "UPMX"
4. otherwise, maybe we can show it is UPMX. Perhaps the following algorithm could prove it:
   * while the graph has $\le \tbinom{n+1}{2} - 2$ edges,
   * find some new edge e whose addition does not create a perfect matching and does not violate the degree condition; add e to the graph
5. now the graph has $\tbinom{n+1}{2} - 1$ edges and no perfect matching, and satisfies the degree condition. I think it's not too hard to show it is UPMX, hence so was the original graph.

You can characterize which new edges would create a perfect matching by using Hall's theorem, and it is not hard to characterize which new edges would violate the degree bound. Unfortunately, even if it's true that an edge of the right type always exists, I have not been able to prove it.

> **Comments:**
> **username_0**: Not a bad approach, I wonder if it is true.  

---

### Answer by username_4 on 2016-08-27. Score: 3

This paper, [Obtaining a triangular matrix by independent row-column permutations](https://hal.archives-ouvertes.fr/hal-01189621/document) Fertin, Rusu, and Vialette, shows that the problem is NP-complete for binary square matrices.

> **Comments:**
> **username_0**: This is quite unfortunate that they've also proved the same result independently from us, I guess we should have communicated better. Anyhow, I'll email them.  
> **username_4**: @domotorp The same problem have been asked on MathOverflow and the best answer was that it is in "NP-limbo". http://mathoverflow.net/questions/191963/transforming-a-binary-matrix-into-triangular-form-using-permutation-matrices/248432#248432  

---

### Answer by username_5 on 2019-01-14. Score: -1

The problem is NP-complete but where is the algorithm to solve it ? I have one algorithm that works on many examples, but I can't demonstrate its going to work all the time.

> **Comments:**
> **username_6**: Can you characterize an interesting class of graphs on which your algorithm is correct?  

---

