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$a_i \in A_i$ for all $i$. For any $i$ and $j$ such that $i\ne j$ there is no edge connecting$a_i$ and $a_j$ in the given graphI 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?
A combinatorial problem
graph algorithms
No, you can't do much better than encoding your problem as a satisfiability problem, as it is NP-complete. Here is an example reduction to 3SAT to your problem: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. 