Exploring Dominating Functions and Their Complexity in Subclasses of Weighted Chordal Graphs and Bipartite Graphs - Chuan-Min Lee (Mathematics)
Domination problems are fundamental problems in graph theory with diverse applications in optimization, network design, and computational complexity. This paper investigates <semantics>{k}</semantics>-domination, k-tuple domination, and their total domination variants in weighted strongly chordal graphs and chordal bipartite graphs. Specifically, the <semantics>{k}</semantics>-domination problem in weighted strongly chordal graphs and the total <semantics>{k}</semantics>-domination problem in weighted chordal bipartite graphs are shown to be solvable in <semantics>O(n+m)</semantics> time. For weighted proper interval graphs and convex bipartite graphs, we solve the k-tuple domination and total k-tuple domination problems in <semantics>O(n2.371552log2(n)log(n/δ))</semantics>, where <semantics>δ</semantics> is the desired accuracy. Furthermore, for weighted unit interval graphs, the k-tuple domination problem achieves a significant complexity improvement, reduced from <semantics>O(nk+2)</semantics> to <semantics>O(n2.371552log2(n)log(n/δ))</semantics>. These results are achieved through a combination of linear and integer programming techniques, complemented by totally balanced matrices, totally unimodular matrices, and graph-specific matrix representations such as neighborhood and closed neighborhood matrices.