Coloring agents on a graph s.th. everyone has at least one friend as neighbor

Question

I've been struggling with the following problem: We have a network with n nodes, b blue, and r red agents (n=b+r). We want to distribute the agents on the network, s.th. every agent has at least one neighbor colored same as him. More specifically, we want to decide whether it is possible to do so.

The hard parts about this problem emerge when multiple leaves are attached to one node, which is attached to a part of the graph, where every node has at least degree 2. This node and its leaves have to be colored in the same color, obviously.

When considering for example the complete graph K5, and the five nodes have additional 0,1,1,5,5 leaves attached to them, this problem is equivalent with the subset sum problem for the subset {1,2,2,6,6} and sum=b. E.g. if b=12 we color the two nodes with 5 leaves blue, rest red and everyone is set. This can be done in polynomial time of the input of the graph, using the pseudo-polynomial dynamic programing for subset sum.

Now, a problem emerges if we consider the scenario above, deleting the inner connections and leaving only the circle "-2-2-6-1-6-": Now, the subset sum problem gives {6,6} as only solution, however coloring the two 5-leave-nodes blue leads to the single node having no neighbors of same color.

I approach these problems in a circle (or later any deg>1-graph) the following way, say k nodes are without any leaf nodes attached, so I run the dynamic programming for b'=b,b-1,...,b-k and see which allocations could be possible.

1st problem: Can it be that there are exponentially many solutions for the subset sum problem with integers greater/equal to two?

2nd problem: Assume there are many nodes with the same amount of leaves, e.g. the subset sum problem gives the subsets {2,2,2,2,3,3,3,3} for b=19 and b'=18 (meaning, we need one extra single node), but there are 6 2's and 8 3's. Now there are bin(6,4)*bin(8,4) different possible allocations of the "two-nodes" and "three-nodes". How to check in a fast way whether any of those can be chosen s.th. no more than one single node is "trapped" in between blue colored nodes?

It seems like in most cases, especially when there are multiple non-leaf-nodes that there are multiple ways of coloring. However I can't find a way of finding out when there's a NO-instance, without going through exponentially many cases, but I don't think that it is NP-hard either.

Any train of thought on how to approach this problem would be very welcome. Thanks in advance!

Answer 1

Can it be that there are exponentially many solutions for the subset sum problem with integers greater/equal to two?

Yes, for instance, for any $n$ you can take the $4n$ numbers $\{4n, 4n+1, \ldots, 8n - 1\}$, and try to obtain the sum $12n^2 - n$ (which is half of the value of the entire list). Then you have at least $\binom{2n}{n}$ solutions: for any $n$-element subset $A$ of $\{4n, 4n + 1, \ldots, 6n - 1\}$ (the lower half) you find the "complimentary subset" in the upper half, $$ B = \{k \in \{6n, 6n+1, \ldots, 8n-1\} \mid k - 2n \notin A\}. $$ Then the sum of the elements in $A$ and $B$ together is precisely $12n^2 - n$.

Answer 2

Solved: The proof of NP-hardness can be done via SetCover. For an instance (U,S,k): Add one node for each element in U and one for each element in S. Connect accordingly, e.g. s1-a, s1-b and s1-c. Connect |U| leaf nodes to each node s1,..,s4. Choose blue=k*(|U|+1)+|U| and red=(|S|-k)*(|U|+1). Now, all of the s-nodes have to be colored in the same color as their leaves, so they always have to be colored in groups of |U|+1. If you color any amount of the U-nodes red, the rest will have at least one agent no friends, as we found above that the rest have to be in groups of size |U|+1. Therefore all U-nodes have to be blue and as they only have s-nodes as neighbors, the problem is only solvable if we can color k of the s-nodes and their leaves blue and the remaining ones red.