<p>The precoloring extension problem is the following:</p>

<p>Input: a number <span class="math-container">$k$</span> and a graph <span class="math-container">$G$</span> some of whose edges are labeled with labels in <span class="math-container">$\{1, 2, \ldots, k\}$</span>.</p>

<p>Decision: is it possible to color the edges of <span class="math-container">$G$</span> with colors <span class="math-container">$1, 2, \ldots, k$</span> such that no adjacent edges share a color and such that each initially labeled edge is colored with the color it is labeled with.</p>

<p>In other words, given a partially colored graph, can you finish coloring it using only <span class="math-container">$k$</span> colors?</p>

<p>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 <span class="math-container">$k = 3$</span> and <span class="math-container">$G$</span> is a planar 3-regular bipartite graph.</p>

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

<p>Given an instance of the precoloring extension problem consisting of partially colored planar 3-regular bipartite graph <span class="math-container">$G$</span> and <span class="math-container">$k = 3$</span>, we build an instance of your problem:</p>

<ul>
<li>We set the degree bound/number of colors (which you called <span class="math-container">$k$</span>) to be <span class="math-container">$3$</span></li>
<li>We set <span class="math-container">$G_1$</span> to be <span class="math-container">$G$</span> with all initially non-colored edges removed</li>
<li>We set <span class="math-container">$c_1$</span> to be the partial coloring of <span class="math-container">$G$</span> (and since <span class="math-container">$G_1$</span> consists of the edges of <span class="math-container">$G$</span> that are colored, <span class="math-container">$c_1$</span> is a coloring of <span class="math-container">$G_1$</span>)</li>
<li>We set <span class="math-container">$G_2$</span> to be <span class="math-container">$G$</span></li>
</ul>

<p>Notice that <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> are both bipartite graphs with vertex-degrees at most <span class="math-container">$3$</span>.</p>

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

<p>Thus, your problem is NP-hard.</p>

<p>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 <span class="math-container">$G_2$</span>, 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 <span class="math-container">$G_1$</span>.</p>

CC BY-SA 4.0
2018-10-03T23:43:36.223Z
2018-10-03T23:43:36.223Z
Mikhail Rudoy
<p>Assume that we have a directed bipartite graph <span class="math-container">$G = \langle L\dot\cup R, E\rangle $</span>. Where <span class="math-container">$E$</span> contains directed edges only from <span class="math-container">$L$</span> to <span class="math-container">$R$</span>, that is, <span class="math-container">$E\subseteq L\times R$</span>. Assume further that the degree of each vertex is at most <span class="math-container">$k$</span>. Now consider the problem of coloring <span class="math-container">$G$</span>'s edges with <span class="math-container">$k$</span> colors, such that no adjacent edges have the same color. This problem can be solved efficiently by noting that <span class="math-container">$G$</span> is a subgraph of a <span class="math-container">$k$</span>-regular bipartite graph and thus one can compute a perfect matchings to color <span class="math-container">$G$</span>.</p>

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

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

<p>My approaches: </p>

<ul>
<li><p>I tried to use the Hungarian algorithm <span class="math-container">$k$</span> times to find <span class="math-container">$k$</span> perfect matchings. Lets say i want to save as many blue colored edges as possible, so i give those edges in <span class="math-container">$G_2$</span> 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.</p></li>
<li><p>I thought that maybe one can state the problem as an instance of LP (linear programming).</p></li>
</ul>

<p>A help would be appreciated, </p>

<graph-algorithms><graph-colouring><scheduling><bipartite-graphs>
Color shifting in a bipartite graph
bbb3321
# Color shifting in a bipartite graph

(Asked by: username_0 on 2018-10-03)

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,

**Tags:** graph-algorithms, graph-colouring, scheduling, bipartite-graphs

---

## 1 answers

### Answer by username_1 on 2018-10-03. Score: 1 | Accepted answer

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


---

