We prove algorithmic results showing that a number of natural parameterized problems are in the restricted-space parameterized classes $\cParaL$ and $\cFPTXL$. The first class comprises problems solvable in $f(k)\, n^{\Oh{1}}$ time using $g(k) + \Oh{\log{n}}$ bits of space ($k$ is the parameter and $n$ is the input size; $f$ and $g$ are computable functions). The second class comprises problems solvable under the same time bound, but using $g(k) \log{n}$ bits of space instead.

Earlier work on these classes has focused largely on their structural aspects and their relationships with various other classes. We complement this with $\cParaL$ and $\cFPTXL$ algorithms for a restriction of $\pHS$, some graph deletion problems where the target class has an infinite forbidden set characterization, a number of problems parameterized by vertex cover number, and $\pFVS$.

§ INTRODUCTION

We consider the task of identifying fixed-parameter tractable (FPT) problems that admit space-efficient algorithms. Towards this end, we devise algorithms for various parameterized problems that run in time $f(k)\, n^{\Oh{1}}$ and use either $g(k) + \log{n}$ or $g(k) \log{n}$ bits of space, where $n$ denotes the input size, $k$ denotes the parameter, and $f, g: \N \to \N$ are computable functions.

§.§.§ Previous Work
Work on restricted-space classes of parameterized problems was initiated by Cai et al. <cit.>, who defined the classes $\cLAdv$ and $\cSlL$, which we call $\cParaL$ and $\cXL$ respectively. Among other things, they showed that $\pVC$ under the usual solution-size parameterization is in $\cParaL$. Continuing this line of work, Flum and Grohe <cit.> showed that the parameterized model-checking problem of first-order formulas on graphs of bounded degree is in $\cParaL$. As a consequence, many standard parameterized graph problems are in $\cParaL$ when restricted to bounded-degree graphs. Then, Elberfeld et al. <cit.> introduced two new restricted-space classes and gave completeness results for those classes, showing that there are problems fixed-parameter tractable (FPT) problems which are outside $\cParaL$ under the assumption that $\cL{} \neq \cNL$. In particular, they identified $\pDFVS$ as one such problem. In contrast, $\pDFVS$ restricted to tournaments can be shown to be in $\cParaL$ (Corollary <ref>). Later work in this setting includes the paper of Chen and Müller <cit.>, who studied additional complexity-theoretic aspects of restricted-space classes and showed that $\pLongPath$ is in $\cParaL$.

$\pdHS$, a generalization of $\pVC$ to hypergraphs was shown by Fafanie and Kratsch <cit.> to be kernelizable in logarithmic space, which puts it in $\cParaL$ (see Lemma <ref>). As a consequence they showed that various graph deletion problems where the target classes are characterized by finite forbidden sets are also in $\cParaL$. For related results, see <cit.> which give constant-time parallel kernelization algorithms for $\pHS$.

§.§.§ Results, Techniques and Organization
Section <ref> begins by showing that $\pHS$ (with possibly unbounded set sizes) can be placed in $\cParaL$ under the restriction that pairwise intersections of sets in the instances have bounded sizes.

Then in Section <ref>, we extend the results of Fafianie and Kratsch <cit.> by showing that some graph deletion problems where the target classes have infinite forbidden sets are also in $\cParaL$.
As applications, we show that $\pDLF$ and $\pDPo$ are in $\cParaL$.

Initially, studies in parameterized complexity concerned the solution-size parameter or width parameters such as treewidth and cliquewidth. In recent times, vertex cover number as a parameter has become a subject of serious investigation <cit.>. In Section <ref> we give $\cParaL$ algorithms for problem parameterized by vertex cover number. We devise a logarithmic-space variant of a general kernelization algorithm <cit.> for problems parameterized by vertex cover number, and as a consequence obtain $\cParaL$ algorithms for $\pFVS$, $\pOCT$, $\pChVD$, $\pPlan$, $\pLongPath$, $\pLongCycle$ and $\pdCol$ under this parameterization.

Finally, in Section <ref>, we address problems that are not known to be in $\cParaL$, but are known to be in $\cFPT$ as well as in $\cXL$, i.e. solvable using $f(k) + \Oh{\log n}$ bits of space. We ask whether there are algorithms for those problems that simultaneously run in time $f(k)\, n^{\Oh{1}}$ and in $f(k) \log{n}$ bits of space. Towards this end, we devise such an algorithm for $\pFVS$. This is achieved via a careful space-efficient implementation of the iterative-compression algorithm of Chen et al. <cit.>.

§ PRELIMINARIES

§.§.§ Notation and Definitions

For a graph $G$, we denote its vertex set by $V(G)$ and edge set by $E(G)$.
A class of graphs $\Pi$ is said to be characterized by a set $\Phi$ of induced subgraphs if $\Pi$ consists of precisely those graphs that do not include induced subgraphs isomorphic to any graph in $\Phi$.

§.§.§ Appendix
Details for all items marked $\dagger$ can be found in the Appendix.

§.§.§ Parameterized Problems and Space Classes

Let $A$ be a decision problem over the alphabet $\Sigma$ and $t: \Sigma^* \to \N$ be a computable function. The pair $(A, t)$ is called a parameterized problem and $t$ is called the parameterization.

An instance of the problem is a pair $(I, t(I))$, where $I$ is an instance of $A$. The problem $(A, t)$ is said to be fixed-parameter tractable (FPT) if there is an algorithm which solves any instance $(I, t(I))$ in time $f(t(I)) {\abs{I}}^c$, where $f: \N \to \N$ is a computable function, $n = \abs{I}$, and $c > 0$ is a constant. Later on, we refer to such running times as FPT time.

The problem is kernelizable if there is an algorithm which in time polynomial in $n$ computes an instance $I'$ such that $\abs{I'} = g(t(I))$ for some computable function $g: \N \to \N$ and $I$ is a  instance if and only if $I'$ is a  instance. The instance $I'$ is called a kernel. Kernels are obtained through what are called reduction rules, which transform a given instance into another. And the rule is safe if the two instances are equivalent.

In this paper, we focus on the space complexity aspect of parameterized problems. A natural problem class to consider in this setting is $\cParaL$, defined below.

$\cParaL$ is the class of all parameterized problems $(A, t)$ for which there is a deterministic algorithm which solves instances $(I, t(I))$ using space $f(k) + \Oh{\log{n}}$, where $f: \N \to \N$ is a computable function, $k = t(I)$ and $n = \abs{I}$.

We also consider an analogous class $\cXL$, where the space bound is $f(k) \cdot \log{n}$ instead of $f(k) + \Oh{\log{n}}$. The two classes are known to be distinct unless $\cP{} = \cL$ (Theorem 3.1 of <cit.>).

$\cXL$ is the class of all parameterized problems $(A, t)$ for which there is a deterministic algorithm which solves instances $(I, t(I))$ using space $f(k) \cdot \log{n}$, where $f: \N \to \N$ is a computable function, $k = t(I)$ and $n = \abs{I}$.

§.§.§ Machine Model

We use the standard model for space-efficient algorithms. The input to an algorithm resides in read-only memory and can be randomly accessed, while the output is written to a stream which cannot be read from. The algorithm uses a small number of read-write cells as auxiliary memory, where each cell can hold a word of size $\Oh{\log{n}}$ bits ($n$ is the input size). The machine is a unit-cost RAM in which basic arithmetic and logic operations involving two words take constant time.

A basic result in parameterized complexity theory is that a problem is fixed-parameter tractable if and only if it is kernelizable. The following lemma is an easy consequence of the result.

If a parameterized problem is fixed-parameter tractable, then it can be solved using $f(k) + n^{O(1)}$ space where $f$ is some function of the parameter $k$, and $n$ is the input size.

The next result is implicit in <cit.>; we include it here for the sake of clarity.
Let $(A, t)$ be a parameterized problem. For any computable function $f: \N \to \N$, the following statements are true.

* If $(A, t)$ can be solved in space $f(k) + \Oh{\log{n}}$, then it can be kernelized in space $\Oh{\log{n}}$.

* If $(A, t)$ can be kernelized in space $f(k) + \Oh{\log{n}}$, then it can be solved in space $g(k) + \Oh{\log{n}}$, where $g: \N \to \N$ is a computable function.

§ HITTING SET AND GRAPH DELETION PROBLEMS

We begin by examining two known small-space kernelization results. The first is a combination a logarithmic-space implementation of the Buss rule <cit.> for $\pVC$ and the observation that the kernel produced is itself a vertex cover.

There is an algorithm which takes as input a graph $G$ and $k \in \N$, and using space $\Oh{\log n}$, either answers correctly that $G$ has no vertex cover of size at most $k$ or produces a vertex cover of size at most $2k^2$.

The next result gives an equivalent algorithm for $\pdHS$.

There is an algorithm which takes as input an instance of $\pdHS$, i.e. a universe $U$, a family $\mathcal{F}$ of subsets of $U$ of size $d$ each and an integer $k$, and in time $n^{\Oh{d^2}}$ and $\Oh{d^2 \log{n}}$ bits of space, either answers correctly that the instance has no hitting set of size at most $k$ or produces an instance $(U', \mathcal{F}', k)$ such that

* $U' \subseteq U,\ \abs{U'} \leq d{(k + 1)}^d$,

* $\mathcal{F}' \subseteq \mathcal{F},\ \abs{\mathcal{F}'} \leq {(k + 1)}^d$, and

* for all $S \subseteq U$ with $\abs{S} \leq k$, $S\ \text{is a minimal hitting set for}\ \mathcal{F}$ if and only if $S\ \text{is a minimal hitting set for}\ \mathcal{F}'$.

Since the above algorithm kernelizes $\pdHS$ in logarithmic space (for constant $d$), we have the following result as a consequence of Lemma <ref>.

For constant $d$, $\pdHS$ is in $\cParaL$.

§.§ Deletion Problems

We begin this section by showing that if a certain restriction of a general graph deletion problem ($\pDelPi$, defined below) is in $\cParaL$, then the entire problem is in $\cParaL$. Combining this with a method for partially encoding these problems as $\pHS$, we show that $\pDLF$ and $\pDPo$ are in $\cParaL$. The problem $\pDelPi$ has the following form.

Instance: $(G, k)$, where $G$ is a graph and $k \in \N$

Question: Is there a set $S \subseteq V$ with $\abs{S} \leq k$ such that $G - S \in \Pi$?

When $\Pi$ is characterized by a finite set of forbidden induced subgraphs $\Phi$, instances of $\pDelPi$ can be modelled as $\pdHS$. As an example, consider $\pCVD$, where the objective is to delete up to $k$ vertices in an input graph such that the resulting graph is a cluster graph. The class of cluster graphs is exactly the class of graphs which do not have a path on three vertices $P_3$ as induced subgraphs. Because of this, an instance $(G, k)$ of the problem can be encoded as an instance $(U, \mathcal{F}, k)$ of $3$–$\pHS$, where $U = \V{G}$ and $\mathcal{F} = \setb{\V{P}}{P\ \text{is an induced}\ P_3\ \text{in}\ G}$. The family of sets $\mathcal{F}$ is can be generated in logarithmic space: enumerate all subsets of $\V{G}$ of size $3$ and output those that induce a $P_3$. t is easy to see that $(U, \mathcal{F}, k)$ is a  instance of $3$–$\pHS$ if and only if $(G, k)$ is a  instance of $\pCVD$. This family can now be used as input to a $3$–$\pHS$ algorithm, and because of Corollary <ref>, the instance can be solved in $f(k) + \log{n}$ bits of space. A variety of other problems can be solved in a similar fashion, leading to the following result.

$\pCVD$, $\pDFVS$ restricted to tournaments, $\pSVD$ and $\pThVD$ are in $\cParaL$.

In what follows, we describe the main result of this section, which extends Corollary <ref> to also include some variants of $\pDelPi$ where $\Pi$ is characterized by an infinite set of forbidden induced subgraphs.

Let $\Psi \supseteq \Pi$ be a class of graphs and let $\prob{ResDel\textPi}$ be the restriction of $\pDelPi$ to graphs in $\Psi$. If $\Psi$ is characterized by a finite set $\Phi$ of forbidden induced subgraphs and $\prob{ResDel\textPi} \in \cParaL$, then $\pDelPi \in \cParaL$.

Since $\pDelPi$ restricted to $\Psi$ is in $\cParaL$, there is an algorithm which solves restricted instances $(H, k)$ of $\pDelPi$ using space $f(k) + \Oh{\log{n}}$ ($f: \N \to \N$, a computable function). Let SolveDelOn be such an algorithm. Using this as a subroutine, Algorithm <ref> solves $\pDelPi$.

$(G, k)$, where $G$ is a graph and $k \in \N$
if there is a set $S \subseteq V$ of size at most $k$ such that $G - S \in \Pi$, and  otherwise

let $c_1, \dotsc, c_t$ be the sizes of the sets in $\Phi$
$d \gets \max \brc{c_1, \dotsc, c_t},\ V \gets \V{G}$
$\mathcal{F} \gets \setb{S \subseteq V}{G[S]\ \text{is isomorphic to some}\ H \in \Phi}$
$(V', \mathcal{F}', k) \gets \algoi{KernelizeDeeHS}{d, V, \mathcal{F}, k}$
BranchAndCall$G, \mathcal{F}', \emptyset, k$
$G, \mathcal{F}', S, l$
$l < 0$

(*[f]$G - S$ is in $\Psi$)$S$ hits all of $\mathcal{F}'$
SolveDelOn$G - S, l$ returns

find a set $A \in \mathcal{F}'$ such that $A \cap S = \emptyset$
$v \in A$
BranchAndCall$G, \mathcal{F}', S \cup \brc{v}, l - 1$ returns

SolveDel: solve  with access to KernelizeDeeHS, which kernelizes , and SolveDelon, which solves the restriction of  to

Algorithm <ref> solves $\pDelPi$ in $g(k) + \Oh{\log{n}}$ bits of space ($g: \N \to \N$, a computable function).

The claim of Theorem <ref> now readily follows from the preceding discussion. The next result is an application of Theorem <ref> which makes use of SolveDelOn routines for some specific graph classes $\Psi$. It is pertinent here to note that the target classes $\Pi$ do not have characterizations by finite forbidden sets.

and  are in $\cParaL$.

Both problems are related to $\pFVS$ (delete vertices so that the resulting graph is a forest): a solution to either problem is also a feedback vertex set. While we are able to show that  and  are in , the known kernelization algorithms and fixed-parameter algorithms for $\pFVS$ (where the parameter, i.e. the solution size, is smaller) use strategies which appear difficult to carry out in the $\cParaL$ setting.

§.§ $\pHS$ with Bounded Intersection

Proposition <ref> shows that one can, in logarithmic space, compute kernels for instances of $\pdHS$ in which each set is of size $d$. In this section, we obtain a similar result for the scenario where not the set sizes, but the intersection between any pair of sets is bounded by a constant $s$. Interestingly, the kernelization question for this natural $\pHS$ variant has not been addressed in earlier works, even with no constraints on space.

§.§ Case $s = 1$

We first consider the case $s = 1$, i.e. when the instances are linear hypergraphs <cit.>. Let $(U, \mathcal{F}, k)$ be an instance of $\pHS$ where the intersection between any pair of sets is of size at most $s = 1$. The algorithm consists of the following sequence of reduction rules.

Rule $1$ Let $S$ be the set of all elements that appear in at least $k + 1$ sets in $\mathcal{F}$. If $\abs{S} > k$, return . Otherwise, delete all sets in $\mathcal{F}$ that intersect with $S$ and delete all elements of $S$ from $U$. Set $k \gets k - \abs{S}$.

Rule $2$ If the number of sets remaining is more than $k^2$, then return NO.

Rule $3$ For each remaining set, determine the elements that appear in no other set. Delete all but one of them from the set and from the universe.

The following lemma establishes the correctness of the above rules and gives a bound on the size of the final instance.
Reduction Rules $1$, $2$ and $3$ produce a kernel $(U', \mathcal{F}', k')$, where $\abs{U'} \leq k^2$ and $\abs{\mathcal{F}'} \leq k^4$.

§.§.§ Space-Efficient Implementation

Reduction Rule $1$ can be implemented using two counters in addition to a constant number of counters for iteration. The first counter counts, for each element, the number of sets it appears in. The second counter counts the number of elements for which the first counter is larger than $k$. If the second counter goes beyond $k$, we return . Otherwise, we set $k \gets k - k'$, where $k'$ is the value of the second counter.

To implement Reduction Rule $2$, we set up two additional counters and run through all the sets. The first counter checks for each set whether there is any element in it that appears more than $k$ times in $\mathcal{F}$. If no element of the set appears in more than $k$ times, then the set survives after Reduction Rule $1$, and we increment the second counter. Once all sets have been processed in this manner, if the value of the second counter is more than $k^2$, we return .

To implement Reduction Rule $3$, we first determine as for Rule $2$ which sets $S$ survive the application of Rule $1$. We suppress the sets that do not survive, and output a subset of $S$ as follows. Observe that at this point, elements in each surviving set appear at most $k$ times in the entire instance. For each element of $S$, we count the number of times it appears in the instance. We output all elements that appear more than once, and of the ones that appear exactly once, we output the first such element in the set. The latter step can be performed using the following rule for each element $x$ in $S$ that appears exactly once in the instance: output $x$ only if there is no other element in $S$ before $x$ which also appears exactly once in the instance. This only uses a constant number of additional counters.

Observe that in all the steps above, only a constant number of additional counters are used, from which it readily follows that the entire procedure uses $\Oh{\log{n}}$ bits of space. Combining this with Lemma <ref>, we have the following result.

Given a number $k \in \N$ and a family of sets from a finite universe of size $n$ where each pair of sets intersect in at most one element, using $\Oh{\log{n}}$ bits of space, one can either determine that the given instance is a  instance of $\pHS$ or output an equivalent instance consisting of a family of at most $k^2$ sets with at most $k^2$ elements each such that each pair of sets intersects in at most one element.

Combining the above result with Lemma <ref>, we have the following corollary.

$\pHS$ restricted to instances where any pair of sets intersect in at most one element is in $\cParaL$.

§.§ Case $s > 1$

In this case, the instance can be reduced using similar rules as before, with a sequence of $s - 1$ rules replacing Reduction Rule $1$ in the $s = 1$ case.

Rule $i$ ($i = 1, \dotsc, s - 1$) If there is an $(s+1-i)$-element subset of the universe that appears as a subset of $k^i+1$ sets, then replace all those sets with just the $(s+1-i)$-element set.

For example, Reduction Rule $1$ ensures that if an $s$-element subset of the universe appears in $k+1$ sets, then all those sets are replaced with just the common $s$-element subset.

Rule $s$ Let $S$ be the set of all elements that appear in at least $k^s + 1$ sets in $\mathcal{F}$. If $\abs{S} > k$, return . Otherwise, delete all sets in $\mathcal{F}$ that intersect with $S$ and delete all elements of $S$ from $U$. Set $k \gets k - \abs{S}$.

Rule $(s+1)$ If the number of sets remaining is more than $k^{s + 1} + 1$, then return .

Rule $(s+2)$ For each remaining set, determine the elements that appear in no other set. Delete all but one of them from the set and from the universe.

As in the $s = 1$ case, the above rules ensure that the size of the final instance is bounded by a function of $k$. In addition, the rules can be applied using $\Oh{s \log{n}}$ bits of space per rule. Owing to space constraints, we defer the space-efficient implementation of the above rules to Appendix <ref> and state our result directly.

Given a family of sets from an $n$-element universe where each pair of sets intersects in at most $s$ elements, using $\Oh{s^2 \log{n}}$ bits of space, one can either determine that the given instance is a  instance of $\pHS$ or output an equivalent family of at most $k^{s + 1}$ sets with at most $s k^{s + 1}$ elements each such that each pair of sets intersects in at most $s$ elements.

Combining the above result with Lemma <ref> yields the following corollary.

For constant $s$, $\pHS$ restricted to instances where any pair of sets intersect in at most $s$ elements is in $\cParaL$.

§ VERTEX COVER NUMBER AS PARAMETER

With respect to the standard parameter (solution size), problems such as $\pTW$ and $\pFVS$ are not known to be in $\cParaL$. In this section, we show that when parameterized by vertex cover number, these problems are in fact in $\cParaL$.

Elberfeld et al. <cit.> give an algorithm for computing the treewidth of an undirected graph using space $f(k) \cdot \log{n}$, which puts the problem in $\cXL$, but it is not known if the problem is in $\cParaL$. For $\pFVS$, the obvious “guess and verify” algorithm puts it in $\cXL$, but does not run in FPT time. The known fixed-parameter algorithms for these problems (see e.g. <cit.>) involve complex branching strategies and it seems unlikely that they can be carried out using space $f(k) + \Oh{\log{n}}$.

The following definition captures classes of graphs which are closed under  certain modification operations. Such graph classes encompass “target” graphs for many graph modification and partitioning problems, and can be used to show the kernelizability of these problems, as shown later.

Let $\Pi$ be a class of graphs and $c_{\Pi} \in \N$ be a constant. If for any graph $G \in \Pi$ and any vertex $v \in \V{G}$, there is a set of vertices $D \subseteq \V{G} \setminus \brc{v}$ with $\abs{D} \leq c_{\Pi}$ such that adding or removing any number of edges between $v$ and $\V{G} \setminus{D}$ produces a graph which is also in $\Pi$, then $\Pi$ is said to be characterized by $c_{\Pi}$ adjacencies.

Consider the following problem, defined with respect to a graph class $\Pi$ characterized by $c_{\Pi}$ adjacencies.

$\pi$ is a class of non-empty graphs and there is a non-decreasing polynomial $p$ such that every vertex minimal graph $G \in \Pi$ satisfies $\abs{G} \leq p(\tau)$, where $\tau$ is the size of a minimum vertex cover for $G$.

Instance: $(G, k)$, where $G$ is a graph and $k \in \N$

Question: Is there a set $S \subseteq V$ with $\abs{S} \leq k$ such that $G - S$ includes no graph in $\Pi$ as an induced subgraph?

Fomin et al. <cit.> give a generic procedure Reduce (see Appendix <ref>), which kernelizes the problem as described in the following proposition.

For an instance $(G, k)$ of $\pIndPiFDS$ with a vertex cover $X$ of size $r \geq k$, Reduce$G, X, r + p(r), c_{\Pi}$ produces a kernel of size ${r}^{c_{\Pi}} (r + p(r))$.

We now state the main result of this section, which is obtained by carefully combining the logarithmic-space $\pVC$ kernelization from earlier with a modified Reduce procedure.

$\pIndPiFDS$ is in $\cParaL$.

While the Reduce procedure of Fomin et al. <cit.> can be used to kernelize $\pIndPiFDS$, it is not clear that the procedure can be carried out in small space. We use a modified reduction procedure ReduceLog (see Appendix <ref>) instead, which uses space $\Oh{\log{n}}$, where $n$ is the order of the input graph.

For an instance $(G, k)$ of $\pIndPiFDS$ with a vertex cover $X$ of size $r \geq k$, ReduceLog$G, X, r + p(r), c_{\Pi}$ produces a kernel of size ${r}^{c_{\Pi}} (r + p(r))$. The procedure uses $\Oh{\log{n}}$ bits of space, where $n = \abs{G}$.

The proof of Theorem <ref> is now straightforward.

Lemma <ref> shows that given access to the input instance $(G, k)$ and a vertex cover $X$ for $G$, $\pIndPiFDS$ is kernelizable (using ReduceLog) in space $\Oh{\log{n}}$, where $n = \abs{G}$. For a solution-size value $k$ (the size of the vertex cover), the $\pVC$ kernelization of Proposition <ref> either correctly determines that $G$ has no vertex cover of size $k$ or produces a kernel $G'$ with $\Oh{k^2}$ vertices. In this case, the vertex set of $G'$ is also a vertex cover for $G$ (Proposition <ref>).

Running ReduceLog on $(G, k)$ with access to $X = \V{G'}$ ($r = \abs{X} = \Oh{k^2}$) thus produces a kernel of size $r^{c_{\Pi}} (r + p(r)) = \Oh{k^{2 c_{\Pi}} (k^2 + p(k^2))}$ for $\pIndPiFDS$. Oracle access to $X = \V{G'}$ can be be provided using space $\Oh{\log{n}}$ and $\algo{ReduceLog}$ uses space $\Oh{\log{n}}$, so the total space used is $\Oh{\log{n}}$. By Theorem <ref>, any problem that can be kernelized in space $\Oh{\log{n}}$ is in $\cParaL$, and thus the claim is true.

The following corollary to Theorem <ref> shows how various deletion problems are in $\cParaL$ via formulations as $\pIndPiFDS$ for suitable $\Pi$.
Under the vertex-cover parameterization, $\pPlan$, $\pOCT$ and $\pChVD$ are in $\cParaL$.

Via formulations as the alternative intermediate problems $\pLIndPiS$ and $\pqPartDisjPiFree$ (defined in Appendix <ref>), the same ReduceLog$G, X, l, c_{\Pi}$ procedure with different values for $l$ can also be used to prove the next result.
Under the vertex-cover parameterization, $\pFVS$, $\pLongPath$, $\pLongCycle$ and $\pdCol$ are in $\cParaL$.

§ SOLVING $\PFVS$ IN $5^K \CDOT N^{\OH{1}}$ TIME AND $\OH{K \CDOT \LOG{N}}$ SPACE

It is known (Lemma <ref>) that problems in $\cFPT$ can be solved in space $f(k) + n^{\Oh{1}}$. If the sole objective is space efficiency, many problems can also be solved (naïvely, by running over all subsets of size at most $k$, for example) in $f(k) \cdot \log{n}$ bits of space, which puts them in $\cXL$. It is pertinent to note that $\cXL$ also contains problems like $\pIS$ and $\pClq$ which are $\probc{W}[1]$-complete, and hence are unlikely to be in $\cFPT$. On the other hand, it is believed that not all problems in $\cFPT$ can be solved in $f(k) \cdot \log{n}$ bits of space <cit.>.

A third class, which requires problems in it to be simultaneously solvable in time $f(k) \cdot n^{\Oh{1}}$ and $g(k) \cdot \log{n}$ bits of space also exists, and contains $\pFVS$ <cit.> and $\pMOdS$ <cit.>. This class, which we call $\cFPTXL$, has been previously identified in the literature as $D[f \oper{poly}, f \oper{log}]$ <cit.>.

In what follows, we devise an $\cFPTXL$ algorithm for $\pFVS$ which runs in time $5^k \cdot n^{\Oh{1}}$ and uses $\Oh{k \log{n}}$ bits of space. This improves on an earlier $((2k)^k \cdot n^{\Oh{1}})$-time,  $\Oh{k \log{n}}$-space algorithm of Elberfeld et al. <cit.>. Along the way, we also devise a much simpler $(3k)^k \cdot n^{\Oh{1}}$-time $\cFPTXL$ algorithm for the problem.

Known $\cFPT$ algorithms for $\pFVS$ <cit.> are based on reduction rules, one of which is the following  “short circuiting” rule for vertices of degree two.

§.§.§ Degree–$2$ Reduction Rule
If there is a vertex $x$ of degree $2$ with neighbours $y$ and $z$, delete $x$ and add an edge between $y$ and $z$, while retaining pre-existing edges.

Once the rule is applied, the graph possibly has parallel edges, so we assume throughout this section that we work with multigraphs. Additionally, we can assume that the graph has no isolated or degree-$1$ vertices (as they can be safely removed), no vertices with self-loops (as they must be included in the solution and then removed) and no more than two edges between a pair of vertices (as other multi-edges do not influence the solution can be removed). The correctness of these assumptions and the rule is easy to see <cit.>.

We first discuss the space-efficient application of these rules. The degree of a vertex can be found from the adjacency list, and so it is easy to `discard' vertices with degree at most one.
Let us remark that our algorithms (in the next subsection) deletes some (up to $k$) vertices and recursively applies these rules. Those deleted vertices are stored in a separate array using $\Oh{k \log n}$ bits, and so when checking for the degree of a vertex, we also check that array appropriately besides checking the read-only adjacency list of the graph.

On a multigraph with $n$ vertices, the Degree–$2$ rule can be applied using $\Oh{\log{n}}$ bits of additional space.

One can combine this proposition with a simple branching strategy to show that $\pFVS$ is in $\cFPTXL$.

$\pFVS$ can be solved in time ${(3k)}^k \cdot n^{\Oh{1}}$ using $\Oh{k \log{n}}$ bits of space.

§.§ Improved algorithm based on Iterative Compression

We now describe a restricted-space implementation of an algorithm of Chen et al. <cit.> which allows us to prove the following result.

$\pFVS$ can be solved using $O(k \log{n})$ bits of space and in time $5^k poly(n)$.

The algorithm goes through a two stage process on an instance $(G, k)$.

Iterative Stage In the iterative stage, the algorithm starts with an arbitrary induced subgraph $H_0$ of $G$ with $k + 1$ vertices. The vertex set of this graph is trivially also a feedback vertex set for $H_0$. The algorithm uses a compression algorithm which given a subgraph $H$ of $G$, and a feedback vertex set $C$ for $H$ of size $k+1$, either produces a feedback vertex set $C'$ for $H$ of size at most $k$ or determines correctly that such a feedback vertex set for $H$ does not exist. In the latter case, we correctly conclude that even $G$ has no feedback vertex set of size $k$. In the former case, both the subgraph and the (compressed) solution are included an additional vertex from the graph, and the compression step is applied again. This process continues until we cover the entire graph. During the iteration, the $(k+1)$-sized solution is stored using $O(k \log n)$ bits of space.

Compression Stage The compression algorithm is given a feedback vertex set $S$ of size $k+1$ for the whole graph $G$, and the goal is to determine whether it has a feedback vertex set of size at most $k$. It starts by checking for every subset $Z$ of $S$ of size at most $k$ whether there is a feedback vertex set of size at most $k$ containing $Z$. This requires storing the set $Z$ which uses $\Oh{k \log{n}}$ bits of space, and requires that $G[P]$ is a forest where $P=S\setminus Z$ which can be checked using $\Oh{\log{n}}$ bits of space (by making $\Oh{n^2}$ connectivity queries on $G[P]$). Recall that $G[V\setminus S]$ is a forest as $S$ is a feedback vertex set.

Next, as a processing step, we include all vertices $v$ of $V\setminus S$ into the solution, if $v$ has at least two neighbors in a connected component of $G[P]$ which can be checked in $\Oh{\log{n}}$ bits of space using Reingold's connectivity algorithm <cit.>. Then for any leaf vertex $v$ in $G[V\setminus S]$, we simply branch by picking $v$ into the solution or excluding $v$ from the solution which involves including $v$ into $P$. If either branch returns , we return . The depth of the recursion is at most $k$ and each level uses $\Oh{\log{n}}$ bits of space, so the overall process uses $\Oh{k \log{n}}$ bits of space.

Observe that both the iterative and compression stages use $\Oh{k \log{n}}$ bits of space overall. Appendix <ref> gives pseudocode (FVSCompress, Procedure <ref>) for the compression procedure described above. For proof of correctness, we refer the reader to Chen et al. <cit.>, who also prove a running time bound of $5^k \cdot n^{\Oh{1}}$ which readily carries over to this setting. We now have the following lemma.

FVSCompress solves instances $(G, S, k)$ using $O(k \log{n})$ bits in time $5^k poly(n)$.

The compression procedure is called at most $n - k$ times (to include one additional vertex each time starting with the first $(k + 1)$-sized subgraph), and each time it drops a vertex and adds a new vertex, with at most $k+1$ vertices at any point of time. Thus, the iterative stage adds only an overhead of $n^{\Oh{1}}$ to the running time of FVSCompress, and Theorem <ref> follows.

The routine either stops at an intermediate stage and declares that $(G, k)$ is a  instance or continues until $i = n$, at which stage it returns the output $T_n$ of the compression routine as a feedback vertex set for $G$ of size at most $k$.

§ PRELIMINARIES

§.§ Proof of Lemma <ref>

To see that the first statement holds, consider an algorithm that solves $(A, t)$ in space $f(k) + c \log{n}$.

* Simulate the algorithm $A$ on $I$ and use a counter to count the auxiliary space used until the algorithm $A$ uses up to $(c + 1) \log{n}$ bits of memory. If it finishes executing without using more memory, output a constant-sized instance indicating the answer ( or ). This uses space $(c+1) \log(n) + O(\log \log n)$ which is $\Oh{\log{n}}$. The second term is the space used for the counter.

* Otherwise, i.e. if the algorithm needs to use more memory, output the input instance. In this case, $f(k) + c \log{n} > (c + 1)  \log{n}$, i.e. $f(k) > \log{n}$, and
$n < 2^{f(k)}$.

In both cases, the output instance is a kernel.

To see that the second statement holds, observe that once a kernel of size $g(k)$ has been obtained in space $f(k) + \Oh{\log{n}}$, it can be solved by brute force in space $\Oh{h(k)}$, where $h: \N \to \N$ is a computable function. Thus, the problem can be solved in space $f(k) + h(k) + \Oh{\log{n}}$.

§ HITTING SET AND GRAPH DELETION PROBLEMS

§.§ Proof of Lemma <ref>

Let $\mathcal {F}$ be the family of sets after Reduction Rule $2$ and $\mathcal {F'}$ be the family of sets after Reduction Rule $3$. We claim that $\mathcal{F}$ has a $k$-sized hitting set if and only if $\mathcal{F'}$ has a $k-$ sized hitting set.

If $\mathcal {F'}$ has a $k$-sized hitting set, then the same hitting set will serve for $\mathcal {F}$ as every set in $\mathcal{F'}$ is a subset of a set in $\mathcal{F}$.
To show the converse, suppose $\mathcal{F}$ has a hitting set $S$ containing an element $x$ which was not present in $\mathcal{F'}$. Suppose $x$ intersects a set $F \in \mathcal{F}$.
As $x$ was not present in $\mathcal{F'}$, then $x$ was present only in $F \in \mathcal{F}$ and hence reduction rule $3$ deleted it. But then there must be some other element $y$ that was present in $F$ and was present only in $F \in \mathcal{F}$.
Thus $S \setminus {x } \cup {y} $ will be a set that will intersect $F \in \mathcal{F}$ and is of the same size as $S$. Repeating this process for every set in $\mathcal{F'}$ not intersected by $S$, will result in a hitting set of $\mathcal{F'}$ of the same size as $S$.

Observe that after Reduction Rule $2$, the number of remaining sets is at most $k^2$. Let $F$ be any set in the family after Reduction Rule $3$, and let $x$ be any element of $F$. Then $x$ appears in only $F$ in the family (and if so, it is the only such element), or it appears in some other set of the family. But as any pair of sets has intersection at most one, if $x$ appears in some other set $F'$ of the family, no other element of $F$ can appear in $F'$. Hence every distinct element of $F$ can appear in a distinct element of $F$, and so $F$ has at most $k^2$ elements, and the lemma follows.

§.§ Space-Efficient Implementation of Rules in Subsection <ref>

Ultimately, we need to determine the sets that exist in the family at the end of Reduction Rule $(d+1)$ and the elements that survive at the end of Reduction Rule $(d+2)$, as these are the sets and elements that will be written to the output stream. We call the input family of sets Stream $0$ and for each $i \in [d + 2]$, we call the family of sets that exists after Rule $i$ has been applied as Stream $i$.

Now a set $X$ is in Stream $i$ if and only if any of the following conditions is satisfied:

* $X$ is in Stream $(i - 1)$ and no $(d - 1 + i)$-subset of $X$ appears more than $k^i$ times in Stream $(i-1)$ or

* $X$ is a $(d-i+1)$ subset of the universe that appears more than $k^i$ times in Stream $(i-1)$.

The correctness follows from the correctness of the reduction rules.
Since we don't have space to store any specific stream, we recursively check for sets in the previous stream.

If $s_i$ is the space used for checking for a set in Stream $i$, we observe that $s_i$ satisfies $s_i = \Oh{\log{n}} + (d - 1 + i) \log{n} + s_{i - 1}$. The second term is to enumerate all subsets of size $(d-1+i)$.  Since the input can be read using space $s_0 = \Oh{\log{n}}$, this recurrence yields $s_d = \Oh{d^2 \log{n}}$. Thus, a set in Stream $d$ can be checked using $\Oh{d^2 \log{n}}$ bits of space. Observe that given access to Stream $d$, Rule $d + 1$ can be applied by simply counting the number of sets in Stream $d$, which uses $\Oh{\log{n}}$ bits of additional space.

Also all sets in Stream $i$ can be generated, given access to Stream $i-1$ as follows.

* For each set $X$ in Stream $i-1$

* For each subset $Y$ of $X$ of size $(d-1+i)$,

* Count the number of times $Y$ appears in Stream $(i - 1)$.

* If this number is at least $k^i + 1$, then break out of this enumeration and move to the next set (and $X$ is not output).

* Write $X$ to the output stream (if no $Y$ appears in $k^i +1$ sets of Stream $i-1$).

* For each $(d-1+i)$-subset $Y$ of the universe,

* Count the number of times $Y$ appears in Stream $(i - 1)$.

* If this number is at least $k^i + 1$, then output $Y$.

Now Stream $(d + 2)$ which is the output, can be generated as follows.

* For each set $X$ in Stream $(d + 1)$:

* Set $f_X \gets 0$.

* For each element $e$ of $X$:

* Count the number of times $e$ appears in Stream $(d + 1)$.

* If this number is at least $2$, write $e$ to the output stream and skip to the next element in this enumeration.

* If $f_X = 1$, skip to the next element in this enumeration.

* Write $e$ to the output stream and set $f_X \gets 1$.

* Write a set separator to the output stream.

The above procedure uses a constant number of extra counters to count/enumerate sets and elements in Stream $(d + 1)$, which only requires an additional $\Oh{\log{n}}$ bits of space. Thus Stream $(d + 2)$ can be generated using space $\Oh{d^2 \log{n}}$ overall, and we have the following result.

§.§ Algorithm for the Proof of Theorem <ref>

§.§ Proof of Lemma <ref>

Let $(G, k)$ be an instance of $\pDelPi$. Consider the family $\mathcal{F} = \setb{S \subseteq V}{\exists\ \text{injective homomorphism}\ H \to G[S]\ \text{for some}\ H \in \Phi}$. Any solution $R$ for $(G, k)$ can be decomposed as $R = S \sqcup T$, where $S$ is a minimal set of vertices such that $G - S$ is in $\Psi$. This follows directly from the fact that $\Pi \subseteq \Psi$. The family $\mathcal{F}$ consists of precisely those sets of vertices in $G$ which must be hit by $S$ so that $G - S \in \Psi$. Thus, $S$ is a minimal hitting set for $\mathcal{F}$ if and only if it is a minimal set of vertices such that $G - S \in \Pi$.

Algorithm <ref> first constructs the  instance $(V, \mathcal{F}, k)$ and then using KernelizeDeeHS, it obtains the kernel $(V', \mathcal{F}', k)$. Then by the branching procedure BranchAndCall, it attempts to find a minimal set $S$ of size at most $k$ such that $G - S \in \Psi$.

Recall that any minimal set of size at most $k$ which hits all of $\mathcal{F}'$ also a hits all of $\mathcal{F}$ and vice versa (Proposition <ref>). In the BranchAndCall procedure, the algorithm branches on sets appearing in $\mathcal{F}'$. At each recursive call, one of the at most $d$ vertices in the set is added to $S$.

In this way, all possible minimal hitting sets of size at most $k$ (if they exist) for $\mathcal{F}'$ and therefore also $\mathcal{F}$ are explored. At the leaves of the branching tree where $l \geq 0$, a minimal hitting set $S$ for $\mathcal{F}$ of size at most $k - l$ is obtained.

In the other case, i.e. when $l < 0$ at a leaf of the branching tree, the sequence of vertices picked on the branching path cannot yield a set $S$ of size at most $k$ such that $G - S \in \Psi$. If this condition occurs at all the leaves of the branching tree, the procedure correctly indicates that the input is a  instance.

Now at the leaves of the branching tree where $l \geq 0$, the algorithm executes SolveDelOn$G - S, l$, which checks if  at most $l$ more vertices can be deleted from $G - S$ such that the resulting graph is in $\Psi$. Observe that this occurs for every minimal set $S$ of size $k$ such that $G - S \in \Psi$. Thus, if the output of SolveDelOn$G - S, l$ on any of these sets $S$ is , then the input is a  instance of $\pDelPi$. Because all such minimal sets are explored in the branching tree, if the output of SolveDelOn$G - S, l$ at each of the leaves is , then the algorithm correctly determines that the input is a  instance.

§.§ Proof of Theorem <ref>

Observe that $(V, \mathcal{F}, k)$ can be generated implicitly by enumerating all sets $S \subseteq V$ of sizes $c_1, \dotsc, c_t$, and only retaining those sets $S$ for which a graph in $\Phi$ has an injective homomorphism to $G[S]$. Since the graphs in $\Phi$ are of constant size and there are finitely many of them, this can be done in space $\Oh{\log{n}}$.

The initial kernelization step uses space $\Oh{\log{n}}$ (Proposition <ref>). The later branching steps have implicit access to the kernel, and at each branch, the vertex $v \in \mathcal V' \subseteq V$ to be deleted must be stored in memory. Performing this deletion naïvely would require space $\Oh{\log{n}}$. However, the vertices to be deleted are picked from $V'$, which has $\Oh{(k + 1)^d}$ elements (Proposition <ref>). Thus, the vertices deleted in the branching steps can be stored in memory as their indices in the vertex set $V'$, which uses $\Oh{\log{k}}$ space per vertex. Thus, all the vertices deleted on any branching path can be stored using space $\Oh{k \log{k}}$.

At every leaf of the branching tree, the graph $G - S$ can be represented implicitly using space $\Oh{\log{n}}$ because $G - S = G[V \setminus S]$ is an induced subgraph of $G$. The subsequent call to SolveDelOn uses space $f(k) + \log{n}$, so the total space used by the procedure is $\Oh{h(k) + k \log{k} + \log{n}} = g(k) + \Oh{\log{n}}$ for some computable function $g: \N \to \N$. This proves the claim.

§.§ Problem Definitions

The problems considered in Section <ref> section are defined as follows.

Instance: $(G, k)$, where $G$ is a graph and $k \in \N$

Question: Is there a set $S \subseteq V$ with $\abs{S} \leq k$ such that $G - S$ is a linear forest, i.e. a forest consisting exclusively of vertex-disjoint paths?

Instance: $(G, k)$, where $G$ is a graph and $k \in \N$

Question: Is there a set $S \subseteq V$ with $\abs{S} \leq k$ such that $G - S$ is a graph of pathwidth $1$?

In any graph on $n$ vertices, it can be determined if any two vertices are connected by a path using space $\Oh{\log{n}}$.

A graph which is $T_2$-, $C_3$- and $C_4$-free is a disjoint union of trees, cycles and cycles with some pendant vertices.

§.§ Proof of Corollary <ref>

$\pDLF{} \in \cParaL$.

Observe that in a linear forest, no vertex can have more than $2$ neighbours, i.e. the forest does not include $T_1$ as a subgraph. Conversely, any graph that does not include $T_1$ as a subgraph can only have vertices of degree at most $2$, i.e. it consists exclusively of paths and cycles. In that case, deleting exactly one vertex from each cycle yields a linear forest, i.e. the number of vertices that must be deleted is equal to the number of connected components that are not trees. Procedure <ref> shows how this can be done. The correctness of the procedure is immediate from the preceding discussion.

To see that it uses space $\Oh{\log{n}}$, note that using the algorithm of Proposition <ref>, the connected component of any vertex can be determined in space $\Oh{\log{n}}$. To determine if $G[C]$ is not a tree, it suffices to count the number of edges in G[C], which exceeds $\abs{C} - 1$ if and only if $G[C]$ is not a tree. With access to $C$, this can be done in space $\Oh{\log{n}}$. All other steps in the procedure also use space $\Oh{\log{n}}$, which makes a total of $\Oh{\log{n}}$ for the entire procedure.

Thus, $\pDLF$ restricted to $\Psi^2$, the class of graphs of degree at most $2$ is in $\cL{} \subseteq \cParaL$. Since $T_1$ characterizes $\Psi^2$ as a forbidden induced subgraph, the claim follows from Theorem <ref>.

$\pDPo{} \in \cParaL$.

Consider the class of graphs $\Psi_3$ which do not include $T_2, C_3$ or $C_4$ as a subgraph. Any graph of pathwidth at most $1$ cannot include a $T_2$ or a cycle, so $\Psi_3$ includes all graphs of pathwidth at most $1$. By Proposition <ref>, graphs in $\Psi_3$ are disjoint unions of trees, cycles and cycles with pendant vertices. To convert such a graph to a graph of pathwidth at most $1$, exactly one vertex from each cycle must be deleted. Equivalently, the number of vertices to be deleted is equal to the number of connected components that are not trees. Consider Procedure <ref>. From the preceding discussion, it is clear that the procedure also correctly solves $\pDPo$ on $\Psi_3$. The space used by the procedure, as before, is $\Oh{\log{n}}$.

$l \gets 0$
$v \in V$
determine $C$, the set of vertices in the connected component of $v$
$v$ is the smallest vertex in $C$ and $G[C]$ is not a tree
$l \gets l + 1$
$l > k$

SolveDLFP1On(): solve a restricted graph deletion problem

§ VERTEX COVER NUMBER AS PARAMETER

§.§ The ReduceLog Procedure

$(G, X, l, c_{\Pi})$, where $G$ is a graph, $X$ is a vertex cover for $G$, and $l, c_{\Pi} \in \N$
$G'$, a reduced graph

$S \gets \emptyset$
$v \in \V{G}$
$Y \subseteq X$ with $\abs{Y} \leq c_{\Pi}$
each partition $Y = Y^+ \sqcup Y^-$
$Z \gets \setb{w \in \V{G} \setminus X}{w\ \text{is adjacent to all of}\ Y^+\ \text{and none of}\ Y^-}$
$v$ is among the first $l$ vertices in $Z$
$S \gets S \cup \brc{v}$

$G - S$

ReduceLog(): reduce $G$ using the vertex cover $X$

The orginal Reduce procedure, described below, differs only in the way the vertices $v \in Z$ to be added to $S$ are determined.

$(G, X, l, c_{\Pi})$, where $G$ is a graph on $n$ vertices, $X$ is a vertex cover for $G$, and $l, c_{\Pi} \in \N$
$G'$, a reduced graph

$S \gets \emptyset$
$Y \subseteq X$ with $\abs{Y} \leq c_{\Pi}$
each partition $Y = Y^+ \sqcup Y^-$
let $Z$ be the set of vertices in $\V{G} \setminus X$ adjacent to all of $Y^+$ and none of $Y^-$
let $T$ be an arbitrary set of $l$ vertices of $Z$ or all of it, if $Z$ has less than $l$ vertices
$S \gets S \cup T$;

$G - S$

Reduce(): reduce $G$ using the vertex cover $X$

The original Reduce procedure marks vertices $v \in G$ if $v$ is adjacent to all of $Y^+$ and none of $Y^-$ for some partition $Y^+ \sqcup Y^-$ of $X$. This may require space $\Om{n}$. In contrast, ReduceLog bypasses this marking step while producing the same kernelization guarantees as in Proposition <ref>. Correctness is easy to see by comparing the procedures ReduceLog and Reduce. We now prove Lemma <ref>.

The space used by the loop at Line <ref> is $\Oh{\log{n}}$, since it only requires the vertex $v \in \V{G}$ to be stored. The loop at Line <ref> must store a set $Y \subseteq X$ of size at most $c_{\Pi}$. With access to $X$, individual elements within it can be referenced using $\Oh{\log{\abs{X}}}$ bits of space, so $Y$ can be stored using space $\Oh{c_{\Pi} \log{\abs{X}}}$. Similarly, the partition $Y^+ \sqcup Y^- = Y$ in the loop at Line <ref> can be stored using space $\Oh{c_{\Pi} \log{\abs{X}}}$.

Now the set $Z$ can be determined by enumeration: for each $v \in \V{G}$, enumerate $Y^+$ and check if $v$ is adjacent to all vertices enumerated, and then enumerate $Y^-$ and check if $v$ is adjacent to none of the vertices enumerated. This uses space $\Oh{\log{n}}$ (to enumerate all vertices $v \in \V{G}$), in addition to the space used to store $Y^+$ and $Y^-$.

Observe that the set $S$ is only modified on Line <ref>, and in fact, the loop at Line <ref> simply determines for every vertex $v \in \V{G}$ whether $v$ is in $S$. Thus, $S$ can be determined implicitly using the loop; the check at Line <ref> determines whether $v$ is in $S$. The output of the procedure is the induced graph $G - S$, which, given access to $S$, can be produced by enumerating the vertices and edges of $G$ and suppressing vertices which appear in $S$ (this can again be checked by enumerating $S$) and edges whose endpoints appear in $S$. This uses an additional $\Oh{\log{n}}$ bits of space. Thus, the total space used by the procedure is $\Oh{c_{\Pi} \log{\abs{X}} + \log{n}} = \Oh{\log{n}}$, since $\abs{X} \leq n$, and $c_{\Pi}$ is a constant.

§.§ Problem Definitions

$\Pi$ is a class of possibly empty graphs and there is a non-decreasing polynomial $p$ such that every $G \in \Pi$ satisfies $\abs{G} \leq p(\tau_G)$.

Instance: $(G, k)$, where $G$ is a graph and $k \in \N$

Question: Is there a set $S \subseteq V$ with $\abs{S} \geq k$ such that $G[S] \in \Pi$?

$\Pi$ is class of possibly empty graphs and there is a non-decreasing polynomial $p$ such that every vertex minimal $G \in \Pi$ satisfies $\abs{G} \leq p(\tau_G)$.

Instance: $(G, k)$, where $G$ is a graph and $k \in \N$

Question: Is there a partition $\V{G} = V_1 \sqcup \dotsc \sqcup V_q$ such that $G[V_i]\ (i \in [q])$ contains no graph in $\Pi$ as an induced subgraph?

Instance: $(G, k)$, where $G$ is a graph and $k \in \N$

Question: Is there a set $S \subseteq V$ with $\abs{S} \leq k$ such that $G - S$ is a planar graph?

Instance: $(G, k)$, where $G$ is a graph and $k \in \N$

Question: Is there a set $S \subseteq V$ with $\abs{S} \leq k$ such that $G - S$ is a bipartite graph?

Instance: $(G, k)$, where $G$ is a graph and $k \in \N$

Question: Is there a set $S \subseteq V$ with $\abs{S} \leq k$ such that $G - S$ is a chordal graph?

Instance: $(G, k)$, where $G$ is a graph and $k \in \N$

Question: Is there a set $S \subseteq V$ with $\abs{S} \leq k$ such that $G - S$ is a forest?

$\prob{Longest Path/Cycle}$

Instance: $(G, k)$, where $G$ is a graph and $k \in \N$

Question: Does $G$ contain a path/cycle of length at least $k$?

§.§ Formulating problems as $\pIndPiFDS$, $\pLIndPiS$ or $\pqPartDisjPiFree$

* forbidden class is the class of graphs containing $K_{3, 3}$ or $K_5$ minors, characterized by $c_{\Pi} = 4$ adjacencies

* equivalent to $\pIndPiFDS$

* forbidden class is the class of odd-length cycles characterized by $c_{\Pi} = 2$ adjacencies

* equivalent to $\pIndPiFDS$

* forbidden class is the class of chordless cycles characterized by $c_{\Pi} = 3$ adjacencies

* equivalent to $\pIndPiFDS$

* forbidden class is the class of cycles characterized by $c_{\Pi} = 2$ adjacencies

* equivalent to $\pqPartDisjPiFree$

* target class is the class of hamiltonian paths characterized by $c_{\Pi} = 2$ adjacencies

* equivalent to $\pLIndPiS$

* target class is the class of hamiltonian cycles characterized by $c_{\Pi} = 2$ adjacencies

* equivalent to $\pLIndPiS$

The above formulations show that all problems appearing in Corollaries <ref> and <ref> can be formulated as $\pDelPi$, $\pLIndPiS$ or $\pqPartDisjPiFree$, from which it is clear that they can be kernelized using ReduceLog. For further details, we refer the reader to Fomin et. al <cit.>.

§ $\PFVS$

The following procedure determines whether a pair of vertices $u$ and $v$ are adjacent after applying the Degree-$2$ rule.

§.§ Solving $\pFVS$ in time ${(3k)}^k \cdot n^{\Oh{1}}$ using $\Oh{k \log{n}}$ bits of space

The following result allows us to use a simple branching strategy to solve $\pFVS$.

Let $G$ be a graph with minimum degree $3$ and let $v_1, \dotsc, v_n$ be the vertices of $G$ ordered by degree from smallest to largest. Any any feedback vertex set for $G$ of size at most $k$ ($3k \leq n$) contains one of the vertices $v_1, \dotsc, v_{3k}$.

Consider the following algorithm. Start by applying the Degree–$2$ Rule and remove vertices that are isolated, have degree one and have self-loops (in this case, decrease the solution budget by one). Now branch by picking one of the $3k$ highest-degree vertices into the solution and decrease the solution budget by one. At the beginning of each branch, reapply the Degree–$2$ rule and the rules for vertices that are isolated, have degree one or have self loops. After $k$ steps of this branching process, check whether the remaining graph is a forest. If it is, output the solution vertices and if all the branches fail, return .

The last step of checking if the graph is a forest can be performed using space $\Oh{\log{n}}$ (see the proof of Corollary <ref>) and as discussed earlier each of the reduction rules can be performed using space $\Oh{\log{n}}$. As the height of the recursion is at most $k$, the space used to store the solution vertices is $\Oh{k \log{n}}$. Thus, the algorithm uses a total of $\Oh{k \log{n}}$ bits of space. Additionally, the algorithm branches on $3k$ vertices at each level of the recursion, so the running time is ${(3k)}^k \cdot n^{\Oh{1}}$. The next theorem follows directly from this discussion.

§.§ Solving $\pFVS$ in time $5^k \cdot n^{\Oh{1}}$ using $\Oh{k \log{n}}$ bits of space

$(G, S, k)$, where $G$ is a graph, $k \in \N$ and $S$ is a feedback vertex set for $G$ of size at most $k + 1$
$S'$, a feedback vertex set for $G$ of size at most $k$ or $\NO$ if no such set exists
each $Z \subseteq S$ of size at most $k$
FVSBranch$G - Z, S \setminus Z, \emptyset, k - \abs{Z}$

$H, P, R, l$
$l \leq 0$
return $R$ if $H$ is a forest and  otherwise

each $v \in \V{H} \setminus R$
there is a cycle $C$ such that $\V{C} \setminus P = \brc{v}$
$R \gets R \cup \brc{v}, l \gets l  - 1$

apply the Degree-2 rule exhaustively to $H$
each leaf $v \in H \setminus P$
all $u, w \in \Nbr{P}{v}$
$u$ and $w$ are connected in $H[P]$
$U \gets \algoi{FVSBranch}{H, P, R \cup \brc{v}, l - 1}, W \gets \algoi{FVSBranch}{H, P \cup \brc{v}, R, l}$
if $U \neq \NO$ then return $U$
if $W \neq \NO$ then return $W$

FVSCompress(): find a smaller feedback vertex set given one as input


# Latitudinal Connectivity of Ground Level Enhancement Events

N. Gopalswamy1, P. Mäkelä1,2 1NASA Goddard Space Flight Center, Greenbelt, MD
20771, U.S.A.
2The Catholic University of America, Washington, DC 20064, U.S.A.

###### Abstract

We examined the source regions and coronal environment of the historical
ground level enhancement (GLE) events in search of evidence for non-radial
motion of the associated coronal mass ejection (CME). For the 13 GLE events
that had source latitudes $>$30∘ we found evidence for possible non-radial CME
motion due to deflection by large-scale magnetic structures in nearby coronal
holes, streamers, or pseudo streamers. Polar coronal holes are the main source
of deflection in the rise and declining phases of solar cycles. In the maximum
phase, deflection by large-scale streamers or pseudo streamers overlying high-
latitude filaments seems to be important. The B0 angle reduced the ecliptic
distance of some GLE source regions and increased in others with the net
result that the average latitude of GLE events did not change significantly.
The non-radial CME motion is the dominant factor that reduces the ecliptic
distance of GLE source regions, thereby improving the latitudinal connectivity
to Earth. We further infer that the GLE particles must be accelerated at the
nose part of the CME-driven shocks, where the shock is likely to be quasi-
parallel.

##  1 Introduction

Ground level enhancement (GLE) in solar energetic particle (SEP) events
represents the highest energy ($\sim$GeV) particles accelerated during large
solar eruptions. GLE particles are thought to be accelerated by the flare
process or the CME-driven shock. Extensive CME observations became available
only during Solar Cycle (SC) 23 (Cliver 2006; Gopalswamy et al. 2012a). Among
the 16 GLEs observed during SC 23, fast and wide CMEs were observed in all but
one GLE. The 1998 August 24 GLE was the exception, occurring when the SOHO
spacecraft was temporarily disabled (no CME observations). However, a fast
interplanetary CME was observed, implying a fast CME near the Sun. Thus a one-
to-one correspondence between GLEs and fast CMEs was established (Gopalswamy
et al. 2012a). Based on metric type II radio burst onset, flare rise time, and
CME speed, these authors found that the CME shocks form very close to the Sun
($<$0.5 solar radii above the solar surface) and that the shocks have
sufficient time to accelerate particles to GeV energies. These observations
strongly support the shock acceleration mechanism. Even though a large number
of type II radio bursts were observed during SC 24 (indicating the occurrence
of CME-driven shocks), there was only one GLE (on May 17, 2012) so far.
Gopalswamy et al. (2013) suggested that poor latitudinal connectivity may be
one of the main reasons for the very low occurrence rate of GLEs. In this
paper, we present additional evidence in support of this connectivity
constraint by considering all GLE events since their discovery in 1942
(Forbush, 1946). Heliographic coordinates of the associated flares are known
for almost all CMEs (Cliver et al. 1982; Cliver, 2006; Gopalswamy et al.
2012a; Nitta et al. 2012; Miroshnichenko et al. 2013). CMEs were discovered in
1971, but routine information became available only after the launch of SOHO
in December 1995. Therefore, we cannot determine CME non-radial motion for
most GLEs. However, we identify coronal holes and streamers that can deflect
the GLE-causing CMEs.

Figure 1.: (a) A coronal hole map derived from the Kitt Peak Vacuum Telescope
(KPVT) data. The blue and red patches correspond to coronal holes with
positive and negative polarities, respectively. The flare location (N11W76) of
the 2012 May 17 GLE at 02:40 UT is shown by the white circle. The large
coronal hole to the north of the GLE source region is consistent with the
southward (non-radial) motion of the GLE-associated CME. (b) The white-light
CME in a SOHO/LASCO image taken by its C2 telescope at 01:48 UT. Superposed on
the coronagraph image is a 193 Å EUV image taken by the Solar Dynamics
Observatory s Atmospheric Imaging Assembly (AIA) showing the flare location
close to the northeast limb.

##  2 The 2012 May 17 GLE Event

The first and only GLE event of SC 24 as of this writing originated from NOAA
active region 11476 in the northwest quadrant of the Sun (N11W76). Coronagraph
images from SOHO and STEREO show that the CME moved non-radially, heading in
the southwest direction (Gopalswamy et al. 2013). Forward-fitting of the
coronagraph images using Thernisien (2011) flux rope model indicated that the
effective location of the CME source region was S07W76, indicating that the
CME was deflected to the south by about 18∘. When we examined the coronal
environment of the GLE source a few hours before the eruption, we found a
large coronal hole close to the active region in the northeast direction (see
Fig. 1a). The southern end of the coronal hole was less than 10∘ away from the
active region. The approximate centroid of the coronal hole was at N30W60. The
CME motion is thus consistent with a deflection by the coronal hole (Fig. 1b).
Such deflections are thought to cause “driverless” shocks observed at Earth in
extreme cases (Gopalswamy et al. 2009; 2010) and decide whether a CME flux
rope appears as a magnetic cloud or non-cloud ejecta in in-situ observations
(Xie et al. 2013; Mäkelä et al. 2013). The configuration in Fig. 1 is the
motivation for us to look at historical GLE events for possible non-radial
motion of the associated CMEs. The SC 24 GLE was associated with only an M5.1
flare, which is well below the typical soft X-ray flare size for SC 23 GLEs
(X3.8). Historically, there were only two other GLEs with flare size smaller
than the SC 24 GLE: GLE 33 on 1979 August 21 with a C6 flare and GLE 35 on
1981 May 10 with a M1 flare (Cliver, 2006; Gopalswamy et al. 2012a). The CME
associated with the SC 24 GLE was very fast ( 2000 km/s), capable of driving a
strong shock, and hence produce GLE particles (Gopalswamy et al. 2013). By
examining the source regions of several eruptions from SC 24 that had the same
the source longitude range as this GLE event, Gopalswamy et al. (2013)
concluded that the non-GLE source regions had latitudinal distance from the
ecliptic: 32∘ compared to 9∘ for SC 23 GLEs from similar source longitude (13∘
when all SC 23 GLEs were considered). Unfavorable solar B0-angles and non-
radial CME motions were found to be the reasons for the increased distance
from the ecliptic. The B0 angle is the heliographic latitude of the central
point of the solar disk and can vary from -7∘.23 to + 7∘.23. B0 represents the
fact that the ecliptic plane (where Earth is located) and the Sun’s equatorial
plane are not aligned. Thus for a northern (southern) CME source with negative
(positive) B0 angle the magnetic connectivity to Earth worsens. B0 was -2∘.4
for the SC 24 GLE, making the latitudinal distance to the ecliptic as 4∘.6,
which is less than the average distance for SC 23 GLE source regions (13∘).
Thus the latitudinal connectivity of the shock nose is important for GLEs.

##  3 Source Regions of Historical GLE Events

The historical GLE events are shown as a “butterfly” diagram in Fig. 2. The
source locations were taken from the published literature (see e.g., Cliver et
al. 1982; Cliver 2006; Gopalswamy et al. 2012a; Miroshnichenko et al. 2013).
The first two GLEs were observed in SC 17 on 1942 February 28 and March 7,
respectively. Forbush (1946) reported on these two GLEs and on the third GLE
(1946 July 25), which occurred in SC 18. For the five cycles starting from SC
19, there were roughly a dozen GLEs per cycle, but we have only one GLE event
in SC 24. Figure 2b shows that the source latitudes are below 40∘, as expected
because the energy needed for the GLE events are available only in sunspot
regions. The latitude distribution is bimodal because of the northern and
southern active region belts. The average latitudes are -15∘.3 (south) and
19∘.6 (north). When we corrected for the B0 angle, the average ecliptic
distances did not change significantly: -17∘.9 and 19∘.2 in the southern and
northern hemispheres, respectively. These average latitudes are slightly
larger than the 13∘ obtained for SC 23 events (after accounting for non-radial
CME motion). Unfortunately, we have no CME observations for most of the pre-
SOHO GLEs, but we shall show that the effective ecliptic distances are
expected to be lower for pre-SOHO GLEs based on their coronal environment. The
source longitudes of historical GLE events (Fig. 2d) range from E88 to W150,
but there were only two events beyond E15 (E88 and E39). On the other hand,
there were a dozen events behind the west limb. The longitude distribution
suggests that the magnetic connectivity of Earth to the source region is very
important.

Figure 2.: (a) GLE latitude as a function of time for GLEs since their
discovery in 1942. The approximate times of solar maxima of cycles 18–24 are
denoted by vertical dashed lines (from http://sidc.oma.be/DATA/monthssn.dat).
(b) The distribution of flare latitudes of the GLE events as in (a). (c) The
latitude distribution corrected for the B0 angle. (d) The distribution of
flare longitudes. The bin size is 6 degrees for all the distributions. In the
latitude distribution, there are only 70 events because the latitude of the
backside event 39 is unknown. The two GLEs with the easternmost source
longitudes are on 1960 September 3 and 1978 April 29. In the longitude
distribution, the $>$90∘ bin (the dark bin) includes all behind the west-limb
events.

###  3.1 Higher-Latitude GLEs

The GLE events with latitudes $>$30∘ are of interest because they clearly
contradict our conclusion that the ecliptic distance of the source regions
needs to be small for a GLE event. These higher-latitude GLEs are listed in
Table 1 along with the flare location, B0 angle, latitudinal distance to the
ecliptic ($\lambda$e), Carrington Rotation (CR) number with its starting day,
and whether a deflecting structure (coronal hole, streamer, or pseudo
streamer) existed poleward of the source region. We have included GLEs with
source latitude $>$30∘ either before accounting for B0 angle or after. Before
B0 correction, there were nine events with source latitude $>$30∘ and all were
from the north. After B0 correction, GLEs 32 and 58 had $\lambda$e $<$30∘. GLE
15 had similar trend, but $\lambda$e $\sim$31∘. After B0 correction, 4 events
from the south (GLEs 42–45) had $\lambda$e $>$30∘ (i.e, the connectivity
worsened). The B0 angle was less than 2∘ and hence insignificant for six
events (GLEs 47–52).

GLEs with either flare latitude or $\lambda$e exceeding 30∘ fall into three
groups depending on the SC phase: GLEs 15, 32, and 58 were rise-phase events,
GLEs 51 and 52 were declining-phase events, and the remaining 8 were maximum-
phase events. Accordingly, one expects different coronal environment for the
two groups. For example, strong polar coronal holes (PCH) prevail in the rise
phase and the sunspots appear at relatively higher latitudes.

Table 1.: Historical GLE events with flare latitudes $>$30∘ GLE # | Date | Flare Loc. | B0 |  $\lambda$e | CR # | Start Date | Deflector
---|---|---|---|---|---|---|---
15 | 1966/07/07 | N35W48 | +3.55 | N31 | 1509 | 22.0747 | PCH?
32 | 1978/09/23 | N35W50 | +7.02 | N28 | 1673 | 20.0572 | PCH
42 | 1989/09/29 | S24W105 | +6.80 | S31 | 1820 | 11.5184 | S+CH
43 | 1989/10/19 | S25E09 | +5.54 | S31 | 1821 | 8.7953 | S
44 | 1989/10/22 | S27W32 | +5.29 | S32 | 1821 | 8.7953 | S
45 | 1989/10/24 | S29W57 | +5.11 | S34 | 1821 | 8.7953 | S
47 | 1990/05/21 | N34W37 | -1.94 | N36 | 1829 | 15.2476 | PS
48 | 1990/05/24 | N36W76 | -1.59 | N38 | 1829 | 15.2476 | PS
49 | 1990/05/26 | N35W103 | -1.35 | N36 | 1829 | 15.2476 | PS
50 | 1990/05/28 | N35W120 | -1.11 | N36 | 1829 | 15.2476 | PS
51 | 1991/06/11 | N32W15 | +0.57 | N31 | 1843 | 1.0619 | PCH
52 | 1991/06/15 | N36W70 | +1.07 | N35 | 1843 | 1.0619 | PCH
58 | 1998/08/24 | N35E09 | +7.01 | N28 | 1939 | 1.3214 | PCH

We examined coronal hole maps available from Kitt Peak National Observatory
(KPNO): ftp://nsokp.nso.edu/kpvt/synoptic/choles/ for Carrington Rotations
1633 (1975 September 25) to 1987 (2002 March 2). We also used Yohkoh soft
X-ray data for confirmation in SC 23. Finally, we also examined the H-alpha
synoptic charts (ftp://ftp.ngdc.noaa.gov/STP/SOLAR_DATA/SGD_PDFversion/)from
the Solar Geophysical Data to understand the environment of GLE source
regions. Figure 3 shows the source regions of GLEs 51, 52, and 58 on He 10830
Å coronal hole maps. Clearly there were polar coronal holes (PCH) in each of
the three cases. For GLE 58, there is additional confirmation from Yohkoh Soft
X-ray Telescope (SXT) images, which show a prominent PCH in the north (see
also Fig. 3 in Gopalswamy et al. 2012a). KPNO maps show north PCH for GLE 32
also. Sheeley (1980) reported on this PCH (his Figure 1), which shows an
extension of the PCH in the direction of the GLE source. Note that GLEs 51 and
52 occurred right after the polarity reversal in the northern hemisphere
during cycle 22 and the PCH started increasing area. On the other hand GLE 58
occurred during the rise phase of SC 23, when the PCH area is close to its
peak.

Figure 3.: Coronal hole synoptic maps with the GLE source regions superposed
for Carrington rotations 1843 (GLEs 51, 52) and 1939 (GLE 58). The maps were
derived from He 1083 nm spectroheliograms at KPNO.

There was no coronal hole observations for GLE 15, but one can infer a PCH
because the event occurred during the rise phase of SC 20. The cycle started
in October 1964 and the GLE occurred within 2 years into the cycle. The
situation is somewhat similar to GLE 58, which also occurred within 2 years
into SC 23. The PCH attains its maximum area around the solar minimum,
remaining high for two years on either side of the minimum. The GLE sources
are generally at higher-latitude during the rise phase because sunspots
originate at higher latitudes in the rise phase. Thus the combination of
strong polar coronal holes and the higher-latitude source regions is conducive
for CME deflections. This has been suggested as the reason for the offset
between position angles of prominence eruptions and the corresponding CMEs
(Gopalswamy et al. 2003; 2012b) and the larger fraction of flux-rope type CMEs
(magnetic clouds) occurring during the rise phase of solar cycles (Gopalswamy
et al. 2008). Thus we conclude that GLE 15 is consistent with a possible PCH
deflection of the associated CME.

The eight maximum-phase events occurred during SC 22. Since the PCHs disappear
in this phase, we do not expect deflection of CMEs by coronal holes. Figure 4
shows that there was no coronal hole but an extended “switchback” filament to
the north of the source region of GLEs. The leading and trailing branches of
the switch back filaments can also be seen in the He 10830 Å synoptic map in
Fig. 4. H-alpha synoptic chart available at the Solar Geophysical Data
confirms the switch back filament (see the H-alpha solar synoptic chart for
Carrington Rotation 1829 in
ftp://ftp.ngdc.noaa.gov/STP/SOLAR_DATA/SGD_PDFversion/). The filament was very
long, extending from Carrington longitude 170∘ to 360∘. The trailing and
leading branches of the switchback were about 15∘ and 35∘ from the active
region. One expects a pseudo-streamer type magnetic configuration immediately
to the north of the eruption region. We suggest that the magnetic field of the
streamer behaves similar to that of coronal holes in deflecting CMEs. For GLEs
42–45, the situation was very similar in the southern hemisphere. GLE 42
occurred from the same source region of GLEs 43–45, but one Carrington
rotation earlier. In addition the long filament, GLE 42 had an isolated
coronal hole to the southwest, which also might have contributed to the
deflection (see H-alpha solar synoptic chart for Carrington Rotation 1820 and
1821 in ftp://ftp.ngdc.noaa.gov/STP/SOLAR_DATA/SGD_PDFversion/). The switch
back was not as sharp as in Fig. 4, but the filament was even longer: 135∘ to
360∘ in Carrington longitude. The streamer nearest to the active region and
overlying the filament is expected to be a normal streamer. Thus we conclude
that the coronal environment is conducive for an equatorward deflection in all
the GLEs listed in Table 1. The last column of Table 1 lists the magnetic
structures that might have caused the deflection: a polar coronal hole (PCH),
streamer (S), or pseudo streamer (PS). In one case, it is possible that a
streamer and a coronal hole might have jointly caused the deflection. A
preliminary examination of the remaining GLE events with CH observations
indicate that small coronal holes were present at large distances, suggesting
little influence on the CMEs. In some cases, the coronal holes were favorably
located to improve the connectivity. There were a few cases in which the
deflection would worsen the connectivity, but these need a detailed
investigation to see if the ecliptic distance would increase substantially. A
detailed report will be published elsewhere.

Figure 4.: He 10830 Å synoptic map with the source region of GLEs 47 and 48
marked. In the map compact dark patches are active regions and thin elongated
features are filaments. A long switch back filament can be seen to the north
of the GLE source region. The arrow with the label switchback shows roughly
the location where the two arms converge. The poleward arm is pointed by the
upper arrow.

##  4 Discussion

The main results of this paper are: (i) the non-radial motion of the SC 24 GLE
seems to be due to the deflection by a coronal hole located to the northeast
of the eruption region, (ii) the CMEs in historical GLE events with flare
latitude $>$30∘ occurring in the rise and declining SC phases seem to be
deflected toward the ecliptic by polar coronal holes, (iii) higher-latitude
GLEs occurring in the maximum phase seem to deflected by a large-scale
streamer or pseudo streamer structure overlying high-latitude filaments. The
B0 angle reduced the ecliptic distance of the GLE source region in some cases
and increased in others with the net result that the average latitude of GLE
events did not change significantly. The non-radial motion seems to the
dominant factor in reducing the ecliptic distance of GLE source regions and
hence increasing the latitudinal connectivity to Earth. The coronal deflection
of CMEs happens because of the enhanced magnetic content of the coronal holes
(Gopalswamy et al. 2009; Gopalswamy et al. 2010; Shen et al. 2011). For polar
coronal holes, this represents the solar dipolar field, which is the strongest
during solar minima (see e.g., Svalgaard et al. 1978; Gopalswamy et al. 2003).
One of the main properties of coronal holes is that the magnetic field at the
photospheric level is enhanced and unipolar relative to the neighboring quiet
regions. The field expands into the corona and represents magnetic pressure
gradient between the coronal hole and the eruption region (e.g., Panasenco et
al. 2012; Kay et al. 2013) and hence pushes the CME away from the coronal
hole. We suggest that the same physical picture applies when a large-scale
streamer or pseudo streamer is present on one side of the eruption region
causing the magnetic pressure gradient. The equatorward deflection of CMEs
associated with GLE events suggests that Earth may be connected to the nose
part of the CME-driven shocks. Given the fact that GLE particles are released
when the CME leading edge is at a heliocentric distance of $\sim$3 Rs
(Gopalswamy et al. 2012a), we suggest that the GLE particles may be
accelerated at the quasi-parallel section of CME-driven shocks. This is
because the nose part is well above the source surface where the field lines
in the ambient medium are expected to be radial. It must be pointed out that
coronal hole deflection may not be the only reason for non-radial CME motion.
In some active regions, it is possible that non-radial ejections happen due to
the magnetic complexities in the source regions. It is also possible that CMEs
involve a high-inclination flux rope so that the nose region is much extended
in the north-south direction. We confirm that the ecliptic distance of the
source region of a solar eruption is one of the factors that determine whether
an SEP event becomes a GLE event. This may be one of the reasons why GLE
events are so rare. Other reasons include the reduced number of energetic
eruptions during SC 24 and the reduction in seed particles (and preceding
CMEs) available to be accelerated by the CME-driven shocks. The reduced
efficiency of particle acceleration by the shocks due to the change in
physical conditions in the heliosphere (e.g., increase in the Alfvén speed of
the ambient medium). Thus, GLE events require special conditions in terms of
CME kinematics, coronal environment, and magnetic connectivity to Earth.

##  5 Summary

We have confirmed that non-radial CME motion is likely to have happened in
historical GLE events that occurred at latitudes $>$30∘ due to deflection by
large-scale magnetic structures in coronal holes or in streamers. We also
infer that the highest energy particles are produced at the nose part of the
CME-driven shocks, where the shock strength is highest. Furthermore, the shock
is likely to be quasi-parallel in the nose region because the GLE associated
CMEs typically cross the potential field source surface at the time of GLE
particle release. The special conditions needed to detect a GLE event at Earth
coupled with the reduced frequency of energetic eruptions may be responsible
for the paucity of GLE events in SC 24.

#### Acknowledgments

This work utilizes SOLIS data obtained by the NSO Integrated Synoptic Program
(NISP), managed by the National Solar Observatory, which is operated by the
Association of Universities for Research in Astronomy (AURA), Inc. under a
cooperative agreement with the National Science Foundation. Work supported by
NASA’s Living with a Star program.

## References

  * Cliver (2006) Cliver, E. W. 2006, Astrophys. J. 639, 1206
  * Cliver et al. (1982) Cliver, E. W., Kahler, S. W., Shea, M. A., & Smart, D. F. 1982, Astrophys. J. 260, 362
  * Forbush (1946) Forbush, S. E. 1946 Phys. Rev. 70, 771
  * Gopalswamy et al. (2003) Gopalswamy, N., Shimojo, M., Lu, W., Yashiro, S., Shibasaki, K., & Howard, R. A. 2003 Astrophys. J. 586, 562
  * Gopalswamy et al. (2008) Gopalswamy, N., Akiyama, S., Yashiro, S., Michalek, G., & Lepping, R. P. 2008, J. Atmos. Sol.-Terr. Phy. 70, 245
  * Gopalswamy et al. (2009) Gopalswamy, N., Mäkelä, P., Xie, H., Akiyama, S., & Yashiro, S. 2009, J. Geophys. Res. 114, A00A22
  * Gopalswamy et al. (2010) Gopalswamy, N., Mäkelä, P., Xie, H., Akiyama, S., & Yashiro, S. 2010, Solar Wind 13, AIP Conference Proceedings, Vol. 1216, pp. 452–458
  * Gopalswamy et al. (2012a) Gopalswamy, N., Xie, H. Yashiro, S., Akiyama, S., Mäkelä, P., & Usoskin, I. G. 2012a, Space Sci. Rev. 171, 23
  * Gopalswamy et al. (2012b) Gopalswamy, N., Yashiro, S., Mäkelä, P., Michalek, G., Shibasaki, K., & Hathaway, D. H. 2012b, Astrophys. J. 750, L42
  * Gopalswamy et al. (2013) Gopalswamy, N., Xie, H., Akiyama, S., Yashiro, S., Usoskin, I. G., & Davila, J. M. 2013, Astrophys. J. 765, L30
  * Kay et al. (2013) Kay, C., Opher, M., & Evans, R. M. 2013, Astrophys. J. 775, 5
  * Mäkelä et al. (2013) Mäkelä, P., Gopalswamy, N., Xie, H., Mohamed, A. A., Akiyama, S., & Yashiro, S. 2013, Solar Phys. 284, 59
  * Miroshnichenko et al. (2013) Miroshnichenko, L. I., Vashenyukc, E. V., & P rez Peraza, J. A. 2013, Geomagnetism and Aeronomy 53, 541
  * Nitta et al. (2012) Nitta, N. V., Liu, Y., DeRosa, M. L., & Nightingale, R. W. 2012, Space Sci. Rev. 171, 61
  * Panasenco et al. (2013) Panasenco, O., Martin, S. F., Velli, M., & Vourlidas, A. 2013, Solar Phys. Online First, DOI: 10.1007/s11207-012-0194-3
  * Sheeley (1980) Sheeley, N. R., Jr. 1980, Solar Phys. 65, 229
  * Shen et al. (2011) Shen, C., Wang, Y.-M., Gui, B., Ye, P., & Wang, S. 2011, Solar Phys. 269, 389
  * Svalgaard et al. (1978) Svalgaard, L., Duvall, T. L., Jr., & Scherrer, P. H. 1978, Solar Phys. 58, 225
  * Thernisien (2011) Thernisien, A. 2011, Astrophys. J. Suppl. S. 194, 33
  * Xie et al. (2013) Xie, H., Gopalswamy, N., & St. Cyr, O. C. 2013, Solar Phys. 284, 47