Algorithms for Vertex Partitioning Problems on Partial k-Trees

TLDR

The authors’ characterization of vertex partitioning problems establishes a taxonomy that enables uniform complexity classification and common algorithmic treatment. The paper aims to develop practical solution algorithms for NP‑hard vertex partitioning problems on partial k‑trees by applying algorithm design theory to this graph class. They introduce new graph parameters, provide a precise characterization of vertex partitioning problems—including domination, coloring, and packing variants—and detail algorithmic techniques with complexity analyses to make the methods feasible for practical use. The resulting algorithms exhibit computational complexity that depends reasonably on the treewidth parameter k, yielding the first polynomial‑time algorithm for computing the Grundy number on partial k‑trees and establishing practical time bounds for other vertex partitioning problems.

Abstract

In this paper, we consider a large class of vertex partitioning problems and apply to them the theory of algorithm design for problems restricted to partial k-trees. We carefully describe the details of algorithms and analyze their complexity in an attempt to make the algorithms feasible as solutions for practical applications. We give a precise characterization of vertex partitioning problems, which include domination, coloring and packing problems, and their variants. Several new graph parameters are introduced as generalizations of classical parameters. This characterization provides a basis for a taxonomy of a large class of problems, facilitating their common algorithmic treatment and allowing their uniform complexity classification. We present a design methodology of practical solution algorithms for generally $\NP$-hard problems when restricted to partial k-trees (graphs with treewidth bounded by k). This "practicality" accounts for dependency on the parameter k of the computational complexity of the resulting algorithms. By adapting the algorithm design methodology on partial k-trees to vertex partitioning problems, we obtain the first algorithms for these problems with reasonable time complexity as a function of treewidth. As an application of the methodology, we give the first polynomial-time algorithm on partial k-trees for computation of the Grundy number.