2
$\begingroup$

Given an undirected Graph $G=(V,E)$, a set of colors $C$ and a score function $s:V\times C \rightarrow \mathbb{R}$ that assigns each pair of color and vertex a score, find the graph coloring $c:V\rightarrow C$ (so that adjacent vertices have different colors, $\forall \{u,v\}\in E : c(u)\neq c(v)$) that minimizes (or maximizes) $\sum_{v\in V} s(v,c(v))$.

I found the terms "Weighted Graph coloring"/"Cost Vertex Coloring"/"Minimum Sum Coloring Problem" (where the score is just a function of the color but not the vertex) and "Graph Coloring at minimum cost" (where the cost is the sum of the differences in colors between adjacent vertices).

I am aware that this problem is equivalent to the bipartite graph matching problem (Hungarian Algorithm, by treating colors as one partition of the graph and vertices as the second partition) for complete graphs. I also know that this problem is NP-hard for arbitrary graphs and solvable in polynomial time for chordal graphs (similar to standard graph coloring). I just want to know whether there is any literature on this problem.

$\endgroup$
3
  • $\begingroup$ This is not equivalent to bipartite matching, for which there are polynomial algorithms. In your proposed transformation, you have ignored the requirement that adjacent original vertices must have different colors. $\endgroup$
    – RobPratt
    Commented Dec 3, 2022 at 1:24
  • 1
    $\begingroup$ I think I wasn't clear enough: If $G$ is complete, you need (at least) $|V|$ colors to color it and can use every color at most once. You can construct a bipartite Graph $G'$, where one Partition is $V$ and the other one is $C$. The edges between the two partitions are annotated with $s$. A perfect matching on $G'$ is then equivalent to a coloring of $G$. And the coloring I look for is the matching produced by the Hungarian algorithm in $O(n^3)$. $\endgroup$
    – thequilo
    Commented Dec 5, 2022 at 14:51
  • $\begingroup$ Using each color at most once is much stronger than a proper coloring in the original graph, for which only adjacent vertices must have different colors. Your transformation forces all vertex pairs (adjacent or not) to have different colors. $\endgroup$
    – RobPratt
    Commented Dec 5, 2022 at 15:16

1 Answer 1

1
$\begingroup$

This problem appears in the book on Parameterized Algorithms by Cygan et al. [1], namely in Thm. 10.18.

The naive solution is an $O(3^n)$-time algorithm by resorting to subset convolution in the $(\min, +)$-semi-ring. In that section, they show an $O^*(2^n M)$-time algorithm, provided that the cost function takes values in $\{-M, \ldots, M\}$.

Apart from that, I'm not aware of any other reference on that. I'm interested in more references myself.

Update: There is now an exponential-time $(1+\varepsilon)$-approximation algorithm that runs in time $O^*(2^{n} \log M / \varepsilon)$ or, alternatively, $O^*(2^{3n/2} / \sqrt{\varepsilon})$; the latter running time is independent of $M$ [2].

References:

[1] https://link.springer.com/book/10.1007/978-3-319-21275-3

[2] https://arxiv.org/abs/2404.11364

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .