Alladi Ramakrishnan Hall

On the Parameterized Complexity of Minus Domination

Mohanapriya

IMSc

ominating set is a well-studied combinatorial problem. Given a graph G, a dominating function f that maps V(G) to 0 or 1 such that $\sum_{w \in N[v]} f(w) \geq 1$, for each vertex $v\in V(G)$. We study a generalization of the Dominating set problem called Minus domination which is a function f that maps V(G) to $ \{-1, 0, 1\}$. Such a function is said to be a minus dominating function if for each vertex $v\in V(G)$, we have $\sum_{w \in N[v]}f(w) \geq 1$. The objective is to minimize the weight of a minus domination function. The problem is NP-hard even on bipartite, planar, and chordal graphs.

In this paper, we study \mdsh~from the perspective of parameterized complexity. After observing the complexity of the problem with the natural parameters such as the number of vertices labeled 1, -1 and 0, we study the problem with respect to structural parameters. We show that \mdsh~is fixed-parameter tractable when parameterized by twin-cover number, neighborhood diversity or the combined parameters component vertex deletion set and size of the largest component. In addition, we give an XP-algorithm when parameterized by distance to cluster number.


(This is a joint work with Sriram Bhyravarapu, Lawqueen Kanesh, Nidhi Purohit,
N. Sadagopan, and Saket Saurabh, To appear in SOFSEM 2024)