A New Kernel for Parameterized Max-Bisection Above Tight Lower Bound

Abstract

In this paper, we study kernelization of Parameterized Max-Bisection above Tight Lower Bound problem, which is to find a bisection $(V_1, V_2)$ of G with at least $\lceil |E|/2\rceil +k$ crossing edges for a given graph $G=(V, E)$. The current best vertex kernel result for the problem is of size 16k. Based on analysis of the relation between maximum matching and vertices in Gallai-Edmonds decomposition of G, we divide graph G into a set of blocks, and each block in G is closely related to the number of crossing edges of bisection of G. By analyzing the number of crossing edges in all blocks, an improved vertex kernel of size 8k is presented.

This work is supported by the National Natural Science Foundation of China under Grants (61420106009, 61232001, 61472449, 61672536, 61572414).

1 Introduction

Given a graph $G=(V, E)$, for two subsets $V_1, V_2$ of V, if $V_1\cup V_2=V$, $V_1\cap V_2=\emptyset$, and $||V_1|-|V_2||\le 1$, then $(V_1, V_2)$ is called a bisection of G. An edge of G with one endpoint in $V_1$ and the other endpoint in $V_2$ is called a crossing edge of $(V_1, V_2)$. The Maximum Bisection problem is to find a bisection $(V_1, V_2)$ of G with maximum number of crossing edges. Jansen et al. [8] proved that the Maximum Bisection problem is NP-hard on planar graph. Díaz and Kamiński [1] proved that the Maximum Bisection is NP-hard on unit disk graphs.

Frieze and Jerrum [4] gave an approximation algorithm for the Maximum Bisection problem with ratio 0.651. Ye [13] presented an improved approximation algorithm with ratio 0.699. Halperin and Zwick [7] gave an approximation algorithm with ratio 0.701. Feige et al. [3] studied the Maximum Bisection problem on regular graphs, and presented an approximation algorithm with ratio 0.795. Karpiński et al. [9] studied approximation algorithms for Maximum Bisection problem on low degree regular graphs and planar graphs. For three regular graphs, an approximation algorithm of ratio 0.847 was presented in [9]. For four and five regular graphs, two approximation algorithms with ratios 0.805, 0.812 were presented in [9], respectively. For planar graph of a sublinear degree, a polynomial time approximation scheme was presented in [9]. Jansen et al. [8] studied Maximum Bisection problem on planar graphs, and gave the first polynomial time approximation scheme for the problem.

For a given graph G, it is easy to find a bisection with $\lceil |E|/2\rceil$ crossing edges by probabilistic method. In this paper, we study the following problem.

Parameterized Max-Bisection above Tight Lower Bound (PMBTLB): Given a graph $G=(V, E)$ and non-negative integer k, find a bisection of G with at least $\lceil |E|/2\rceil +k$ crossing edges, or report that no such bisection exists.

Gutin and Yeo [5] gave a vertex kernel of size $O(k^2)$ for the PMBTLB problem. Based on the relation between edges in maximum matching and crossing edges, a parameterized algorithm of running time $O^*(16^k)$ was presented in [5]. Mnich and Zenklusen [11] presented a vertex kernel of size 16k for PMBTLB problem based on Gallai-Edmonds decomposition of the given graph.

In this paper, we further analyze the relation between maximum matching and vertices in Gallai-Edmonds decomposition for a given graph G. The vertices in Gallai-Edmonds decomposition are divided into several categories, which play important role in getting improved kernel. Based on the categories of vertices, we divide graph G into a set of blocks, where each block is closely related to the number of crossing edges of bisection of G. By analyzing the number of crossing edges in all blocks, a vertex kernel of size 8k is presented.

2 Preliminaries

For a given graph $G=(V, E)$, we use n, m to denote the number of vertices in V and the number of edges in E, respectively. Assume that all the graphs discussed in the paper are loopless undirected graph with possible parallel edges. For a graph $G=(V, E)$, if |V| is a odd number, we can add an isolated vertex into G such that the number of crossing edges in each bisection of G is not changed. For simplicity, we assume that all the graphs in the paper have even number of vertices.

For two subsets $A, B\subseteq V$, let E(A) be the set of edges in G[A], and let E(A, B) be the set of edges with one endpoint in A and the other endpoint in B. For two vertices u and v in G, for simplicity, let uv denote an edge between u and v, and let E(u, v) denote the set of edges between u and v. For a vertex v in G, let d(v) denote the degree of v in G. For a subset $X \subseteq V$ and a vertex v in X, let $d_X(v)$ denote the degree of v in induced subgraph G[X], and let $\delta (G[X])$ be the number of connected components in G[X]. For a subgraph H of G, let V(H) be the set of vertices contained in H. Let N[V(H)] denote the set of neighbors of vertices in V(H), where V(H) is contained in N[V(H)], and let $N(V(H))=N[V(H)]-V(H)$.

Given a matching M in G, let V(M) denote the set of vertices in M. If a vertex u in G is not contained in V(M), then u is called an unmatched vertex. Matching M is called a near-perfect matching of G if there is exactly one unmatched vertex in G. For a connected graph G, and any vertex u in G, if the size of maximum matching in $G\backslash \{u\}$ is equal to the size of maximum matching in G, then G is called a factor-critical graph. A Gallai-Edmonds decomposition of graph G is a tuple (X, Y, Z), where X is the set of vertices in G which are not covered by at least one maximum matching of G, Y is N(X), and $Z=V(G)\backslash (X\cup Y)$. The Gallai-Edmonds decomposition of G can be obtained in polynomial time [10].

Lemma 1

([2, 10]). For a given graph G, a Gallai-Edmonds decomposition (X, Y, Z) of G has the following properties:

• 1. the components of the subgraph induced by X are factor-critical,

• 2. the subgraph induced by Z has a perfect matching,

• 3. if M is any maximum matching of G, it contains a near-perfect matching of each component of G[X], a perfect matching of each component of G[Z], and matches all vertices of Y with vertices in distinct components of G[X],

• 4. the size of the maximum matching is $\frac{1}{2}(|V| - \delta (G[X]) + |Y|)$.

For two subsets A, B of V, if $A\cap B = \emptyset$ and $|A| = |B|$, then (A, B) is called a basic block of graph G. Let $\mathcal{C}=\{C_1, \ldots , C_h\}$ be the set of basic blocks of G, where $C_i=(A_i, B_i)$. For a basic block $C_i=(A_i, B_i)$, let $V(C_i)$ denote the set of vertices in $A_i\cup B_i$. Given two basic blocks $C_i, C_j \in \mathcal C$, for simplicity, let $E(C_i, C_j)=E(V(C_i), V(C_j))$. For all basic blocks in $\mathcal C$, if $V(C_i)\cap V(C_j) = \emptyset$ ($i\ne j)$ and $\bigcup _{i=1}^h V(C_i)=V$, then $\mathcal C$ is called a block cluster of G. For a basic block $C\in \mathcal C$, we use $\mathcal{C}-C$ to denote $\mathcal{C}\backslash \{C\}$.

Based on the block cluster $\mathcal C$ and V, a bisection $(V_1, V_2)$ of G can be constructed in the following way: for each basic block $C_i=(A_i, B_i)$ in $\mathcal C$, put all vertices in $A_i$ into $V_1$ and $V_2$ with probability 1/2, 1/2, respectively; if $A_i$ is put into $V_1$, then $B_i$ will be put into $V_2$, and if $A_i$ is put into $V_2$, then $B_i$ will be put into $V_1$.

Let $r_1=\sum _{i=1}^h |E(A_i, B_i)|$, $r_2=\sum _{i=1}^{h-1}\sum _{j=i+1}^{h}|E(C_i, C_j)|$, and $r_3=\sum _{i=1}^h$ $(|E(A_i)|+|E(B_i)|)$. For a basic block $C_i=(A_i, B_i)$ in $\mathcal C$, let $r(C_i)=|E(A_i, B_i)|-|E(A_i)|-|E(B_i)|$. Let $r(\mathcal{C})=\sum _{i=1}^h r(C_i)$.

Lemma 2

For any block cluster $\mathcal C$ of graph G, there exists a bisection $(V'_1, V'_2)$ of G obtained from $\mathcal C$ such that $|E(V'_1, V'_2)|$ is at least $\lceil m/2\rceil +r(\mathcal{C})/2$.

Proof

For any two basic blocks $C_i, C_j$ ($i\ne j$) in $\mathcal C$, we now analyze the expected number of crossing edges from $E(C_i, C_j)$ for bisection $(V_1, V_2)$. Assume that $A_i$ is in $V_1$, and $B_i$ is in $V_2$. In the process of constructing $(V_1, V_2)$, $A_j$ is put into $V_1$ and $V_2$ with probability 1/2, 1/2, respectively. Therefore, the expected number of crossing edges from $E(C_i, C_j)$ is $|E(C_i, C_j)|/2$. Moreover, for a basic block $C_i$ in $\mathcal C$, if $E(A_i, B_i) \ne \emptyset$, then the edges in $E(A_i, B_i)$ are all crossing edges, and edges in $E(A_i)\cup E(B_i)$ are not crossing edges. Therefore, the expected number of crossing edges in $(V_1, V_2)$ is $r_1+r_2/2=(2r_1+r_2)/2=(r(\mathcal{C)}+r_3+r_1+r_2)/2$. Since $r_1+r_2+r_3=m$, $(r(\mathcal{C)}+r_3+r_1+r_2)/2= m/2+r(\mathcal{C})/2$. Therefore, there must exist a bisection $(V'_1, V'_2)$ of G with $|E(V'_1, V'_2)|\ge \lceil m/2\rceil +r(\mathcal{C})/2$.    $\square$

Lemma 3

For a given instance (G, k) of PMBTLB problem and any block cluster $\mathcal C$ of G, if $r(\mathcal{C})\ge 2k$, then G has a a bisection of size at least $\lceil m/2\rceil +k$ based a standard derandomization as given by Ries and Zenklusen [12].

3 Kernelization for PMBTLB Problem

For a given instance (G, k) of PMBTLB, assume that (X, Y, Z) is a Gallai-Edmonds decomposition of G. Let MM be a maximum matching of G. Based on the degree of vertices in X and the maximum matching MM, we divide X into following subsets:

• $X_0 = \{v | v\in X, d(v) = 0\}$,

• $X_1 = \{v | v\in X, d_X(v) = 0, v\in V(MM)\}$,

• $X_2 = \{v | v\in X, d_X(v) = 0, v\notin V(MM)\}$,

• $X_3 = \{v | v\in X, d_X(v) \ge 1,\exists u\in Y, uv\in MM\}$,

• $X_4 = \{v | v\in X, \exists u\in X, uv\in MM\}$,

• $X_5 = \{v | v\in X, d_X(v)\ge 1, v\notin V(MM)\}$.

We now give the process to construct a block cluster $\mathcal C$ of graph G, as given in Fig. 1. Assume that $\mathcal{C}=\{C_1, \ldots , C_h\}$ is the block cluster of G obtained by algorithm BBDA1 in Fig. 1.

Fig. 1.

Algorithm for constructing block cluster $\mathcal C$

Lemma 4

([6]). If M is a matching in a graph G, then G has a bisection of size at least $\lceil m/2\rceil +\lfloor |M|/2\rfloor$, which can be found in $O(m + n)$ time.

By Lemma 4, we can get that the size of matching M is less than 2k, otherwise a bisection with at least $\lceil m/2\rceil + k$ crossing edges can be found in polynomial time. For a maximum matching MM of G, if $V'=V\backslash V(MM)$ is empty, then G is a graph with perfect matching. Since the size of matching MM is less than 2k, the number of vertices in G is bounded by 4k.

In the following, assume that $V'$ is not empty. Since $V'= V\backslash V(MM)$, $V'$ is an independent set. Assume that $C_h$ is the basic block constructed by step 4 of algorithm BBDA1. According to the construction process of $\mathcal C$, for each basic block $C_i$ in $\mathcal{C}- C_h$, $r(C_i)\ge 1$. Especially, $r(C_h)=0$. We now construct a new block cluster based on $\mathcal C$. The general idea is to move vertices of $V(C_h)$ to the basic blocks in $\mathcal{C}-C_h$ to get new basic blocks. In the construction process, if no vertex in added into a basic block $C=(A, B)$, then the value r(C) is not changed. Since vertices in $V(C_h)$ form an independent set, after removing some vertices of $C_h$, the vertices in the remaining basic block $C_h$ still form an independent set, and $r(C_h)$ is still zero. In the following, we give the process to get a new block cluster $\mathcal{C'}=\{C'_1, \ldots ,$ $C'_h\}$ based on $\mathcal C$, which is given in Fig. 2.

Fig. 2.

Algorithm for constructing block cluster $\mathcal C'$

Let $\mathcal C'$ be the block cluster returned by algorithm BBDA2. We now analyze the difference between $r(\mathcal C)$ and $r(\mathcal C')$. For two vertices v, w in $X_2$ that are added into $C_l$ in step 3 of algorithm BBDA2, $r(C_l)$ is increased by at least one. Assume that S is returned by algorithm BBDA2. For any two vertices w, v in S, it is easy to see that for each vertex u in G, $|E(w, u)|=|E(v, u)|$. Since all vertices in $|X_2\backslash S|$ are moved to $C'_Y$ in algorithm BBDA2, $r(\mathcal{C}'_Y)-r(\mathcal{C}_Y)$ is at least $|X_2\backslash S|/2$, and $r(\mathcal{C'})-r(\mathcal{C})$ is at least $|X_2\backslash S|/2$. In algorithm BBDA1, each edge in MM is chosen to construct a basic block. Therefore, the value $r(\mathcal C)$ is at least |MM|. Since $\mathcal C'$ is constructed based on $\mathcal C$, we have

$$\begin{aligned} r(\mathcal{C'})\ge |MM|+|X_2\backslash S|/2. \end{aligned}$$

(1)

Since the vertices in $X_0$, $X_2$ and $X_5$ are not in V(MM), in algorithm BBDA1, $V(C_h)=X_0\cup X_2\cup X_5$. In algorithm BBDA2, the vertices in $X_2\backslash S$ are moved from $C_h$ to $\mathcal{C}'_Y$. Therefore, $V(C'_h)=X_0\cup S\cup X_5$.

Lemma 5

For any basic block $C'_l=(A'_l, B'_l)$ in $\mathcal C'$, where $V(C'_l)$ contains one vertex u of Y and $u\in N(S)$, assume that $u\in A'_l$. Then, S cannot be connected to any vertex in $B'_l$, and the number of basic blocks in $\mathcal C'$ containing one vertex in N(S) is |N(S)|.

For any connected component H in G[X] with at least three vertices, there is exactly one vertex v in V(H) such that v is in either $X_3$ or $X_5$, and other vertices in $V(H)\backslash \{v\}$ are in $X_4$.

Lemma 6

$|X_5| < 2k$.

Proof

If $X_5$ is empty, then this lemma is correct. Let $\mathcal{H}=\{H_1,\ldots , H_l\}$ be the set of connected components in G[X], each of which has size at least three and contains one vertex in $X_5$. For any $H_i$ ($1\le i\le l$) in $\mathcal H$, there exists a perfect matching in $G[V(H_i)\backslash \{v\}]$, and the number of edges from $E(H_i)$ in MM is $(|V(H_i)|-1)/2$. By above discussion, the number of edges in MM is less than 2k. Therefore, $\sum _{i=1}^l(|V(H_i)|-1)/2< 2k$. Thus, $|X_5| < 2k$.    $\square$

In the following, we will construct two new block clusters $\mathcal C''$ and $\mathcal C'''$ based on $\mathcal C'$ by adding vertices in $X_0$, $X_5$ and S into basic blocks of $\mathcal{C'}-C'_h$.

Case 1. $|X_0|\ge |S|$. Under this case, the general idea to construct $\mathcal C''$ is to use the vertices in S and $X_0$ firstly. When all vertices in S are added into basic blocks in $\mathcal{C'}-C'_h$ to get new basic blocks in $\mathcal C''$, we consider the vertices $X_5$ and the remaining vertices in $X_0$ to construct basic blocks in $\mathcal C'''$ based on $\mathcal C''$.

By Lemma 5, find a basic block $C'_i=(A'_i, B'_i)$ in $\mathcal C'$ such that $V(C'_i)\cap N(S)=\{u\}$, and assume that u is contained in $A'_i$. A new basic block $C''_i=(A''_i, B''_i)$ of $\mathcal C''$ can be constructed from $C'_i$ by the following steps: $B''_i = B'_i\cup S$; arbitrarily choose |S| vertices from $X_0$, denoted by P; $A''_i=A'_i\cup P$. Let $C''_h=C'_h\backslash (S\cup P)$, $\mathcal{C''}=(\mathcal{C'}-C'_i-C'_h)\cup C''_i\cup C''_h$. Since no vertex in S is connected to any vertex in $B'_i$ and no vertex in P is connected to any vertex in $V(C'_i)$, $r(C''_i)-r(C'_i)$ is at least |S|. Thus,

$$\begin{aligned} r(\mathcal{C''})-r(\mathcal{C'})\ge |S|. \end{aligned}$$

(2)

Let $\mathcal H$ be the set of connected components in G[X] such that for each connected component H in $\mathcal H$, V(H) contains one vertex of $X_5$, and $N(V(H))\cap Y\ne \emptyset$. For each connected component H in $\mathcal H$, assume that $E'$ is the set of edges in H that are contained in MM. Let $\mathcal{C}_H$ be a subset of $\mathcal C''$, where $\mathcal{C}_H$ can be constructed by the edges in $E'$. Since H is factor-critical, there exists a vertex v in V(H) such that v is an unmatched vertex. If v is not connected to any vertex in Y, then find a vertex u in V(H) that is connected to some vertices in Y, and find a perfect matching $M'$ in $G[V(H)\backslash \{u\}]$. Construct a set $\mathcal F$ of basic blocks by the edges in $M'$, and let $\mathcal{C''}=(\mathcal{C''}- \mathcal{C}_H)\cup \mathcal F$. After dealing with all connected components in $\mathcal H$ by the above process, a new maximum matching $MM'$ can be obtained, and for each connected component H in G[X] satisfying that V(H) has at least three vertices and $N(H)\cap Y\ne \emptyset$, if v is an unmatched vertex in H, then v is connected to at least one vertex in Y.

The vertices in $X_5$ are divided into the following two types. Let $X_5^y$ be a subset of $X_5$ such that each vertex v in $X_5^y$ is connected to at least one vertex in Y, and let $X_5^i$ be a subset of $X_5$ such that each vertex u in $X_5^i$ is not connected to any vertex in Y.

Lemma 7

Given a vertex $v\in X_5^y$, for any basic block $C''_l=(A''_l, B''_l)$ in $\mathcal C''$, where $V(C''_l)$ contains one vertex u of Y and $u\in N(v)$, assume that $u\in A''_l$. Then, v cannot be connected to any vertex in $B''_l$.

Let $X'_0=X_0\backslash P$. We now construct basic blocks of $\mathcal C'''$ by vertices in $X'_0$ and $X_5^y$. Assume that $|X'_0|\ge |X_5^y|$. For a vertex v in $X_5^y$, by Lemma 7, there exists a basic block $C''_i=(A''_i, B''_i)$ in $\mathcal C''$ containing u such that $u\in N(v)$. Without loss of generality, assume that u is contained in $A''_i$. A new basic block $C'''_i=(A'''_i,B'''_i)$ of $\mathcal C'''$ can be constructed from $C''_i$ by the following process: $B'''_i=B''_i\cup \{v\}$; arbitrarily choose a vertex w in $X'_0$, let $A'''_i=A''_i\cup \{w\}$. Let $C'''_h=C''_h\backslash \{v, w\}$, $\mathcal{C'''}=(\mathcal{C''} - C''_i-C''_h)\cup \{C'''_i\}\cup \{C'''_h\}$. Since v is not connected to any vertex in $B''_i$ and w is not connected to any vertex in $V(C''_i)$, it is easy to see that $r(C'''_i)-r(C''_i)\ge 1$. By considering all vertices in $X_5^y$, we have

$$\begin{aligned} r(\mathcal{C'''})-r(\mathcal{C''})\ge |X_5^y|. \end{aligned}$$

(3)

For the case when $|X'_0|< |X_5^y|$, a similar construction process can be obtained as above. By considering all vertices in $X'_0$, we can get that

$$\begin{aligned} r(\mathcal{C'''})-r(\mathcal{C''})\ge |X'_0|. \end{aligned}$$

(4)

Lemma 8

Based on $MM'$, $|X_5^i|\le \delta (G\backslash X_0)$.

Proof

We prove this lemma by discussing the types of connected components in $G\backslash X_0$. For a connected component H in $G\backslash X_0$, if V(H) contains no vertex of X, then no vertex in V(H) is contained in $X_5^i$. If all vertices in V(H) are from X, then H is a factor-critical connected component, and no vertex in V(H) is connected to Y. Under this case, one vertex from V(H) is contained in $X_5^i$. Assume that $V(H)\backslash X$ is not empty. By the construction process of $MM'$, if a vertex v in $N(Y)\cap V(H)$ is contained in $X_5$, then v is in $X_5^y$, and no vertex in V(H) is in $X_5^i$. Therefore, $|X_5^i|\le \delta (G\backslash X_0)$.    $\square$

Rule 1. For a given instance (G, k) of PMBTLB, if $|X_0|+\delta (G\backslash X_0) > \frac{n}{2}$, then arbitrarily delete $|X_0|+\delta (G\backslash X_0)-\frac{n}{2}$ vertices from $X_0$.

Lemma 9

Rule 1 is safe.

Proof

Assume that $|X_0|+\delta (G\backslash X_0) > \frac{n}{2}$, and assume that $(V_1, V_2)$ is a maximum bisection of G. If $X_0=\emptyset$, then the number of connected components in $G\backslash X_0$ is at most n / 2, because each connected component in $G\backslash X_0$ has at least two vertices. Assume that the number of connected components in $G\backslash X_0$ is at least one, otherwise, the PMBTLB problem can be trivially solved. Assume that $\mathcal{H}=\{H_1, \ldots , H_l\}$ is the set of connected components in $G\backslash X_0$. We now prove that all vertices in $X_0$ cannot be contained totally in $V_1$ or $V_2$. Assume that all vertices of $X_0$ are contained in $V_1$. Since $|X_0|+\delta (G\backslash X_0) > \frac{n}{2}$, there must exist a connected component $H_i$ in $\mathcal H$ such that all vertices in $V(H_i)$ are contained in $V_2$. Choose a vertex v in $V(H_i)$, and find a vertex u of $X_0$ in $V_1$. Let $V'_1=(V_1\backslash \{u\})\cup \{v\}$, $V'_2=(V_2\backslash \{v\})\cup \{u\}$. Then, $|E(V'_1, V'_2)|-|E(V_1, V_2)|\ge 1$, contradicting the fact that $(V_1, V_2)$ is a maximum bisection of G. Therefore, $V_1\cap X_0\ne \emptyset$ and $V_2\cap X_0\ne \emptyset$. Assume that $X'_0$ and $X''_0$ are two subsets of $X_0$ such that $X'_0$ is contained in $V_1$, and $X''_0$ is contained in $V_2$. Without loss of generality, assume that $|X'_0|\le |X''_0|$. Let R be any subset of $X''_0$ of size $|X'_0|$. Let $V''_1=V_1-X'_0$, $V''_2=V_2-R$. Then, $|V''_1|=|V''_2|$. Denote the new graph with bisection $(V''_1, V''_2)$ by $G'$. It is easy to see that $|E(V_1, V_2)|$ is bounded by $\lceil m/2\rceil +k$ if and only if $|E(V''_1, V''_2)|$ is bounded by $\lceil m/2\rceil +k$. Repeat the above process until $|X_0|+\delta (G\backslash X_0) \le \frac{n}{2}$.    $\square$

For a given instance (G, k) of PMBTLB, by applying Rule 1 on G exhaustively, we can get the following result.

Lemma 10

For a given instance (G, k) of PMBTLB, if $|X_0|\ge |S|$, then the number of vertices in G is bounded by 8k.

Proof

Based on block cluster $\mathcal C'''$, we prove this lemma by analyzing the sizes of $X'_0$ and $X_5^y$.

(1) $|X'_0|\ge |X_5^y|$. By Lemma 3 and inequalities (1), (2) and (3), we can get that $r(\mathcal{C'''})=|MM|+\frac{|X_2\backslash S|}{2}+|S|+|X_5^y|< 2k$. Based on Gallai-Edmonds decomposition (X, Y, Z) and MM, we know that $|MM|=(|Z|+|Y|+|X\backslash (X_0\cup X_2\cup X_5)|)/2$. Then, $|Z|+|Y|+|X\backslash (X_0\cup S\cup X_5 )|+ 2|S| + 2|X_5^y|<4k$. Since $X_5=X_5^y\cup X_5^i$, and S, $X_5^i$, $X_5^y$, $X_0$ are disjoint, we can get that

$$\begin{aligned} |Z|+|Y|+|X|-|X_0|-|X_5^i|+|S|+|X_5^y| < 4k. \end{aligned}$$

(5)

By Lemmas 8 and 9, $|X_0| + |X_5^i| \le \frac{n}{2}$. Then, we can get that

$$\begin{aligned} |V|=|Z|+|Y|+|X|&=|Z|+|Y|+ |X\backslash (X_0\cup X_{5i})|+|X_0| + |X_5^i|\nonumber \\&=\underbrace{ |Z|+|Y|+|X|-|X_0|-|X_5^i| }_{<4k\, \mathrm by\,(5)}+|X_0|+|X_5^i|\nonumber \\&< 4k +|V|/2. \end{aligned}$$

Therefore, $|V|< 8k$.

(2) $|X'_0| < |X_5^y|$. By Lemma 3 and inequalities (1), (2) and (4), we can get that $r(\mathcal{C'''})=|MM|+\frac{|X_2\backslash S|}{2}+|S|+|X'_0|< 2k$. Since $P\subseteq X_0$, $X'_0 = X_0\backslash P$ and $|S|=|P|$, we can get that $r(\mathcal{C'''})=|MM|+\frac{|X_2\backslash S|}{2}+|X_0|< 2k$. Similarly, $|MM|=(|Z|+|Y|+|X\backslash ( X_0\cup X_2\cup X_5)|)/2$. Then, $|Z|+|Y|+|X\backslash (X_0\cup S\cup X_5 )|+ 2|X_0|<4k$. Since S, $X_5$, $X_0$ are disjoint and $|X_0| \ge |S|$, we can get that

$$\begin{aligned} |Z|+|Y| +|X|-|X_5| < 4k. \end{aligned}$$

(6)

By Lemma 6, $|X_5|< 2k$. Then, we can get that

$$\begin{aligned} |V|=|Z|+|Y|+|X|&=|Z|+|Y|+ |X\backslash X_5|+|X_5| \nonumber \\&=\underbrace{|Z|+|Y|+|X|-|X_5|}_{<4k\, \mathrm by\,(6)} + |X_5|\nonumber \\&<4k +2k=6k. \end{aligned}$$

Therefore, if $|X_0|\ge |S|$, the number of vertices in G is bounded by 8k.    $\square$

Case 2. $|X_0|<|S|$. Under this case, the general idea to construct $\mathcal C''$ is to use the vertices in S and $X_0$ firstly. When all vertices in $X_0$ are added into basic blocks in $\mathcal{C'}-C'_h$ to get new basic blocks in $\mathcal C''$, we consider vertices in $X_5$ and the remaining vertices in S to construct basic blocks in $\mathcal C'''$ based on $\mathcal C''$.

By Lemma 5, find a basic block $C'_i=(A'_i, B'_i)$ in $\mathcal C'$ such that $V(C'_i)\cap N(S)=\{u\}$, and assume that u is contained in $A'_i$. A new basic block $C''_i=(A''_i, B''_i)$ of $\mathcal C''$ can be constructed from $C'_i$ by the following steps: $A''_i = A'_i\cup X_0$; arbitrarily choose $|X_0|$ vertices from S, denoted by Q; $B''_i=B'_i\cup Q$. Let $C''_h=C'_h\backslash (X_0\cup Q)$, $\mathcal{C''}=(\mathcal{C'}-C'_i-C'_h)\cup \{C''_i\}\cup \{C''_h\}$. Since no vertex in Q is connected to any vertex in $B'_i$ and no vertex in $X_0$ is connected to any vertex in $V(C'_i)$, $r(C''_i)-r(C'_i)$ is at least $|X_0|$. Thus,

$$\begin{aligned} r(\mathcal{C''})-r(\mathcal{C'})\ge |X_0|. \end{aligned}$$

(7)

Since $|X_0|<|S|$, S is not empty. For a connected component H in G[X], and for any three vertices w, v and u, where $w\in S$, $v\in V(H)$ and $u\in N(S)$, if $N(V(H))=N(S)$ and $|E(w, u)|=|E(v, u)|$, then H is called a special component in G[X].

Let $\mathcal H$ be the set of connected components in G[X] such that for each connected component H in $\mathcal H$, V(H) contains one vertex of $X_5$ and H is not a special component. For each connected component H in $\mathcal H$, assume that $E'$ is the set of edges in H that are contained in MM. Let $\mathcal{C}_H$ be a subset of $\mathcal C''$, where $\mathcal{C}_H$ can be constructed by the edges in $E'$. Since H is factor-critical, there exists a vertex v in V(H) such that v is an unmatched vertex. Based on N(S) and N(v), we give following five conditions: (1) $N(v)\cap N(S)=\emptyset$; (2) $N(v)\backslash N(S)\ne \emptyset$; (3) $N(v) \subset N(S)$; (4) $N(v)=N(S)$, and for any two vertices $w\in S$ and $u\in N(S)$, $|E(v, u)|>|E(w, u)|$; (5) $N(v)=N(S)$, and for any two vertices $w\in S$ and $u\in N(S)$, $|E(w, u)|<|E(v, v)|$.

We now introduce how to get a new maximum matching based on the above five conditions. Since V(H) is not a special component, if v does not satisfy any condition from conditions (1)–(5), then a vertex u in H can be found such that u satisfies one of the above conditions. Then, find a perfect matching $M'$ in $G[V(H)\backslash \{u\}]$, and construct a set $\mathcal F$ of basic blocks by the edges in $M'$. Let $\mathcal{C''}=(\mathcal{C''}- \mathcal{C}_H)\cup \mathcal F$. After dealing with all connected components in $\mathcal H$ by above process, a new maximum matching $MM'$ can be obtained.

The vertices in $X_5$ are divided into the following three types. Let $X_5^1$ be a subset of $X_5$ such that for each vertex v in $X_5^1$, the connected component in G[X] containing v is a special component. Let $X_5^2$ be a subset of $X_5$ such that for each vertex v in $X_5^2$, v satisfies one of conditions (1), (2), and (4). Let $X_5^3$ be a subset of $X_5$ such that for each vertex v in $X_5^3$, v satisfies one of conditions (3) and (5).

Lemma 11

For any vertex v in $X_5^2$ and any vertex w in S, there exists a vertex u in N(v) with $|E(v,u)| > |E(w,u)|$ such that a basic block $C''_i=(A''_i, B''_i)$ in $\mathcal C''$ can be found with $V(C''_i)\cap Y=\{u\}$. Assume that $A''_i\cap Y=\{u\}$. Then, no vertex in $B''_i$ is connected to $\{v, w\}$.

Lemma 12

For any vertex v in $X_5^3$ and any vertex w in S, there exists a vertex u in N(w) with $|E(w,u)| > |E(v,u)|$ such that a basic block $C''_i=(A''_i, B''_i)$ in $\mathcal C''$ can be found with $V(C''_i)\cap Y=\{u\}$. Assume that $A''_i\cap Y=\{u\}$. Then, no vertex in $B''_i$ is connected to $\{v, w\}$.

Let $S'=S\backslash Q$. We now construct basic blocks of $\mathcal C'''$ by vertices in $S'$, $X_5^2$ and $X_5^3$. Assume that $|S'|\ge |X_5^2|+|X_5^3|$. For a vertex v in $X_5^2$ and any vertex w in $S'$, by Lemma 11, there exists a vertex u in N(v) with $|E(v,u)|> |E(w,u)|$ such that a basic block $C''_i=(A''_i, B''_i)$ in $\mathcal C''$ can be found with $V(C''_i)\cap Y=\{u\}$. Without loss of generality, assume that u is contained in $A''_i$. A new basic block $C'''_i=(A'''_i,B'''_i)$ can be constructed from $C''_i$ by the following process: $B'''_i=B''\cup \{v\}$ and $A'''_i=A''\cup \{w\}$. Let $C'''_h=C''_h\backslash \{v, w\}$, $\mathcal{C'''}=(\mathcal{C''} - C''_i-C''_h)\cup \{C'''_i\}\cup \{C'''_h\}$. By Lemma 11, no vertex in $B''_i$ is connected to $\{v, w\}$. It is easy to see that $r(C'''_i)-r(C''_i)\ge 1$.

For a vertex v in $X_5^3$ and any vertex w in $S'$, by Lemma 12, there exists a vertex u in N(w) with $|E(w,u)|>|E(v,u)|$ such that a basic block $C''_j=(A''_j, B''_j)$ in $\mathcal C''$ can be found with $V(C''_j)\cap Y=\{u\}$. Without loss of generality, assume that u is contained in $A''_j$. A new basic block $C'''_j$ can be constructed from $C''_j$ by the following process: $B'''_j=B''\cup \{w\}$ and $A'''_j=A''\cup \{v\}$. Let $C'''_h=C''_h\backslash \{v, w\}$, $\mathcal{C'''}=(\mathcal{C''} - C''_j-C''_h)\cup \{C'''_j\}\cup \{C'''_h\}$. By Lemma 12, no vertex in $B''_j$ is connected to $\{v, w\}$. It is easy to see that $r(C'''_j)-r(C''_j)\ge 1$.

By considering all vertices in $X_5^2\cup X_5^3$, we can get that

$$\begin{aligned} r(\mathcal{C'''})-r(\mathcal{C''})\ge |X_5^2|+|X_5^3|. \end{aligned}$$

(8)

For the case when $|S'|< |X_5^2|+|X_5^3|$, a similar construction process can be obtained as above. By considering all vertices in $S'$, we can get that

$$\begin{aligned} r(\mathcal{C'''})-r(\mathcal{C''})\ge |S'|. \end{aligned}$$

(9)

Rule 2. For a given instance (G, k) of PMBTLB, if $|S|+|X_5^1|>\frac{n}{2}$, then arbitrarily delete $|S|+|X_5^1|-\frac{n}{2}$ vertices from S.

Lemma 13

Rule 2 is safe.

Proof

Assume that $|S|+|X_5^1| > \frac{n}{2}$, and assume that $(V_1, V_2)$ is a maximum bisection of G. Since $|S|>|X_0|$, S is not empty. We prove this lemma by discussing whether $X_5^1$ is empty or not.

(a) $X_5^1\ne \emptyset$. Assume that $\mathcal{H}=\{H_1, \ldots , H_l\}$ is the set of connected components in G[X] containing one vertex of $X_5^1$, and assume that $S=\{v_1, \ldots , v_j\}$. We now prove that all vertices in S cannot be contained totally in $V_1$ or $V_2$. Assume that all vertices of S are contained in $V_1$. Since $|S|+|X_5^1| > \frac{n}{2}$, there must exist a connected component $H_i$ in $\mathcal H$ such that all vertices in V(H) are contained in $V_2$. Choose a vertex v in $H_i$, and find a vertex u of S in $V_1$. Let $V'_1=(V_1-\{u\})\cup \{v\}$, $V'_2=(V_2-\{v\})\cup \{u\}$. Then, $|E(V'_1, V'_2)|-|E(V_1, V_2)|\ge 1$, contradicting the fact that $(V_1, V_2)$ is a maximum bisection of G. Therefore, $V_1\cap S\ne \emptyset$ and $V_2\cap S\ne \emptyset$.

(b) $X_5^1=\emptyset$. Since $|S|> \frac{n}{2}$, $V_1\cap S\ne \emptyset$ and $V_2\cap S\ne \emptyset$.

Assume that $S'$ and $S''$ are two subsets of S such that $S'$ is contained in $V_1$, and $S''$ is contained in $V_2$. Without loss of generality, assume that $|S'|\le |S''|$. Let R be any subset of $S''$ of size $|S'|$. Let $V''_1=V_1-S'$, $V''_2=V_2-R$. Then, $|V''_1|=|V''_2|$. Denote the new graph with bisection $(V''_1, V''_2)$ by $G'$. It is easy to see that $|E(V_1, V_2)|$ is bounded by $\lceil m/2\rceil +k$ if and only if $|E(V''_1, V''_2)|$ is bounded by $\lceil m'/2\rceil +k$, where $m'$ is the number of edges in $G'$. Repeat the above process until $|S|+|X_5^1| \le \frac{n}{2}$.    $\square$

For a given instance (G, k) of PMBTLB, by applying Rule 2 on G exhaustively, we can get following result.

Lemma 14

For a given instance (G, k) of PMBTLB, if $|S|>|X_0|$, then the number of vertices in G is bounded by 8k.

Proof

Based on block cluster $\mathcal C'''$, we prove this lemma by analyzing the sizes of $S'$, $X_5^2$ and $X_5^3$.

(1) $|S'|\ge |X_5^2|+|X_5^3|$. By Lemma 3 and inequalities (1), (7) and (8), we can get that $r(\mathcal{C'''})=|MM|+\frac{|X_2\backslash S|}{2}+|X_0|+|X_5^2|+|X_5^3|< 2k$. Since $|MM|=(|Z|+|Y|+|X\backslash (X_0\cup X_2\cup X_5)|)/2$, we can get that $|Z|+|Y|+|X\backslash (X_0\cup S\cup X_5)|+ 2(|X_0| +|X_5^2|+|X_5^3|)<4k$. Since $X_5=X_5^1\cup X_5^2\cup X_5^3$, and S, $X_5^1$, $X_5^2$, $X_5^3$, $X_0$ are disjoint, we have

$$\begin{aligned} |Z|+|Y|+|X|-|S|-|X_5^1|+|X_0|+|X_5^2|+|X_5^3| < 4k. \end{aligned}$$

(10)

By Lemma 13, $|S|+|X_5^1|<n/2$. Then, we can get that

$$\begin{aligned} |V|=|Z|+|Y|+|X|&=|Z|+|Y|+ |X\backslash (S\cup X_5^1)|+|S| + |X_5^1|\nonumber \\&=\underbrace{ |Z|+|Y|+|X|-|S|-|X_5^1| }_{<4k \, \mathrm by\, (10)}+|S|+|X_5^1|\nonumber \\&< 4k +|V|/2. \end{aligned}$$

Therefore, $|V|< 8k$.

(2) $|S| < |X_5^2|+|X_5^3|$. By Lemma 3 and inequalities (1), (7) and (9), we have $r(\mathcal{C'''})=|MM|+\frac{|X_2\backslash S|}{2}+|X_0|+|S'|< 2k$. Since $Q\subseteq S$, $S' = S\backslash Q$ and $|X_0|=|Q|$, we can get that $r(\mathcal{C'''})=|MM|+\frac{|X_2\backslash S|}{2}+|S| < 2k$. Similarly, $|MM|=(|Z|+|Y|+|X\backslash (X_0\cup X_2\cup X_5)|)/2$. Then, $|Z|+|Y|+|X\backslash (X_0\cup S\cup X_5)|+ 2|S|<4k$. Since S, $X_5$, $X_0$ are disjoint and $|X_0|<|S|$, we can get that

$$\begin{aligned} |Z|+|Y| +|X|-|X_5| < 4k. \end{aligned}$$

(11)

By Lemma 6, $|X_5|< 2k$. Then, we can get that

$$\begin{aligned} |V|=|Z|+|Y|+|X|&=|Z|+|Y|+ |X\backslash X_5|+|X_5| \nonumber \\&=\underbrace{|Z|+|Y|+|X|-|X_5|}_{<4k\, \mathrm by\,(11)} +|X_5|\nonumber \\&<4k +2k=6k. \end{aligned}$$

Therefore, if $|X_0|<|S|$, the number of vertices in G is bounded by 8k.   $\square$

For a given instance (G, k) of PMBTLB, our kernelization algorithm is to apply Rule 1 and Rule 2 on G exhaustively. By Lemmas 10 and 14, we can get the following result.

Theorem 1

The PMBTLB problem admits a vertex kernel of size 8k.