Dynamic programming algorithm for NP-complete problem

Question

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 :

1. No two nodes in a set are connected to each other

2. Every node is member of at least one set

3. 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

solution:

1. A B /

2. / B D

   1. A : 1 = 10
   2. B : 2 = 11
   3. D : 3 = 01

not a solution:

1. A D B

2. / D B

   1. A : 1 = 10
   2. D : 2 = 11 _ same combination of
   3. 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.

Answer 1

[Edited ro reflect the intended meaning of the 3rd condition]

I believe you you describe the graph vertex coloration problem with a variation . We allow a vertex to have multiple colours :

1. No adjacent nodes should be colored with the same color.
2. Every node should have at least one color.
3. For every pair of nodes (x,y) with x /neq y , one of these nodes must be colored with a color that the other is not colored with.

I want to present two situations, due to the nature of condition 3.

a) If only 1 and 2 apply. The minimum number of sets will be found if we color each node with only one color. Every other color applied to a node not only does not help solve the problem, but it adds additional constraints. Therefore this problem can be reduced to the single-colored vertex coloring problem.

b) 1,2 and 3 apply. For starters, let's 1-colour the graph. That give us a number of sets, let it be S1. For node belonging to different colours, the 3rd condition holds. However, for nodes belonging to the same colour, it doesn't. For every set, the problem of separating the same-set nodes reduces to colouring a full node graph, which we know needs N colours. However, we need not use new colours. We can re-use the already-used colours that of course obey the condition 1.

Therefore, we can create a graph this way: Create a full graph containing all the nodes in the same set. Then, extend it with the nodes that are adjacent to the set colours. Maintain the existing colour for the added nodes (not belonging to the full graph). Also, add a node with the color of the set that is adjacent to every other node in the full graph, so that the original colour cannot be used. Then, try to colour the new graph. Repeat for every set (S1 repeats).

A sketch of the algorithm follows

Multi-colour(graph G) :

1. Color the graph with 1 color per node. Let S0 be the number of colors used.

2. For every color ( i from 1 to S0 ) :

   a. Create a full graph containing the nodes with THIS color.

   b. Add to the graph the nodes adjacent to the nodes colored with THIS color. The adjacent nodes are colored with their colored from step 1.

   c. Add a node adjacent to the nodes from step a. Color it with THIS color.

   d. Color the graph. Prefer colors that were used in step 1. if none is eligible, use a NEW color.

   e. Add every NEW color to the list of "used" colors. Let Si be the number of new colors used. (Si can be zero or positive ). S0 = S0 + Si .

3. S0 is the number of minimum sets.

Complexity: The number of sets created by step 1 is O(n), where n is the number of vertices. Therefore this problem belongs in the same complexity as the graph coloring problem.

My algorithm is a top-down approach, therefore it is not dynamic programming. I do not know if dynamic programming could be applied to this problem. Does the Principle of Optimality hold for this problem?

Answer 2

Given G = (V,E), If 3 means that when you take the union of all your sets you get V, I can not see why the following naive algorithm does not work: 1. Compute the connected components of G 2. while there is at least one non empty connected component, remove one vertex from each non empty connected component and put them in a new set.