11institutetext: Department of Computer Science and Engineering, IIT Madras,
Chennai, India
11email<EMAIL_ADDRESS>22institutetext:
Faculty of Informatics, Czech Technical University in Prague, Czech Republic
22email<EMAIL_ADDRESS>
# Parameterized Complexity of Minimum Membership Dominating Set

Akanksha Agrawal 11 Pratibha Choudhary 22 N. S. Narayanaswamy 11 K. K. Nisha
11 Vijayaragunathan Ramamoorthi 11

###### Abstract

Given a graph $G=(V,E)$ and an integer $k$, the Minimum Membership Dominating
Set (MMDS) problem seeks to find a dominating set $S\subseteq V$ of $G$ such
that for each $v\in V$, $|N[v]\cap S|$ is at most $k$. We investigate the
parameterized complexity of the problem and obtain the following results about
MMDS:

  1. 1.

W[1]-hardness of the problem parameterized by the pathwidth (and thus,
treewidth) of the input graph.

  2. 2.

W[1]-hardness parameterized by $k$ on split graphs.

  3. 3.

An algorithm running in time
$2^{\mathcal{O}(\textbf{vc})}|V|^{\mathcal{O}(1)}$, where vc is the size of a
minimum-sized vertex cover of the input graph.

  4. 4.

An ETH-based lower bound showing that the algorithm mentioned in the previous
item is optimal.

##  1 Introduction

For a graph $G=(V,E)$, a set $S\subseteq V$ is a dominating set for $G$, if
for each $v\in V$, either $v\in S$, or a neighbor of $v$ in $G$ is in $S$. The
Dominating Set problem takes as input a graph $G=(V,E)$ and an integer $k$,
and the objective is to test if there is a dominating set of size at most $k$
in $G$. The Dominating Set problem is a classical NP-hard problem [14], which
together with its variants, is a well-studied problem in Computer Science. It
is also known under standard complexity theoretic assumption that, Dominating
Set cannot admit any algorithm running in time $f(k)\cdot|V|^{\mathcal{O}(1)}$
time, where $k$ is the size of dominating set.111More formally, in the
framework of parameterized complexity (see Section 2 for definitions), the
problem is W[2]-hard, and thus we do not expect any FPT algorithm for the
problem, when parameterized by the solution size. A variant of Dominating Set
that is of particular interest to us in this paper, is the one where we have
an additional constraint that the number of closed neighbors that a vertex has
in a dominating set is bounded by a given integer as input.222For a vertex $v$
in a graph $G=(V,E)$, the closed neighborhood of $v$ in $G$, $N_{G}[v]$, is
the set $\\{u\in V\mid\\{a,b\\}\in E\\}\cup\\{v\\}$. As Dominating Set is a
notoriously hard problem in itself, so naturally, the above condition does not
make the problem any easier. The above variant has been studied in the
literature, and several hardness results are known for it [20]. Inspired by
such negative results, in this paper, we remove the size requirement of the
dominating set that we are seeking, and attempt to study the complexity
variation for such a simplification. We call this version (to be formally
defined shortly) of the Dominating Set problem as Minimum Membership
Dominating Set (MMDS, for short). For a graph $G=(V,E)$, a vertex $u\in V$ and
a set $S\subseteq V$, the membership of $u$ in $S$ is $M(u,S)=|N[u]\cap S|$.
Next we formally define the MMDS problem.

Minimum Membership Dominating Set (MMDS)
Input: A graph $G=(V,E)$ and a positive integer $k$. Parameter: $k$. Question:
Does there exist a dominating set $S$ of $G$ such that $\max_{u\in
V}M(u,S)\leq k$?

We refer to a solution of MMDS as a $k$-membership dominating set ($k$-mds).
Unless, otherwise specified, for MMDS, by $k$ we mean the membership. The term
“membership” is borrowed from a similar version of the Set Cover problem by
Kuhn et al. [19], that was introduced to model reduction in interference among
transmitting base stations in cellular networks.

Our results. We prove that the MMDS problem is $\NP$-Complete and study the
problem in the realm of parameterized complexity.

###### Theorem 1.1

The MMDS problem is -complete on planar bipartite graphs for $k=1$.

This shows that the MMDS problem for the parameter $k$ is Para-NP-hard, even
for planar bipartite graphs. In other words, for every polynomial time
computable function $f$, there is no $O(n^{f(k)})$-time algorithm for the MMDS
problem. Further, our reduction also shows that the MMDS restricted to planar
bipartite graphs does not have a $(2-\epsilon)$ approximation for any
$\epsilon>0$.

Having proved the $\NP$-Completeness property of MMDS, we study the problem
parameterized by the pathwidth and treewidth of the input graph. (Please see
Section 2 for formal definitions of treewidth and pathwidth). We note that
Dominating Set parameterized by the treewidth admits an algorithm running in
time $3^{\sf tw}|V|^{\mathcal{O}(1)}$ [5]. In contrast to the above, we show
that such an algorithm cannot exist for MMDS.

###### Theorem 1.2

MMDS is W[1]-hard when parameterized by the pathwidth of the input graph.

We note that the pathwidth of a graph is at least as large as its treewidth,
and thus the above theorem implies that MMDS parameterized by the treewidth
does not admit any FPT algorithm. We prove Theorem 1.2 by demonstrating an
appropriate parameterized reduction from a well-known W[1]-hard problem called
Multi-Colored Clique (see [12] for its W[1]-hardness).

Next we study MMDS for split graphs, and prove the following theorem.

###### Theorem 1.3

MMDS is W[1]-hard on split graphs when parameterized by $k$.

We prove the above theorem by giving a parameterized reduction from Multi-
Colored Independent Set, which is known to be W[1]-hard [12]. Our reduction is
inspired by the known parameterized reduction from Multi-Colored Independent
Set to Dominating Set, where we carefully incorporate the membership
constraint and remove the size constraint on the dominating set. We would like
to note that Dominating Set is known to be W[2]-complete for split graphs
[24].

Next we study MMDS parameterized by the vertex cover number of the input graph
and show that it admits an FPT algorithm.

###### Theorem 1.4

MMDS admits an algorithm running in time
$2^{\mathcal{O}(\textbf{vc})}|V|^{\mathcal{O}(1)}$, where vc is the size of a
minimum-sized vertex cover of the input graph.

We prove the above theorem by exhibiting an algorithm which is obtained by
“guessing” the portion of the vertex cover that belongs to the solution, and
for the remainder of the portion, solving an appropriately created instance of
Integer Linear Programming.

To complement our Theorem 1.4, we obtain a matching algorithmic lower bound as
follows.

###### Theorem 1.5

Assuming ETH, MMDS does not admit an algorithm running in time
$2^{o({\textbf{vc}})}|V|^{\mathcal{O}(1)}$, where vc is the size of a minimum-
sized vertex cover of the input graph.

Related works. Kuhn et al. [19] introduced the “membership” variant, in a
spirit similar to what we have, for the Set Cover problem, called Minimum
Membership Set Cover (MMSC, for short). For the above problem, they obtained
several results, including $\NP$-completeness, an $\mathcal{O}(\ln n)$
approximation algorithm, and a matching approximation hardness result. A
special case of the MMSC problem is studied in [8] where the collection of
sets have _consecutive ones property_. In such a set system, the problem is
shown to be polynomial-time solvable. Narayanaswamy et al. [6] and recently,
Mitchell and Pandit [21] have studied the dual of the MMSC problem which is
the _Minimum Membership Hitting Set_ (MMHS) problem in various geometric
settings.

The problem Perfect Code is a variant of Dominating Set where (in addition to
the size constraint) we require the membership of each vertex in the
dominating set to be exactly one. Perfect Code is another well-studied variant
of Dominating Set, see for instance [1, 13, 15, 16, 17, 18, 22, 2]. Telle [25,
26] studied a variant of Dominating Set where two vectors $\sigma,\rho$ are
additionally given as input, and the membership of vertices in the dominating
set and outside this set needs to be determined by $\sigma$ and $\rho$,
respectively. They obtained several results with respect to parameterized
complexity of the above variant of Dominating Set. Also, Chapelle [3] studied
the above variant with respect to treewidth as the parameter and gave an
algorithm running in time $k^{\textbf{tw}}|V|^{\mathcal{O}(1)}$, where tw is
the treewidth of the input graph. MMDS with membership constraint $k$, is the
same as $[\sigma,\rho]$-Dominating Set, when $\sigma=[0,k-1]$ and
$\rho=[1,k]$, thus the problem also admits such an algorithm.

Chellali et al. [4] introduced a version called $[j,\ell]$-Dominating Set,
where we seek a dominating set where the membership of each vertex is at least
$j$ and at most $\ell$. They studied the above problem for the viewpoint of
combinatorial bounds on special graph classes like claw-free graphs,
$P_{4}$-free graphs, and caterpillars, for restricted values of $j$ and
$\ell$. Recently Meybodi et al. [20] studied the problems $[1,j]$-Dominating
Set and $[1,j]$-Total Dominating Set in the realm of parameterized complexity.
Though these problems involve constrained membership, unlike MMDS, they
require a membership constraint only on the open neighborhood of vertices.

##  2 Preliminaries

We recall in this section some notations and definitions used throughout this
article. For any two positive integers $x$ and $y$, by $[x,y]$ we mean the set
$\\{x,x+1,\ldots,y\\}$, and by $[x]$ we mean $[1,x]$. We assume that all our
graphs are simple and undirected. Given a graph $G=(V,E)$, $n$ represents the
number of vertices, and $m$ represents the number of edges. We denote an edge
between any two vertices $u$ and $v$ by $uv$. For a subset $S\subseteq V$, by
$G[S]$ we mean the subgraph of $G$ induced by $S$, and by $G-S$ we mean
$G[V\setminus S]$. For every vertex $u\in V$, by $N(u)$ we mean open
neighborhood of $u$, and by $N[u]$ we mean closed neighborhood of $u$.
Similarly, for any set $S\subseteq V$, $N(S)=\bigcup_{u\in S}N(u)\setminus S$
and $N[S]=\bigcup_{u\in S}N[u]$. Other than this, we follow the standard
graph-theoretic notations based on Diestel [7]. We refer to the recent books
of Cygan et al. [5] and Downey and Fellows [10] for detailed introductions to
parameterized complexity.

Treewidth and pathwidth. For an undirected graph $G=(V,E)$, a tree
decomposition of $G$ is a pair $(\mathcal{T},X)$, where $\mathcal{T}$ is a
tree and $X=\\{X_{\textbf{i}}\subseteq V\mid\textbf{i}\in V(\mathcal{T})\\}$
such that

  * •

$\bigcup_{\textbf{i}\in V(\mathcal{T})}X_{\textbf{i}}=V$,

  * •

for each edge $uv\in E$, there exists a node $\textbf{i}\in V(\mathcal{T})$
such that $u,v\in X_{\textbf{i}}$, and

  * •

for each $u\in V$, the set of nodes $\\{\textbf{i}\in V(\mathcal{T})\mid u\in
X_{\textbf{i}}\\}$ induces a connected subtree in $\mathcal{T}$.

The width of a tree decomposition $(\mathcal{T},X)$ is $\max_{\textbf{i}\in
V(\mathcal{T})}(|X_{\textbf{i}}|-1)$. The treewidth of $G$ is the minimum
width over all possible tree decompositions of $G$. A tree decomposition
$(\mathcal{T},X)$ is said to be a path decomposition if $\mathcal{T}$ is a
path. The pathwidth of a graph $G$ is the minimum width over all possible path
decompositions of $G$. Let $\textbf{pw}(G)$ and $\textbf{tw}(G)$ denote the
pathwidth and treewidth of the graph $G$, respectively. The pathwidth of a
graph $G$ is one less than the minimum clique number of an interval supergraph
$H$ which contains $G$ as an induced subgraph. It is well-known that the
maximal cliques of an interval graph can be linearly ordered such that for
each vertex, the maximal cliques containing it occur consecutively in the
linear order. This gives a path decomposition of the interval graph. A path
decomposition of the graph $G$ is the path decomposition of the interval
supergraph $H$ which contains $G$ as an induced subgraph. In our proofs we
start with the path decomposition of an interval graph and then reason about
the path decomposition of graphs that are constructed from it.

##  3 The MMDS problem on planar bipartite graphs is $\NP$-complete

We show that the MMDS problem is $\NP$-hard for $k=1$ even when restricted to
planar bipartite graphs. The $\NP$-hardness is proved by a reduction from
Planar Positive 1-in-3 SAT as follows. Let $\phi$ be a boolean formula with no
negative literals on $n$ variables $X=\\{x_{1},x_{2},\dots,x_{n}\\}$ having
$m$ clauses $C=\\{C_{1},C_{2},\dots,C_{m}\\}$. Further we consider the
restricted case when the graph encoding the variable-clause incidence is
planar. Such a boolean formula is naturally associated with a planar bipartite
graph $G_{\phi}=(C\cup X,E)$ where $X=\\{x_{1},x_{2},\dots,x_{n}\\}$,
$C=\\{C_{1},C_{2},\dots,C_{m}\\}$ and $E=\\{(x_{i},C_{j})~{}|~{}\text{variable
}x_{i}$ appears in the clause $C_{j}\\}$.

PP1in3SAT (Planar Positive 1-in-3 SAT)
Input : A boolean formula $\phi(X)$ without negative literals and that
$G_{\phi}$ is planar Decide: Does there exist an assignment of values
$a_{1},a_{2},\dots,a_{n}$ to the variables $x_{1},x_{2},\dots,x_{n}$ such that
exactly one variable in each clause is set to true?

It is known that PP1in3SAT is $\NP$-complete [23]. A reduction from PP1in3SAT
to the MMDS problem is shown to prove that the MMDS problem is $\NP$-hard.

######  Proof (Proof of Theorem 1.1 )

Given a set $S$, we can check the feasibility of the set $S$ to the instance
$(G,k)$ of the MMDS problem in polynomial time. Therefore, the MMDS problem is
in $\NP$. To prove that the MMDS problem is -hard, we present a reduction from
PP1in3SAT. Let $\phi$ be a positive 3-CNF formula such that $G_{\phi}$ is
planar. Now, construct a bipartite graph $\hat{G}_{\phi}$ as follows. For each
vertex $x_{i}\in G_{\phi}$, add an additional vertex $\hat{x}_{i}$ and connect
this vertex to the corresponding $x_{i}$ using an edge. Let
$\hat{X}=\\{\hat{x}_{1},\hat{x}_{2},\dots,\hat{x}_{n}\\}$. The resultant graph
$\hat{G}_{\phi}=\big{(}((X\cup\hat{X})\cup
C),E\cup\\{(x_{i},\hat{x}_{i}),1\leq i\leq n\\}\big{)}$ is also a planar
graph. We show that $\phi$ is satisfiable if and only if $\hat{G}_{\phi}$ has
a dominating set which hits the closed neighborhood of each vertex exactly
once. Given a set $S$, we can check the feasibility of the set $S$ to the
instance $(G,k)$ of the MMDS problem in polynomial time. Therefore, the MMDS
problem is in $\NP$. To prove that the MMDS problem is -hard, we present a
reduction from PP1in3SAT. Let $\phi$ be a positive 3-CNF formula such that
$G_{\phi}$ is planar. Now, construct a bipartite graph $\hat{G}_{\phi}$ as
follows. For each vertex $x_{i}\in G_{\phi}$, add an additional vertex
$\hat{x}_{i}$ and connect this vertex to the corresponding $x_{i}$ using an
edge. Let $\hat{X}=\\{\hat{x}_{1},\hat{x}_{2},\dots,\hat{x}_{n}\\}$. The
resultant graph $\hat{G}_{\phi}=\big{(}((X\cup\hat{X})\cup
C),E\cup\\{(x_{i},\hat{x}_{i}),1\leq i\leq n\\}\big{)}$ is also a planar
graph. We show that $\phi$ is satisfiable if and only if $\hat{G}_{\phi}$ has
a dominating set which hits the closed neighborhood of each vertex exactly
once.

Let $A=\\{a_{1},a_{2},\dots a_{n}\\}$ be a satisfying assignment for $\phi$,
such that exactly one variable is set to true in each clause. For the graph
$\hat{G}_{\phi}$ , construct a set $S\subseteq V$ such as
$S=\big{\\{}\\{x_{i}|a_{i}=1,~{}a_{i}\in~{}A\\}\cup\\{\hat{x}_{i}~{}|~{}a_{i}=0,~{}a_{i}\in~{}A\\},1\leq
i\leq n\big{\\}}$. Clearly, $S$ is a dominating set for $\hat{G}_{\phi}$.
Consider a clause vertex $c\in C$. Let the three variable vertices adjacent to
$c$ be $x,y$ and $z$, out of which only one will be assigned value 1 by the
satisfying assignment. Without loss of generality, let this be $y$. The vertex
$y$ will dominate $c$ and $\hat{y}$, and vertices $x$ and $z$ will be
dominated by $\hat{x}$ and $\hat{z}$ respectively. Therefore, the $S$ is an
MMDS of $\hat{G}_{\phi}$ for membership parameter $k=1$.

To prove the reverse direction, let $S$ be a dominating set for
$\hat{G}_{\phi}$ such that the closed neighborhood of each vertex is
intersected exactly once by $S$. Since the membership of each vertex in $S$ is
1, it follows that, for each clause $c\in C$, $c\notin S$, and exactly one
neighbor of $c$ is in $S$. Therefore, for each $i$, either $x_{i}\in S\text{
or }\hat{x}_{i}\in S$ Consider the truth assignment $A$ for $\phi$ as follows:
For each $x_{i}\in S$, assign $a_{i}=1$, and for each $x_{i}\notin S$, assign
$a_{i}=0$. As there is exactly one vertex $x\in S$ from every $c\in C$, only
one literal from every clause will be satisfied by $A$, and thus $A$ is a
satisfying assignment for $\phi$. Hence, the MMDS problem is -complete for
$k=1$ even on planar bipartite graphs.

Remark: The reduction also shows that the MMDS problem does not have a
polynomial time $(2-\epsilon)$ approximation algorithm unless $\P=\NP$. This
is because such an algorithm can solve the MMDS problem for $k=1$. Also, we
believe that starting with the hardness of planar 3-SAT variants in which each
variable occurs exactly 3 times [23], our reduction shows that the MMDS
problem on planar bipartite graphs of maximum degree 4 is -complete.

##  4 W[1]-hardness with respect to pathwidth

We prove Theorem 1.2 by a reduction from the Multi-Colored Clique problem to
the MMDS problem. It is well-known that the Multi-Colored Clique problem is
W[1]-hard for the parameter solution size [9].

Multi-Colored Clique Input: A positive integer $k$ and a $k$-colored graph
$G$. Parameter: $k$ Question: Does there exists a clique of size $k$ with one
vertex from each color class?

Let $(G=(V,E),k)$ be an instance of the Multi-Colored Clique problem. Let
$V=(V_{1},\ldots,V_{k})$ denote the partition of the vertex set $V$. By a
partition, we mean the set of all vertices of same color. We assume, without
loss of generality, $|V_{i}|=n$ for each $i\in[k]$. We usually use $n$ to
denote number of vertices in the input graph. However, we use $n$ here to
denote the number of vertices in each color class. For each $1\leq i\leq k$,
let $V_{i}=\\{u_{i,\ell}\mid 1\leq\ell\leq n\\}$.

###  4.1 Gadget based reduction from Multi-Colored Clique

For an input instance $(G,k)$ of the Multi-Colored Clique problem, the
reduction outputs an instance $(H,k^{\prime})$ of the MMDS problem where
$k^{\prime}=n+1$. The graph $H$ is constructed using two types of gadgets,
$\mathcal{D}$ and $I$ (illustrated in Figure 1). The gadget $I$ is the primary
gadget and the gadget $\mathcal{D}$ is secondary gadget that is used to
construct the gadget $I$.
Gadget of type $\mathcal{D}$. For two vertices $u$ and $v$, the gadget
$\mathcal{D}_{u,v}$ is an interval graph consisting of vertices $u$, $v$ and
$n+2$ additional vertices that form an independent set. The vertices $u$ and
$v$ are adjacent, and both $u$ and $v$ are adjacent to every other vertex. We
refer to the vertices $u$ and $v$ as heads of the gadget $\mathcal{D}_{u,v}$.
Intuitively, for any feasible solution $S$, and for any gadget
$\mathcal{D}_{u,v}$, either $u$ or $v$ should be in $S$. Otherwise, remaining
$n+2$ vertices must be in $S$ which contradicts the optimality of $S$ because
membership for both $u$ and $v$ is at least $n+2$.

###### Observation 4.1

The pathwidth of the gadget $\mathcal{D}$ is two. Indeed, it is an interval
graph with maximum clique of size three and thus, by definition, has pathwidth
2.

Gadget of type $I$. Let $n\geq 1$ be an integer. The gadget has two vertices
$h_{1}$ and $h_{2}$, and two disjoint sets: $A=\\{a_{1},\ldots,a_{n}\\}$ and
$D=\\{d_{1},\ldots,d_{n}\\}$. For each $i\in[n]$, vertices $a_{i}$ and $d_{i}$
are connected by the gadget $\mathcal{D}_{a_{i},d_{i}}$. Let $h_{2}$ and
$h_{1}$ be two additional vertices which are adjacent. The vertices in the
sets $A$ and $D$ are adjacent to $h_{2}$ and $h_{1}$, respectively. For each
$1\leq i\leq n$, $a_{i}$ and $h_{1}$ are connected by the gadget
$\mathcal{D}_{a_{i},h_{1}}$, and $d_{i}$ and $h_{2}$ are connected by the
gadget $\mathcal{D}_{d_{i},h_{2}}$. In the reduction a gadget of type $I$ is
denoted by the symbol $I$ and an appropriate subscript.

$A$$D$$h_{1}$$h_{2}$$u$$v$ Figure 1: To the left is the type-$I$ gadget for
$n=4$ and to the right is the type-$D$ gadget. The zigzag edges between
vertices $u$ and $v$ represent the gadget $\mathcal{D}_{u,v}$.

###### Claim 4.2

The pathwidth of a gadget type $I$ is at most four.

##### Proof:

We observe that the removal of the vertices $h_{1}$ and $h_{2}$ results in a
graph in which for each $i\in[n]$, there is a connected component consisting
$a_{i}$ and $d_{i}$ which are the heads of a gadget of type $\mathcal{D}$ and
they are both adjacent to $n+2$ vertices of degree 1. Each component is an
interval graph with a triangle as the maximum clique and from Observation 4.1
is of pathwidth 2. Let $(\mathcal{T}^{\prime},X^{\prime})$ be the path
decomposition of $I-\\{h_{1},h_{2}\\}$ with width two. Thus adding $h_{1}$ and
$h_{2}$ into all the bags of the path decomposition
$(\mathcal{T}^{\prime},X^{\prime})$ gives a path decomposition for the gadget
$I$, and thus the pathwidth of the gadget $I$ is at most 4. ∎

In the following parts, when we refer to a gadget we mean the primary gadget
$I$ unless the gadget $\mathcal{D}$ is specified. For each vertex and edge in
the given graph, our reduction has a corresponding gadget in the instance
output by the reduction.
Description of the reduction. For $1\leq i<j\leq k$, let $E_{i,j}$ denote the
set of edges with one end point in $V_{i}$ and the other in $V_{j}$, that is
$E_{i,j}=\\{xy\mid x\in V_{i},y\in V_{j}\\}$.
For each vertex and edge in $G$, the reduction uses a gadget of type $I$. For
each $1\leq i<j\leq k$, the graph $H$ has an induced subgraph $H_{i}$
corresponding to $V_{i}$, and has an induced subgraph $H_{i,j}$ for the edge
set $E_{i,j}$. We refer to $H_{i}$ as a vertex-partition block and $H_{i,j}$
as an edge-partition block. Inside block $H_{i}$, there is a gadget of type
$I$ for each vertex in $V_{i}$, and in the block $H_{i,j}$ is a gadget for
each edge in $E_{i,j}$. For a vertex $u_{i,x}$, $I_{x}$ denotes the gadget
corresponding to $u_{i,x}$ in the partition $V_{i}$, and for an edge $e$,
$I_{e}$ denotes the gadget corresponding to $e$. Finally, the blocks are
connected by the connector vertices which we describe below. We next define
the structure of a block which we denote by $B$. The definition of the block
applies to both the vertex-partition block and the edge-partition block.

A block $B$ consists of the following gadgets, additional vertices, and edges.

  * •

The block $B$ corresponding to the vertex-partition block $H_{i}$ for any
$i\in[k]$ is as follows: for each $\ell\in[n]$, add a gadget $I_{\ell}$ to the
vertex-partition block $H_{i}$, to represent the vertex $u_{i,\ell}\in V_{i}$.

  * •

The block $B$ corresponding to the edge-partition gadget $H_{i,j}$ for any
$1\leq i<j\leq k$ is as follows: for each $e\in E_{i,j}$, add a gadget $I_{e}$
in the edge-partition block $H_{i,j}$, to represent the edge $e$.

  * •

In addition to the gadgets, we add $(n+1)(n+3)+2$ vertices to the block $B$ as
follows (See Figure 2 in appendix): Let $C(B)$ denote the set
$\\{f,f^{\prime},c_{1},c_{2},\ldots,$ $c_{n+1},b_{1},b_{2},\ldots,$
$b_{(n+1)(n+2)}\\}$, which is the set of additional vertices that are added to
the block $B$. Let $C^{\prime}(B)$ denote the subset
$\\{c_{1},c_{2},\ldots,c_{n+1}\\}$. For each gadget $I$ in $B$, and for each
$t\in[n]$, $a_{t}$ in $I$ is adjacent to $f$, and the vertex $f$ is adjacent
to $f^{\prime}$. Further, the vertex $f^{\prime}$ is adjacent to each vertex
$c_{p}$ for $p\in[n+1]$. Finally, for each $p\in[n+1]$ and $(p-1)(n+2)<q\leq
p(n+2)$, $c_{p}$ is adjacent to $b_{q}$.

$C(H_{i})$$f$$A$$I_{1}$$I_{2}$$I_{n}$ Figure 2: Illustration of a vertex block
$H_{i}$ for some $i\in[k]$. An edge block $H_{i,j}$ for some $1\leq i<j\leq k$
will have $|E_{i,j}|$-many internal gadgets.

Next, we introduce the connector vertices to connect the edge-partition blocks
and vertex-partition blocks. Let
$R=\\{r_{i,j}^{i},s_{i,j}^{i},r_{i,j}^{j},s_{i,j}^{j}\mid 1\leq i<j\leq k\\}$
be the connector vertices. The blocks are connected based on the following
exclusive and exhaustive cases, and is illustrated in Figure 3:
For each $i\in[k]$, each $i<j\leq k$ and each $\ell\in[n]$, the edges are
described below.

  * •

for each $1\leq t\leq\ell$, the vertex $a_{t}$ in the gadget $I_{\ell}$ of
$H_{i}$ is adjacent to the vertex $s_{i,j}^{i}$

  * •

for each $\ell\leq t\leq n$, the vertex $a_{t}$ in the gadget $I_{\ell}$ of
$H_{i}$ is adjacent to the vertex $r_{i,j}^{i}$

For each $i\in[k]$, each $1\leq j<i$ and each $\ell\in[n]$,

  * •

for each $1\leq t\leq\ell$, the vertex $a_{t}$ in the gadget $I_{\ell}$ of
$H_{i}$ is adjacent to the vertex $s_{j,i}^{i}$

  * •

for each $\ell\leq t\leq n$, the vertex $a_{t}$ in the gadget $I_{\ell}$ of
$H_{i}$ is adjacent to the vertex $r_{j,i}^{i}$

For each $1\leq i<j\leq k$, and for each $e=u_{i,x}u_{j,y}\in E_{i,j}$,

  * •

for each $1\leq t\leq x$, the vertex $a_{t}$ in the gadget $I_{e}$ of
$H_{i,j}$ is adjacent to the vertex $r_{i,j}^{i}$

  * •

for each $x\leq t\leq n$, the vertex $a_{t}$ in the gadget $I_{e}$ of
$H_{i,j}$ is adjacent to the vertex $s_{i,j}^{i}$

  * •

for each $1\leq t\leq y$, the vertex $a_{t}$ in the gadget $I_{e}$ of
$H_{i,j}$ is adjacent to the vertex $r_{i,j}^{j}$

  * •

for each $y\leq t\leq n$, the vertex $a_{t}$ in the gadget $I_{e}$ of
$H_{i,j}$ is adjacent to the vertex $s_{i,j}^{j}$

$a_{1}$$A$$a_{x}$$I_{x}$$H_{i}$$a_{n}$$a_{1}$$A$$a_{y}$$I_{y}$$H_{j}$$a_{n}$$a_{n}$$A$$a_{x}$$I_{e}$$H_{i,j}$$a_{y}$$a_{1}$$s^{i}_{i,j}$$r^{i}_{i,j}$$s^{j}_{i,j}$$r^{j}_{i,j}$
Figure 3:  An illustration of the connector vertices $s_{i,j}^{i}$,
$r_{i,j}^{i}$, $s_{i,j}^{j}$ and $r_{i,j}^{j}$ connect the blocks $H_{i}$ and
$H_{i,j}$, and, $H_{j}$ and $H_{i,j}$ for some $1\leq i<j\leq k$. The edge $e$
represented in the gadget $I_{e}$ is $u_{i,x}u_{j,y}\in E_{i,j}$.

This completes construction of the graph $H$ with ${\cal O}(mn^{2})$ vertices
and ${\cal O}(mn^{3})$ edges. We next bound the pathwidth of the graph $H$ as
a polynomial function of $k$.

###### Claim 4.3

The pathwidth of a block $B$ is at most five.

##### Proof:

If we remove the vertex $f$ from the block $B$, then the resulting graph is a
disjoint collection of gadgets and a tree of height two. We know that the
pathwidth of a gadget is four from Claim 4.2, and the pathwidth of a tree of
height two is two. Let $(\mathcal{T}^{\prime},X^{\prime})$ be a path
decomposition of $B-\\{f\\}$ with pathwidth four. Thus adding $f$ into all
bags of $(\mathcal{T}^{\prime},X^{\prime})$ gives a path decomposition for the
block $B$, and thus the pathwidth of the block is at most five. ∎

###### Lemma 1

The pathwidth of the graph $H$ is at most $4{k\choose 2}+5$.

###### Proof

Removal of the connector vertices from $H$ results in a collection of disjoint
blocks. From Claim 4.3, the pathwidth of a block is five. Let
$(\mathcal{T}^{\prime},X^{\prime})$ be a path decomposition of $H-R$ with
pathwidth five. Therefore, adding all connector vertices to the path
decomposition $(\mathcal{T}^{\prime},X^{\prime})$ gives a path decomposition
for the graph $H$ with pathwidth at most $4{k\choose 2}+5$.

####  4.1.1 Properties of a feasible solution for the MMDS instance
$(H,k^{\prime})$.

Let $S$ be a feasible solution for the MMDS instance $(H,k^{\prime})$. We
state the following properties of the set $S$. In all the arguments below, we
crucially use the property that for each $u\in V(H)$, $M(u,S)\leq n+1$.

###### Claim 4.4

For each block $B$ in the graph $H$, $C^{\prime}(B)\subseteq S$.

##### Proof:

By construction of graph $H$, for each $1\leq p\leq n+1$, the vertex $c_{p}$
must be in the set $S$ since it has $n+2$ vertices of degree one as neighbors.
Otherwise, its membership will be at least $n+2$, contradicting that $S$ is a
feasible solution for $(H,k^{\prime})$. Hence the claim. ∎

###### Claim 4.5

For each block $B$ in $H$, the vertices $f$ and $f^{\prime}$ in $B$ are not in
the set $S$.

##### Proof:

We know that $f$ is made adjacent to $f^{\prime}$, and $f^{\prime}$ is
adjacent to each vertex in $C^{\prime}(B)$. From Claim 4.4, we know that
$C^{\prime}(B)$ is a subset of $S$. Thus, $n+1$ neighbors of $f^{\prime}$ is
in $S$. If either $f$ or $f^{\prime}$ is in the set $S$, then
$M(f^{\prime},S)$ is $n+2$. This contradicts the feasibility of the set $S$.
Hence the claim. ∎

###### Claim 4.6

For each gadget of type $I$ in each block $B$ in the graph $H$, either $A\cap
S=A$ or $A\cap S=\emptyset$.

##### Proof:

We prove this by contradiction. Assume that $\emptyset\subsetneq A\cap
S\subsetneq A$. Let $J=\\{j\in[n]\mid a_{j}\in S\\}$, that is $J$ is the index
of the elements in $A\cap S$. Note that by our premise $J$ is non-empty and it
is not all of $[n]$. Since $J$ is a strict subset of $[n]$, we observe that
the vertex $h_{1}$ is in $S$. This is because, for each $i\in[n]\setminus J$,
$h_{1}$ and $a_{i}$ is connected by the gadget of type $\mathcal{D}$. If both
$a_{i}$ and $h_{1}$ are not in $S$, then the $n+2$ neighbours in the gadget of
type $\mathcal{D}$ containing the edge $\\{a_{i},h_{1}\\}$ will be in $S$, and
thus $M(a_{i},S)$ and $M(h_{1},S)$ are both at least $n+2$. This violates the
hypothesis that for each $u\in V(H)$, $M(u,S)\leq n+1$. We now consider two
cases, one in which the vertex $h_{2}$ is in $S$ and the other in which
$h_{2}$ is not in $S$.
First, we consider $h_{2}\in S$. For each $i\in[n]$, by using the same
argument which we used for $a_{i}$ and $h_{1}$, it follows that at least one
of the $a_{i}$ or $d_{i}$ is in the set $S$ since $a_{i}$ and $d_{i}$ are both
in a gadget of type $\mathcal{D}$. Therefore, for each $i\in[n]\setminus J$,
the vertex $d_{i}$ is in $S$. That is $|D\cap S|\geq n-|J|$. Consequently,
using the fact that $h_{1}\in S$ and the premise that $h_{2}\in S$, it follows
that the membership of $h_{1}$ is

$M(h_{1},S)\geq|A\cap S|+|D\cap S|+2\geq|J|+n-|J|+2\geq n+2.$

This contradicts the feasibility of $S$.
Next we consider the case that $h_{2}$ is not in $S$. For each $i\in[n]$,
$d_{i}$ is in $S$ since $d_{i}$ and $h_{2}$ are in a gadget of type
$\mathcal{D}$. Then, the $N[h_{1}]=(A\cap S)\cup D\cup\\{h_{1}\\}$. Further,
we know that $J$ is a non-empty set, and thus, the membership of $h_{1}$ is

$M(h_{1},S)\geq|A\cap S|+|D|+1\geq|J|+n+1\geq n+2.$

Therefore, our assumption that that $A\subsetneq S$ and $A\cap S\neq\emptyset$
is wrong. Therefore, either the set $A$ is completely included in the set $S$
or completely excluded from the set $S$. ∎

###### Claim 4.7

For each block $B$ in the graph $H$, there exists a unique gadget of type $I$
in the block $B$ such that the set $A$ in the gadget is in $S$.

##### Proof:

The vertices $f$ and $f^{\prime}$ in $B$ are not in the solution $S$ due to
Claim 4.5. The Claim 4.6 states that either the set $A$ in any gadget is
completely included in the set $S$ or completely excluded in the set $S$. If
for each gadget in $B$, the set $A$ is not in $S$ then the vertex $f$ is not
dominated by $S$. This contradicts the feasibility of $S$. If the set $A$ of
at least two gadgets in the block $B$ are in the set $S$, then the membership
of $f$ will be $2n>n+1$. This contradicts the feasibility of $S$. Thus, there
exists an unique gadget $I$ in each block such that the set $A$ in $I$ is in
$S$. ∎

Using these properties in the following two lemmas, we prove the correctness
of the reduction.

###### Lemma 2

If $(G,k)$ is a YES-instance of the Multi-Colored Clique problem, then
$(H,k^{\prime})$ is a YES-instance of the MMDS problem.

###### Proof

Let $K=\\{u_{i,x_{i}}\mid i\in[k]\\}$ be a $k$-clique in $G$. That is, for
each $i\in[k]$, $x_{i}$-th vertex of the partition $V_{i}$ is in the clique.
Now we construct a feasible solution $S$ for the instance $(H,k^{\prime})$ of
the MMDS problem. The set $S$ consists of the following vertices. For each
$i\in[k]$,

  * •

for each $\ell\in[n]$ with $\ell\not=x_{i}$, add $D\cup\\{h_{1}\\}$ in the
gadget $I_{\ell}$ in the vertex-partition block $H_{i}$ to $S$, and

  * •

in the gadget $I_{x_{i}}$ in the vertex-partition block $H_{i}$, add
$A\cup\\{h_{2}\\}$ to $S$, and

  * •

add $C^{\prime}(H_{i})$ to $S$.

For each $1\leq i<j\leq k$,

  * •

for each edge $e\in E_{i,j}$ with $e\not=u_{i,x_{i}}u_{j,x_{j}}$, add
$D\cup\\{h_{1}\\}$ in the gadget $I_{e}$ the edge-partition block $H_{i,j}$ to
$S$, and

  * •

for the edge $e=u_{i,x_{i}}u_{j,x_{j}}$, add $A\cup\\{h_{2}\\}$ in the gadget
$I_{e}$ the edge-partition block $H_{i,j}$ to $S$, and

  * •

add $C^{\prime}(H_{i,j})$ to $S$.

We show that $S$ is a feasible solution to the MMDS problem in $H$ for
membership value $k^{\prime}=n+1$.

First we show that the set $S$ is a dominating set in $H$. In each gadget in
each block, we have added either $D\cup\\{h_{1}\\}$ or $A\cup\\{h_{2}\\}$ into
$S$. Therefore, in every gadget of type $\mathcal{D}$ at least one head is in
$S$. That is, $S$ dominates every vertex which is part of some gadget of type
$\mathcal{D}$. Since every vertex in a gadget of type $I$ is part of some
gadget of type $\mathcal{D}$, the gadget of type $I$ is dominated by $S$.
Thus, every gadget of type $I$ is dominated by $S$.

Then we consider the vertices outside any gadget of type $I$. In any block
$B$, this is the set $C(B)$. In each block $B$ in $H$, from Claim 4.7,
vertices in the set $A$ of exactly one gadget of type $I$ is in $S$. Each of
these vertices dominate $f$. All other vertices in the block which are outside
the gadgets are dominated by $C^{\prime}(B)$ which is a subset of $S$ by
definition. For $1\leq i<j\leq k$, consider a connector vertex pair
$(s_{i,j}^{i},r_{i,j}^{i})$ that connects the blocks $H_{i}$ and $H_{i,j}$.
Both vertices were made adjacent to the vertices in the set $A$ of each gadget
in the block $H_{i}$. Since $S$ contains the set $A$ in the gadget $I_{x_{i}}$
of $H_{i}$, both connector vertices are dominated. Thus all the connector
vertices are dominated by $S$. Therefore, $S$ is a dominating set of $H$.

Next we show that the membership of any vertex $u\in V(H)$ in $S$ is
$k^{\prime}$, that is, we show that $M(u,S)=n+1$. Observe that the vertices in
any gadget of type $I$ are solely dominated by the vertices of $S$ which are
inside the gadget. The maximum membership of $n+1$ is achieved by the vertices
$h_{1}$ and $h_{2}$ for any gadget $I$. Therefore, the membership of any
vertex in a gadget of type $I$ is $n+1$. In each block $B$, among the vertices
$C(B)$, the maximum membership of value $n+1$ is achieved by the vertices $f$
and $f^{\prime}$.

We next show crucially that the membership of the connector vertices is at
most $n+1$. For each $1\leq i<j\leq k$, consider the edge
$e=u_{i,x_{i}}u_{j,x_{j}}\in E_{i,j}$. By construction of the set $S$, we
picked the set $A$ only from the gadgets $I_{e}$ in $H_{i,j}$, $I_{x_{i}}$
from $H_{i}$, and $I_{x_{j}}$ from $H_{j}$. From the reduction and the
definition of $S$, it is clear that for all the other gadgets in a block, the
vertices in $S$ are not adjacent to the connector vertices. Therefore, the
$M(s_{i,j}^{i},S)$ is $x_{i}+(n-x_{i}+1)=n+1$, and $M(r^{i}_{i,j},S)$ is
$(n-x_{i}+1)+x_{i}=n+1$. Next, we consider the membership of
$s_{i,j}^{j}=x_{j}+(n-x_{j}+1)$ and the membership of $r_{i,j}^{j}$ is
$x_{j}+(n-x_{j}+1)=n+1$. These membership values can be seen clearly from
Figure 3. Hence, the membership of any vertex in $V(H)$ is $n+1$. Thus, the
instance $(H,k^{\prime})$ is a YES-instance of the MMDS problem.

###### Lemma 3

If $(H,k^{\prime})$ is a YES-instance of the MMDS problem, then $(G,k)$ is a
YES-instance of the Multi-Colored Clique problem.

###### Proof

Let $S$ be a feasible solution to the instance ($H,k^{\prime}$) of the MMDS
problem. For each $i\in[k]$, let $I_{x_{i}}$ be the unique gadget for some
$x_{i}\in[n]$, where the set $A$ of $I_{x_{i}}$ is in $S$. For each $1\leq
i<j\leq k$, let $I_{e}$ be the unique gadget for some
$e=u_{i,x_{i}^{\prime}}u_{j,x_{j}^{\prime}}\in E_{i,j}$, where the set $A$ of
$I_{e}$ is in $S$. The existence of such gadgets are ensured by Claim 4.7. Let
$K=\\{u_{i,x_{i}}\mid i\in[k]\\}$. We show that the set $K$ is a clique in $G$
as follows. Observe that we picked one vertex from each partition $V_{i}$ for
$i\in[k]$. Next we show that for each $1\leq i<j\leq k$, there is an edge
$u_{i,x_{i}}u_{j,x_{j}}\in E(G)$. Let $i,j\in[k]$ such that $i<j$. The vertex
$s_{i,j}^{i}$ is adjacent to $x_{i}$ vertices in $I_{x_{i}}$ from $H_{i}$, and
$n-x_{i}^{\prime}+1$ vertices in $I_{e}$ from $H_{i,j}$. The vertex
$r_{i,j}^{i}$ is adjacent to $n-x_{i}+1$ vertices in $I_{x_{i}}$ from $H_{i}$,
and $x_{i}^{\prime}$ vertices in $I_{e}$ from $H_{i,j}$. Then, the membership
of the connector vertices $r^{i}_{i,j}$ and $s^{i}_{i,j}$ in $S$ are

$M(r^{i}_{i,j},S)\geq(n-x_{i}+1)+(x_{i}^{\prime})\geq
n+x_{i}^{\prime}-x_{i}+1\textrm{ , and}$ $M(s^{i}_{i,j},S)\geq
x_{i}+(n-x_{i}^{\prime}+1)\geq n+x_{i}-x_{i}^{\prime}+1.$

Further, the membership of the vertices is at least one and at most $n+1$,
that is $1\leq M(r_{i,j}^{i},S),M(s_{i,j}^{i},S)\leq n+1$. Therefore, $n+1\geq
n+x_{i}^{\prime}-x_{i}+1\Longrightarrow x_{i}\geq x_{i}^{\prime}$ and $n+1\geq
n+x_{i}-x_{i}^{\prime}+1\Longrightarrow x_{i}^{\prime}\geq x_{i}$. Thus, we
have $x_{i}=x_{i}^{\prime}$. Similarly, we will get $x_{j}=x_{j}^{\prime}$.
Therefore, by construction of the graph $H$, there is an edge
$u_{i,x_{i}}u_{j,x_{j}}\in E(G)$. Thus, the set $K$ is a feasible solution for
the instance ($G,k$) of the Multi-Colored Clique problem.

Thus, we conclude the section with the proof of Theorem 1.2.

######  Proof (Proof of Theorem 1.2 )

On an instance $(G,k)$ of Multi-Colored Clique the reduction constructs
$(H,k^{\prime}=n+1)$ in polynomial time. From Lemma 1 we know that the
pathwidth of $H$ is a quadratic function of $k$. Finally, from Lemma 2 and
Lemma 3 it follows that the MMDS instance $(H,k^{\prime})$ output by the
reduction is equivalent to the Multi-Colored Clique instance $(G,k)$ that was
input to the reduction. Since Multi-Colored Clique is known to be W[1]-hard
for the parameter $k$, it it follows that the MMDS problem is W[1]-hard with
respect to the parameter pathwidth of the input graph.

##  5 W[1]-hardness in split graphs

In this section we prove that MMDS is W[1]-hard on split graphs when
parameterized by the membership parameter $k$. We prove this result by
demonstrating a parameterized reduction from Multi-Colored Independent Set
(MIS) to Minimum Membership Dominating Set. Multi-Colored Independent Set
requires finding a colorful independent set of size $k$ and is known to be
W[1]-hard for the parameter solution size [12]

Multi-Colored Independent Set Input: A positive integer $k$, and a $k$-colored
graph $G$. Parameter: $k$ Question: Does there exist an independent set of
size $k$ with one vertex from each color class?

Let $(G=(V,E),k)$ be an instance of the Multi-Colored Independent Set problem.
Let $V=(V_{1},\ldots,V_{k})$ be the partition of the vertex set $V$, where
vertices in set $V_{i}$ belong to the $i^{th}$ color class, $i\in[k]$. We now
show how to construct a split graph $H=(V^{\prime}\cup
V^{\prime\prime},E^{\prime})$ such that if $(G,k)$ is a YES instance, then $H$
has a dominating set with maximum membership $k$. $V^{\prime}$ refers to the
clique partition of $H$ and $V^{\prime\prime}$ consists of the partition
containing a set of independent vertices.

Construction of graph $H=(V^{\prime}\cup V^{\prime\prime},E^{\prime})$:

$u$$v$$w$
$V_{1}$$V_{2}$$V_{k}$$U_{1}$$U_{2}$$U_{k}$$k+1$$x_{uv}$$D_{12}$$D_{pq}$${k\choose
2}$ Figure 4: Construction of graph $H$

For each vertex in $V$ we introduce a vertex in the clique $V^{\prime}$ as in
the input instance. Additionally we add a vertex $w$ to $V^{\prime}$. Edges
are added among each pair of vertices in $V^{\prime}$. The set
$V^{\prime\prime}$ in $H$ is an independent set, and it consists of a set of
vertices denoted by $U$, a set of vertex sets denoted by
$\mathcal{D}=\\{D_{pq}\mid p,q\in[k],p<q\\}$. The vertex set $U$ comprises a
partition of $k$ vertex sets, $U=\\{U_{i}\mid i\in[k]\\}$, and $|U_{i}|=k+1$.
For each edge between a vertex $u\in V_{p}$ and $v\in V_{q}$ in $G$, we
introduce a vertex $x_{uv}$ in the set $D_{pq}$. Thus, the vertex set of $H$,
$V(H)=V^{\prime}\cup V^{\prime\prime}$, where $V^{\prime}$ induces a clique
and $V^{\prime\prime}$ induces an independent set.
The remaining edges, other than those in clique $V^{\prime}$, are described as
follows: $V_{i}\uplus U_{i}$ forms a complete bipartite graph, vertex $w$ is
made adjacent to all vertices in the set $D$, each vertex $x_{uv}\in D_{pq}$
is made adjacent to every vertex in $V_{p}\setminus\\{u\\}$ and
$V_{q}\setminus\\{v\\}$. The above construction is depicted in Figure 4. Next
we show the correctness of the reduction from the instance $(G,k)$ of MIS to
the instance $(H,k)$ of MMDS.

###### Lemma 4

If $(G,k)$ is a YES instance of the Multi-Colored Independent Set problem then
$(H,k)$ is a YES instance of the MMDS problem.

###### Proof

Let $(G,k)$ be a YES instance of Multi-Colored Independent Set , and
$S=\\{v_{1},\ldots,v_{k}\\}$ be a solution to $(G,k)$ where $v_{i}\in
V_{i},~{}i\in[k]$. We show that the vertices in $V(H)$ that correspond to the
set $S$, denoted by $S^{\prime}$, form a dominating set in $H$ with membership
value $k$. We start by showing that $S^{\prime}$ is a dominating set for $H$.
Observe that since $S^{\prime}\subset V^{\prime}$ and $V^{\prime}$ induces a
clique, $S^{\prime}$ dominates all vertices in the set $V^{\prime}$. For each
$i\in[k]$, the vertex $v_{i}\in S^{\prime}$ dominates all vertices in $U_{i}$,
since $V_{i}$ and $U_{i}$ together form a complete bipartite graph. Consider a
vertex $x_{uv}\in D_{pq}$ where $u\in V_{p},v\in V_{q}$, which represents the
edge $(u,v)\in G$. The vertex $x_{uv}$ is connected to every vertex in
$V_{p}\setminus\\{u\\}$ and $V_{q}\setminus\\{v\\}$. Since $S$ is an
independent set, both $u$ and $v$ cannot belong to $S$. Without loss of
generality, let $u\in S$, then $\exists v^{\prime}_{v^{\prime}\in
S^{\prime}}\in V_{q}\setminus\\{v\\}$ which dominates $x_{uv}$. This holds
true for all vertices in the set $\\{x_{uv}\in D_{pq}\mid 1\leq p,q\leq
k,p\neq q\\}$. Thus $S^{\prime}$ is a dominating set for $H$.

Secondly, we observe that the membership constraint $k$ is satisfied by the
dominating set $S$ due to the fact that $|S|=k$. It follows that for all
vertices $v$ in $H$, $N[v]\cap S\leq k$. Hence it is proved that if $(G,k)$ is
a YES instance of the Multi-Colored Independent Set problem then $(H,k)$ is a
YES instance of the MMDS problem.

###### Lemma 5

If $(H,k)$ is a YES instance of the MMDS problem then $(G,k)$ is a YES
instance of the Multi-Colored Independent Set problem.

###### Proof

Let $(H,k)$ be a YES instance and $S$ be a feasible solution for MMDS in the
graph $H$ with membership value $k$. Since $S$ is a $k$ membership dominating
set of $H$, $S$ exhibits the following properties.

  1. 1.

$|S\cap V_{i}|=1,i\in[1,k]$.
At least one vertex from each of the sets $V_{i}$ must belong to $S$.
Otherwise in order to dominate $U_{i}$, all $k+1$ vertices from $U_{i}$ need
to be included in $S$, thus violating the membership constraint for the
vertices in $V_{i}$. Observe that $S$ contains exactly one vertex from each
set $V_{i}$, $i\in[k]$. As the $V_{i}$’s are a part of the clique $V^{\prime}$
in $H$, if more than one vertex from a $V_{i}$ is included in the solution,
then $|V^{\prime}\cap S|>k$ and the membership constraint of vertices in
$V^{\prime}$ will be violated. Therefore exactly one vertex from each $V_{i}$
is included in $S$.

  2. 2.

$w\notin S$.
The vertex $w$ is part of the clique $V^{\prime}$ and $S$ already contains $k$
vertices from $V^{\prime}$ and any more vertices from $V^{\prime}$ will
violate the membership constraint of vertices in $V^{\prime}$.

  3. 3.

$|U_{i}\cap S|=0,i\in[1,k]$.
Every vertex in $U_{i},i\in[1,k]$ is already dominated by a vertex in the
corresponding $V_{i}$, and has membership value $1$. If a vertex from
$U_{i},i\in[1,k]$ is included in $S$, all vertices in $V_{i}$ will have
membership $k+1$ leading to a violation of the membership constraint for them.

  4. 4.

$|S\cap D_{pq}|=0,p,q\in[1,k],p<q$.
Every vertex $x_{uv}\in D_{pq}$ is adjacent to $V_{p}\setminus u$ and
$V_{q}\setminus v$, $u\in V_{p},v\in V_{q}$. As $V^{\prime}\cap S=k$, adding
any vertex $x_{uv}\in D_{pq}$ to $S$ will violate the membership constraint of
vertices in $V_{p}\setminus u$ and $V_{q}\setminus v$. Even if $|V_{p}|=1$ or
$|V_{q}|=1$, adding $x_{uv}$ to $S$ will violate the membership constraint of
$w\in V^{\prime}$.

It follows from the above properties of $S$ that $S$ contains a vertex from
each of the vertex sets $V_{i}$, $i\in[k]$. Let
$S=\\{v_{1},v_{2},\ldots,v_{k}~{}|~{}v_{i}\in V_{i},1\leq i\leq k\\}$. We now
prove that the vertices corresponding to $S$ in $G$, say $S^{\prime}$, form an
independent set. Suppose not. This implies that $\exists v_{i},v_{j}\in S$
such that $v_{i}v_{j}\in E(H)$. Without loss of generality, let $v_{i}\in
V_{i},v_{j}\in V_{j}$. Consider the vertex $x_{v_{i}v_{j}}\in D_{ij}$. Due to
the construction of graph $H$, the vertex $x_{v_{i}v_{j}}$ is not adjacent to
$v_{i}$ and $v_{j}$, and hence not dominated. This is a contradiction to the
fact that $S$ is a dominating set for $H$. Therefore, vertices $v_{i},v_{j}\in
S,i,j\in[1,k]$ cannot have an edge between them. Hence it is proved that
$S^{\prime}$ is a solution of size $k$ for the given instance of Multi-Colored
Independent Set implying that $(G,k)$ is a YES instance.

######  Proof (Proof of Theorem 1.3 )

Lemma 4 and Lemma 5 along with the fact that Multi-Colored Independent Set is
W[1]-hard [12] proves that MMDS is W[1]-hard parameterized by $k$, the
membership.

##  6 Parameterizing MMDS by Vertex cover

First, we show that MMDS is FPT parameterized by vertex cover number, vc. We
then show that conditioned on the truth of the ETH, MMDS does not have a
subexponential algorithm in the size of vertex cover.

###  6.1 MMDS is FPT parameterized by vertex cover

In order to design an FPT algorithm parameterized by the size of a vertex
cover of the input graph, we construct an FPT-time Turing reduction from MMDS
to Integer Linear Programming (ILP, See Appendix for formal definition). In
the reduced instance the number of constraints is at most twice the size of a
minimum vertex cover. We then use the recent result by Dvořák et al. [11]
which proves that ILP is FPT parameterized by the number of constraints. The
following theorem directly follows from Corollary 9 of [11].

Integer Linear Programming Input : A matrix $A\in\mathbb{Z}^{m\times\ell}$ and
a vector $b\in\mathbb{Z}^{m}$. Parameter : $m$ Question : Is there a vector
$x\in\mathbb{Z}^{\ell}$ such that $A\cdot x\leq b$?

######  Theorem 6.1 (Corollary 9, [11])

ILP is FPT in the number of constraints and the maximum number of bits for one
entry.

FPT time Turing reduction from MMDS to ILP: Let $(G,k)$ be the input instance
of MMDS. Compute a minimum vertex cover of $G$, denoted by $C$, in time FPT in
$|C|$ [5]. Let $I$ denote the maximum independent set $V\setminus C$. The
following lemma is crucial to the correctness of the reduction.

###### Lemma 6

Let $D$ be a $k$ membership dominating set of $G$. Let $C_{1}=D\cap C$,
$I_{1}=I\setminus(N(C_{1})\cap I)$, and $R=N(C_{1})\cap I\cap D$. Then,
$I_{1}\subseteq D$, and $C\setminus(N[C_{1}]\cup N(I_{1}))$ is dominated by
$R$.

###### Proof

The outline is that $I_{1}$ cannot be dominated by any other vertex other than
by itself. Further, $R\subseteq D$ is the the only vertices which can dominate
$C\setminus(N[C_{1}]\cup N(I_{1}))$. Hence the lemma.

As a consequence of this lemma, it is clear that the choice of $C_{1}$
immediately fixes $I_{1}$. Thus, to compute the set $D$, the task is to
compute $R$. We pose this problem as the constrained MMDS problem. A CMMDS
problem instance is a 4-tuple $(G,k,C,C_{1})$ where $C$ is a vertex cover and
$C_{1}$ is a subset of $C$. The decision question is whether there is a $k$
membership dominating set $D$ of $G$ such that $D\cap C=C_{1}$. From Lemma 6,
we know that given an instance of $(G,k,C,C_{1})$, we know that $C_{1}$
immediately fixes $I_{1}\subseteq I=V\setminus C$. Thus, to compute $D$, we
need to compute $R$ as defined in Lemma 6. We now describe the ILP formulation
to compute $R$ once $C_{1}$ (and thus $I_{1}$) is fixed. Since $R$ is a subset
of $I\setminus I_{1}$, it follows that the variables correspond to vertices in
$I\setminus I_{1}$ which do not already have $k$ neighbors in $C_{1}$; we use
$I_{e}$ to denote this set. It can be immediately checked if $C_{1}\cup I_{1}$
can be part of a feasible solution- we check that for no vertex is the
intersection of its closed neighborhood greater than $k$. We now assume that
this is the case, and specify the linear constraints. The linear constraints
in the ILP are associated with the vertices in $C$. For each vertex in $C$
there are at most two constraints- if $v$ is in $C\setminus(N[C_{1}]\cup
N(I_{1}))$, then at least one neighbor and at most $k$ neighbors from $I_{e}$
must be chosen into $R$. On the other hand, for $v\in(N[C_{1}]\cap C)\cup
N(I_{1})$, we have the constraint that at most $k$ neighbors must be in
$C_{1}\cup I_{1}\cup R$. The choice of variables in $I_{e}$ does not affect
any other vertex in $I$, and thus there are no costraints among the vertices
in $I$. To avoid notation, we assume that an instance of CMMDS$(G,k,C,C_{1})$,
also denotes the ILP.

###### Lemma 7

The CMMDS problem on an instance $(G,k,C,C_{1})$ can be solved in time which
is FPT in the size of the vertex cover.

###### Proof

Since the instance $(G,k,C,C_{1})$ uniquely specifies the ILP for the choice
of $R$, it follows that this ILP has ${\cal O}(|C|)$ constraints. From Theorem
6.1, we know that the ILP can be specified in FPT time with $|C|$ as the
parameter, and this proves the Lemma.

######  Proof (Proof of Theorem 1.4 )

Given an input instance $(G,k)$ of MMDS, we first compute a minimum vertex
cover $C$ in FPT time (in size of the cover as the parameter) using any of the
well-known methods (see the book by Cygan et al. [5], for example). Let
$I=V\setminus C$ be the independent set. Now we iterate through each subset
$C_{1}$ of $C$, and check if it can be extended to a $k$ membership dominating
set $D$ such that $D\cap C=C_{1}$. For each such $C_{1}$, we know from Lemma 6
that $I_{1}=I\setminus(N(C_{1})\cap I)$ must be added to the solution, if one
exists. For each subset $C_{1}\subseteq C$, we assume that $C_{1}\cup I_{1}$
goes into the solution set. Then, we solve CMMDS on the instance
$(G,k,C,C_{1})$ to check if there is an $R\subseteq I_{e}$ such that
$C_{1}\cup I_{1}\cup R$ in a $k$ membership dominating set. From Lemma 7, we
know that this check can be solved in FPT time. It thus follows that MMDS is
FPT when parameterized by the size of vertex cover.

###  6.2 Lower bound assuming ETH

We show that there is no sub-exponential-time parameterized algorithm for MMDS
when the parameter is _the vertex cover number_ , using a reduction from
$3$-SAT. By the ETH, we know that $3$-SAT does not have a sub-exponential-time
algorithm, and thus the reduction proves the lower bound for MMDS.

######  Proof (Proof of Theorem 1.5 )

Let $\phi$ be a boolean formula on $n$ variables
$X=\\{x_{1},x_{2},\dots,x_{n}\\}$ having $m$ clauses
$C=\\{C_{1},C_{2},\dots,C_{m}\\}$. We construct a graph $G=(V,E)$ from the
input formula $\phi$ such that $\phi$ has a satisfying assignment if and only
if $G$ has a $k$ membership dominating set.
Construction of graph $G$

Figure 5: Construction for reduction from $3$-SAT to MMDS.

We construct a variable gadget and a clause gadget. For each variable
$x_{i},~{}1\leq i\leq n$ in $\phi$, create two vertices $v_{x_{i}}$ and
$v_{\overline{x_{i}}}$, denoting its literals, with an edge between them. Make
both $v_{x_{i}}$ and $v_{\overline{x_{i}}}$ adjacent to $k+1$ degree-two
vertices labelled $a_{i}^{j}:1\leq j\leq k+1$ and another set of $k-1$
vertices $b_{i}^{j}:1\leq j\leq k-1$. Each $b_{i}^{j}$ is in turn adjacent to
$k+1$ pendant vertices $d_{i,j}^{t}:1\leq t\leq k+1$. This completes the
variable gadget for a variable $x_{i}$.
For each clause $C_{l}:1\leq l\leq m$, create a vertex $v_{C_{l}}$. For each
clause $C_{l}$, make $v_{C_{l}}$ adjacent to a vertex $Y$. $Y$ is again
connected to $k$ more vertices $u_{q}:1\leq q\leq k$. Each $u_{q}$ is in turn
adjacent to $k+1$ pendant vertices $r_{q}^{p}:1\leq p\leq k+1$. This is the
clause gadget for graph $G$.
Finally, create edges between clause vertices and those literal vertices which
are in the clause. The reduction is illustrated in Figure 5.

###### Claim 6.2

The vertex cover number of graph $G$ is $(n+1)(k+1)$.

###### Proof

A minimum vertex cover of graph $G$ contains
$\big{\\{}v_{x_{i}},v_{\overline{x_{i}}}~{}|~{}1\leq i\leq n\big{\\}}$,
$\big{\\{}b_{i}^{j}~{}|~{}1\leq j\leq k-1,1\leq i\leq n\big{\\}}$, $Y$ and
$\big{\\{}u_{q}~{}|~{}1\leq q\leq k\big{\\}}$ to cover all edges. Therefore
$|VC(G)|=2n+n(k-1)+k+1=(n+1)(k+1)$. When $k$ is ${\cal O}(1)$, $|VC(G)|={\cal
O}(n)$.

###### Lemma 8

If $\phi$ has a satisfying assignment then $G$ has a dominating set with
membership value $k$.

###### Proof

Let $A:\\{x_{i}|i\in[n]\\}\to\\{0,1\\}$ be a satisfying assignment for $\phi$.
Now, we construct a feasible solution $S$ for the MMDS problem as follows.

  * •

For each $i\in[n]$,

    * –

add $v_{x_{i}}$ if $A[x_{i}]=1$ or $v_{\overline{x_{i}}}$ if $A[x_{i}]=0$ to
$S$.

    * –

add $\\{b_{i}^{j}~{}|~{}1\leq j\leq k-1\\}$ to $S$.

  * •

Add $\\{u_{q}~{}|~{}1\leq q\leq k\\}$ to $S$.

We claim that $S$ is a dominating set for $G$ and has membership at most $k$.
First, we show that $S$ is a dominating set. In the variable gadget, exactly
one among $v_{x_{i}}$ or $v_{\overline{x_{i}}}$, and all of $b_{i}^{j}$’s are
in $S$. They dominate all other vertices in the variable gadget. It is given
that $A$ is a satisfying assignment. i.e, for each clause $C_{l}$, there is at
least one literal assigned 1. Therefore each vertex $v_{C_{l}}$ is dominated
by the vertex corresponding to the literal assigned 1 in $C_{l}$. The vertices
$Y$ and $\\{r_{q}^{p}~{}|~{}p\in[k+1],q\in[k]\\}$ are dominated by
$\\{u_{q}:q\in[k]\\}$.
Next we show that the membership of any vertex in $G$ is at most $k$. In each
variable gadget, maximum membership of $k$ is attained by the vertices
$v_{x_{i}}$ and $v_{\overline{x_{i}}}$. Each clause vertex has membership at
most 3. Vertex set $Y$ has the maximum membership of $k$ in clause gadget.

###### Lemma 9

If $G$ has a dominating set with membership value $k$, then $\phi$ has a
satisfying assignment.

###### Proof

Let $S$ be feasible solution for MMDS in graph $G$. Then $S$ has the following
properties:

  * •

In every variable gadget for a variable $x_{i},~{}1\leq i\leq n$,

    * –

$\\{b_{i}^{j}~{}|~{}1\leq j\leq k-1\\}$ must be there in $S$. If there is any
$b_{i}^{j}\notin S$, all $d_{i,j}^{t}:1\leq t\leq k+1$ should be included in
$S$ which will violate the membership property by making the membership of
$b_{i}^{j}$ to be $k+1$.

    * –

Either $v_{x_{i}}$ or $v_{\overline{x_{i}}}$ must be there in $S$, in order to
dominate $\\{a_{i}^{j}~{}|~{}1\leq j\leq k+1\\}$. Note that both $v_{x_{i}}$
and $v_{\overline{x_{i}}}$ together cannot be there in $S$ since it violates
the membership property of both vertices.

  * •

$\\{u_{q}:1\leq q\leq k\\}\in S$. If any $u_{q}\notin S$, all $r_{q}^{p}:1\leq
p\leq k+1$ must be included in $S$ which violates the membership property for
$u_{q}$.

  * •

$\\{v_{C_{l}},~{}1\leq l\leq m\\}\notin S$, since inclusion of any clause
vertex $v_{C_{l}}$ violates the membership property for vertex $Y$.

  * •

Out of the three literal vertices in any clause $C_{l}$, atleast one will be
included in $S$ in order to dominate corresponding clause vertex $v_{C_{l}}$.

It follows from the above properties that atleast one literal vertex from
every clause will be included in $S$ and assigning 1 to those literals makes a
satisfying assignment for the boolean formula $\phi$.

From Lemma 8 and Lemma 9, it follows that the $3$-SAT can be reduced to MMDS
parameterized by vertex cover number. Therefore a
$2^{o(\textbf{vc}(G))}n^{{\cal O}(1)}$ algorithm for MMDS will give a
$2^{o(n)}$ algorithm for $3$-SAT which is a violation of ETH. Hence it is
proved that there is no sub-exponential algorithm for MMDS when parameterized
by vertex cover number.

##  7 Conclusion

In this paper we study the parameterized complexity of the Minimum Membership
Dominating Set problem, which requires finding a dominating set such that each
vertex in the graph is dominated minimum possible times. We start our analysis
by showing that in spite of having no constraints on the size of the solution,
unlike Dominating Set, MMDS turns out to be W[1]-hard when parameterized by
pathwidth (and hence treewidth). We further show that the problem remains
W[1]-hard for split graphs when the parameter is the size of the membership.
For general graphs we prove that MMDS is FPT when parameterized by the size of
vertex cover. Finally, we show that assuming ETH, the problem does not admit a
sub-exponential algorithm when parameterized by the size of vertex cover, thus
showing our FPT algorithm to be optimal. There are many related open problems
that are yet to be explored. One such problem is analyzing the complexity of
MMDS in chordal graphs. Other directions involve structural parameterization
of MMDS with respect to other parameters such as maximum degree, distance to
bounded degree graphs, bounded genus and maximum number of leaves in a
spanning tree. We have got an idea from an anonymous reviewer from IPEC 2021
that a W[2] hardness could be proved. We are working on it.

## References

  * [1] Biggs, N.: Perfect codes in graphs. Journal of Combinatorial Theory, Series B 15(3), 289 – 296 (1973)
  * [2] Cesati, M.: Perfect code is w[1]-complete. Information Processing Letters 81(3), 163–168 (2002). https://doi.org/https://doi.org/10.1016/S0020-0190(01)00207-1, https://www.sciencedirect.com/science/article/pii/S0020019001002071
  * [3] Chapelle, M.: Parameterized complexity of generalized domination problems on bounded tree-width graphs. CoRR abs/1004.2642 (2010)
  * [4] Chellali, M., Haynes, T.W., Hedetniemi, S.T., McRae, A.A.: [1, 2]-sets in graphs. Discret. Appl. Math. 161(18), 2885–2893 (2013)
  * [5] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)
  * [6] Dhannya, S.M., Narayanaswamy, N.S., Ramya, C.: Minimum membership hitting sets of axis parallel segments. In: Computing and Combinatorics - 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, Proceedings. pp. 638–649 (2018)
  * [7] Diestel, R.: Graph Theory, 4th Edition, Graduate texts in mathematics, vol. 173. Springer (2012)
  * [8] Dom, M., Guo, J., Niedermeier, R., Wernicke, S.: Minimum membership set covering and the consecutive ones property. In: Algorithm Theory - SWAT 2006, 10th ScandinavianWorkshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings. pp. 339–350 (2006)
  * [9] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science, Springer (1999)
  * [10] Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer (2013). https://doi.org/10.1007/978-1-4471-5559-1, https://doi.org/10.1007/978-1-4471-5559-1
  * [11] Dvořák, P., Eiben, E., Ganian, R., Knop, D., Ordyniak, S.: Solving integer linear programs with a small number of global variables and constraints. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17. pp. 607–613 (2017). https://doi.org/10.24963/ijcai.2017/85, https://doi.org/10.24963/ijcai.2017/85
  * [12] Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science 410(1), 53–61 (2009). https://doi.org/https://doi.org/10.1016/j.tcs.2008.09.065, https://www.sciencedirect.com/science/article/pii/S0304397508007329
  * [13] Fellows, M.R., Hoover, M.N.: Perfect domination. Australas. J Comb. 3, 141–150 (1991), http://ajc.maths.uq.edu.au/pdf/3/ocr-ajc-v3-p141.pdf
  * [14] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)
  * [15] Huang, H., Xia, B., Zhou, S.: Perfect codes in cayley graphs. SIAM J. Discret. Math. 32(1), 548–559 (2018)
  * [16] Kratochvíl, J.: Perfect codes over graphs. J. Comb. Theory, Ser. B 40(2), 224–228 (1986)
  * [17] Kratochvíl, J.: Perfect Codes in Graphs and Their Powers. PhD dissertation(in czech), Charles University, Prague (1987)
  * [18] Kratochvíl, J., Krivánek, M.: On the computational complexity of codes in graphs. In: Chytil, M., Janiga, L., Koubek, V. (eds.) Mathematical Foundations of Computer Science 1988, MFCS’88, Carlsbad, Czechoslovakia, August 29 - September 2, 1988, Proceedings. Lecture Notes in Computer Science, vol. 324, pp. 396–404. Springer (1988). https://doi.org/10.1007/BFb0017162, https://doi.org/10.1007/BFb00
  * [19] Kuhn, F., von Rickenbach, P., Wattenhofer, R., Welzl, E., Zollinger, A.: Interference in cellular networks: The minimum membership set cover problem. In: Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings. pp. 188–198 (2005), https://doi.org/10.1007/11533719_21
  * [20] Meybodi, M.A., Fomin, F.V., Mouawad, A.E., Panolan, F.: On the parameterized complexity of [1, _j_]-domination problems. Theor. Comput. Sci. 804, 207–218 (2020). https://doi.org/10.1016/j.tcs.2019.11.032, https://doi.org/10.1016/j.tcs.2019.11.032
  * [21] Mitchell, J.S.B., Pandit, S.: Minimum membership covering and hitting. In: WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Guwahati, India, February 27 - March 2, 2019, Proceedings. pp. 394–406 (2019)
  * [22] Mollard, M.: On perfect codes in cartesian products of graphs. Eur. J. Comb. 32(3), 398–403 (2011). https://doi.org/10.1016/j.ejc.2010.11.007, https://doi.org/10.1016/j.ejc.2010.11.007
  * [23] Mulzer, W., Rote, G.: Minimum-weight triangulation is np-hard. J. ACM 55(2), 11:1–11:29 (2008)
  * [24] Raman, V., Saurabh, S.: Short cycles make w-hard problems hard: Fpt algorithms for w-hard problems in graphs with no short cycles. Algorithmica 52(2), 203–225 (Aug 2008)
  * [25] Telle, J.A.: Complexity of domination-type problems in graphs. Nord. J. Comput. 1(1), 157–171 (1994)
  * [26] Telle, J.A.: Vertex Partitioning Problems: Characterization, Complexity and Algorithms on Partial K-Trees. Ph.D. thesis, USA (1994), uMI Order No. GAX95-02388