# A combinatorial problem

I have a finite graph with vertices $V$.

The sets $A_i, i=1,\ldots,N$ are non-empty disjoint subsets of $V$.

I want to find out if there is some way of selecting $a_i, i=1,\ldots,N$ such that

1. $a_i \in A_i$ for all $i$.

2. For any $i$ and $j$ such that $i\ne j$ there is no edge connecting $a_i$ and $a_j$ in the given graph

I know that I can set this up as a boolean satisfiability problem. But I was wondering if there is anything in the structure of this particular problem which will allow for a more efficient approach?

• This is just the $N$-partite Independent Set Problem. The problem is NP-complete even when each $A_i$ is of constant size independent of the size of $V$. – Igor Shinkar Jan 7 '14 at 10:42
• It seems interesting when the structure among A_i is special. For example, the problem can be easily solved if it is a multi-stage graph. – Bangye Jan 8 '14 at 0:30
• You might find it useful to search for information on independent transversals. If you can restrict the problem at all, it might help. As is, the problem is NP hard, as others have noted. – Andrew D. King Jan 8 '14 at 22:18

For every clause, instantiate three vertices (one for every literal), which form one of your sets A_i. Chosing a vertex means that your 3SAT-solution should satisfy the clause by satisfying the respective literal. Then, add an edge between a node $x$ and $\neg x$ between of any clause for all variables $x$ in order to enforce that solutions are consistent. A solution to your problem for this graph then almost represents a 3SAT solution. I am writing "almost" as some variables may not occur in a chosen literal. These can have any value, however.