6

Let $G$ be a graph with a set of nodes $V$ and a set of edges $E$. Let $G'$ be a graph with the same set of nodes $V$ but a second set of edges $E'$.

For a set of nodes $X\subset V$, we denote $f(X)$ as the number of cliques (using the edges $E'$) when partitioning $X$ in cliques. More precisely, this partition is computed by recursively finding the biggest clique. So, if $X_1$ is the biggest clique in $X$ and $X_2$ is the biggest clique in $X\setminus X_1$ and so on, we have $X=X_1\cup X_2\cup\cdots\cup X_k$ and $f(X) = k$.

Now, I want to color $G$ (using the set of edges $E$ and not $E'$) with the minimal number of colors such that, writing this partitioning of colors as $V = V_1 \cup\cdots\cup V_m$ we minimize $f(V_1) + \cdots+f(V_m)$.

I'm stuck on this problem, any hint is precious :)

Right now, I have tried to colorize the graph node by node (with the DSATUR heuristic) and when there are different possible colors, I compute $f$ for each choice and choose the one that minimizes $f$. But it's way too slow.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Jin Kazama
  • 93
  • 4
  • I am curious, is there a practical application behind this problem ? Where does it come from ? – Kuifje Jun 26 '22 at 10:32
  • 1
    Also, if my understanding is correct, you are dealing with 2 objectives simultaneously : the number of color of classes with respect to $(V,E)$, and the total number of cliques with respect to $E'$ in each color class. How do you weigh each of these objectives ? And does it make sense to do that ? – Kuifje Jun 26 '22 at 10:38
  • 2
    If there are ties for the biggest clique, the value of $f$ can depend on which one you choose. For example, a path on four nodes can yield $f=2$ or $f=3$. – RobPratt Jun 26 '22 at 12:43
  • About the 2 objectives, I want the minimal number of colors and, for this number, I want the minimal number of cliques – Jin Kazama Jun 27 '22 at 12:10

0 Answers0