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 otherEvery node is member of at least one setfor 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=>Dsolution:A B // B DA : 1 = 10B : 2 = 11D : 3 = 01not a solution: A D B/ D BA : 1 = 10D : 2 = 11  _ same combination of B : 3 = 11  / setsD 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.
Dynamic programming algorithm for NP-complete problem
ds.algorithms;set cover;exp time algorithms