Perfect Italian Domination on Structured Bipartite Graphs: Algorithms, Parameterization, and Hardness

Abstract

A perfect Italian dominating function assigns values in {0,1,2} to the vertices of a graph so that every zero-valued vertex has a neighbor-value sum of exactly two. We determine the computational complexity of the problem for bipartite graphs whose neighborhoods are subtrees of a simple host tree. On convex bipartite graphs, whose host is a path, an explicit ten-coordinate boundary dynamic programming algorithm computes the optimum value in O(n11) time and O(n10) space. We extend the method to the annotated setting in which the input supplies a size-k vertex set whose deletion leaves a convex bipartite graph, together with a convex representation of the remainder. Enumerating the modulator labels and tracking four-valued exact-sum counters gives an O(k6kn11)-time fixed-parameter tractable algorithm. On triad-convex bipartite graphs, whose host consists of three paths with a common endpoint, we give a polynomial-time algorithm by combining a constructible mim-width-three decomposition with a three-stable locally checkable formulation. More generally, the same method is polynomial for (t,Δ)-tree-convex bipartite graphs for every fixed pair (t,Δ), provided that the representation is supplied. In contrast, we prove that the decision problem is NP-complete on star-convex bipartite graphs. The reduction from Restricted Exact Cover by 3-Sets uses a forced label-2 center and constant-size set gadgets whose two minimum-weight modes encode an exact cover. We further prove that the problem parameterized by the target weight is W[1]-hard on the same graph class through a parameter-preserving reduction from Perfect Code.