3
$\begingroup$

Suppose we have a graph with $n$ vertices and $n$ lists of colors such that no vertex coloring of the graph using colors from given lists is a proper list coloring. We can characterize the obstacle to proper list coloring in terms of frustrated cycles -- simple cycles such that every list coloring of the induced subgraph is improper.

Given graph and set of color lists I'd like to delete a small number of vertices to break a large number of frustrated cycles.

Is anything known about this problem, especially from algorithmic point of view?

Improve this question
$\endgroup$
2
  • $\begingroup$ If (a few) lists of size 1 are allowed, there are also interesting examples of trees with no proper list coloring. It might be a good idea for you to provide some examples so that "small", "large", are made clear. Also a few words on the obstacle characterization would be appreciated. Do you want to eventually break all cycles? Or are you content with a maximal colorable subgraph? Also, it would help if you contrasted your problem with known literature, so that experts can suggest alternatives that you want. Gerhard "Ask Me About System Design" Paseman, 2011.01.09 $\endgroup$
    – Gerhard Paseman
    Commented Jan 10, 2011 at 4:30
  • $\begingroup$ I unfortunately don't know any related literature, this is a theoretical example for a practical problem that arises when running a particular message passing algorithm on graph. Frustrated cycles cause convergence problems and I can delete a few nodes and correct for their removal. There's a bounded number of nodes I can afford to remove, so I want to break as many frustrated cycles as possible with that number. $\endgroup$
    – Yaroslav Bulatov
    Commented Jan 10, 2011 at 19:07

1 Answer 1

Reset to default
2
$\begingroup$

It sounds like you are asking if the Erdős–Pósa property holds for frustrated cycles. That is, does there exists a function $f: \mathbb{N} \to \mathbb{N}$, such that every graph (with lists) either has $k$ disjoint frustrated cycles, or a set of vertices $X$, of size at most $f(k)$, such that $G -X$ contains no frustrated cycles.

Erdős and Pósa proved that the Erdős–Pósa property holds for the class of all cycles. However, the Erdős–Pósa property does not hold for the class of odd cycles. From this, it follows that the Erdős–Pósa property does not hold for frustrated cycles. This is because if each list consists of the same two colours, then the frustated cycles are precisely the odd cycles.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I realize that breaking all frustrated cycles is probably too hard, so I need to find k nodes that break as many cycles as possible $\endgroup$
    – Yaroslav Bulatov
    Commented Jan 10, 2011 at 19:09

You must log in to answer this question.

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