Graph Theory and its Practical applications: Combinatorial and Algorithmic advances in Identifying codes and Scheduling

Abstract

The Identifying Code (IC) problem seeks a vertex subset whose intersection with every vertex’s closed neighborhood is unique, enabling fault detection in multiprocessor systems and practical uses in identity verification, environmental monitoring, and dynamic localization. A closely related problem is the Locating-Dominating Set (LD), which requires each nondominating vertex to be uniquely identified by its intersection with the set. Cappelle, Gomes, and Santos (2021) proved LD is W-hard for minimum clique cover and lacks polynomial kernels for parameters like vertex cover, but their methods did not apply to IC. This paper answers their question, showing IC does not admit a polynomial kernel parameterized by solution size plus vertex cover unless NP ⊆ coNP/poly. On the positive side, we establish that IC is fixed-parameter tractable when parameterized by cliquewidth (by giving an explicit algorithm), extending tractability to a broad family of graph classes. Further, we define and discuss a bit about a sister problem in the appendix. We further study another industry-motivated problem, namely single-machine coupledtask scheduling (CTS) in the exact-gap model. Each job i is specified by a triple (Ai, Li, Bi): it consists of two processing blocks of lengths Ai and Bi separated by an idle gap of fixed length Li. The objective is to minimize the makespan Cmax. Compatibility constraints are given by a graph G = (V, E): a job j may be executed inside the idle gap of a job i only if {i, j} ∈ E. Bessy and Giroudeau [8] observed that the complexity of bounded CTS when G is a tree was open, and proved that CTS becomes NP-complete even when G is a star if task lengths are not bounded (via a reduction from Subset Sum). We resolve the tree case in the bounded-length regime by giving an algorithm with running time O(n4L10max), where Lmax = maxi Li, and hence polynomial whenever Lmax is polynomially bounded. For paths, we design a purely combinatorial O(n3)-time algorithm that works without any boundedness assumption on the gap lengths, and we extend it to all graphs of maximum degree 2. Together with the known NP-hardness of CTS on graphs of maximum degree 3 [23, 41], this yields a sharp degree threshold: CTS is solvable in strongly polynomial time for maximum degree 2, whereas for maximum degree 3 and above it is strongly NP-hard. Our algorithmic approach on trees is a bottom-up dynamic program that integrates a 0–1 knapsack subroutine as the crucial local decision step; to the best of our knowledge, this is the first use of knapsack as a subroutine inside a dynamic program for coupled-task scheduling on trees, and it may be useful for other scheduling problems with graph-structured compatibility constraints.