# 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,

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.

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