1
$\begingroup$

Let the following data be given.

  • Two positive integers $m$ and $n$.
  • A family of sets $B_a \subseteq \{1, \dots, n\}$ (for $a \in \{1, \dots, m\}$).

The task is to count the number $N$ of injective functions $$f \colon \{1, \dots, m\} \to \{1, \dots, n\}$$ such that $f(a) \in B_a$ for each $a \in \{1, \dots, m\}$.

I'm pretty much sure this must be a well known problem in combinatorial enumeration.

For example, the numbers $1,\dots,n$ represent $n$ employees, the numbers $1,\dots,m$ represent $m$ tasks, the set $B_a$ represent the tasks that employee $a$ can perform, and $f$ is an assignment of the tasks (assuming that no more than one employee can work on a task, and it is fine is some tasks are unassigned). Then $N$ is the number of possible task assignments.

Also, the question is similar to that of determining rooks polynomials, but somehow weaker, because all the board must be filled.

Also also, I suspect the problem to be "hard". Something like the "analog" of NP-complete for counting problems (I'm not familiar with complexity classes of counting problems, sorry).

My question is: Where can I find a reference to this problem and to the state-of-the-art algorithms to solve it?

I'm aware of a simple recursive algorithm to compute $N$ (simply loop over the possible $f(1)$, then recursively over the possible $f(2)$, ... keeping tracks of the used values) that has complexity about $N$.

Thanks!

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ The analogue of NP-completeness for counting problems is #P-complete. $\endgroup$ Commented Aug 9 at 10:16
  • 1
    $\begingroup$ Have you mixed up $n$ and $m$ in the beginning? You have $f(a)$, where $a$ is from $\{1,\ldots,m\}$, but the domain of $f$ is said to be $\{1,\ldots,n\}$. If $n<m$, this doesn't make sense. $\endgroup$ Commented Aug 9 at 11:36
  • $\begingroup$ @JoelDavidHamkins fixed. thx. $\endgroup$ Commented Aug 9 at 14:11

2 Answers 2

Reset to default
5
$\begingroup$

This is the problem of counting perfect matchings, and is indeed #P-complete, even in the case $n=m$. This result is known as Valiant's theorem.

As such, it is essentially hopeless to compute it in large cases, but if it is helpful to you it can be approximated efficiently (see Computing the Permenant on Wikipedia). Additionally, it can be computed in polynomial time if the relevant graph is planar via the FKT algorithm.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ In practice a careful implementation of Ryser's method can get up to about order 35 or so. $\endgroup$ Commented Aug 9 at 11:44
  • $\begingroup$ I do not see exactly how each $f$ corresponds to a perfect matching of some graph. Can you please be more explicit? $\endgroup$ Commented Aug 9 at 14:17
  • $\begingroup$ You define a bipartite graph with $1,2,...,m$ in one side and $1,2,3,...,n$ on the other, and connect vertex $i$ on the first side to all vertices in $B_i$ $\endgroup$ Commented Aug 9 at 15:36
  • $\begingroup$ @DanielWeber alright. So the problem I posted is equivalent to computing the number of perfect matching of a bipartite graph, which is equivalent to computing the permanent, which in turn is P#-complete $\endgroup$ Commented Aug 9 at 16:27
0
$\begingroup$

Inclusion-exclusion gives the following formula: $$N = \sum_{\pi \in S([m])} (-1)^{m-|\pi|} \prod_{T\in\pi} (|T|-1)! |{\cal B}_T|,$$ where $S([m])$ is the set of set partitions of $[m]:=\{1,2,\dots,m\}$ and ${\cal B}_T:=\bigcap_{t\in T} B_t$.

In practice, when we go over set partitions, we can try to avoid $\pi$ such that ${\cal B}_T=\emptyset$ for some part $T\in\pi$. Hence, it may be beneficial to employ a depth-first-search with pruning on the poset of set partitions to avoid visiting such $\pi$.

Another application inclusion-exclusion gives the following formula: $$N = \sum_{T\subseteq [n]\atop |T|\leq m} (-1)^{m-|T|} \binom{n-|T|}{m-|T|}\prod_{a=1}^n |B_a\cap T|.$$ The number of terms in this formula is at most $2^n$ terms, and for $m \ll n$ can be bounded by $\binom{n+m}{m}$.

Here we can also use DFS with pruning to visit only those $T$ that make nonzero contribution.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.