Precoloring Extension with Demands on Paths

For contradiction, assume that Algorithm 1 fails, that is, there exists a feasible solution to the instance, and the algorithm does not find any. Let us denote the vertices of the path $P$ as $v_1,v_2,\mathrm{\dots },v_n$ from left to the right and let $R=\{v_t,\mathrm{\dots },v_n\}$ be the right precolored segment of $P$. Let the algorithm produce a partial coloring $\gamma$ and let ${\gamma }^{\prime }$ be a feasible solution where the index $i$ satisfying $\gamma (v_j)={\gamma }^{\prime }(v_j)$ for all and $\gamma (v_i)\ne {\gamma }^{\prime }(v_i)$ is the maximum possible. We are going to modify ${\gamma }^{\prime }$ such that we obtain another feasible solution that agrees with $\gamma$ even on $\gamma (v_i)$.

Let $a=\gamma (i)$ and $b={\gamma }^{\prime }(i)$. By alternating $ba$-sequence starting at $v_i$ we denote a maximal subsequence $S=(s_1,s_2,\mathrm{\dots }{s}_k)$ of the vertices $v_i,v_{i+1},\mathrm{\dots },v_n$ such that $s_1=v_i$, ${\gamma }^{\prime }(s_j)=b$ for odd $j$ and ${\gamma }^{\prime }(s_j)=a$ for even $j$, the distance of $s_j$ and $s_{j+1}$ is at most $d$ for every $j\in [k-1]$, and no vertex $s_j$ is precolored. Observe that when the algorithm was assigning color to $v_i$, the remaining demand of the color $a$ was at least the remaining demand of the color $b$, and that there is no color $a$ in the distance less than $d$ of the vertex $v_i$. Also note that for an alternating $ba$-sequence $s_1,\mathrm{\dots },s_k$, there can be no vertex of $P$ between any $s_i$ and $s_{i+1}$ colored by $a$ or $b$, as this would break the distance property. Let us distinguish several cases.

First, consider the case when the last element of the sequence $S$ is closer than $d$ to the right precolored part $R$ of $P$. In this case the sequence $S$ must contain all occurrences of color $a$ and $b$ among the vertices from $v_i$ to $v_n$ in ${\gamma }^{\prime }$. This implies that $S$ is an even sequence, as the demand of $a$ was at least the demand of $b$. If the vertices from $R$ contain neither color $a$ nor color $b$, we can freely swap the colors $a$ and $b$ in $S$. Suppose now the vertices from $R$ contain color $a$ (or $b$). If there is no occurrence of $a$ or $b$ in $R$ that is within distance $d$ of $s_k$, then the colors $a$ and $b$ can be swapped in ${\gamma }^{\prime }$. If the first occurrence of $a$ or $b$ in $R$ is within distance $d$ of $s_k$, it must be $b$ because $s_k$ is colored $a$ by ${\gamma }^{\prime }$, but this contradicts the fact that the algorithm has colored $s_i$ with $a$ instead of $b$.

Next, assume that the alternating $ba$-sequence $S$ starting at $v_i$ has even length and its last element is more than $d$ vertices away from the precolored right part $R$ of $P$. We can freely swap the colors $a$ and $b$ at the vertices of $S$ as there is no conflict both to the left and right of $S$, thus obtaining a feasible solution ${\gamma }^{\prime \prime }$ with greater index $i$.

It remains to solve the case when $S$ has odd length and its last element is more than $d$ vertices far from the precolored right part $R$ of $P$. The sequence $S$ contains one more color $b$ than $a$ and as the algorithm has chosen the color $a$ for $v_i$ (which means the remaining demand of $b$ was not greater than $a$), there must exists alternating $ab$-sequence $S^{\prime }$ starting at some vertex $w$ of odd length, $S^{\prime }$ disjoint from $S$, which thus contains one more color $a$ than $b$. We may assume that $S^{\prime }$ is not within distance $d$ to the right precolored part $R$: if this is the case, we either obtain a contradiction if $a$ occurs before $b$ in $R$ and $a$ and $b$ had the same demand, or we can recolor $S$ and $S^{\prime }$ without problems. We may now swap the colors $a$ and $b$ both in $S$ and $S^{\prime }$, which does not change the total number of colors used. This produces a feasible solution ${\gamma }^{\prime \prime }$ with greater index $i$.

We obtained the contradiction in all cases, which shows the correctness of the algorithms. The time complexity $O(n\log c)$ follows from using a smarter data structure for assigning the available colors: we may dynamically maintain a binary heap containing the set of feasible colors $C_f$ with the key being a combination of the remaining demand with position ($\mathrm{pos}(\cdot )$) and the value stored being the color label. $◀$

Let ${\gamma }_i$ be a $d$-distance coloring of an initial segment $\{v_1,\mathrm{\dots },v_i\}$ of the path $G$. The signature of ${\gamma }_i$ consists of the colors of the rightmost $d$ vertices together with the frequencies of individual colors as used by ${\gamma }_i$. The algorithm sequentially computes for each $i\in [n]$ all possible signatures of $d$-distance colorings of $\{v_1,\mathrm{\dots },v_i\}$ that, moreover, extend the precoloring ${\gamma }^{\prime }$. At the end, this suffices to check whether there is a $d$-distance coloring of $\{v_1,\mathrm{\dots },v_n\}$ that extends ${\gamma }^{\prime }$ and the frequencies of colors used equal the demands. $◀$

It is only natural to ask whether we can achieve a polynomial runtime in this regime where the degree of the polynomial is independent of both $c$ and $d$. We answer this question negatively, under standard theoretical assumptions, by showing that DPED is W[1]-hard with respect to both of these parameters.

We first show W[1]-hardness of a related coloring problem, namely List Coloring with Demands. We define the problem formally as follows.

List Coloring with Demands (LCD)
Input: A graph $G=(V,E)$ on $v$ vertices, a set of colors $C$, a function $L:V\to 2^C$ that assigns a list of colors $L(v)$ to each vertex, and a demand function $\eta :C\to [n]$. Question: Is there an $L$-list coloring $\gamma :V\to C$ that satisfies the demands $\eta$?

An instance $(G,C,\eta ,L)$ of LCD is a path instance if the graph $G$ is a disjoint union of paths. Moreover, a path instance of LCD is non-alternating if there does not exist a color $c\in C$ and three consecutive vertices $v_{i-1},v_i,v_{i+1}$ on some path such that $c\notin L(v_i)$ and simultaneously $c\in L(v_{i-1})\cap L(v_{i+1})$.

The LCD problem has already been shown to be W[1]-hard on paths with respect to the number of colors by Gomes, Guedes, and dos Santos [15] albeit under a different name of Number List Coloring. However, the produced instances of LCD therein are very far from having the non-alternating property that is crucial in proving Theorem 3. We devise a novel reduction from a multidimensional version of the subset problem that, moreover, produces non-alternating path instances of LCD. Due to the space constraints, we omit the proof which can be found in the full version.

Theorem 3 is obtained through a polynomial-time reduction from LCD on non-alternating path instances. Crucially, both the distance parameter and the number of colors in the produced DPED instance are linear in the number of colors in the original LCD instance.

For technical reasons, we first modify the LCD instance to guarantee that it is a single path, and both of its endpoints have a list identical to its only neighbor $v$. That is achieved by introducing two extra colors $a,b$ and concatenating all paths in arbitrary order with two extra vertices in between consecutive pairs and two extra vertices at the very beginning and end where we add $\{a,b\}$ to the list of all vertices and set $L(v)=\{a,b\}$ for each new vertex. Finally, we set $\eta (a)=\eta (b)=p+1$ where $p$ is the total number of paths in $G$. It is easy to see that the modified instance is equivalent. Furthermore, the modified instance remains non-alternating because there are two extra new vertices between any pair of original paths, and the colors $a,b$ are included in the list of every vertex.

From now on, we assume that $G$ is a single path with vertices $v_1,\mathrm{\dots },v_n$ and edges $e_1,\mathrm{\dots },e_{n-1}$ such that $e_i=\{v_i,v_{i+1}\}$ for each $i\in [n-1]$. Moreover, we have $L(v_1)=L(v_2)$ and $L(v_{n-1})=L(v_n)$.

Now, we show that the lists of such a non-alternating LCD path instance can be alternatively represented by lists of forbidden colors for each edge. It is crucial that the instance of LCD is non-alternating, as otherwise, this may not be possible. Moreover, we will also guarantee that any fixed color can be contained in the forbidden sets of at most two consecutive edges.

We define the assignment inductively along the path. We set $F(e_1)=C\setminus L(v_1)$ and $F(e_{n-1})=C\setminus L(v_n)$. Recall that we first modified the instance to guarantee that each endpoint of the path has an identical list to its neighbor, i.e., $L(v_1)=L(v_2)$ and $L(v_{n-1})=L(v_n)$. For $i\in \{2,\mathrm{\dots },n-2\}$, we let $F(e_i)$ contain a color $c\in C$ if and only if $c\notin L(v_i)\cup L(v_{i+1})$ and moreover, either (i) $c\notin F(e_{i-1})$, or (ii) $c\in L(v_{i+2})$. See Figure 2. Clearly, $F$ can be computed in polynomial time.

Let us verify the properties of $F$. For the endpoints $v_1$ and $v_n$, we have $L(v_1)=C\setminus F(e_1)$ and $L(v_n)=C\setminus F(e_{n-1})$ by definition. Now, fix arbitrary $i\in \{2,\mathrm{\dots },n-1\}$ and a color $c\in C$. If we have $c\in L(v_i)$, then neither $F(e_{i-1})$ nor $F(e_i)$ contain $c$ by definition and $c\in C\setminus (F(e_{i-1})\cup F(e_i))$. On the other hand, if $c\notin L(v_i)$, it follows from the non-alternating property that either $c\notin L(v_{i-1})$ or $c\notin L(v_{i+1})$. We consider the three possible cases. First, assume that $c$ appears in none of the lists $L(v_{i-1})$, $L(v_i)$, and $L(v_{i+1})$. Then either $c\in F(e_{i-1})$ or we have $c\notin F(e_{i-1})$ which triggers the condition (i) in the definition of $F(e_i)$ and either way, we get that $c\in F(e_{i-1})\cup F(e_i)$. Second, assume that $c$ appears in the list $L(v_{i+1})$ but not in $L(v_{i-1})$. In this case, we have $c\in F(e_{i-1})$ by condition (ii) in the definition of $F(e_{i-1})$ and again, we see that $c\in F(e_{i-1})\cup F(e_i)$. Finally, assume that $c$ appears in the list $L(v_{i-1})$ but not in $L(v_{i+1})$. In this case, we have $c\notin F(e_{i-1})$, which implies $c\in F(e_i)$ by condition (i) in the definition. In all cases, we obtained $c\in F(e_{i-1})\cup F(e_i)$.

Assume for a contradiction that there are three consecutive edges $e_{i-1}$, $e_i$ and $e_{i+1}$ such that the intersection $F(e_{i-1})\cap F(e_i)\cap F(e_{i+1})$ is non-empty and let $c$ be an arbitrary color in the intersection. However, observe that in the definition of $F(e_i)$ neither condition (i) nor (ii) holds for $c$ and thus, we must have $c\notin F(e_i)$. $\mathrm{⊲}$

With this assignment $F$, we are finally ready to define the path instance $(G^{\prime },C^{\prime },d,{\gamma }^{\prime },{\eta }^{\prime })$ of DPED. Let $t$ denote the size of the color set $C$ and let $C=\{c_1,\mathrm{\dots },c_t\}$ be an arbitrary enumeration of the colors. We set $d=2t+1$. We take the graph $G^{\prime }$ to be a path of length $nd+1$ on vertices $v_1^{\prime },\mathrm{\dots },v_{nd+1}^{\prime }$ in this order along the path. To simplify the exposition, we partition the vertices into two distinct sets. Every vertex $v_{(k-1)d+1}^{\prime }$ for some $k\in [n]$ is a main vertex and we denote it alternatively by $x_k$. All the remaining vertices are auxiliary. For $i\in [n-1]$, $j\in [t]$ and $\alpha \in [2]$, the vertex $v_{(i-1)d+2j+\alpha -1}^{\prime }$ is an auxiliary vertex associated to color $c_j$ and we alternatively denote it by $y_{j,\alpha }^i$. Observe that every two consecutive main vertices $x_i$ and $x_{i+1}$ are separated by exactly $2t$ auxiliary vertices that are grouped into pairs associated to colors $c_1,\mathrm{\dots },c_t$ in this order. More specifically, the segment between $x_i$ and $x_{i+1}$ contains the auxiliary vertices $y_{j,\alpha }^i$ for all $j\in [t]$ and $\alpha \in [2]$, ordered lexicographically by the pairs $(j,\alpha )$. See Figure 3.

Our goal is to define a pre-coloring of all the auxiliary vertices such that there is a one-to-one correspondence between feasible colorings of the main vertices and feasible colorings of the original LCD instance. As a final ingredient, we need to be able to assign extra colors to certain vertices without affecting the rest of the instance. To that end, we set $C^{\prime }=C\cup C^{\star }$ where $C^{\star }=\{c_0^{\star },\mathrm{\dots },c_d^{\star }\}$ is a set of auxiliary colors disjoint from $C$. Moreover, we define an auxiliary coloring ${\gamma }^{\star }:V(G^{\prime })\to C^{\star }$ where ${\gamma }^{\star }(v_i^{\prime })=c_{imod(d+1)}^{\star }$ for each $i\in [nd+1]$. Informally, the coloring ${\gamma }^{\star }$ simply cyclically iterates through the sequence of auxiliary colors $c_0^{\star },\mathrm{\dots },c_d^{\star }$ along the path, starting with $c_1^{\star }$. Clearly, ${\gamma }^{\star }$ is a proper $d$-distance coloring of $G^{\prime }$.

We define the pre-coloring ${\gamma }^{\prime }$ of every auxiliary vertex. For $i\in [n-1]$ and $j\in [t]$, we set

where we additionally define $F(e_0)=\mathrm{\varnothing }$ for simplicity.

First, observe that the pre-coloring ${\gamma }^{\prime }$ exactly encodes the assignment of forbidden colors to edges.

Moreover, we show that ${\gamma }^{\prime }$ distributes the occurrences of a fixed color at a sufficient distance from each other.

Assume for a contradiction that ${\gamma }^{\prime }$ does contain such a pair of monochromatic vertices. We have already observed that ${\gamma }^{\star }$ is a proper $d$-coloring on a disjoint set of auxiliary colors and thus, this pair must use some color $c_j\in C$. We cannot have ${\gamma }^{\prime }(y_{j,1}^i)={\gamma }^{\prime }(y_{j,2}^i)=c_j$ for any fixed $i,j$ since the respective conditions in the definition of ${\gamma }^{\prime }$ are mutually exclusive.

For any different $i,i^{\prime }\in [n-1]$ with and arbitrary $\alpha ,{\alpha }^{\prime }\in [2]$, the distance between $y_{j,\alpha }^i$ and $y_{j,{\alpha }^{\prime }}^{i^{\prime }}$ is at most $d$ if and only if $i^{\prime }-i=1$ and ${\alpha }^{\prime }\le \alpha$. We cannot have ${\gamma }^{\prime }(y_{j,1}^i)={\gamma }^{\prime }(y_{j,1}^{i+1})=c_j$ by definition of ${\gamma }^{\prime }(y_{j,1}^{i+1})$. So the only option left is that ${\gamma }^{\prime }(y_{j,2}^i)={\gamma }^{\prime }(y_{j,\alpha }^{i+1})=c_j$ for either $\alpha \in [2]$. But in that case, we have $c_j\in F(e_{i-1})\cap F(e_i)$ since ${\gamma }^{\prime }(y_{j,2}^i)=c_j$ and simultaneously, $c_j\in F(e_{i+1})$ since ${\gamma }^{\prime }(y_{j,\alpha }^{i+1})=c_j$. Thus, we reached a contradiction since $F$ does not contain the same color in the sets $F(e_{i-1}),F(e_i),F(e_{i+1})$ of three consecutive edges. $\mathrm{⊲}$

To finish the construction, it remains to define the demand function ${\eta }^{\prime }$. We set ${\eta }^{\prime }(c_j)=\eta (c_j)$ for every original color $c_j\in C$ and we set ${\eta }^{\prime }(c_j^{\star })=0$ for every auxiliary color $c_j^{\star }\in C^{\star }$.

Suppose that $(G,C,\eta ,L)$ is a yes-instance of LCD and let $\rho :V(G)\to C$ be an $L$-list coloring that meets the demands. We define a coloring $\gamma :V(G^{\prime })\to C^{\prime }$ by simply setting $\gamma (x_i)=\rho (v_i)$ for every main vertex $x_i$ and $\gamma (y_{j,\alpha }^i)={\gamma }^{\prime }(y_{j,\alpha }^i)$ for every auxiliary vertex $y_{j,\alpha }^i$. The coloring $\gamma$ is an extension of ${\gamma }^{\prime }$ by definition, and it meets the demands because the demand functions $\eta$ and ${\eta }^{\prime }$ are equal when restricted to the color set $C$. Thus, it remains to show that $\gamma$ is a proper $d$-distance coloring.

Assume for a contradiction that $\gamma$ contains a pair of monochromatic vertices $u$ and $w$ at a distance at most $d$. At least one of these vertices has to be a main vertex since the colors of all auxiliary vertices are fixed by ${\gamma }^{\prime }$ and there is no such monochromatic pair of pre-colored vertices by Claim 7. First, assume that both $u$ and $w$ are main vertices. Two main vertices are in distance at most $d$ if and only if they are consecutive, i.e., we have without loss of generality $u=x_i$ and $w=x_{i+1}$ for some $i\in [n-1]$. But then they cannot share the same color since $\gamma (x_i)=\rho (v_i)$, $\gamma (x_{i+1})=\rho (v_{i+1})$ and $\rho$ is a proper list-coloring of $G$. Otherwise, suppose without loss of generality that $u$ is a main vertex $x_i$ and $w$ is an auxiliary vertex. The coloring $\gamma$ can use only the colors from $C$ on the main vertices and thus, we have $\gamma (x_i)=\gamma (w)=c_j$ for some $c_j\in C$. Moreover, the vertex $w$ lies either on the segment between $x_{i-1}$ and $x_i$ or on the segment between $x_i$ and $x_{i+1}$ as those are the only auxiliary vertices at a distance at most $d$ from $x_i$. Observation 6 then implies that we have either $c_j\in F(e_{i-1})$ or $c_j\in F(e_i)$. But we know that $L(x_i)=C\setminus (F(e_{i-1})\cap F(e_i))$ by Claim 5. In particular, the color $c_j$ does not appear in the list $L(v_i)$, which is a contradiction with $\rho$ being a proper list-coloring since $\rho (v_i)=\gamma (x_i)=c_j$.

Now suppose that $(G^{\prime },C^{\prime },d,{\gamma }^{\prime },{\eta }^{\prime })$ is a yes-instance of DPED and let $\gamma :V(G^{\prime })\to C^{\prime }$ be a witnessing $d$-distance coloring, i.e., $\gamma$ extends the pre-coloring ${\gamma }^{\prime }$ and meets the demands given by ${\eta }^{\prime }$. We define a coloring $\rho :V(G)\to C$ by simply restricting $\gamma$ to the main vertices, that is we set $\rho (v_i)=\gamma (x_i)$. First, observe that the range of $\rho$ is indeed only the color set $C$ since the demand ${\eta }^{\prime }(c_j^{\star })$ of any auxiliary color is zero and thus, $\gamma$ uses only the colors from $C$ on the main vertices. Moreover, we have $\rho (v_i)\ne \rho (v_{i+1})$ for every $i\in [n-1]$ because the main vertices $x_i$ and $x_{i+1}$ are at distance $d$ in $G^{\prime }$. The demands are also satisfied by $\rho$ because the demand functions $\eta$ and ${\eta }^{\prime }$ are equal when restricted to the color set $C$.

It remains to check that $\rho$ is an $L$-list coloring, i.e., we have $\rho (v_i)\in L(v_i)$ for all $i\in [n]$. Assume for a contradiction that this does not hold for a vertex $v_i$ with $\rho (v_i)=\gamma (x_i)=c_j$. By Claim 5, the color $c_j$ belongs to at least one of the sets $F(e_{i-1})$ and $F(e_i)$. Observation 6 implies that the color $c_j$ is used by $\gamma$ on some auxiliary vertex from the segment between $x_{i-1}$ and $x_{i+1}$. But all these vertices are at a distance at most $d$ from $x_i$ and we reach a contradiction with $\gamma$ being a proper $d$-distance coloring. $◀$

Let $(G,C,d,{\gamma }^{\prime })$ be an instance of DPE where $G$ is a path with $n$ vertices. We construct an instance $(G^{\prime },C,d,{\gamma }^{\prime },\eta )$ where $G^{\prime }$ is simply obtained by adding $(|C|-1)\cdot n$ isolated vertices (paths of zero length) to $G$ and setting $\eta (a)=n$ for every $a\in C$. Clearly, every $d$-distance coloring of $G^{\prime }$ that extends ${\gamma }^{\prime }$ induced the desired $d$-distance coloring of $G$, regardless of the demands. On the other hand, we can extend any $d$-distance coloring $\gamma$ of $G$ to $G^{\prime }$ by coloring exactly $n-|{\gamma }^{-1}(a)|$ of the isolated vertices with each color $a\in C$ to satisfy all demands.

Finally, we construct an equivalent instance of DPED on a single path. It suffices to concatenate all the disjoint paths in $G^{\prime }$ to a single path while adding $d$ auxiliary vertices between each consecutive pair of original paths. These auxiliary vertices are then greedily precolored with $2d+1$ new auxiliary colors disjoint from $C$ that have zero demands. In this way, the $d$-distance colorings of individual paths from $G^{\prime }$ are independent from each other, and the equivalence follows. $◀$

In contrast, we show that the problem Distance Precoloring Extension without demands becomes FPT by the distance parameter $d$ even for an unbounded number of colors. Recall that Distance Precoloring Extension with Demands is W[1]-hard with respect to $d$ by Theorem 3. In fact, we show the existence of an FPT algorithm for the more general problem of Distance List Coloring where the task is to find a list coloring that assigns different colors to every pair of vertices at distance at most $d$.