A Linear Kernel for Independent Set Reconfiguration in Planar Graphs

We show $\mathrm{ISR}-\mathrm{TJ}(G^{\prime },I_s,I_t)$ and $\mathrm{ISR}-\mathrm{TJ}(G,I_s,I_t)$ are equivalent. Since $G^{\prime }\subseteq G$, if the latter is a no-instance, then so is the former. So assume instead that $\mathrm{ISR}-\mathrm{TJ}(G,I_s,I_t)$ is a yes-instance. First, suppose that it is impossible, starting from $I_s$, to ever unlock a big 2-class. So all big 2-classes will always remain locked, and it is impossible to ever move a token to a vertex of a big 2-class. Thus, since every vertex of $V(G)\setminus V(G^{\prime })$ is in a big 2-class, every reconfiguration sequence in $G$, starting from $I_s$ is also valid in $G^{\prime }$. This proves the desired result. The argument is identical if it is imposible to unlock a big 2-class, starting from $I_t$. Thus, we assume instead that, starting from both $I_s$ and $I_t$, it is possible to unlock some big 2-class. Now we are done by Lemma 4. $◀$

The second statement follows from the first by Lemma 5; thus, we prove the first.

Assume $|{𝒞}_1|\ge {\chi }_{up}(G)k$. By definition, $G$ is ${\chi }_{up}(G)$-colorable, and we can compute such a coloring efficiently. By Pigeonhole, ${𝒞}_1$ contains an independent set $I_m$ (for middle) of size ${\chi }_{up}(G)k/{\chi }_{up}(G)=k$. Starting with tokens on $I_s$, for each $v\in I_s$ with a neighbor $w_v\in I_m$, move the token on $v$ to some such $w_v$. Now move all remaining tokens (in an arbitrary order) to the unoccupied vertices of $I_m$. By symmetry, we can also move all tokens from $I_t$ to $I_m$. Thus, we have a yes-instance of $\mathrm{ISR}-\mathrm{TJ}(G,I_s,I_t)$, as claimed. $◀$

Henceforth we assume . Recall from above that $N_3(G)$ denotes the number of sets $Y\subseteq X$ with $|Y|\ge 3$ and ${𝒞}_Y\ne \mathrm{\varnothing }$. The next lemma follows directly from the fact that $G$ is $K_{3,r}$-minor-free.

Suppose the lemma is false. By Pigeonhole, there exists $Y\subseteq X$ with $|{𝒞}_Y|\ge \lceil |{𝒞}_3|/N_3(G)\rceil >(r-1)N_3(G)/N_3(G)$. That is, $|{𝒞}_Y|\ge r$. But now $G$ contains the subgraph $K_{3,r}$ with the vertices in the part of size 3 in $Y$ and those in the part of size $r$ in ${𝒞}_Y$. This contradicts that $G$ is $K_{3,r}$-minor-free. $◀$

When $G$ is planar, we can use Euler’s formula to improve the bound above.

We draw a plane graph $G_X$ with vertex set $X$ where each set $Y\subseteq X$ with $|Y|=2$ and $C_Y\ne \mathrm{\varnothing }$ corresponds to an edge of $G_X$. Think of restricting $G$ to $X$ and one vertex $v_Y$ in $C_Y$ for each such $Y$ with $|C_Y|=2$ (deleting any edges among vertices of $X$). For each $v_Y$, we now contract exactly one of its two incident edges. Note that for the resulting plane graph $G_X$ its number of edges is precisely $|N_2(G)|$, the number of $2$-classes of $G$. By Euler’s Formula, $G_X$ has at most $3|X|-6$ edges, so $N_2(G)\le 3|X|\le 6k$.

For every class $C$ in ${𝒞}_3$, we choose one representative $x_C$ (recall that $x_C\notin X$). We denote by $p$ the number of such classes, i.e., $p:=|N_3(X)|$. We now construct the bipartite graph with parts $X$ and $\{x_C:C\in {𝒞}_3\}$; that is, we consider the subgraph induced by these vertices, but with all edges removed that have both endpoints inside $X$ or have both endpoints inside $\{x_C:C\in {𝒞}_3\}$. The resulting graph is indeed a bipartite planar graph. By Euler’s formula, the number of edges of a bipartite planar graph is at most twice its number of vertices. So we have , which implies that , as claimed. $◀$

The neighborhood complexity of a graph class $𝒢$ is the smallest function $f$, if it exists, such that for all $G\in 𝒢$, nonempty $A\subseteq V(G)$, and nonnegative integers $r$, we have the bound $|\{N^s[v]\cap A:v\in V(G)\}|\le f(s)|A|$. Here $N^s[v]$ is the set of vertices at distance at most $s$ from $v$. We need the following result.

Since we are interested only in neighborhoods (that is, distance 1), we let $s:=1$. Since $G$ is $K_{3,r}$-minor-free, it is also $K_{3+r}$-minor-free. So we let $t:=r+3$. Finally, we let $A:=X$ and recall that $|A|=|X|\le 2k$.

Combining the results in this subsection, we get the following.

We start with the first statement. If $G$ is $K_{3,r}$-minor-free, with $r\le 6300$, then also $G$ is $K_{3,6300}$-minor-free. So the bound on $|{𝒞}_1|$ follows from Lemma 6, and the bound on $|{𝒞}_3|$ follows from Lemma 7 and Corollary 10. Summing these bounds gives the first statement.

Now we prove the second statement. By Lemma 6, we assume that $|{𝒞}_1|\le 4k$. By Lemma 7 (with $r:=3$) and Lemma 8 we get that $|{𝒞}_3|\le (3-1)(4k)=8k$. Summing these bounds gives the second statement. $◀$

If $|{𝒞}_2|\le {\chi }_{up}(G)(N_2(G)(4r-1)+k)$, then we are done, trivially. So assume not. Now we define $I$ and delete vertices of big 2-classes as in Construction 13. If a 2-class ${𝒞}_Y$ is either small or intersects $I$ in at most $3r-2$ vertices, then in ${𝒞}_2^{\prime }$, we keep at most ${\chi }_{up}(G)(2r-1)$ vertices of ${𝒞}_Y$. Thus, the total number of vertices in these classes (restricted to $G^{\prime }$) is at most $N_2(G){\chi }_{up}(G)(2r-1)$.

If a 2-class ${𝒞}_Y$ is big and intersects $I$ in at least $3r-1$ vertices, then in $G^{\prime }$ we keep in ${𝒞}_Y$ only its vertices in $I$. Thus, the total number of vertices in these classes (restricted to $G^{\prime }$) is at most $|I|\le N_2(G)(3r-2)+k$. So the total size of ${𝒞}_2^{\prime }$ is at most $N_2(G){\chi }_{up}(G)(2r-1)+N_2(G)(3r-2)+k\le {\chi }_{up}(G)(N_2(G)(4r-1)+k)$. $◀$

A helpful independent set is any subset of $I$ of size $k$. Since $I$ is independent, the following is clear.

For a $2$-class ${𝒞}_Y$, we call the 2 vertices in $Y$ the key vertices of ${𝒞}_Y$. To unlock a big 2-class ${𝒞}_Y$ is to move tokens to reach an independent set $I^{\prime }$ such that $|I^{\prime }\cap N({𝒞}_Y)|\le 1$. After we unlock a class ${𝒞}_Y$, we can move the single token in $N({𝒞}_Y)$, if it exists, onto ${𝒞}_Y$ and then move additional tokens onto ${𝒞}_Y$ (provided that ${𝒞}_Y$ contains a large enough independent set).

If not, then $G$ contains a $K_{3,r}$-minor, where one side consists of the vertices $x,x^{\prime }$, and the component $A$ with $r$ neigbhbors in $C$, and the other side consists of $r$ vertices of $N(A)\cap C$. $◀$

Assume that there exists an independent set $J_0^{\prime }$ that can be reached from $I_s$ such that $|N(C)\cap J_0^{\prime }|=1$ for some big class $C$. Among all transformations from $I_s$ to $J_0^{\prime }$, take a transformation $ℛ$ of minimum length. The case when $ℛ$ has length 0 (that is $J_0^{\prime }=I_s$) is easier, so we handle it briefly at the end. For now we assume that $ℛ$ has positive length.

We claim that: (i) the last step of $ℛ$ consists in moving a token on a key vertex $x$ of class $C$ to some vertex $z$ and, (ii) each jump of the transformation except the last one consists of moving a token (from its current vertex) to an adjacent vertex. Point (i) follows from the minimality of the transformation. At some step in $ℛ$, we move a token away from a key vertex of some big 2-class. If $ℛ$ continues with further steps, then we can omit these steps, contradicting the minimality of $ℛ$. Point (ii) holds because if, prior to the last step in $ℛ$, we moved a token from a vertex $v$ to a vertex $w$, with $w$ not adjacent to $v$, then we should have instead moved the token on the key vertex $x$ to $w$; this gives a shorter transformation, again contradicting the minimality of $ℛ$.

We form $G^{\prime \prime }$ from $G$ by deleting all vertices in big classes and all key vertices for big classes. Now (ii) above implies that all vertices that have gained or lost a token during $ℛ$ must be in the same component of $G^{\prime \prime }$; otherwise we can simply omit from $ℛ$ all moves in components of $G^{\prime \prime }$ other than the component where we move our token on our final move, which unlocks $C$.

We claim that each big class $C^{\prime }$ has at most $2(r-1)$ vertices with neighbors in $J_0^{\prime }\setminus I_s$, as follows. Let $z$ denote the vertex where we move a token on the final step of $ℛ$ (unlocking $C$). Note that all vertices of $J_0^{\prime }\setminus (I_s\cup \{z\})$ belong to the same component of $G^{\prime \prime }$; this follows from the previous paragraph, since each of these vertices received a token during $ℛ$ (excluding its last step). Lemma 16 ensures that each big class $C^{\prime }$ has at most $r-1$ vertices with neighbors in $J_0^{\prime }\setminus (I_s\cup \{z\})$. Lemma 16 also ensures that each big 2-class $C^{\prime }$ has at most $r-1$ neighbors of $z$. Thus, the claim holds.

By the definition of $J_0^{\prime }$, there is a big 2-class $C$ that has been unlocked; that is $J_0^{\prime }$ only contains a token on at most one of the two key vertices of $C$. Regardless of whether or not $C$ contained (in $G$) at least $3r-1$ vertices of $I$, we know that $C$ contains in $G^{\prime }$ an independent set of size at least $2r$. From above, at most $2r-2$ of these vertices have neighbors in $J_0^{\prime }\setminus I_s$. So at least $2r-(2r-2)=2$ of them have no such neighbor. We denote by $\{a,b\}$ an independent set of size 2 in $C\setminus N(J_0^{\prime }\setminus I_s)$.

By Lemma 16, each of $a,b$ has at most $r-1$ neighbors in each other big class $C^{\prime }$. Actually, let $x,y$ denote the key vertices for the big 2-class $C$ that contains $a,b$. For each big class $C^{\prime }$, with $C^{\prime }\ne C$, one of $x$ and $y$ is not a key vertex for $C^{\prime }$; by symmetry, we assume $x$ is not. If $|N(\{a,b\})\cap C^{\prime }|\ge r$, then we get a $K_{3,r}$-minor by contracting $\{a,b\}$ onto $x$ (with $x$ and the two key vertices of $C^{\prime }$ as the part of size 3). Thus, $|N(\{a,b\})\cap C^{\prime }|\le r-1$. So for each class $C^{\prime }$ containing at least $3r-1$ vertices of $I$, we know that $|(C^{\prime }\cap I)\setminus N(\{a,b\}\cup (J_0^{\prime }\setminus X))|\ge (3r-1)-(r-1)-(r-1)-(r-1)=2$. We denote by $I^{\prime }$ the set $I\setminus N(\{a,b\})$. Note in particular that by construction $I^{\prime }$ contains at least $2$ vertices in each big 2-class that contains (in $G^{\prime }$) vertices of $I$.

Let $C_1,\mathrm{\dots },C_{\mathrm{\ell }}$ be the big classes intersecting $I$ in $G^{\prime }$ (different from $C$ if $C$ also intersects $I$). Let $b$ be a vetex of $I^{\prime }\cap C_1$ and $x_1$ be a key vertex of $C_1$. Note that no vertex of $J_0^{\prime }$ is adjacent to $b$. So we can move the token⁴⁴4If $x_1=x$, then we have already moved the token that was on $x_1$, so we now do nothing. on $x_1$ to $b$ to reach an independent set that we denote by $J_0$. Note that $C_1$ is unlocked in $J_0$ (since $|N(C_1)\cap X|=1$.) We can now unlock all the big classes $C_1,\mathrm{\dots }{C}_i,\mathrm{\dots },C_{\mathrm{\ell }}$ intersecting $I$ in $G^{\prime }$, by induction.

At the end of this transformation, we get an independent set $J_{\mathrm{\ell }}$ where every big class containing vertices of $I$ has been unlocked. Moreover, by construction, vertices of $J_{\mathrm{\ell }}\setminus I$ have at most $3r-3$ neighors in each big class. When constructing $G^{\prime }$ from $G$, we deleted vertices of $I$ only in step (5b). So the number of vertices of $I$ we deleted is at most $N_2(G)(3r-2)$. Thus, the total number of vertices in $I$ (in $G$) that are unavailable in $G^{\prime }$ to receive tokens from $J_{\mathrm{\ell }}$ is at most $N_2(G)(3r-2)$. So the number of vertices available to receive tokens, from $J_{\mathrm{\ell }}$ is at least $|I|-N_2(G)(3r-2)=k$. Hence, in $G^{\prime }$ all the tokens of $J_{\mathrm{\ell }}$ can be moved to $I$, as desired.

Now we remark briefly on the case that $ℛ$ has length 0; that is, some big 2-class $C$ is already unlocked. In this case, we just begin immediately moving tokens to $a,b$ in $C$. Now each big 2-class $C^{\prime }$ has at most $r-1$ vertices in $N(\{a,b\})$, but we do not need to worry about neighbors of $z$ in the component of $G^{\prime \prime }$ where other moves occurred. So the analysis above still holds. $◀$

If some vertex $v$ in $C$ has at least 3 neighbors in $C$, say $w_1,w_2,w_3$, then $G$ contains as a subgraph $K_{3,3}$, with $\{w_1,w_2,w_3\}$ in one part and with $v$ and the key vertices for $C$ in the other. This $K_{3,3}$ contradicts that $G$ is planar. And if $C$ induces a cycle $H$, then $H$ separates the key vertices, so no other vertex is adjacent to both key vertices. Thus, $H$ spans $C$. $◀$

In particular, every $2$-class $C$ contains an independent set of size $\lfloor |C|/2\rfloor$. Moreover, if we consider a strict subset of $C$, that is a set $D⊊C$, then $D$ induces a disjoint union of paths; so $D$ admits an independent set of size at least $\lceil |D|/2\rceil$. The subset $D$ is typically formed from $C$ by deleting $2$ vertices. We usually remove vertices to guarantee that $2$-classes are anticomplete to each other (disjoint vertex subsets $A$ and $B$ are anticomplete to each other if no edge of $G$ has one endpoint in $A$ and the other in $B$). Namely, we often use the following remark.

In the case of planar graphs, we can actually strengthen Remark 21(a) to apply to more than two classes, and we prove the following version.

Consider a plane drawing of the subgraph of $G$ induced by ${\cup }_{i\le r}{C}_i\cup X$ such that the outer face of the drawing contains either the 2 key vertices of $C_r$ or 2 vertices contained in $C_r$, possibly both. For every class $C_i$, let $G_i$ denote the subgraph induced by $C_i$ and its 2 key vertices. A class $C_i$ is nested in $C_j$ if all the vertices of $C_i$ lie within a face of $G_j$ distinct from its outer face. Two classes $C_i$ and $C_j$ are incomparable if the vertices of $C_a$ are on the outer face of $G_b$ whenever $\{a,b\}=\{i,j\}$. For every $2$-class $C$, the vertices of $C$ plus its two key vertices form a $K_{2,|C|}$ (possibly with extra edges among $C$), so every pair of classes is either nested or incomparable.

Now, for every , let $B_i$ denote the at most two vertices of $C_i$ on the boundary of $G_i$, and let $C_i^{\prime }:=C_i\setminus B_i$. We claim that, $C_i^{\prime }$ is anticomplete to $C_j^{\prime }$ for every $j\ne i$ (with $C_r^{\prime }:=C_r$). If the two classes are incomparable, then the only vertices of $C_i$ that can be adjacent to $C_j$ are the vertices of $B_i$ and $B_j$, but the vertices of at least one of these sets are excluded from $C_i^{\prime }\cup C_j^{\prime }$ (and the vertices of both are if $r\notin \{i,j\}$). Otherwise, up to symmetry, $C_i$ is nested in $C_j$. By the definition of the plane drawing, $i\ne r$ and the vertices of the outer face of $C_i$ are excluded from ${𝒞}_i^{\prime }$. $◀$

Later we will need a slight variation of Lemma 22. (Its proof is nearly identical to that above.)

Since $I$ is $I_s$-weakly greedy, we simply need to prove that we can move the tokens from the activation pair of $I_s$ to the activation pair of $I$. Indeed, if we can do this, then afterward we can complete the transformation, from $I_s$ into $I$, greedily.

First suppose that $I$ is $3$-clean. By definition, the activation pair $\{i_1,i_2\}$ of $I$ is in $C$ and the activation pair $\{j_1,j_2\}$ of $I_s$ contains the vertex $j_1$ of $N(C)\cap I_s$ (if it exists). We can replace⁶⁶6By replace $a$ with $b$ we mean to move the token from vertex $a$ to vertex $b$; this replaces $a$ with $b$ in the independent set defined by the vertices currently with a token. $j_1$ with $i_1$ and replace $j_2$ with $i_2$ (since $N(C)\cap I_s$ has at most one vertex, namely $j_1$) and the conclusion follows.

Now instead assume that $I$ is $(2,2)$-clean. If $|N(C)\cap X|\le 1$, then we can perform the same moves and the conclusion follows similarly. So we assume that the activation pair of $I_s$ is $\{x,j_2\}$, the two vertices of $N(C)\cap X$. By assumption not all the vertices of $N(C\cup C^{\prime })\cap X$ are in $I_s$. So the second key vertex of $C^{\prime }$ is not in $I_s$. Thus, we can replace $x$ with a vertex $y^{\prime }$ of $I\cap C^{\prime }$, replace $j_2$ with $i_1$, and finally replace $y$ with $i_2$. This completes the proof. $◀$

From now on, by Lemma 24, we assume that the classes $C$ and $C^{\prime }$ are locked, that is $N(C)\cap I_s$ and $N(C^{\prime })\cap I_s$ each have size $2$. In particular, the activation pair of $I$ is $N(C)\cap I_s$. If $I$ is $3$-clean (resp. $(2,2)$-clean), then the vertex of $I\cap C$ (resp. the two vertices of $I\cap C^{\prime }$) that is not in the $I$-activation pair (if several such vertices exist, then we choose one of them arbitrarily) is called the auxiliary activation vertex (resp. vertices) of $I$. Moreover, if $I$ is $(2,2)$-clean, then the key vertex of $C^{\prime }$ that is not a key vertex of $C$ is called the auxiliary activation vertex of $I_s$.

An independent set is clean for $I_s$ if it is $I_s$-greedy, $3$-clean for $I_s$, or $(2,2)$-clean for $I_s$. As we already mentioned, it is weakly clean if it is clean but not $I_s$-greedy. And if $I$ is $I_s$-greedy, then we can transform $I$ into $I_s$. We now explain informally how we will make use of an independent set that is $3$-clean or $(2,2)$-clean for $I_s$. We will argue that if we can unlock a large enough class $D$, then (if we consider a good transformation) we can replace an $X$-vertex adjacent to $C$ (resp. replace $x$, when $I$ is $(2,2)$-clean) with a vertex in the class $D$. This fact, together with the fact that $C\cap I$ (resp. $(C\cup C^{\prime })\cap I$) is large enough will allow us to find a transformation from $I_s$ into $I$. We formalize this intuition with the following simple example.

The conclusion follows if the independent set $I$ is $I_s$-greedy. So we instead assume that $I$ is weakly $I_s$-greedy. Thus, if we can replace the activation pair of $I_s$ by the activation pair of $I$, then we can complete the transformation greedily. The rest of the proof consists in showing that we can do this. Let $\{i_1,i_2\}$ be the $I$-activation pair and $i_3$ be an auxiliary $I$-activation vertex (and $i_4$ be the other if $I$ is $(2,2)$-clean). We denote by $C$ the class containing $i_1,i_2$ (and by $C^{\prime }$ the class containing $i_3$ if $I$ is $(2,2)$-clean). Since $G$ is $K_{3,3}$-free, there is a non-edge between some vertex $a\in V(G)\setminus N(I_s)$ and some vertex $i_b$ of $\{i_1,i_2,i_3\}$.