Theoretical Computer Science
graph-algorithms graph-colouring scheduling bipartite-graphs
Updated Fri, 27 May 2022 00:14:30 GMT

Color shifting in a bipartite graph


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,



Solution

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 "NPcompleteness 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$.


References