Pushing the Frontiers of Subexponential FPT Time for Feedback Vertex Set

Given an $n$-vertex graph $G$ and a parameter $k\in \mathbb{N}$, the Feedback Vertex Set problem (FVS for short) asks whether there exists a set $S$ of at most $k$ vertices such that $G-S$ has no cycle. This is a fundamental decision problem in graph theory and one of Karp’s 21 NP-complete problems. Because of its hardness in a classical setting, the problem has been widely studied within the realm of parameterized complexity. This line of research aims to investigate the existence of FPT algorithms, i.e., algorithms that run in time $f(k)\cdot n^{𝒪(1)}$, for some computable function $f$. Such algorithms provide a fine-grained understanding on the time complexity of a problem and describe regions of the input space where the problem can be solved in polynomial time. Note that it is crucial here to obtain good bounds on the function $f$ since the (potentially) super-polynomial part of the running time is confined in the $f(k)$ term. In this direction it was proved that under the Exponential Time Hypothesis of Impagliazzo, Paturi and Zane, FVS does not admit an algorithm with running time $2^{o(n)}{n}^{𝒪(1)}$ (see [11]). Nevertheless certain classes of graphs (typically planar graphs) have been shown to admit algorithms with running times of the form $2^{𝒪(k^{\epsilon })}{n}^{𝒪(1)}$ (for some ), i.e., where the contribution of the parameter $k$ is subexponential. Such algorithms are called subexponential parameterized algorithms and they are the topic of this paper. Given the numerous existing results on this theme, there are two main directions of research: to improve the running times in the classes where an algorithm is already known, or to extend the tractability horizon of FVS by providing more general settings where subexponential FPT algorithms exist. We are here interested by the second direction, that can be summarized by the following question.

Historically, a primary source of graph classes studied to make progress on the above question was geometric intersection graphs. In an intersection graph, each vertex corresponds to a subset of some ambient space, and two vertices are adjacent if and only if the subsets intersect. Taking the Euclidean plane as the ambient space, many graph classes can been defined by setting restrictions on the subsets used to represent the vertices. One can for instance consider intersection graphs of disks in the plane, or segments, or Jordan arcs¹¹1In the following, those are called strings.. With such subsets, one defines the class of disk graphs, segment graphs, and string graphs respectively. It is also often the case that there are conditions dealing with all the $n$ subsets representing the vertices of a given graph. For example, if we consider disks (resp. segments) one can ask those to have the same diameter (resp. to use at most $d$ different slopes), and this defines the class of unit disk graphs (resp. $d$-DIR graphs). When considering strings, one possible property is that any string has at most $d$ points shared with the other considered strings. This defines string graphs with edge degree at most $d$. A weaker condition is to ask every pair of the considered strings to intersect on at most $s$ points, this defines $s$-string graphs. This class generalizes several natural classes such as planar graphs, map graphs, unit-disk graphs, segment graphs, string graphs of bounded edge-degree, and intersection graphs of $\alpha$-convex bodies that exclude a fixed subgraph (see [25, 18, 3]).

For all these graph classes, FVS is NP-complete, and actually under ETH none of them admits a $2^{o(\sqrt{n})}$-time algorithm. Indeed, this lower bound was given in [12] for induced grid graphs, which form a subclass of unit disk graphs and $2$-DIR graphs. On the other hand for each of the aforementioned classes there is an algorithm solving FVS in subexponential time. More precisely, this algorithm applies to any string graph and runs in time $2^{\widetilde{𝒪}(n^{2/3})}$ [9].²²2The notation $\widetilde{𝒪}$ ignores polylogarithmic factors, i.e. we write $g(x)=\widetilde{𝒪}(f(x))$ if for some $c$ we have $g(x)=𝒪(f(x)\cdot {\log }^{c}x)$. Regarding subexponential parameterized algorithms, the case of unit disk graphs was settled with an algorithm whose running time matches the ETH lower bound [2]. This result uses the fact that these graphs admit vertex partitions into cliques such that each of these cliques is adjacent to only a constant number of the other cliques. Such a property does not hold for the other graph classes mentioned above. However, other techniques have been developed to deal with the other aforementioned classes such as the classes of bounded edge degree string graphs [3], contact-segment and square graphs [5], disk graphs [21, 1], or the pseudo-disk graphs [4]. Note that when dealing with classes of intersection graphs, the representation of the input (if known) could be used by the algorithm. Some of these algorithms are robust, meaning that the input graph $G$ is provided using one of the classical graph data structures, where there is no indication of the intersection model of $G$. Because the recognition problem is difficult for most of the classes discussed above, robustness is a substantial advantage.

Toward answering 1, in the same spirit as in [23], which introduces a generic setting where certain hitting problems can be solved in subexponential parameterized time, we identify sufficient conditions for a graph class (then said to be nice) to admit a subexponential parameterized algorithm for FVS. As we will see later these conditions are satisfied by several natural graph classes, some of which were not known to admit a subexponential parameterized algorithm prior to this work.

Let us now provide some intuition behind the conditions we require for a nice graph class. We discuss here the similarities between these conditions and classical studied properties, while the reasons why these conditions help to get a subexponential parameterized algorithm for FVS are examined in Section 2. A starting point is to review known results about the class of string graphs, which constitutes a good candidate to answer the previous question. In particular, the following results are known for string graphs. For a graph $H$, let us say that a graph is $H$-free if it does not contain $H$ as subgraph.

These results³³3Note that an error was found in the proof of the above results in [20], but a claim by the author was made that the proof can be corrected in the case of string graphs (see [10]). Moreover the earlier bound in [24] yields similar results, up to logarithmic factors. are interesting in our case, as a simple folklore branching allows us to reduce the problem to the case where the instance $(G,k)$ of FVS is $K_{r,r}$-free for $r=\lceil k^{\epsilon }\rceil$. Thus, among the conditions required for a graph class to be nice, two of them correspond to a relaxed version of the above theorems.

Our last main condition is related to neighborhood complexity. A graph class $𝒢$ has linear neighborhood complexity (with ratio $c$) if for any graph $G\in 𝒢$ and any $X\subseteq V(G)$, $|\{N(v)\cap X,v\in V(G)\}|\le c|X|$. It is known that bounded-expansion graph classes have linear neighborhood complexity [26] as well as bounded twin-width graphs [8]. In previous work on parameterized subexponential algorithms [22, 1, 4, 5], it appeared useful that the considered graphs have the property that, if $G$ is $K_{r,r}$-free (or even $K_r$-free), then for any $X\subseteq V(G)$, $|\{N(v)\cap X,v\in V(G)\}|\le r^{𝒪(1)}|X|$. Notice that this is slightly stronger than requiring that a class that is $K_{r,r}$-free (or $K_r$-free) for a fixed $r$ has linear neighborhood complexity, as it is important for our purpose that the dependency in $r$ is polynomial. We point out that $K_{r,r}$-free string graphs have bounded-expansion, hence linear neighborhood complexity, however this does not imply that the dependency in $r$ is polynomial. Thus, our last main condition (called bounded tree neighborhood complexity) can be seen as a slightly stronger version of this “polynomially dependent” neighborhood complexity. Let us now proceed to the formal definitions.

Our main result is the following.

Actually we provide a single generic algorithm for all nice classes (which requires the values of $\alpha ,f_1,f_2,d$, but not $f$ and $\delta$). The techniques used to prove the above result are discussed in Section 2. For the time being, let us focus on consequences. As hinted above, being nice is a natural property shared by several well-studied classes of graphs. In particular we show that it is the case for $s$-string graphs and pseudo-disk graphs, hence we have the following applications.

Observe that the two corollaries above encompass a wide range of classes of geometric intersection graphs for which subexponential parameterized algorithms have been given in previous works such as planar graphs, map graphs, unit-disk graphs, disk graphs, or more generally pseudo-disk graphs, and string graphs of bounded edge-degree. In this sense our main result unifies the previous algorithms.

Also, it captures new natural classes such as segment graphs, or more generally $s$-string graphs, where previous tools were not sufficient (as discussed in Section 2). We point out that before this work, the existence of subexponential parameterized algorithm for FVS was open even for the very restricted class of $2$-DIR graphs.

Generality has a cost and the running time bound we obtain for pseudo-disk graphs is worst than the one obtained in [4], which heavily relied on the input pseudo-disk representation. On the other hand our algorithm has the extra property of being robust (i.e., it does not require a geometric representation) which is a relevant advantage for those classes of intersection graphs where computing a representation is difficult.

In this paper logarithms are binary and all graphs are non-oriented and simple. Unless otherwise specified we use standard graph theory terminology, as in [13] for instance. For a graph $G$, and $v\in V(G)$, we denote $N_G(v)$ the neighbors of $v$. We omit the subscript when it is clear from the context. For $A\subseteq V(G)$, we use the notation $N(A)=\left({\cup }_{v\in A}N(v)\right)\setminus A$ and denote $G[A]$ the subgraph induced by $G$ on $A$. For $v\in V(G)$ and $B\subseteq V(G)$, we denote $N_B(v)=N(v)\cap B$ and for $A\subseteq V(G)$ we denote $N_B(A)=N(A)\cap B$, with the additional notation $d_B(A)=|N_B(A)|$. For a graph $H$ we say that $G$ is $H$-free if $H$ is not a subgraph of $G$. Two disjoint vertex subsets or subgraphs $Z,Z^{\prime }$ of a graph $G$ are said to be non-adjacent (in $G$) if there is no edge in $G$ with one endpoint in $Z$ and the other in $Z^{\prime }$.

Even if our goal is to abstract from a specific graph class, let us consider in this section the class of $2$-DIR graphs, corresponding to the intersection graphs of vertical or horizontal segments in the plane. As these objects are non “fat”⁵⁵5A connected regions $R$ of the plane is said to be $\alpha$-fat if the radius of smallest disk enclosing $R$ is at most $\alpha$ times larger than the radius of the largest disk enclosed in $S$. A family of regions of the plane is then said to be fat if there exists $\alpha$ such that all the elements of the family are $\alpha$-fat. and can cross (unlike pseudo-disks), this class constitutes a good candidate to exemplify the difficulties.

A common approach is as follows. Given an instance $(G,k)$ of FVS, we compute first in polynomial time a $2$-approximation, implying that we either detect a no-instance, or define a set $M$ with $|M|\le 2k$ and such that $G-M$ is a forest. The goal is then to reduce, using kernelization or subexponential branching rules, to equivalent instances $(G^{\prime },k^{\prime })$ with small treewidth, that is $\text{tw}(G^{\prime })=𝒪(k^{1-\epsilon })$. As FVS can be solved in $2^{\widetilde{𝒪}(\text{tw}(G^{\prime }))}{n}^{𝒪(1)}$ using a classical dynamic programming approach, we get a subexponential parameterized algorithm. Thus, one has to find a way to destroy in $G$ the obstructions preventing a small treewidth. A first type of obstructions is $K_r$ and $K_{r,r}$, which are easy to handle as there are folklore subexponential branchings when $r=k^{\epsilon }$. Now, one can see the hard part as destroying $K_{r,r}$ hidden (as a minor for example) (see Figure 1).

A point that seems crucial to us is the following. In intersection graphs of “fat objects” (like disks, squares, or pseudo-disks more generally), the “locally non planar structure” when an object (vertex $v$ in Figure 1) is “traversed” (by $v_1$, $v_2$ in Figure 1) comes to the price of an edge ($\{v_1,v_2\}$) in the neighborhood of $v$. Thus, the presence of a large $K_{r,r}$ as a minor implies that a large matching $E_v$ (of size $\mathrm{\Omega }(r)$) will appear in the neighborhood of a vertex $v$. However, as $G[\{v\}\cup E_v]$ (called a triangle bundle in [22]) contains $r$ triangles pairwise intersecting on exactly one vertex $v$, the set $\{v\}\cup E_v$ is a good structure to perform a subexponential branching for FVS. Indeed, [21] proposed a “virtual branching” to handle this structure by either taking $v$ in the solution, or absorbing $E_v$ in $M$, implying then that the parameter virtually decreases by $|E_v|$ as a solution which does not contain $v$ has to hit all these edges, even if we cannot branch to determine which are exactly the vertices in the solution.

Once no more virtual branching is possible on large triangle bundles, they obtain by some additional specialized techniques that any vertex in $M$ is such that $N_{V(G)\setminus M}(v)$ is an independent set. Then, it is proved ([21], Corollary 1.1) that in a disk graph where for any $v\in M$, $N_{V(G)\setminus M}(v)$ is an independent set, and where there does not exist a vertex in $V(G)\setminus M$ whose neighborhood is contained in $M$, then $tw(G)=𝒪\left(\sqrt{|M|}\omega {(G)}^{2.5}\right)$, where $\omega (G)$ denotes the maximum size of a clique in $G$. This no longer holds for $2$-DIR graphs: the family of pairs $(G,M)$ depicted on the right of Figure 1 is indeed a counter example as they respect the conditions, have $\omega (G)=2$, but $tw(G)=\mathrm{\Omega }(|M|)$.

More generally, the role of the size of a matching in the neighborhood was studied in [5] which shows how subexponential parameterized algorithms can be obtained for graph classes having the “almost square grid minor property” (ASQGM), corresponding informally⁶⁶6In the correct definition ${\mu }_N(G)$ is replaced by a slightly more technical parameter. to $tw(G)=𝒪(\omega {(G)}^{𝒪(1)}{\mu }_N(G)\mathrm{⊞}(G))$ where ${\mu }_N(G)$ is the maximum size of a matching in a neighborhood of a vertex, and $\mathrm{⊞}(G)$ is the largest size of a grid contained as a minor in $G$. The previous counter example shows that $2$-DIR does not have the ASQGM property, implying that we need another approach to handle them.

To simplify the arguments, but still understand why properties in 5 of a nice graph class are needed, let us assume that the forest $G-M$ only contains paths ${(P_i)}_i$, and use the example of segment graphs. This case remains challenging as a large $K_{r,r}$ can still be hidden as a minor (as in Figure 1), and we need to destroy it in order to reduce the treewidth of the graph. To keep notations simple, we use the notation $poly(.)$ to denote a polynomial dependency on the parameter, and thus we do not try to compute tight formulas depending on the polynomial $f_1,f_2,f,d$ given in the definition of a nice class. We assume that we performed folklore branching and that we are left with a $K_{r,r}$-free graph $G$ for $r=k^{\epsilon }$. It is known for string graphs (and thus segment graphs) that in this case $tw(G)=poly(k^{\epsilon })n^{1/2}$ (corresponding to item 3 of the definition of nice). Thus, our goal is to reduce $|V(G)|$ to $𝒪(k^{2-{\epsilon }^{\prime }})$ for some ${\epsilon }^{\prime }$.

A first obvious rule is to iteratively contract edges of $G-M$ whose endpoints have no neighbors in $M$. This explains why we need the property of item 1 of the definition of nice.

Let us now explain how the property of item 2 (bounded tree neighborhood complexity, abbreviated bounded T-NC) allows to obtain the following “degree-related size property”: for any subpath $P$ of a $P_i$, $|P|\le poly(r)(d_M{(P)}^{\alpha +1})$. Define an independent set $𝒯$ of size $|P|/2$ by picking every second vertex in $P$. According to the definition of bounded T-NC (item) with $A=N_M(P)$, we get $|\{N_M(v),v\in 𝒯\}|\le f_1(r){(d_M(P))}^{\alpha }$. Thus, if $|P|\ge x\cdot f_1(r){(d_M(P))}^{\alpha }$, we found $x$ vertices in $P$ having the same neighborhood $M^{\prime }$ in $M$, and thus a vertex $u\in M^{\prime }$ adjacent to $x$ vertices in $P$. If $x$ is large enough (about $d_M(P)$), it is always better to take any arbitrary vertex $u\in M^{\prime }$. This leads to a kernelization rule (denoted (KR₅) in the full version): if there is a vertex $u\in M$ adjacent to approximately $d_M(P)$ vertices in a subpath $P$, delete $u$ and decrease $k$ by one. To sum it up, after applying this rule, for any subpath $P$ of a $P_i$, if we have $d_M(P)=poly(r)$, then $|P|=poly(r)$.

Before the next step we need to apply the following “large degree rule” (denoted (KR₃) in the full version): if there is a vertex $v$ in a $P_i$ such that $d_M(v)>t$, then add $v$ to $M$. One can prove that by taking $t=2d_r$, with $d_r=poly(r)$ the constant defined in item 4 of the definition of a nice class, $M$ does not grow too much after applying this rule exhaustively: by denoting $A\subseteq M$ the set of vertices already in $M$ before applying this rule, we always have $|A|=poly(r)|M\setminus A|$. This claim will be discussed in Subsection 2.3.

Observe that at this stage we may still have a large $K_{r,r}$ as minor, with for example graphs as in Figure 1 where no rule applies. It remains to define a crucial rule to destroy these $K_{r,r}$ minors. Let us now present a partitioning algorithm of the connected components in $G-M$. For any connected component $P_i$ in $G-M$, we start (see Figure 2) from an endpoint of $P_i$ and collect greedily vertices until we find a subpath $P_i^1$ such that $d_M(P_i^1)\ge t$, or that there is no more vertices in $P_i$. If $d_M(P_i^1)\ge t$, then restart a new path starting from the next vertex to create $P_i^2$, and so on. This defines a partition $P_i={\bigcup }_{\mathrm{\ell }\in [x(P_i)]}(P_i^{\mathrm{\ell }})$, where $d_M(P_i^{\mathrm{\ell }})\ge t$ for any $\mathrm{\ell }\in [1,x(P_i)-1]$ and no lower bound for $d_M\left(P_i^{x(P_i)}\right)$. As we applied the large degree rule, we also know that $d_M(P_i^{\mathrm{\ell }})\le 2t$ for any $\mathrm{\ell }\in [1,x(P_i)]$, because collecting at each step a new vertex in the path $P_i^{\mathrm{\ell }}$ can increase $d_M(P_i^{\mathrm{\ell }})$ by at most $t$. This implies, using the degree-related size property introduced above, that $|P_i^{\mathrm{\ell }}|\le poly(r)$ for any $\mathrm{\ell }\in [1,x(P_i)]$. Let us denote ${𝒯}^{+}$ the set of $P_i^{\mathrm{\ell }}$ such that $d_M(P_i^{\mathrm{\ell }})\ge t$ the “large-degree subpaths”. Observe that the last considered subpath $P_i^{x(P_i)}$ of each connected component $P_i$ (on the right of each path of $G-M$ in Figure 2) may have as there was no more vertices to complete it, hence it is not contained in ${𝒯}^{+}$. We denote ${𝒯}^{-}$ those remaining “small-degree subpaths”.

Let us now explain how the bounded T-NC property (item) allows to obtain the following “small number of large-degree subpaths” property. By removing half of the ${𝒯}^{+}$’s, we can get a set ${𝒯}^{{+}^{\prime }}$ of non-adjacent trees (meaning with no edge between the $T_i^{\prime }s$) such that $|{𝒯}^{{+}^{\prime }}|\ge \frac{1}{2}|{𝒯}^{+}|$. We can then apply the T-NC property with $A=M$, $𝒯={𝒯}^{{+}^{\prime }}$ and $p=m=poly(r)$ to obtain $|\{N_M(T),T\in {𝒯}^{{+}^{\prime }}\}|\le poly(r)|M|$. Thus, if $|{𝒯}^{{+}^{\prime }}|\ge x\cdot poly(r)|M|$, we found $x$ large-degree subpaths (denoted $T_i^{\prime }$) having the same neighborhood $X^{\prime }$ in $M$ with $|X^{\prime }|\ge t$. By choosing $x=t$ and considering $X\subseteq X^{\prime }$ with $|X|=t$, we found a structure that we call a $\widetilde{K_{t,t}}$ (see Figure 3), formally defined as a pair $(X,{(T_i)}_{1\le i\le t})$ where

1. (P1)

   $X\subseteq M$ has size $t$,

2. (P2)

   ${(T_i)}_i$ a family of $t$ vertex-disjoint non-adjacent subtrees (paths here) of $G-M$ such that for all $1\le i\le t$, $X\subseteq N_M(T_i)$, and

3. (P3)

   for any $T_i$, $|T_i|\le poly(r)$.

Now, inspired by the “virtual branching rule” for a triangle bundle, we introduce a branching rule (denoted (BR₂) in the full version) that either deletes almost all vertices in $X$, or is adding to $M$ a subset of $t-1$ of the $T_i^{\prime }s$. The complexity behind this rule is fine as in the second branch, the parameter virtually decreases by $t-1$, and $M$ grows by $(t-1){\max }_i\{|T_i|\}=poly(r)$. This explains how we deal with the $K_{t,t}$-minors.

These rules do not suffice to bound $|V(G)\setminus M|$. Recall that any $P\in {𝒯}^{+}\cup {𝒯}^{-}$ is such that $|P|\le poly(r)$, and thus we only need to bound $|{𝒯}^{+}\cup {𝒯}^{-}|$. As we cannot apply the previous rule, we know that the number of big paths is small: $|{𝒯}^{+}|\le poly(r)|M|$. Now, to bound $|{𝒯}^{-}|$, observe that we can partition ${𝒯}^{-}={𝒯}_1^{-}\cup {𝒯}_2^{-}$, where

• $\mathrm{■}$

  ${𝒯}_1^{-}$ is the set of small-degree paths $P_i^{\mathrm{\ell }}$ for some $\mathrm{\ell }>1$ (belonging to the same path $P_i$ than a large-degree path $P_i^{\mathrm{\ell }-1}$).

• $\mathrm{■}$

  ${𝒯}_2^{-}$ is the set of small-degree paths which are entire connected components of $G-M$.

As $|{𝒯}_1^{-}|\le |{𝒯}^{+}|$, it only remains to bound $|{𝒯}_2^{-}|$. Now, we can exploit once again the bounded T-NC property (item) to obtain that, if $|{𝒯}_2^{-}|\ge x\cdot poly(r)|M|$, then we can find $x$ disjoint non-adjacent paths in ${𝒯}_2^{-}$ having the same neighborhood $X$ in $M$. This case is different from the $\widetilde{K_{t,t}}$ case as $X$ may be arbitrarily small (we only know that ), and thus unlike $\widetilde{K_{t,t}}$ this does not decrease the parameter $k$ by a large amount. However, in this case, paths of ${𝒯}_2^{-}$ are just connected components of $G-M$, and we use a last rule (denoted KR₄ in the full version) that identifies paths that can be safely removed. It can be shown that if $x+2$ paths have the same neighborhood in $M$, of size $x$, one of the paths is redundant. Hence after applying the rule exhaustively we can assume .

This concludes the sketch of proof for this restricted setting where the connected components of $G-M$ are paths, as we obtain by taking $\epsilon$ small enough $|V(G)\setminus M|\le poly(r)|M|\le poly(k^{\epsilon })k=𝒪(k^{2-{\epsilon }^{\prime }})$ as required.

We now consider the real setting where given $(G,k)$ where $G$ is $K_{r,r}$-free for $r=k^{\epsilon }$, and given $M$ a feedback vertex set of size at most $2k$, we want to reduce the graph to obtain $|V(G)\setminus M|=𝒪(k^{2-{\epsilon }^{\prime }})$. The approach still consists in partitioning $G-M$ in an appropriate way (called a $t$-uniform partition).

A first problem when trying to adapt the approach of Subsection 2.2 is the degree-related size property. Indeed, for trees we are now only able to obtain that for any subtree $T$ of $G-M$, $|T|\le poly(r)\mu {(T)}^{𝒪(\alpha )}$ where $\mu (T)=\max (d_M(T),b_{\overline{M}}(T))$ and $b_{\overline{M}}(T)=|\{v\in T,N(v)⊈M\cup T\}|$ is the size of the “border of $T$”. Observe that $b_{\overline{M}}(P)$ is at most $2$ for any subpath $P$ of path $P_i$, whereas $b_{\overline{M}}(T)$ can only be bounded by $|T|$ for a subtree $T$. Informally, in the path case $|P|$ was only polynomially dependent on $d_M(P)$, and now $|T|$ is also polynomially depends on $b_{\overline{M}}(T)$.

A second problem is the large degree rule. Suppose that this rule no longer applies (meaning that for every $u\in V(G-M)$, we have $d_M(u)\le t$), and suppose now that because of another rule a vertex $v\in V(G)\setminus M$ is added to $M$, denoting $M^{\prime }=M\cup \{v\}$. Then this can create a new large degree vertex $v^{\prime }$ with $d_{M^{\prime }}(v^{\prime })>t$ (and so $d_M(v^{\prime })=t$). Then $v^{\prime }$ would need to be added and the problem may arise again for another vertex $v^{\prime \prime }$. This “cascading” can easily be prevented if $G-M$ is a forest of paths: it suffices to apply the rule a first time at the start of the algorithm, but with $t^{\prime }=t-2$. We then have for each $v\in V(G-M)$ the bound $d_M(v)\le t-2$, and we do not need to apply the rule again after as adding vertices to $M$ may increase $d_M(v)$ by at most $2$ ensuring the wanted bound $d_M(v)\le t$ for $v\in V(G-M)$. However, in the case of a tree, we can have in $G-M$ a vertex of arbitrarily large degree, so we cannot apply the same solution. The problem is treated with the help of a technical lemma which ensures that throughout the execution of the algorithm we keep $|M|=poly(r)k$.

Finally, a third problem is the definition of the partition. As in the case of paths we want to partition $G-M$ into a “$t$-uniform partition” $𝒯$, where in particular we have $𝒯={𝒯}^{+}\cup {𝒯}^{-}$, and for any $T\in 𝒯$, $d_M(T)\le 2t$ and $|T|\le poly(r)\mu {(T)}^{𝒪(\alpha )}$. The greedy approach presented for the case of paths is now more involved, as we have to cut each tree of $G-M$ into subtrees that have small border $b_{\overline{M}}(T)$, as otherwise the previous bound $|T|\le poly(r)\mu {(T)}^{𝒪(\alpha )}$ becomes useless when $\mu (T)$ is too large.

This partitioning procedure can either:

• $\mathrm{■}$

  Fail and find a subtree $T$ with $|T|>poly(r)\mu {(T)}^{C\alpha }$, for some constant $C$, implying that our degree-related size rule can be applied.

• $\mathrm{■}$

  Fail and find too many subtree $T_i\in {𝒯}^{+}$ with large degree, implying that we found a $\widetilde{K_{t,t}}$, and that our $\widetilde{K_{t,t}}$ rule can be applied.

• $\mathrm{■}$

  Produce a $t$-uniform partition with $|{𝒯}^{+}|\le poly(r)|M|$.

In the third case, we either find another way to apply one more time a reduction rule, or prove that $|V(G)\setminus M|=𝒪(k^{2-{\epsilon }^{\prime }})$.

We believe that one important application of our main theorem is the class of $s$-string graphs (recall that segment graphs are a subclass of $1$-string graphs). To prove that $s$-string graphs is a nice class (and thus captured by our result), one needs to prove that $s$-string graphs have a bounded tree neighborhood complexity. This property is not straightforward, and we would like to point out the following theorem which seems useful to obtain results related to neighborhood complexity.

A very important aspect in this result is that it is not required that $ℱ\cup ℬ$ is a family of pseudo-disks, and thus pseudo-disks of $ℬ$ may “cross” pseudo disks of $ℱ$. This is indeed the case in our application where in particular we associate to each tree in $G-M$ a pseudo-disk in $ℬ$, and this pseudo disk may cross pseudo-disks associated to vertices of $ℳ$ (see proof of 11).

In this section, we prove that the class of pseudo-disk graphs is nice, and so by our main theorem it admits a robust subexponential FPT algorithm for FVS. Note that for this graph class, the existence of such algorithm was already known [4].

We now show how to adapt the arguments from the previous section to the case of $s$-strings.