Hello everybody here is a problem i have approximated but would like to hear your opinion about. Perhaps someone finds a better solution than me :)
Given a Graph G with undirected edges:
Divide it into the minimal number of sets, so that :
No two nodes in a set are connected to each other
Every node is member of at least one set
for any two distinct nodes x and y, there is a set which contains exactly one of x and y. All nodes appear in a different combination of sets. That means node x and y do not appear only in the same sets together. if you expressed the appearence of the nodes as a bit pattern, the bit pattern would differ at least in one digit.
Put another way, we want to find a 0-1 matrix with $|V|$ rows and a minimum number of columns, such that (1) each column denotes an independent set in the graph $G$, (2) every row has at least one $1$ in it, and (3) every pair of rows differs in at least one bit. Note it is trivial to give an $|V| \times |V|$ matrix of this kind for every $G$: just take the identity matrix. The problem becomes interesting when the number of columns can be made much smaller.
Example: B has no adjacent nodes, D=>A, A=>D
- A B /
/ B D
- A : 1 = 10
- B : 2 = 11
- D : 3 = 01
not a solution:
- A D B
/ D B
- A : 1 = 10
- D : 2 = 11 _ same combination of
- B : 3 = 11 / sets
D and B appear in the same combination of sets. D appears in the second and third set, as well as B.
what i need is something of a dynamic programming equation or another kind of solution that gives me an exact solution to this problem. I know that it is NP-hard, so an exponential solution is fine with me. ( i did a reduction onto Clique and Max-Sat)
An optimal solution would give me the composition of the sets, so that the number of sets is minimal, yet all nodes are part of the solution.
thanks for your help.