11
$\begingroup$

The 3-Clique Partition problem is the problem of determining whether the vertices of a graph, say $G$, can be partitioned into 3 cliques. This problem is NP-hard by a simple reduction from the 3-colorability problem. It is not hard to see that the answer to this problem is easy when $\textrm{diam}(G) = 1$ or $\textrm{diam}(G) > 5$. The problem remains NP-hard when $\textrm{diam}(G) = 2$ by a simple reduction from itself (given a graph $G$, add a vertex and connect it to all other vertices).

What is the complexity of this problem for graphs with $\textrm{diam}(G) = p$ for $3\le p \le 5$?

$\endgroup$
6
$\begingroup$

The problem seems to be in $P$.

Take two vertices $u$, $v$ with distance exactly 3 (such a pair must exist when $p\ge 3$). They must have different colors (I will use R, G, B to denote 3 colors and the vertices in the same clique are colored the same color). Wlog assume $u$ is colored Red and $v$ is colored Green.

Now the rest of the vertices are partitioned into 3 sets: $\Gamma(u)$ (neighbors of $u$), $\Gamma(v)$ and $V-\Gamma(u)-\Gamma(v)$. The third set must be colored Blue because they are adjacent to neither $u$ nor $v$. Neighbors of $u$ must be colored either Red or Blue because they are not adjacent to $v$, similarly neighbors of $v$ must be colored either Green or Blue. Each vertex now has at most two choices, therefore the problem becomes a 2-SAT instance that we can solve in polynomial time.

$\endgroup$
  • 1
    $\begingroup$ can you describe corresponding 2-SAT formulation? $\endgroup$ – user5153 Mar 3 '12 at 4:52
  • 1
    $\begingroup$ Let $B(v)$ be true if and only if we color vertex $v$ blue. Consider two vertices $u$ and $v$ not connected by an edge. Assume both of them can be blue or red. You must have the following clauses in your 2-SAT instance: $(B(v) \vee B(u))$ and $(\bar{B(v)} \vee \bar{B(u)})$. The other case that one of them can be blue or red and the other one blue or green is similar (you just need one clause). $\endgroup$ – Babak Behsaz Mar 4 '12 at 5:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.