Title: Precoloring extension with demands on paths Show Chinese title

Title: 带有路径需求的预着色扩展

Abstract: Let $G$ be a graph with a set of precolored vertices, and let us be given an integer distance parameter $d$ and a set of integer demands $d_1,\dots,d_c$. The Distance Precoloring Extension with Demands (DPED) problem is to compute a vertex $c$-coloring of $G$ such that the following three conditions hold: (i) the resulting coloring respects the colors of the precolored vertices, (ii) the distance of two vertices of the same color is at least $d$, and (iii) the number of vertices colored by color $i$ is exactly $d_i$. This problem is motivated by a program scheduling in commercial broadcast channels with constraints on content repetition and placement, which leads precisely to the DPED problem for paths. In this paper, we study DPED on paths and present a polynomial time exact algorithm when precolored vertices are restricted to the two ends of the path and devise an approximation algorithm for DPED with an additive approximation factor polynomially bounded by $d$ and the number of precolored vertices. Then, we prove that the Distance Precoloring Extension problem on paths, a less restrictive version of DPED without the demand constraints, and then DPED itself, is NP-complete. Motivated by this result, we further study the parameterized complexity of DPED on paths. We establish that the DPED problem on paths is $W[1]$-hard when parameterized by the number of colors and the distance. On the positive side, we devise a fixed parameter tractable (FPT) algorithm for DPED on paths when the number of colors, the distance, and the number of precolored vertices are considered as the parameters. Moreover, we prove that Distance Precoloring Extension is FPT parameterized by the distance. As a byproduct, we also obtain several results for the Distance List Coloring problem on paths. Show Chinese abstract

Abstract: 设 $G$ 是一个带有预着色顶点集合的图，并且给定一个整数距离参数 $d$ 和一个整数需求集合 $d_1,\dots,d_c$。 距离预着色扩展问题（DPED）是计算图$G$的顶点$c$-着色，使得以下三个条件成立：(i) 所得到的着色尊重预着色顶点的颜色，(ii) 同一颜色的两个顶点之间的距离至少为$d$，以及 (iii) 由颜色$i$着色的顶点数量正好为$d_i$。这个问题的动机来自于商业广播频道中的程序调度，其中对内容重复和放置有约束，这恰好导致了路径上的 DPED 问题。在本文中，我们研究路径上的 DPED，并当预着色顶点被限制在路径的两个端点时，提出了一个多项式时间精确算法，并为 DPED 设计了一个近似算法，其加法近似因子在$d$和预着色顶点数量上是多项式有界的。然后，我们证明了路径上的距离预着色扩展问题，即没有需求约束的 DPED 的较不严格版本，以及 DPED 本身都是 NP 完全的。受此结果的启发，我们进一步研究了路径上 DPED 的参数化复杂性。我们确定当以颜色数量和距离作为参数时，路径上的 DPED 问题是$W[1]$-难的。在积极方面，当颜色数量、距离和预着色顶点数量被视为参数时，我们为路径上的 DPED 设计了一个固定参数可tractable（FPT）算法。此外，我们证明了距离预着色扩展问题在距离参数化下是 FPT 的。作为副产品，我们还获得了关于路径上距离列表着色问题的几个结果。