How hard is this graph problem?

Question

Hi guys,

I have a problem to solve for a social-networks application, and it sounds hard: I'm not sure if its NP-complete or not. It smells like it might be NP-complete, but I don't have a good sense for these things. In any case, an algorithm would be much better news for me.

Anyhow, the input is some graph, and what I want to do is partition the nodes into two sets so that neither set contains a triangle. If it helps, I know this particular graph is 3-colorable, though I don't actually know a coloring.

Heuristically, a "greedy" algorithm seems to converge quickly: I just look for triangles in either side of the partition, and break them when I find them.

Answer 1

MY ANSWER IS WRONG

I'll keep it up for discussion. Please don't down vote, the idea might still be helpful.

---

I'm going to argue that it's NP-hard based on the claim that coloring a 3-colorable graph with 4 colors is NP-hard (On the hardness of 4-coloring a 3-collorable graph).

We give a new proof showing that it is NP-hard to color a 3-colorable graph using just four colors. This result is already known, but our proof is novel as [...]

Suppose we can partition a 3-colorable graph into 2 sets A, B, such that neither has a triangle, in polynomial time. Then we can solve the 4-coloring as follows:

• color set A with C1,C2 and set B with C3,C4.
• each set is 2-colorable since it has no triangle <- THIS IS WHERE I GOT IT WRONG
• 2-coloring a 2-colorable graph is polynomial
• we have then 4-colored a 3-colorable graph in polynomial time

Through this reduction, I claim that what you are doing must be NP-hard.

Answer 2

This is not possible for any set with 5 tightly interconnected nodes, and I can prove it with a simple thought experiment. 5 tightly interconnected nodes is very common in social networks; a cursory glance at my facebook profile found with among my family members and one among a group of coworkers.

By 'tightly interconnected graph', I mean a set of nodes where the nodes have a connection to every other node. 5 nodes like this would look like a star within a pentagon.

Lets start with a set of 5 cousins named Anthony, Beatrice, Christopher, Daniel, and Elisabeth. As cousins, they are all connected to each other.

1) Lets put Anthony in Collection #1. 2) Lets put Beatrice in Collection #1. 3) Along comes Christopher through our algorithm... we can't put him in collection #1, since that would form a triangle. We put him in Collection #2. 4) Along comes Daniel. We can't put him in collection #1, because that would form a triangle, so we put him in Collection #2. 5) Along comes Elisabeth. We can't put her in Collection #1, because that would form a triangle with Anthony and Beatrice. We can't put her in Collection #2, because that would for a triangle with Christopher and Daniel.

Even if we varied the algorithm to put Beatruce in Collection #2, the thought experiment concludes with a similar problem. Reordering the people causes the same problem. No matter how you pace them, the 5th person cannot go anywhere - this is a variation of the 'pidgenhole principle'.

Even if you loosened the requirement to ask "what is the smallest number of graphs I can partition a graph into so that there are no triangles, I think this would turn into a variation of the Travelling Salesman problem, with no definitive solution.

Answer 3

This problem might be helpful: http://en.wikipedia.org/wiki/Monochromatic_triangle. I haven't yet tried to reduce it to your problem, but it might be promising.

And to play devil's advocate, if your graph has max degree <=3 (which I am not saying is true) then there is a polynomial time algorithm (which you yourself gave).

That the algorithm works for this case can be proven by considering the number of edges in the cut formed by the current partition. It always increases, hence terminates in polynomial number of steps.

Here is another idea: If we assume that every 3-colorable graph has a vertex of degree <= 3 (which is not true in general, but might as well be true in your case: of subgraphs of your sparse graph) then such a triangle free partition is always possible, and a proof of that using induction also gives a polynomial time algorithm.

If it is true (that a triangle free partition exists) for every n-vertex 3-colorable graph, then consider a 3-colorable n+1 vertex graph.

Pick a minimum degree vertex v. Now partition the rest of graph by our induction hypothesis.

Now we add v to the partition with the least neighbours. This partition is now a triangle free partition of our graph with n+1 vertices.

This induction also gives an algorithm, which can naively be done in O(n^2logn) time I believe.

Of course we are assuming the existence of a degree <= 3 vertex at each step. Not sure how true that is for the graph you have. In any case, perhaps you can just run this and when you get stuck you could try a different heuristic (like triangle breaking you already have).

Answer 4

This problem has an O(n^5) algorithm I think, where n is the number of vertices.

Answer 5

Here's an idea that might work. I doubt this is the ideal algorithm, so other people, please build off of this.

Go through your graph and find all the triangles first. I know it seems ridiculous, but it wouldn't be too bad complexity-class wise, I think. You can find any triangles a given node is part of just by following all its edges three hops and seeing if you get to where you started. (I suspect there's a way to get all of the triangles in a graph that's faster than just finding the triangles for each node.)

Once you have the triangles, you should be able to split them any way you please. By definition, once you split them up, there are no more triangles left, so I don't think you have to worry about connections between the triangles or adjacent triangles or anything horrible like that.