3
$\begingroup$

I would like a name for the following problem. We consider a relaxed vertex coloring problem, where

  • Let $k$ be the number of colors

  • Let $B$ be the set of edges violating coloring, i.e., $$B := \{(u,v) \in E \mid c(u) = c(v)\}$$

  • Then the objective is something like $k + \beta |B| \to \min$ over all colorings (for some $\beta$).

Does this problem have a name?

Somehow, I can't find anything. "Approximate graph coloring" and similar queries talk about approximations for graph coloring. Maybe there is another objective of form $k^\alpha + \beta |B|^\gamma$ (and maybe coefficients may depend on $|V|$)?

I am particularly interested in the hardness of such problems (the harder the better). E.g., hardness for coloring is pretty crazy. I am also particularly interested in a weighted version of this problem, e.g., $k + \beta \sum_{e \in B} w_e \to \min$.

Improve this question
$\endgroup$
6
  • $\begingroup$ Dmitry, are you acquainted with (physical) frustration? $\endgroup$
    – Rodrigo de Azevedo
    Nov 17, 2021 at 10:37
  • $\begingroup$ @RodrigodeAzevedo, I'm not familiar (I'm also almost zero in physics). I took a brief look at the article, didn't really understand it. Did I understand correctly that they only consider k=2? I need arbitrary $k$. $\endgroup$
    – Dmitry
    Nov 17, 2021 at 10:52
  • $\begingroup$ @RodrigodeAzevedo, the closest problem I can think of is Correlation clustering, but there is no dependence on $k$ in the objective function. $\endgroup$
    – Dmitry
    Nov 17, 2021 at 10:53
  • 1
    $\begingroup$ @Dmitry Also, for an introduction, you may want to read Brian Hayes's On the Threshold (2003) [PDF]. $\endgroup$
    – Rodrigo de Azevedo
    Nov 17, 2021 at 11:05
  • 1
    $\begingroup$ If you want to maximize the number of properly colored edges, that's know as maximum cut. That's usually with two colors, but you can generalize. $\endgroup$
    – Juho
    Nov 17, 2021 at 11:50

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.