20
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do you reduce this to the original problem? By the way, this problem looks interesting in itself. $\endgroup$ – Tsuyoshi Ito Oct 1 '10 at 11:50
  • $\begingroup$ 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. $\endgroup$ – Warren Schudy Oct 1 '10 at 21:21
  • $\begingroup$ 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. $\endgroup$ – daveagp Oct 1 '10 at 21:28
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the link to EGRES. I really enjoy the open problems especially the ones related to (perfect) matching. $\endgroup$ – Mohammad Al-Turkistany Nov 22 '10 at 11:57
  • $\begingroup$ What are the other quality open problems sites (related to computational complexity)? $\endgroup$ – Mohammad Al-Turkistany Nov 22 '10 at 12:17
  • $\begingroup$ @turkistany, I don't know any others, I think this is also more about operations research/graph theory. $\endgroup$ – domotorp Nov 22 '10 at 17:49
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Not a bad approach, I wonder if it is true. $\endgroup$ – domotorp Oct 5 '10 at 20:30
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – domotorp Aug 27 '16 at 19:53
  • $\begingroup$ @domotorp The same problem have been asked on MathOverflow and the best answer was that it is in "NP-limbo". mathoverflow.net/questions/191963/… $\endgroup$ – Mohammad Al-Turkistany Aug 27 '16 at 22:32
-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Can you characterize an interesting class of graphs on which your algorithm is correct? $\endgroup$ – R B Jan 14 at 18:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.