The Balanced Satisfactory Partition Problem

Abstract

The Satisfactory Partition problem asks whether it is possible to partition the vertex set of a given undirected graph into two parts such that each vertex has at least as many neighbours in its own part as in the other part. The Balanced Satisfactory Partition problem is a variant of the above problem where the two partite sets are required to have the same cardinality. Both problems are known to be NP-complete but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity. The two main results of the paper are the following: (1) The Satisfactory Partition problem and its balanced version are fixed parameter tractable (FPT) when parametrized by neighbourhood diversity, (2) The Balanced Satisfactory Partition problem is W[1]-hard when parametrized by treewidth.

S. Maity—The author’s research was supported in part by the Science and Engineering Research Board (SERB), Govt. of India, under Sanction Order No. MTR/2018/001025.

1 Introduction

Gerber and Kobler [7] introduced the problem of deciding if a given graph has a vertex partition into two non-empty parts such that each vertex has at least as many neighbours in its part as in the other part. A graph satisfying this property is called partitionable. For example, complete graphs, star graphs, complete bipartite graphs with at least one part having odd size are not partitionable, where as some graphs are easily partitionable: cycles of length at least 4, trees that are not star graphs [4].

Given a graph $G=(V,E)$ and a subset $S\subseteq V(G)$, we denote by $d_S(v)$ the degree of a vertex $v\in V$ in G[S], the subgraph of G induced by S. For $S=V$, the subscript is omitted, hence d(v) stands for the degree of v in G. In this paper, we study the parameterized complexity of Satisfactory Partition and Balanced Satisfactory Partition problems. We define these problems as follows:

A variant of this problem where the two parts have equal size is:

Given a partition $(V_1,V_2)$, we say that a vertex $v\in V_i$ is satisfied if $d_{V_i}(v)\ge d_{V_{3-i}}(v)$, or equivalently if $d_{V_i}(v)\ge \lceil \frac{d(v)}{2} \rceil$. A graph admitting a non-trivial partition where all vertices are satisfied is called satisfactory partitionable, and such a partition is called satisfactory partition. For the standard concepts in parameterized complexity, see the recent textbook by Cygan et al. [5]. We now review the concept of a tree decomposition, introduced by Robertson and Seymour in [12].

Definition 1

A tree decomposition of a graph G is a pair $(T,\{X_{t}\}_{t\in V(T)})$, where T is a tree and each node t of the tree T is assigned a vertex subset $X_{t} \subseteq V(G)$, called a bag, such that the following conditions are satisfied:

• 1. Every vertex of G is in at least one bag.

• 2. For every edge $uv \in E(G)$, there exists a node $t\in T$ such that bag $X_t$ contains both u and v.

• 3. For every $u \in V(G)$, the set $\{t\in V(T)~|~u\in X_t\}$ induces a connected subtree of T.

It is important to note that a graph may have several different tree decomposition. Similarly, the same tree decomposition can be valid for several different graphs. Every graph has a trivial tree decomposition for which T has only one vertex including all of V. However, this is not effective for the purpose of solving problems.

Definition 2

The width of a tree decomposition is defined as $width(T)=max_{t \in V(T)}|X_{t}|-1$ and the treewidth tw(G) of a graph G is the minimum width among all possible tree decomposition of G.

The reason for subtracting 1 in the above definition for width is so that we can define forests as having treewidth 1.

Our Results: Our main results are the following:

• The Satisfactory Partition and Balanced Satisfactory Partition problems are fixed parameter tractable (FPT) when parameterized by neighbourhood diversity.

• The Balanced Satisfactory Partition problem is W[1]-hard when parameterized by treewidth.

Related Work: In the first paper on this topic, Gerber and Kobler [7] considered a generalized version of this problem by introducing weights for the vertices and edges and showed that a general version of the problem is strongly NP-complete. For the unweighted version, they presented some sufficient conditions for the existence of a solution. This problem was further studied in [1, 6, 8]. The Satisfactory Partition problem is NP-complete and this implies that Balanced Satisfactory Partition problem is also NP-complete via a simple reduction in which we add new dummy vertices and dummy edges to the graph [2, 4]. Both problems are solvable in polynomial time for graphs with maximum degree at most 4 [4]. They also studied generalizations and variants of this problem when a partition into $k \ge 3$ nonempty parts is required. Bazgan, Tuza, and Vanderpooten [1, 3] studied an “unweighted" generalization of Satisfactory Partition, where each vertex v is required to have at least s(v) neighbours in its own part, for a given function s representing the degree of satisfiability. Obviously, when $s=\lceil \frac{d}{2}\rceil$, where d is the degree function, we obtain satisfactory partition. They gave a polynomial-time algorithm for graphs of bounded treewidth which decides if a graph admits a satisfactory partition, and gives such a partition if it exists.

2 FPT Algorithm Parameterized by Neighbourhood Diversity

In this section, we present an FPT algorithm for the Satisfactory Partition and Balanced Satisfactory Partition problems parameterized by neighbourhood diversity. We say two vertices u and v in G have the same type if and only if $N_G(u)\!\!\setminus \!\!\{v\}=N_G(v)\!\setminus \!\{u\}$. The relation of having the same type is an equivalence relation. The idea of neighbourhood diversity is based on this type structure.

Definition 3

[10]. The neighbourhood diversity of a graph $G=(V,E)$, denoted by $\mathtt{nd}(G)$, is the least integer k for which we can partition the set V of vertices into k classes, such that all vertices in each class have the same type.

If neighbourhood diversity of a graph is bounded by an integer k, then there exists a partition $\{ C_1, C_2,\ldots , C_k\}$ of V(G) into k type classes. It is known that such a minimum partition can be found in linear time using fast modular decomposition algorithms [14]. Notice that each type class could either be a clique or an independent set by definition. For algorithmic purpose it is often useful to consider a type graph H of graph G, where each vertex of H is a type class in G, and two vertices $C_i$ and $C_j$ are adjacent iff there is complete bipartite clique between these type classes in G. It is not difficult to see that there will be either a complete bipartite clique or no edges between any two type classes. In this section, we prove the following theorem:

Theorem 1

The Satisfactory Partition problem is fixed-parameter tractable when parameterized by the neighbourhood diversity.

Let G be a connected graph such that $\mathtt{nd}(G)=k$. Let $C_1,\ldots ,C_k$ be the partition of V(G) into sets of type classes. We assume $k\ge 2$ since otherwise the problem becomes trivial. We define $I_1=\{ C_i~|~C_i\subseteq V_1\}$, $I_2=\{ C_i~|~C_i\subseteq V_2\}$ and $I_3=\{ C_i~|~C_i\cap V_1\ne \emptyset , C_i\cap V_2, \ne \emptyset \}$ where $(V_1,V_2)$ is a satisfactory partition. We next guess if $C_i$ belongs to $I_1$, $I_2$, or $I_3$. There are at most $3^k$ possibilities as each $C_i$ has three options: either in $I_1$, $I_2$, or $I_3$. We reduce the problem of finding a satisfactory partition to an integer linear programming optimization with k variables. Since integer linear programming is fixed parameter tractable when parameterized by the number of variables [11], we conclude that our problem is FPT when parameterized by the neighbourhood diversity.

ILP Formulation: Given $I_1, I_2$ and $I_3$, our goal here is to answer if there exists a satisfactory partition $(V_1,V_2)$ of G with all vertices of $C_i$ are in $V_1$ if $C_i\in I_1$, all vertices of $C_i$ are in $V_2$ if $C_i\in I_2$, and vertices of $C_i$ are distributed amongst $V_1$ and $V_2$ if $C_i\in I_3$. For each $C_i$, we associate a variable: $x_i$ that indicates $|V_1\cap C_i|=x_i$. Because the vertices in $C_i$ have the same neighbourhood, the variables $x_i$ determine $(V_1,V_2)$ uniquely, up to isomorphism. We now characterize a satisfactory partition in terms of $x_i$. Note that $x_i=n_i=|C_i|$ if $C_i\in I_1$; $x_i=0$ if $C_i\in I_2$.

Lemma 1

Let C be a clique type class. Then C is either in $I_1$ or $I_2$.

Proof

Let C be a clique type class. Let $u,v\in C$. Let us denote $N(u)\setminus \{v\}= N(v)\!\!\setminus \!\!\{u\}$ by S and let $a=|S\cap V_1|$ and let $b=|S\cap V_2|$. The satisfiability of u implies $a\ge b+1$ and the satisfiablity of v implies $b\ge a+1$. Clearly, u and v cannot be satisfied simultaneously, as the two inequalities imply $a\ge b+1\ge a+2$, a contradiction. This proves the lemma.

Now we consider the following four cases:

Case 1: Suppose v belongs to a clique type class $C_j$ in $I_1$. Then the number of neighbours of v in $V_1$, that is,

$$d_{V_1}(v) =\sum \limits _{i:C_i\in N_H[C_j] \cap I_1}{n_i} +\Big (\sum \limits _{i:C_i\in N_H[C_j] \cap I_3}{x_i}\Big ) -1.$$

The number of neighbours of v in $V_2$, that is,

$$ d_{V_2}(v) =\sum \limits _{i: C_i\in N_H(C_j)\cap I_2}{n_i}+ \sum \limits _{i: C_i\in N_H[C_j] \cap I_3}{(n_i-x_i)}.$$

Therefore, vertex v is satisfied if and only if

$$\begin{aligned} \sum \limits _{i:C_i\in N_H[C_j] \cap I_1}{n_i} +\sum \limits _{i:C_i\in N_H[C_j] \cap I_3}{2x_i}&\ge 1+ \sum \limits _{i: C_i\in N_H(C_j)\cap I_2}{n_i}+ \sum \limits _{i:C_i\in N_H[C_j] \cap I_3}{n_i} \end{aligned}$$

(1)

Case 2: Suppose v belongs to a clique type class $C_j$ in $I_2$. Then similarly, v is satisfied if and only if

$$\begin{aligned} \sum \limits _{i:C_i\in N_H[C_j] \cap I_2}{n_i} +\sum \limits _{i:C_i\in N_H[C_j] \cap I_3}{n_i}&\ge 1+ \sum \limits _{i: C_i\in N_H(C_j)\cap I_1}{n_i}+ \sum \limits _{i:C_i\in N_H[C_j] \cap I_3}{2x_i} \end{aligned}$$

(2)

Case 3: Suppose v belongs to an independent type class $C_j$ in $V_1$, that is, $C_j\in I_1\cup I_3$. Then the number of neighbours of v in $V_1$, that is,

$$ d_{V_1}(v) =\sum \limits _{i:C_i\in N_H(C_j) \bigcap I_1}{n_i} +\sum \limits _{i:C_i\in N_H(C_j) \bigcap I_3}{x_i}. $$

Note that if $C_j\in I_3$, then only $x_j$ vertices of $C_j$ are in $V_1$ and the the remaining $y_j$ vertices of $C_j$ are in $V_2$. The number of neighbours of v in $V_2$, that is,

$$ d_{V_2}(v) =\sum \limits _{i: ~ C_i\in N_H(C_j)\bigcap I_2}{n_i}+ \sum \limits _{i:~C_i\in N_H(C_j) \bigcap I_3}{(n_i-x_i)}. $$

Therefore, v is satisfied if and only if

$$\begin{aligned} \sum \limits _{i:C_i\in N_H(C_j) \bigcap I_1}{n_i} +\sum \limits _{i:C_i\in N_H(C_j) \bigcap I_3}{2x_i}&\ge \sum \limits _{i: C_i\in N_H(C_j)\bigcap I_2}{n_i}+ \sum \limits _{i:C_i\in N_H(C_j) \bigcap I_3}{n_i} \end{aligned}$$

(3)

Case 4: Suppose v belongs to an independent type class $C_j$ in $V_2$, that is, $C_j\in I_2\cup I_3$. Similarly, vertex v is satisfied if and only if

$$\begin{aligned} \sum \limits _{i:C_i\in N_H(C_j) \bigcap I_2}{n_i} +\sum \limits _{i:C_i\in N_H(C_j) \bigcap I_3}{n_i} \ge \sum \limits _{i: C_i\in N_H(C_j)\bigcap I_1}{n_i}+ \sum \limits _{i:C_i\in N_H(C_j) \bigcap I_3}{2x_i} \end{aligned}$$

(4)

We now formulate ILP formulation of satisfactory partition, for given $I_1, I_2$ and $I_3$. The question is whether there exist $x_j$ under the conditions $x_j=n_j$ if $C_j\in I_1$, $x_j=0$ if $C_j\in I_2$, $x_j\in \{1,2,\ldots , n_j-1\}$ if $C_j\in I_3$ and the additional conditions described below:

• Inequality 1 for all clique type classes $C_j\in I_1$

• Inequality 2 for all clique type classes $C_j\in I_2$

• Inequality 3 for all independent type classes $C_j\in I_1$

• Inequality 4 for all independent type classes $C_j\in I_2$

• $$\begin{aligned} \sum \limits _{C_i\in N_H(C_j) \bigcap I_2}{n_i} +\sum \limits _{C_i\in N_H(C_j) \bigcap I_3}{n_i} = \sum \limits _{C_i\in N_H(C_j)\bigcap I_1}{n_i}+ \sum \limits _{C_i\in N_H(C_j) \bigcap I_3}{2x_i} \end{aligned}$$

  for all independent type classes $C_j\in I_3$.

For Balanced Satisfactory Partition problem, we additionally ask that

$$\sum _{i:C_i\in I_1} {n_i} +\sum _{i:C_i\in I_3}{x_i}=\sum _{i:C_i\in I_3}{(n_i-x_i)}+\sum _{i:C_i\in I_2}{n_i}. $$

Solving the ILP: Lenstra [11] showed that the feasibility version of p-ILP is FPT with running time doubly exponential in p, where p is the number of variables. Later, Kannan [9] designed an algorithm for p-ILP running in time $p^{O(p)}$.

p-Variable Integer Linear Programming Feasibility (p -ILP): Let matrices $A\in \ Z^{m\times p}$ and $b\in \ Z^{p\times 1}$ be given. The question is whether there exists a vector $x\in \ Z ^{p\times 1}$ satisfying the m inequalities, that is, $A\cdot x\le b$. We use the following result:

Lemma 2

[9, 11]. p–ILPcan be solved using $O(p^{2.5p+o(p)}\cdot L)$ arithmetic operations and space polynomial in L. Here L is the number of bits in the input.

In the formulation for Satisfactory Partition problem, we have at most k variables. The value of any variable in the integer linear programming is bounded by n, the number of vertices in the input graph. The constraints can be represented using $O(k^2 \log {n})$ bits. Lemma 2 implies that we can solve the problem with the given guess $I_1,I_2$ and $I_3$ in FPT time. There are at most $3^k$ choices for $(I_1,I_2,I_3$), and the ILP formula for a guess can be solved in FPT time. Thus Theorem 1 holds.

3 Hardness of Balanced Satisfactory Partition Parameterized by Treewidth

In this section, we prove the following theorem:

Theorem 2

The Balanced Satisfactory Partition problem is W[1]-hard when parameterized by the treewidth of the graph.

We introduce several variants of Balanced Satisfactory Partition that we require in our proofs. The problem Balanced Satisfactory Partition$^{\text{ S }}$ generalizes Balanced Satisfactory Partition where some vertices are forced to be in the second part $V_2$. This variant can be formalized as follows:

Balanced Satisfactory Partition$^{\text{ FS }}$ is a further generalization where some vertices are forced to be in the first part $V_1$ and some other vertices are forced to be in the second part $V_2$. This variant can be formalized as follows:

Finally, we introduce the generalization Balanced Satisfactory Partition$^{\text{ FSC }}$ in which we are also given a subset of “complementary pairs" of vertices and feasible solutions are only those for which neither $V_1$ nor $V_2$ contains a complementary pair.

Let $G=(V,E)$ be an undirected and edge weighted graph, where V, E, and w denote the set of nodes, the set of edges and a positive integral weight function $w:~E\rightarrow Z^{+}$, respectively. An orientation $\varLambda$ of G is an assignment of a direction to each edge $\{u,v\}\in E(G)$, that is, either (u, v) or (v, u) is contained in $\varLambda$. The weighted outdegree of u on $\varLambda$ is $w_{\text{ out }}^u=\sum _{(u,v)\in \varLambda }w(\{u,v\})$. We define Minimum Maximum Outdegree problem as follows:

It is known that Minimum Maximum Outdegree is W[1]-hard when parameterized by the treewidth of the input graph [13]. To prove Theorem 2, we give a 4-step reduction. In the first step of the reduction, we reduce Minimum Maximum Outdegree to Balanced Satisfactory Partition$^{\text{ FSC }}$. In the second step of the reduction we reduce the Balanced Satisfactory Partition$^{\text{ FSC }}$ to Balanced Satisfactory Partition$^{\text{ FS }}$. In the third step of the reduction we reduce the Balanced Satisfactory Partition$^{\text{ FS }}$ to Balanced Satisfactory Partition$^{\text{ S }}$. Finally we reduce Balanced Satisfactory Partition$^{\text{ S }}$ to Balanced Satisfactory Partition. To measure the treewidth of a Balanced Satisfactory Partition$^{\text{ FSC }}$ instance, we use the following definition. Let $I=(G, V_{\triangle }, V_{\square }, C)$ be a Balanced Satisfactory Partition$^{\text{ FSC }}$ instance. The primal graph $G^{\prime }$ of I is defined as follows: $V(G^{\prime })=V(G)$ and $E(G^{\prime })=E(G)\cup C$.

Lemma 3

The Balanced Satisfactory Partition$^{\text{ FSC }}$ is W[1]-hard when parameterized by the treewidth of the primal graph.

Proof

Let $G=(V,E,w)$ and a positive integer r be an instance of Minimum Maximum Outdegree. We construct an instance of Balanced Satisfactory Partition$^{\text{ FSC }}$ as follows. An example is given in Figure 1. For each vertex $v\in V(G)$, we introduce a set of new vertices $H_v=\{h_1^{v\triangle }, \dots , h_{2r}^{v\triangle }\}$. For each edge $(u,v)\in E(G)$, we introduce the set of new vertices $V_{uv}=\{u^v_1, \ldots , u^v_{w(u,v)}\}$, $V^{\prime }_{uv}=\{{u^{\prime v}_1}, \ldots , u^{\prime v}_{w(u,v)}\}$, $V_{vu}=\{v^u_1, \ldots , v^u_{w(u,v)}\}$, $V^{\prime }_{vu}=\{{v^{\prime u}_1}, \ldots , v^{\prime u}_{w(u,v)}\}$, $V^{\square }_{uv}=\{u^{v\square }_1, \ldots , u^{v\square }_{w(u,v)}\}$, $V^{\prime \square }_{uv}=\{{u^{\prime v\square }_1}, \ldots , u^{\prime v\square }_{w(u,v)}\}$, $V^{\square }_{vu}=\{v^{ u\square }_1, \ldots , v^{u\square }_{w(u,v)}\}$, $V^{\prime \square }_{vu}=\{{v^{\prime u\square }_1}, \ldots , v^{\prime u\square }_{w(u,v)}\}$. Let $\omega =\sum \limits _{(u,v)\in E}{w(u,v)}$. Finally we add a set $V_0$ of $8\omega +|V|(2r+1)-4$ isolated vertices. We now define the graph $G^{\prime }$ with

$$\begin{aligned} V(G^{\prime })&=V(G) \bigcup \limits _{v\in V(G)}H_v \bigcup \limits _{(u,v)\in E(G)}(V_{uv}\cup V_{uv}^{\square } \cup V_{vu}\cup V_{vu}^{\square })\\&\bigcup \limits _{(u,v)\in E(G)}(V^{\prime }_{uv}\cup V_{uv}^{\prime \square } \cup V^{\prime }_{vu}\cup V_{vu}^{\prime \square }) \bigcup V_0 \end{aligned}$$

and

$$\begin{aligned} E(G^{\prime })&= \big \{(v,h)~|~v\in V(G), h\in H_v\big \} \bigcup \Big \{ (u,x) ~|~ (u,v)\in E(G), x\in V_{uv}\cup V_{uv}^{\square }\Big \}\\&\bigcup \Big \{(x,v)~|~ (u,v)\in E(G), x \in V_{vu}\cup V_{vu}^{\square }\Big \}\\&\bigcup \Big \{ (u_i^v,u_i^{\prime v}), (u_i^{v\square },u_i^{\prime v\square }), (v_i^u,v_i^{\prime u}),(v_i^{u\square },v_i^{\prime u\square })~|~(u,v)\in E(G), 1\le i \le w(u,v)\Big \}. \end{aligned}$$

The number of vertices in $V(G^{\prime })\setminus V_0$ is $8\omega +|V|(2r+1)$. We define the complementary vertex pairs

$$C=\Big \{(u_i^{\prime v}, v_i^{\prime u}),(u_{i+1}^{\prime v}, v_i^{\prime u}), (u_i^{v}, v_i^{\prime u}), (u_i^{\prime v}, v_i^{u})~|~ (u,v)\in E(G), 1\le i\le w(u,v)\Big \}$$

Complementary vertex pairs are shown in dashed lines in Fig. 1. Finally we define $V_{\triangle }=V(G)\bigcup _{v\in V(G)}H_v$ and $V_{\square }=\bigcup _{(u,v)\in E(G)}(V_{uv}^{\square } \cup V_{uv}^{\prime \square }\cup V_{vu}^{\square }\cup V_{vu}^{\prime \square })$. We use I to denote $(G^{\prime }, V_{\triangle }, V_{\square },C)$ which is an instance of Balanced Satisfactory Partition$^{\text{ FSC }}$.

Clearly, it takes polynomial time to compute I. We now prove that the treewidth of the primal graph $G^{\prime }$ of I is bounded by a function of the treewidth of G. We do so by modifying an optimal tree decomposition $\tau$ of G as follows:

• For every edge (u, v) of G, there is a node in $\tau$ whose bag B contains both u and v; add to this node a chain of nodes $1,2,\ldots ,w(u,v)-1$ where the bag of node i is $B\cup \{u_i^v, u_i^{\prime v}, v_{i}^{\prime u}, v_{i}^{u}, u_{i+1}^{ v}, u_{i+1}^{\prime v}, v_{i+1}^{\prime u}, v_{i+1}^{ u} \}$.

• For every edge (u, v) of G, there is a node in $\tau$ whose bag B contains u; add to this node a chain of nodes $1,2,\ldots ,w(u,v)$ where the bag of node i is $B\cup \{u_i^{v \square }, u_i^{\prime v \square }\}$.

• For every edge (u, v) of G, there is a node in $\tau$ whose bag B contains v and add to this node a chain of nodes $1,2,\ldots ,w(u,v)$ where the bag of node i is $B\cup \{v_i^{u \square }, v_i^{\prime u \square }\}$.

• For every vertex v of G, there is a node in $\tau$ whose bag B contains v and add to this node a chain of nodes $1,2,\ldots ,2r$ where the bag of node i is $B\cup \{h_i^{v\triangle }\}$.

Clearly, the modified tree decomposition is a valid tree decomposition of the primal graph of I and its width is at most the treewidth of G plus eight.

Fig. 1.

Result of our reduction on a Minimum Maximum Outdegree instance G with $r=2$. The graph G long with its orientation is shown at the left; and $G^{\prime }$ is shown at the right. Complementary vertex pairs are shown using dashed lines. The vertices in the first part of satisfactory partition $(V_1,V_2)$ of $G^{\prime }$ are shown in red for the given orientation of G. Here $\omega =6$ and $V_0$ contains 64 isolated vertices. The vertices of $V_0$ are distributed among $V_1$ and $V_2$ so that $(V_1,V_2)$ becomes balanced satisfactory partition.

Let D be the directed graph obtained by an orientation of the edges of G such that for each vertex the sum of the weights of outgoing edges is at most r. Consider the partition of $G^{\prime }-V_0$

$$V_1=V_{\triangle } \bigcup _{(u,v)\in E(D)}(V_{vu}\cup V_{vu}^{\prime })=V(G)\bigcup _{v\in V(G)}H_v \bigcup _{(u,v)\in E(D)}(V_{vu}\cup V_{vu}^{\prime })$$

and

$$V_2=\bigcup _{(u,v)\in E(D)}(V_{uv}\cup V^{\prime }_{uv}\cup V_{uv}^{\square }\cup V^{\prime \square }_{uv} ) \bigcup _{(u,v)\in E(D)}(V_{vu}^{\square }\cup V^{\prime \square }_{vu}).$$

To prove that $(V_1,V_2)$ is a satisfactory partition, first we prove that $d_{V_1}(x)\ge d_{V_2}(x)$ for all $x\in V_1$. If x is a vertex in $H_v$ or $V_{vu}\cup V_{vu}^{\prime }$, then clearly all neighbours of x are in $V_1$, hence x is satisfied. Suppose $x\in V(G)$. Let $w_{\text{ out }}^x$ and $w_{\text{ in }}^x$ denote the sum of the weights of outgoing and incoming edges of vertex x, respectively. Hence $d_{V_1}(x)=2r+w_{\text{ in }}^x$ and $d_{V_2}(x)=2w_{\text{ out }}^x+w_{\text{ in }}^x$ in $G^{\prime }$. This shows that x is satisfied as $w_{\text{ out }}^x\le r$. Now we prove that $d_{V_2}(x)\ge d_{V_1}(x)$ for all $x\in V_2$. If x is a vertex in $V_{uv}\cup V^{\square }_{uv}\cup V^{\square }_{vu}$ then x has one neighbour in $V_1$ and one neighbour in $V_2$. If $x\in V^{\prime }_{uv}\cup V^{\prime \square }_{uv}\cup V^{\prime \square }_{vu}$ then x has one neighbour in $V_2$ and no neighbours in $V_1$. Thus the vertices in $V_2$ are satisfied. The isolated vertices of $V_0$ are distributed among $V_1$ and $V_2$ so that it becomes balanced satisfactory partition for $G^{\prime }$.

Conversely, suppose $(V_1,V_2)$ is a balanced satisfactory partition of $G^{\prime }$. That is $|V_1|=|V_2|=8\omega +(2r+1)|V|-2$. Then $V_1^{\prime }=V_1\setminus V_0$ and $V_2^{\prime }=V_2\setminus V_0$ form a satisfactory partition of $G^{\prime }-V_0$. For every $(u,v)\in E(G)$, either $V_{uv}\cup V^{\prime }_{uv}\in V_1^{\prime }$ or $V_{vu}\cup V^{\prime }_{vu}\in V_1^{\prime }$ due to the complementary vertex pairs. We define a directed graph D by $V(D)=V(G)$ and

$$\begin{aligned} E(D)=\Big \{ (u,v) ~|~V_{vu}\cup V^{\prime }_{vu}\in V_1^{\prime }\Big \}\bigcup \Big \{ (v,u) ~|~V_{uv}\cup V^{\prime }_{uv}\in V_1^{\prime }\Big \}. \end{aligned}$$

Suppose there is a vertex x in D for which $w_{\text{ out }}^x>r$. Clearly $x\in V_1^{\prime }$. We know $d_{V_1^{\prime }}(x)=2r+w_{\text{ in }}^x$ and $d_{V_2^{\prime }}(x)=2w_{\text{ out }}^x+ w_{\text{ in }}^x$. Then $d_{V_2^{\prime }}(x)> d_{V_1^{\prime }}(x)$, as by assumption $w_{\text{ out }}^x >r$, a contradiction to the fact that $(V_1^{\prime },V_2^{\prime })$ is a satisfactory partition of $G^{\prime }-V_0$. Hence $w_{\text{ out }}^x\le r$ for all $x\in V(D)$.

Next we prove the following result which eliminates complementary pairs.

Lemma 4

The Balanced Satisfactory Partition$^{\text{ FS }}$ problem, parameterized by the treewidth of the graph, is W[1]-hard.

Proof

Let $I=(G,V_{\square }, V_{\triangle }, C)$ be an instance of Balanced Satisfactory Partition$^{\text{ FSC }}$. Consider the primal graph of I, that is the graph $G^p$ where $V(G^p)=V(G)$ and $E(G^p)=E(G)\cup C$. From this we construct an instance $I^{\prime }=(G^{\prime },V^{\prime }_{\square }, V^{\prime }_{\triangle })$ of Balanced Satisfactory Partition$^{\text{ FS }}$ problem. For each $(a,b)\in C$ in the primal graph $G^p$, we introduce two new vertices $\triangle ^{ab}$ and $\square ^{ab}$ and four new edges in $G^{\prime }$. We now define the $G^{\prime }$ with $V(G^{\prime })=V(G) \bigcup _{(a,b)\in C} \{\triangle ^{ab}, \square ^{ab}\}$ and $E(G^{\prime })=E(G) \bigcup _{(a,b)\in C} \Big \{(a,\triangle ^{ab}), (a, \square ^{ab}), (b,\triangle ^{ab}), (b,\square ^{ab}) \Big \}.$ Finally, we define the sets $V^{\prime }_{\triangle }=V_{\triangle } \bigcup _{(a,b)\in C}\{\triangle ^{ab}\}$ and $V^{\prime }_{\square }=V_{\square } \bigcup _{(a,b)\in C}\{\square ^{ab}\}$. We illustrate our construction in Fig. 2. It is easy to see that we can compute $I^{\prime }$ in polynomial time and its treewidth is linear in the treewidth of I. The following holds for every solution $(V^{\prime }_1,V^{\prime }_2)$ of $I^{\prime }$: $V^{\prime }_1$ contains $\triangle ^{ab}$ for every $(a,b)\in C$, so it must also contain a or b. It cannot contain both a and b for any $(a,b)\in C$, because $\square ^{ab}\in V^{\prime }_2$. Restricting $(V^{\prime }_1, V^{\prime }_2)$ to the original vertices thus is a solution to I. Conversely, for every solution $(V_1,V_2)$ of I, the partition $(V^{\prime }_1,V^{\prime }_2)$ where $V_1^{\prime }=V_1\bigcup _{(a,b)\in C}\{\triangle ^{ab}\}$ and $V_2^{\prime }=V_2\bigcup _{(a,b)\in C}\{\square ^{ab}\}$, is a solution of $I^{\prime }$.

Fig. 2.

Gadget for a pair of complementary vertices (a, b) in the reduction from Balanced Satisfactory Partition$^{\text{ FSC }}$ to Balanced Satisfactory Partition$^{\text{ FS }}$.

Lemma 5

The Balanced Satisfactory Partition$^{\text{ S }}$ is W[1]-hard when parameterized by the treewidth of the graph.

Proof

Let $I = (G,V_{\triangle },V_{\square })$ be a Balanced Satisfactory Partition$^{\text{ FS }}$ instance; let n denote the number of vertices in G. First, we fix a vertex $v \in V_{\square }$. For every pair (u, v) of vertices where $u \in V_{\triangle }$, we introduce two sets of new vertices $X_{uv} = \{ x^{uv}_{1},x^{uv}_{2},\dots ,x^{uv}_{n}\}$ and $Y_{uv}^{\square }= \{ y^{uv\square }_{1},y^{uv\square }_{2},\dots ,y^{uv\square }_{n}\}.$ Next, we define the Balanced Satisfactory Partition$^{\text{ S }}$ instance $I^{\prime }= (G^{\prime },V^{\prime }_{\square })$ where $V^{\prime }_{\square } = V_{\square }\bigcup \limits _{u \in V_{\triangle }} Y_{uv}^{\square }$ and $G^{\prime }$ is the graph defined by

$$ V(G^{\prime }) = V(G) \bigcup \limits _{u \in V_{\triangle }} X_{uv} \bigcup \limits _{u \in V_{\triangle }} Y_{uv}^{\square }$$

and

$$\begin{aligned} E(G^{\prime }) =&E(G) \bigcup \limits _{u\in V_{\triangle }} \Big \{(u,x_{i}^{uv}),(u,y_{i}^{uv\square }),(x_{i}^{uv},v),(y_{i}^{uv\square },v)~|~i\le i\le n\Big \} \\&\bigcup \limits _{u\in V_{\triangle }} \Big \{(x_i^{uv},y_i^{uv\square }), (x_i^{uv},y_{i+1}^{uv\square })~|~1\le i\le n-1 \Big \} \cup \Big \{(x_n^{uv},y_n^{uv\square }),(x_n^{uv},y_1^{uv\square })\Big \} \\&\bigcup \limits _{u\in V_{\triangle }} \Big \{(x_i^{uv},x_{i+1}^{uv}~|~1\le i\le n-1 \Big \} \cup \Big \{(x_n^{uv},x_1^{uv})\Big \} \\&\bigcup \limits _{u\in V_{\triangle }} \Big \{(y_i^{uv\square },y_{i+1}^{uv\square }~|~1\le i\le n-1 \Big \} \cup \Big \{(y_n^{uv\square },y_1^{uv\square })\Big \} \end{aligned}$$

Fig. 3.

Let $n=4$. Gadget for a pair of vertices (u, v) where $u\in V_{\triangle }$ and v is a fixed vertex in $V_{\square }$ in the reduction from Balanced Satisfactory Partition$^{\text{ FS }}$ to Balanced Satisfactory Partition$^{\text{ S }}$.

An example is given in Fig. 3. The treewidth of $G^{\prime }$ is equal to the treewidth of G plus 5. We now claim that I is a yes-instance if and only if $I'$ is a yes-instance. Assume first that there exists a balanced satisfactory partition $(V_{1},V_{2})$ of I such that $V_{\triangle } \in {V_1}$ and $V_{\square } \in V_2$. In this case, we will get a balanced satisfactory partition $(V_1^{\prime },V_{2}^{\prime })$ of $I'$ as follows:

$$V_1^{\prime } = V_{1} \bigcup \limits _{u \in V_{\triangle }} X_{uv} \ \ \text {and} \ \ V_2^{\prime } = V_{2} \bigcup \limits _{u \in V_{\triangle }} Y_{uv}^{\square }. $$

It is easy to see that $(V_{1}^{\prime },V_{2}^{\prime })$ forms a balanced satisfactory partition of $G^{\prime }$ as all the vertices in $V_1 \ \text {and} \ V_2$ will remain satisfied and also the new vertices in $X_{uv}\cup Y_{uv}^{\square }$ for all $u \in V_{\triangle }$ are satisfied in their respective part as each vertex has three neighbours in its own part and three neighbors in the other part. Since we are adding equal number of vertices in the balanced partition $(V_1,V_2)$, we again get a balanced satisfactory partition. This shows that $I'$ is a yes-instance.

Conversely, suppose that there exists a balanced satisfactory partition $(V_1^{\prime },V_2^{\prime })$ of $G^{\prime }$ such that $V^{\prime }_{\square } \in V_{2}^{\prime }$. We first show that all the vertices in $V_{\triangle }$ must lie in $V_1^{\prime }$. Let us assume that there exists a vertex $u \in V_{\triangle }$ that lies in $V_{2}^{\prime }$. Then each vertex in $X_{uv}$ has at least 4 neighbors in $V_{2}^{\prime }$ and at most 2 neighbours in $V_1^{\prime }$; therefore all the vertices in $X_{uv}$ lie in $V_2^{\prime }$. In this case, we cannot get a balanced satisfactory partition as already more than half of the vertices are in $V_2^{\prime }.$ This proves that all the vertices in $V_{\triangle }$ lie in $V_1^{\prime }$. Next, we show that as $V_{\triangle } \subseteq V_1^{\prime }$, the vertices in $\bigcup \limits _{u\in V_{\triangle }}X_{uv}$ also lie in $V_1^{\prime }$. Since $u \in V_1^{\prime }$, it must be satisfied in $V_1^{\prime }$. As the vertices in $Y^{\square }_{uv}$ lie in $V_2^{\prime }$, u has at least n neighbors in $V_2^{\prime }$ and since u has at most $n-1$ neighbors in graph G, it implies that at least one vertex from $X_{uv}$ must be in $V_1^{\prime }$. Without loss of generality, we can assume that $x_1^{uv} \in V_1^{\prime }$. Since $x_1^{uv} \in V_1^{\prime }$, it must be satisfied in $V_1^{\prime }$ and this forces $x_{n}^{uv},x_{2}^{uv}$ to be in $V_{1}^{\prime }$ as well. Repetitively applying the above argument we get that all the vertices in set $X_{uv}$ lie in $V_1^{\prime }$. We claim that $(V_1^{\prime } \cap V(G), V_2^{\prime } \cap V(G))$ forms a balanced satisfactory partition of graph G. As for each vertex in $V_i^{\prime } \cap V(G)$, $i=1,2$, we are removing equal number of neighbors from both the partitions, this implies that all the vertices are satisfied and the partition is balanced. This shows that I is a yes-instance.

Lemma 6

The Balanced Satisfactory Partition problem, parameterized by the treewidth of the graph, is W[1]-hard.

Proof

Let $I = (G,V_{\square })$ be a Balanced Satisfactory Partition$^{\text{ S }}$ instance, where $V_{\square }=\{ u_1,u_2,\dots ,u_{n^{\prime }}\}.$ For every vertex $u_{i}$ in the set $V_{\square }$, we introduce two new sets of vertices $X^{u_{i}} = \{ x^{u_{i}}_{1},x^{u_{i}}_{2},\dots ,x^{u_{i}}_{4n}\}$ and $Y^{u_{i}} = \{ y^{u_{i}}_{1},y^{u_{i}}_{2},\dots ,y^{u_{i}}_{4n}\}$. We also introduce a clique of size 2 containing vertices $\{s,t\}$ and a set $C=\{c_1,c_2,\dots ,c_{8n}\}$ of 8n vertices. We add two new vertices $\{s',t'\}$ along with two sets of vertices $S'=\{s^{\prime }_1,s^{\prime }_2,\dots ,s^{\prime }_{4n}\}$ and $T'=\{t^{\prime }_1,t^{\prime }_2,\dots ,t^{\prime }_{4n}\}$. Now, we define the Balanced Satisfactory Partition instance $I^{\prime }= G^{\prime }$ where $G^{\prime }$ is the graph defined by

$$ V(G') = V(G) \cup \bigcup \limits _{i=1}^{n'} X^{u_{i}} \cup \bigcup \limits _{i=1}^{n'} Y^{u_{i}} \cup \{s,t,s',t'\} \cup S' \cup T' \cup C $$

and

$$\begin{aligned} E(G')&= E(G) \cup \bigcup \limits _{i=1}^{n'} \bigcup \limits _{j=1}^{4n} \Big \{(x_{j}^{u_{i}},u_{i}),(y_{j}^{u_{i}},u_{i}),(y_{j}^{u_{i}},s),(y_{j}^{u_{i}},t)\Big \} \cup \big \{(s,t)\big \} \\&\bigcup \limits _{j=1}^{8n} \Big \{(c_{j},s),(c_{j},t)\Big \} \cup \bigcup \limits _{j=1}^{4n} \Big \{(s',s^{\prime }_{j}),(t',t^{\prime }_{j})\Big \} \cup \Big \{(s',s)(s',t),(t',s),(t',t)\Big \}. \end{aligned}$$

Fig. 4.

An illustration of the reduction from Balanced Satisfactory Partition$^{\text{ S }}$ to Balanced Satisfactory Partition.

Now we claim that I is a yes-instance if and only if $I'$ is a yes-instance. Assume first that there exists a balanced satisfactory partition $(V_1,V_2)$ in the graph G such that $V_{\square } \subseteq V_2$. In this case, a balanced satisfactory partition $(V_1^{\prime },V_2^{\prime })$ for $G^{\prime }$ is defined as follows:

$$ V_1^{\prime } = V_1 \cup \bigcup \limits _{i=1}^{n'} Y^{u_{i}} \cup \{s,t\} \cup C \ \text {and} \ V_2^{\prime } = V_2 \cup \bigcup \limits _{i=1}^{n'} X^{u_{i}} \cup \{s',t'\} \cup S' \cup T'. $$

Clearly, all the vertices are satisfied. Since we are adding equal number of vertices in both the parts, $(V_1^{\prime },V_2^{\prime })$ is a balanced satisfactory partition of $G^{\prime }$. This proves that if I is a yes-instance then $I'$ is a yes-instance.

Conversely, suppose that there exists a balanced satisfactory partition $(V_1^{\prime }, V_2^{\prime })$ of $G'$. We first prove that all the vertices of $V_{\square }$ are in the same part. Since $N_{G'}[s] = N_{G'}[t]$, both s and t would be in the same part; without loss of generality suppose they lie in $V_1^{\prime }$. For $1\le i\le n^{\prime }$, each vertex $y_{j}^{u_{i}}$ is adjacent to 3 vertices $\{u_{i},s,t\}$ and since $\{s,t\}$ belong to $V_1^{\prime }$, it forces $y_{j}^{u_{i}}$ to be in $V_1^{\prime }$ for $1\le j \le 4n$. Similarly, as $s,t \in V_1^{\prime }$, each $c_i$ would also be in $V_1^{\prime }$ for $1\le i\le 4n$. For the sake of contradiction, suppose the vertices of $V_{\square }$ are distributed among $V_1^{\prime }$ and $V_2^{\prime }$, that is, r many vertices of $V_{\square }$ are in $V_1^{\prime }$ and remaining $n^{\prime }-r$ vertices of $V_{\square }$ are in $V_2^{\prime }$. This implies that $V_1^{\prime }$ contains at least $4n(n'+r+2)+r+2$ vertices and $V_2^{\prime }$ contains at most $4n(n'-r+2)+2+(n-r)$. It implies that $|V_1^{\prime }| > |V_2^{\prime }|$, a contradiction to our assumption that $(V_1^{\prime }, V_2^{\prime })$ is a balanced satisfactory partition. This shows that all the vertices of $V_{\square }$ must go to $V_2^{\prime }$. Therefore, for every balanced satisfactory partition of $G'$, we have

$$ \bigcup \limits _{i=1}^{n'}\bigcup \limits _{j=1}^{4n} \{y_j^{u_{i}}\} \cup \{s,t\} \cup C \subseteq V_1^{\prime } \ \text {and} \ \bigcup \limits _{i=1}^{n'}\bigcup \limits _{j=1}^{4n} \{x_j^{u_{i}}\} \cup \{s',t'\} \cup S' \cup T' \cup V_{\square } \subseteq V_2^{\prime }. $$

We now claim that $(V_1^{\prime } \cap V(G), V_2^{\prime } \cap V(G))$ forms a balanced satisfactory partition of G. From the above observation, we have $V_{\square } \subset V_2^{\prime } \cap V(G)$. All the vertices are satisfied in the new partition $(V_1^{\prime } \cap V(G), V_2^{\prime } \cap V(G))$ and it is a balanced partition because we are removing equal number of vertices from both parts. This shows that if $I'$ is a yes-instance then I is also a yes-instance.

This proves Theorem 2.

4 Conclusion

In this work we proved that the Satisfactory Partition and Balanced Satisfactory Partition problems are FPT when parameterized by neighbourhood diversity; the Balanced Satisfactory Partition problem is W[1]-hard when parameterized by treewidth. The parameterized complexity of the Satisfactory Partition problem remains unsettle when parameterized by other important structural graph parameters like clique-width and modular width.