Precoloring Extension with Demands on Paths

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F25%3A00386745" target="_blank" >RIV/68407700:21240/25:00386745 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.ISAAC.2025.23" target="_blank" >https://doi.org/10.4230/LIPIcs.ISAAC.2025.23</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ISAAC.2025.23" target="_blank" >10.4230/LIPIcs.ISAAC.2025.23</a>

Result language

angličtina

Original language name

Precoloring Extension with Demands on Paths

Original language description

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₁,... ,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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

36th International Symposium on Algorithms and Computation (ISAAC 2025)

ISBN

978-3-95977-408-6

ISSN

—

e-ISSN

—

Number of pages

15

Pages from-to

"23:1"-"23:15"

Publisher name

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Place of publication

Dagstuhl

Event location

Tainan

Event date

Dec 7, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—