1
$\begingroup$

Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle $. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the degree of each vertex is at most $k$. Now consider the problem of coloring $G$'s edges with $k$ colors, such that no adjacent edges have the same color. This problem can be solved efficiently by noting that $G$ is a subgraph of a $k$-regular bipartite graph and thus one can compute a perfect matchings to color $G$.

The problem I'm trying to solve is as follows. Assume that we have colored $G_1$ and now we're given a new graph $G_2$ with the same properties and vertices of $G_1$ but with possibly different edges. We want to color $G_2$ while trying to save as many colors from $G_1$ as possible. That is, if there is an edge $e_1$ of $G_1$ that is also present in $G_2$, then we prefer to keep its color from the previous coloring of $G_1$.

Formally, suppose $c_1$ is a coloring of $G_1$ and $c_2$ is a coloring of $G_2$. Define a function $f_{c_2}$ from the edges of $G_2$ to $\{0, 1\}$ as follows: $f_{c_2}(e) = 1$ iff $e$ is present in both $G_1$ and $G_2$ and $c_1(e_1) = c_2(e_2)$. Now the problem can be stated as follows. Given $G_1$, a coloring $c_1$ of $G_1$ and given $G_2 = \langle V_2, E_2\rangle $, we're asked to compute a coloring $c_2$ of $G_2$ such that $\sum_{e \in E_2}f_{c_2}(e)$ is maximized.

My approaches:

  • I tried to use the Hungarian algorithm $k$ times to find $k$ perfect matchings. Lets say i want to save as many blue colored edges as possible, so i give those edges in $G_2$ a high weight, i find a perfect matching to color it with blue and then i proceed to the next color. The problem with this solution is that the order of the colors that we choose may affect the outcome.

  • I thought that maybe one can state the problem as an instance of LP (linear programming).

A help would be appreciated,

$\endgroup$

1 Answer 1

2
$\begingroup$

The precoloring extension problem is the following:

Input: a number $k$ and a graph $G$ some of whose edges are labeled with labels in $\{1, 2, \ldots, k\}$.

Decision: is it possible to color the edges of $G$ with colors $1, 2, \ldots, k$ such that no adjacent edges share a color and such that each initially labeled edge is colored with the color it is labeled with.

In other words, given a partially colored graph, can you finish coloring it using only $k$ colors?

A specific case of this problem was proven NP-hard in the paper "NP‐completeness of list coloring and precoloring extension on the edges of planar graphs" by Daniel Marx. In particular, the author showed that precoloring extension is NP-hard even when $k = 3$ and $G$ is a planar 3-regular bipartite graph.

As it turns out, this means your problem is NP-hard too. Here's a simple reduction:

Given an instance of the precoloring extension problem consisting of partially colored planar 3-regular bipartite graph $G$ and $k = 3$, we build an instance of your problem:

  • We set the degree bound/number of colors (which you called $k$) to be $3$
  • We set $G_1$ to be $G$ with all initially non-colored edges removed
  • We set $c_1$ to be the partial coloring of $G$ (and since $G_1$ consists of the edges of $G$ that are colored, $c_1$ is a coloring of $G_1$)
  • We set $G_2$ to be $G$

Notice that $G_1$ and $G_2$ are both bipartite graphs with vertex-degrees at most $3$.

It is possible to color $G_2$ with a coloring $c_2$ that matches $c_1$ everywhere if and only if it is possible to extend the partial coloring $c_1$ on $G_1$ to a full coloring of $G_2 = G$. In other words, finding a coloring for $c_2$ which differs from $c_1$ as little as possible is equivalent to extending the partial coloring of $G$ into a full coloring.

Thus, your problem is NP-hard.

If you need to solve instances efficiently despite the fact that your problem is NP-hard, I recommend using an ILP solver: for each edge-color pair in $G_2$, make a variable that is 1 if the edge has that color and zero otherwise; then use inequality constraints to enforce that the number of colors of each edge is exactly 1 and that the number of edges at each vertex of each color is at most 1; finally, set the objective that the solver tries to maximize to the sum of the variables corresponding with edge-color pairs present in $G_1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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