3
$\begingroup$

First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it.

I'm trying to come up with a good algorithm for the following, and it's giving me a headache.

I have (not necessarily disjoint) sets $S_1,\ldots,S_T$, each $S_t$ contains a subset of $1,\ldots,N$ for some $N$. I want to generate all possible objects, where an object is defined as a set of $k$ tuples of length $T$, with each tuple in an object containing exactly one element from each of $S_1,\ldots,S_T$ and in each object no base element from $1,\ldots,N$ is repeated.

For example: $k = 3, T = 2, N = 6$.

$S_1 = \{1,2,4,5\}$

$S_2 = \{2,3,4,6\}$

One valid object would be $O_1 = (1,2),(4,3),(5,6)$ - all six numbers appear and each pair has one element from $S_1$ and one element from $S_2$. EDIT: I had before that $O_1 = (1,2),(3,4),(5,6)$. This was incorrect.

An invalid object would be $(1,5),(2,4),(3,6)$, since $1 \in S_1$ but $5 \notin S_2$.

The reason I'm interested in this is because these valid objects are feasible solutions for a problem I'm working on, and I'd like to enumerate all feasible solutions on small test cases to get some intuition on my problem.

One more edit: Thanks to the help of Aaron Meyerowitz, It seems to be that this problem can be thought of as the problem of finding perfect matchings in a $T$-uniform hypergraph on $N$ nodes. I'll leave it open a bit more with the hope that it's easier and not equivalent to this problem, but just learning this much about it is helpful.

$\endgroup$
3
  • $\begingroup$ It sounds a little bit like you are looking for a "system of distinct representatives," perhaps you could search on that term. But if you really want an algorithm, there are sites where that kind of question fits better. Please see the faq. $\endgroup$ Apr 17, 2011 at 23:34
  • 1
    $\begingroup$ Thanks, I'll look into system of distinct representatives. I was considering whether to ask it here. Does it fall into 'what not to ask here' because it's too localized?. Maybe a better wording of the question would have been 'does this look like it's equivalent to some [matching, flow, something] problem, and could you point me in that direction'. Where should I ask this question? Are you referring to one of the homework help sites? I considered stackoverflow, but I decided against it since I wasn't talking about programming it in any specific language. $\endgroup$
    – user14473
    Apr 18, 2011 at 2:44
  • $\begingroup$ No one has voted to close, so it doesn't look like there's any problem with posting here. I just thought a programming website might be a better fit, depending on just exactly what you were interested in. $\endgroup$ Apr 18, 2011 at 5:51

1 Answer 1

2
$\begingroup$

Here is a possible title matchings in hypergraphs This is just a restatement but it might help with finding references. For $T=2$ one has the usual graphs and there are good algorithms for finding maximum size matchings. For larger $T$ finding matchings is (in general) NP-complete even for $T=3$. It may be that there are special features of your problem that bring things into reach.

For $T=2$ make a simple undirected graph with vertices $1,\cdots,N$ and edges all pairs $(i,j)$ which are allowed ($i \in S_1 \text{ and } j \in S_2$ or vice versa). A matching is a set of vertex disjoint edges (also called an independent edge set). If $KT=N$ then you are asking for a perfect matching.

If $T>2$ one can consider a hypergraph whose hyper-edges are all legal $T$-tuples and look for a matching.

Of course it is more compact to list your sets $S_i$ than to list every possible $T$-tuple. Your example above is the complete graph $K_6$ missing only the edges $(1,5)$ and $(3,6).$ The full graph $K_6$ has $15$ perfect matchings, $3$ using each edge. Of these, $10$ work for your problem.

Here is a slightly more promising idea: Make a bipartite graph with $N+T$ vertices labelled $1,\cdots,N$ on one side and $S_1,\cdots,S_T$ on the other. Draw an edge for $j$ to $S_t$ when $j \in S_t$. Then a maximum size matching of this graph would have at best $T$ edges. So you could look for $k$ disjoint $T$-matchings. This has the added structure that each tuple is essentially ordered.


Later thoughts: You've changed the problem to clarify that the tuples are ordered.

An answer might depend on $k$ and $T$. For $T=2$ you could use the first idea of matchings with unordered pairs in a possibly non-bipartite graph. For each solution find out how many of the pairs have both members in $S_1 \cap S_2$. If the number is $j$ then this gives $2^j$ ordered solutions.

If $T$ is large Then you might look to choose $k$ elements from each set so as to get $kT$ elements. Each such choice would describe $(k!)^{T-1}$ solutions. So now your example has 12 solutions because for the two solutions (24)(13)(56) and (24)(16)(53) can each replace (24) with (42). This number is also $\mathbf{2}*3!$ since from $S_1$ you must choose $1,5$ and from $S_2$ $3,6$. This leaves $\mathbf{2}$ choices for $2,4$.

$\endgroup$
1
  • $\begingroup$ Great edit. I was about to post essentially the same idea. To connect it to the comment by Gerry Myerson, each $T$-matching is a system of distinct representatives of $S_1,\ldots,S_T$, so I'm looking for $k$ disjoint SDRs. I'm not sure that this is any easier than finding matchings in the hypergraphs, but it seems to be non-trivial to build the hypergraph for $T > 2$ - each maximum matching of the bipartite graph is a hyperedge of the hypergraph you described. $\endgroup$
    – user14473
    Apr 18, 2011 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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