Positive topological ordering, take 3

Question

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

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.

Answer 1

The problem turned out to be NP-complete. You can read more in detail here and here. 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.

Answer 2

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.

Answer 3

This paper, Obtaining a triangular matrix by independent row-column permutations Fertin, Rusu, and Vialette, shows that the problem is NP-complete for binary square matrices.

Answer 4

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.