Perfect italian domination solved efficiently on split graphs and hard nearby
Perfect Italian Domination on and Near Split Graphs: Algorithms, Hardness, and Approximation
Discrete Mathematics
Summary
The paper studies a special way of labeling points in a network so that certain sum rules hold for neighbors of unlabeled points. The authors find a fast algorithm to solve this labeling problem on a particular kind of network called split graphs, where earlier similar problems were harder. They also prove that if you slightly change these graphs, the problem becomes hard again. Finally, they show how well the problem can be approximated in some cases.
What this means in practice
- •For graph algorithm developers: Identify graph classes where perfect italian domination can be computed efficiently versus where it is NP-hard, improving algorithm design strategies.
- •For network security teams: Understand tractability boundaries when designing networks to ensure certain coverage properties can be checked efficiently or are computationally hard.
A theory result. No direct application yet.
Authors
Anand Babu N B, Ashwin Jacob, Manjusha M S, Renjith P
Abstract
A perfect Italian dominating function assigns a label from $\{0,1,2\}$ to each vertex so that the labels in the neighborhood of every zero-labeled vertex sum to exactly two. Although the associated decision problem (PID) is NP-complete on chordal graphs, the complexity status on split graphs remains open. We give an $O(n^4)$ time algorithm for split graphs on $n$ vertices. We note that this is in contrast to Roman, Italian, and perfect Roman domination, which are NP-complete on split graphs. We further show that this tractability boundary is tight: PID is NP-hard on graphs at deletion distance one from split graphs. We also provide dichotomy results for PID on restricted extensions of split graphs formed by attaching pendant stars, and establish inapproximability results for the same.