0
$\begingroup$

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?

$\endgroup$
3
  • 3
    $\begingroup$ 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$. $\endgroup$ – Igor Shinkar Jan 7 '14 at 10:42
  • $\begingroup$ 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. $\endgroup$ – Bangye Jan 8 '14 at 0:30
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrew D. King Jan 8 '14 at 22:18
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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