2
$\begingroup$

I. Given biadjacency matrix $A$ of a bipartite graph on $2n$ vertices having $n$ vertices of either color on the constraints the graph either has

  1. $0$ perfect matchings
  2. $1$ perfect matchings

is it true to have $1$ perfect matchings the biadjacency matrix has to be lower triangular under some permutation of rows and columns?

II. Is it true if there are no two permutations $P$ and $Q$ so that $PAQ$ is lower triangular then the number of perfect matchings is $0$ if the input graph has $0/1$ perfect matchings?

III. Are there other neccessary and sufficient conditions to guarantee $1$ perfect matching in a $0/1$ perfect matching bipartite graph?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

The answer to Question I is yes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees. This characterizes the bipartite graphs with exactly one perfect matching.

Regarding your other questions, the graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $2^n$ candidates, a set that fails Hall's Condition can be found in polynomial time.

One way to decide if the number of perfect matchings of a general bipartite graph is exactly zero or one is as follows. Compute a maximum matching (this can be done in polynomial time). If the maximum matching is not a perfect matching, then the graph has zero perfect matchings. If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The second question has constraints of $0/1$ mateching. I think I. is similar to II. in the constrained $0/1$ matching problem. $\endgroup$
    – User2021
    Commented Jun 12, 2021 at 13:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .