<p>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:</p>

<p>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. </p>

CC BY-SA 3.0
2014-01-07T10:46:40.740Z
2014-01-07T10:46:40.740Z
DCTLib
<p>I have a finite graph with vertices $V$. </p>

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

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

<ol>
<li><p>$a_i \in A_i$ for all $i$. </p></li>
<li><p>For any $i$ and $j$ such that $i\ne j$ there is no edge connecting
$a_i$ and $a_j$ in the given graph</p></li>
</ol>

<p>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?</p>

CC BY-SA 3.0
2014-01-07T10:42:22.660Z
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
CC BY-SA 3.0
2014-01-08T00:30:03.447Z
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
CC BY-SA 3.0
2014-01-08T22:18:04.543Z
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
<graph-algorithms>
A combinatorial problem
Jyotirmoy Bhattacharya
# A combinatorial problem

(Asked by: username_0 on 2014-01-07)

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?

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: 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$.  
> **username_2**: 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.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2014-01-07. Score: 3 | Accepted answer

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.


---

