<p>[Edited ro reflect the intended meaning of the 3rd condition]</p>

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

<ol>
<li>No adjacent nodes should be colored with the same color.</li>
<li>Every node should have at least one color.</li>
<li>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.</li>
</ol>

<p>I want to present two situations, due to the nature of condition 3.</p>

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

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

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

<p>A sketch of the algorithm follows</p>

<p>Multi-colour(graph G) :</p>

<ol>
<li><p>Color the graph with 1 color per node. Let S0 be the number of colors used.</p></li>
<li><p>For every color ( i from 1 to S0 ) : </p>

<p>a. Create a full graph containing the nodes with THIS color.</p>

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

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

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

<p>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 . </p></li>
<li><p>S0 is the number of minimum sets.</p></li>
</ol>

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

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

CC BY-SA 2.5
2010-09-06T16:31:24.243Z
I interpreted the explanation of the condition 3 by the questioner (in the comments to the question) differently: if there is a set containing x and not containing y exists, a set containing y and not x is not required.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-08T08:35:37.500Z
Tsuyoshi Ito's interpretation of condition 3 is what i meant, and i updated it in the question also.
tarrasch
CC BY-SA 2.5
2010-09-06T16:21:38.567Z
2010-09-09T01:18:59.047Z
2010-09-09T01:18:59.047Z
chazisop
<p>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 :)</p>

<p>Given a Graph G with undirected edges: </p>

<p>Divide it into the minimal number of sets, so that :</p>

<ol>
<li><p>No two nodes in a set are connected to each other</p></li>
<li><p>Every node is member of at least one set</p></li>
<li><p>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. </p></li>
</ol>

<p>Put another way, we want to find a 0-1 matrix with $|V|$ rows and a <em>minimum</em> 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.</p>

<p>Example: B has no adjacent nodes, D=>A, A=>D</p>

<p>solution:</p>

<ol>
<li>A B /</li>
<li><p>/ B D</p>

<ol>
<li>A : 1 = 10</li>
<li>B : 2 = 11</li>
<li>D : 3 = 01</li>
</ol></li>
</ol>

<p>not a solution: </p>

<ol>
<li>A D B</li>
<li><p>/ D B</p>

<ol>
<li>A : 1 = 10</li>
<li>D : 2 = 11  _ same combination of </li>
<li>B : 3 = 11  / sets</li>
</ol></li>
</ol>

<p>D and B appear in the same combination of sets. D appears in the second and third set, as well as B. </p>

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

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

<p>thanks for your help.</p>

CC BY-SA 2.5
2010-09-06T12:50:17.933Z
What are you trying to optimize? Do you want to minimize the number of sets?
Matthias
CC BY-SA 2.5
2010-09-06T12:52:36.980Z
1. I cannot understand what the condition 3 means.  2. NP and NP-complete are different notions.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-06T12:57:17.163Z
added example to help with understanding.
tarrasch
CC BY-SA 2.5
2010-09-06T12:59:34.070Z
I read revision 2, but I still cannot understand what the condition 3 means.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-06T13:10:36.950Z
What is a "combination of sets"?
Aaron Sterling
CC BY-SA 2.5
2010-09-06T13:18:28.443Z
I read revision 3.  Now I understand the condition 3 as follows: for any two distinct nodes x and y, there is a set which contains exactly one of x and y.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-06T13:38:26.077Z
@aeron sterling The combination of sets would be the complete solution, all sets combined. @ Tsuyoshi Ito you are correct. exactly one of the two nodes. @mashca the number of sets is to be minimised. There are at least log(n) sets and at max n sets
tarrasch
CC BY-SA 2.5
2010-09-06T13:48:30.183Z
May I suggest to write the objective function (“minimize the number of sets”) near the beginning so that people can easily find it?  Also, I believe that the current wording of the condition 3 is hard to understand.  I already made a suggestion on how to rephrase it.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-06T13:55:03.390Z
Also, although I understand the problem now, the question is still unclear.  If you can use exponential time, two easy ways to find the exact solution is generate-and-test and backtracking.  Are you looking for a slightly more practical algorithm than these?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-06T14:11:22.510Z
i am looking for an algorithm that finds a solution in an elegant way. My solution depends on a statistical approximation that generates a solution and tests if it found a better one that was already found. Can you suggest a method to build a solution? Mine just adds nodes into a combination if it fits. Thus it depends on the sequence of the input nodes and that generates a solution, but uses a lot of time - maybe too much. i am just looking for something better.
tarrasch
CC BY-SA 2.5
2010-09-06T15:47:29.617Z
The title 'Dynamic algorithm' is very misleading, because it implies that you're inserting and deleting objects. Further, your comment about reduction "onto" clique does not imply NP-hardness.
Suresh Venkat
CC BY-SA 2.5
2010-09-06T17:17:38.230Z
The title should be changed to "Dynamic programming algorithm ...", as a dynamic algorithm is something else. There seems to be a lot of confusion about condition 3. Here is how I understand this condition. For any vertex x, let Sets(x) denote the set of sets containing x. Then, condition 3 means that for every two distinct vertices x and y, Sets(x) is not equal to Sets(y).
Serge Gaspers
CC BY-SA 2.5
2010-09-08T08:34:49.047Z
the title is dynamic algorithm was chosen, because i was actually looking for a dynamic algorithm, as i was not able to formulate the problem as a problem to be splitted. If anyone can show me how to split this problem into several smaller problems that would be helpful.
tarrasch
CC BY-SA 2.5
2010-09-09T01:51:32.610Z
@tarrasch, I have edited your question to include an alternative description of the problem, based on what I think you are saying. If it is not correct, please change it. If no one can figure out what you are asking, we will unfortunately have to close this question.
Ryan Williams
CC BY-SA 2.5
2010-09-09T20:23:35.410Z
@tarrasch: I find your question interesting, and I do not currently know an answer. The title is very vague though and does not reflect what you are actually asking (please check http://en.wikipedia.org/wiki/Dynamic_problem_%28algorithms%29 for the definition of 'dynamic algorithm' and http://en.wikipedia.org/wiki/Dynamic_programming for the definition of 'dynamic programming algorithm' and decide what kind of algorithm you are asking for). I assume you are asking for a dynamic programming algorithm. Would you also be interested in exact exponential-time algorithms relying on other techniques?
Serge Gaspers
CC BY-SA 2.5
2010-10-07T07:42:58.560Z
if there is another way to do this, of course. i already wrote an approximation for this that just adds nodes into a bin and adds a new bin if its not possible to insert it into the bins so far. i do it a lot of times with permuted nodes and just return the best solution so far.
tarrasch
CC BY-SA 2.5
2010-10-09T17:44:14.513Z
I edited the title from “dynamic algorithm” to “dynamic programming algorithm” because, in spite of what the asker stated in a comment, it does not seem that the question has anything to do with dynamic algorithms (algorithms for an object which is updated gradually).
Tsuyoshi Ito
<ds.algorithms><set-cover><exp-time-algorithms>
Dynamic programming algorithm for NP-complete problem
tarrasch
# Dynamic programming algorithm for NP-complete problem

(Asked by: username_0 on 2010-09-06)

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.

**Tags:** ds.algorithms, set-cover, exp-time-algorithms
> **Comments:**
> **username_1**: What are you trying to optimize? Do you want to minimize the number of sets?  
> **username_2**: 1. I cannot understand what the condition 3 means.  2. NP and NP-complete are different notions.  
> **username_0**: added example to help with understanding.  
> **username_2**: I read revision 2, but I still cannot understand what the condition 3 means.  
> **username_3**: What is a "combination of sets"?  
> **username_2**: I read revision 3.  Now I understand the condition 3 as follows: for any two distinct nodes x and y, there is a set which contains exactly one of x and y.  
> **username_0**: @aeron sterling The combination of sets would be the complete solution, all sets combined. @ Tsuyoshi Ito you are correct. exactly one of the two nodes. @mashca the number of sets is to be minimised. There are at least log(n) sets and at max n sets  
> **username_2**: May I suggest to write the objective function (“minimize the number of sets”) near the beginning so that people can easily find it?  Also, I believe that the current wording of the condition 3 is hard to understand.  I already made a suggestion on how to rephrase it.  
> **username_2**: Also, although I understand the problem now, the question is still unclear.  If you can use exponential time, two easy ways to find the exact solution is generate-and-test and backtracking.  Are you looking for a slightly more practical algorithm than these?  
> **username_0**: i am looking for an algorithm that finds a solution in an elegant way. My solution depends on a statistical approximation that generates a solution and tests if it found a better one that was already found. Can you suggest a method to build a solution? Mine just adds nodes into a combination if it fits. Thus it depends on the sequence of the input nodes and that generates a solution, but uses a lot of time - maybe too much. i am just looking for something better.  
> **username_4**: The title 'Dynamic algorithm' is very misleading, because it implies that you're inserting and deleting objects. Further, your comment about reduction "onto" clique does not imply NP-hardness.  
> **username_5**: The title should be changed to "Dynamic programming algorithm ...", as a dynamic algorithm is something else. There seems to be a lot of confusion about condition 3. Here is how I understand this condition. For any vertex x, let Sets(x) denote the set of sets containing x. Then, condition 3 means that for every two distinct vertices x and y, Sets(x) is not equal to Sets(y).  
> **username_0**: the title is dynamic algorithm was chosen, because i was actually looking for a dynamic algorithm, as i was not able to formulate the problem as a problem to be splitted. If anyone can show me how to split this problem into several smaller problems that would be helpful.  
> **username_6**: @tarrasch, I have edited your question to include an alternative description of the problem, based on what I think you are saying. If it is not correct, please change it. If no one can figure out what you are asking, we will unfortunately have to close this question.  
> **username_5**: @tarrasch: I find your question interesting, and I do not currently know an answer. The title is very vague though and does not reflect what you are actually asking (please check http://en.wikipedia.org/wiki/Dynamic_problem_%28algorithms%29 for the definition of 'dynamic algorithm' and http://en.wikipedia.org/wiki/Dynamic_programming for the definition of 'dynamic programming algorithm' and decide what kind of algorithm you are asking for). I assume you are asking for a dynamic programming algorithm. Would you also be interested in exact exponential-time algorithms relying on other techniques?  
> **username_0**: if there is another way to do this, of course. i already wrote an approximation for this that just adds nodes into a bin and adds a new bin if its not possible to insert it into the bins so far. i do it a lot of times with permuted nodes and just return the best solution so far.  
> **username_2**: I edited the title from “dynamic algorithm” to “dynamic programming algorithm” because, in spite of what the asker stated in a comment, it does not seem that the question has anything to do with dynamic algorithms (algorithms for an object which is updated gradually).  

---

## 1 answers

### Answer by username_7 on 2010-09-06. Score: 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?

> **Comments:**
> **username_2**: I interpreted the explanation of the condition 3 by the questioner (in the comments to the question) differently: if there is a set containing x and not containing y exists, a set containing y and not x is not required.  
> **username_0**: Tsuyoshi Ito's interpretation of condition 3 is what i meant, and i updated it in the question also.  

---

