N.S. Narayanaswamy and C.S. Rahul Billy Editor and Bill Editors2Conference
title on which this volume is based on111 10.4230/LIPIcs.xxx.yyy.p

# A Classification of Connected $f$-factor Problems inside
$\mathsf{NP}$111Supported by the Indo-German Max Planck Center for Computer
Science grant for the year 2013-2014 in the area of Algorithms and Complexity

N.S. Narayanaswamy  Indian Institute of Technology Madras, Chennai, India
<EMAIL_ADDRESS>C.S. Rahul  Indian Institute of Technology Madras,
Chennai, India
<EMAIL_ADDRESS>
###### Abstract.

Given an undirected graph $G=(V,E)$ with $|V|=n$, and a function
$f:V\rightarrow\mathbb{N}$, we consider the problem of finding a connected
$f$-factor in $G$. This problem is $\mathsf{NP}$-Complete when $f(v)\geq
n^{\epsilon}$ for every $v$ in $V$ and a contant $\epsilon>0$. We design an
algorithm to check for the existence of a connected $f$-factor, for the case
where $f(v)\geq n/g(n)$, for all $v$ in $V$ and $g(n)$ is polylogarithmic in
$n$. The running time of our algorithm is $\tilde{\mathcal{O}}(n^{2g(n)})$. As
a consequence of this algorithm, we conclude that the complexity of connected
$f$-factor for the case we consider is unlikely to be $\mathsf{NP}$-Complete
unless the Exponential Time Hypothesis (ETH) is false. Secondly, under the ETH
assumption, we show that the problem is also unlikely to be in $\mathsf{P}$
for $g(n)$ in $\mathcal{O}((\log{n})^{1+\epsilon})$ for any constant
$\epsilon>0$. These results show that for each $\epsilon>0$ and $g(n)$ in
$\mathcal{O}((\log{n})^{1+\epsilon})$, connected $f$-factor problem for
$f(v)\geq n/g(n)$ is in $\mathsf{NP}$-Intermediate unless the ETH is false.
Further, for any constant $c>0$, when $g(n)=c$, our algorithm for connected
$f$-factor runs in polynomial time. Finally we extend our algorithm to compute
a minimum weight connected $f$-factor in edge weighted graphs in the same
asymptotic time bounds.

###### Key words and phrases:

$f$-factors, Connected $f$-factors, $\mathsf{NP}$-Complete,
$\mathsf{NP}$-Intermediate, $\mathsf{P}$-time

###### 1991 Mathematics Subject Classification:

"F.1.3 Complexity Measures and Classes", "G.2.2 Graph Theory

##  1\. Introduction

Let $G=(V,E)$ be an undirected graph with $n$ vertices and
$f:V\rightarrow\mathbb{N}$ be a function. An $f$-factor [20] of $G$ is a
spanning subgraph $H$ such that $d_{H}(v)=f(v)$, for each $v$ in $V$. The
problem of deciding whether a given graph $G$ has an $f$-factor is a well
studied problem over many years [1, 17, 15, 4, 8, 14] and the problem is shown
to be polynomial time solvable by Tutte [18]. When edges have weights, a
simple modification to Tutte’s reduction solves the minimum weighted
$f$-factor problem.
A connected $f$-factor is an $f$-factor which is connected. For the case when
$f(v)=2$ for all $v$ in $V$, a connected $f$-factor is a Hamiltonian cycle
[20] and is $\mathsf{NP}$-Complete to decide. In fact, Cheah and Corneil [2]
showed that the connected $f$-factor problem is $\mathsf{NP}$-Complete where
$f(v)=d$ for each $v$ in $V$ and an integer constant $d>1$. For
$f(v)\geq\lceil\frac{n}{2}\rceil$ for every $v$ in $V$, deciding a connected
$f$-factor is same as deciding whether there exists an $f$-factor or not. This
is because in this case, any $f$-factor turns out to be connected, due to Ore
[13] and Dirac [5].
Past Work on Connected Factors. There has been an extensive study on connected
$[a,b]$-factors in the literature over the past twenty years. An
$[a,b]$-factor is a subgraph $H$ of a graph $G$ such $a\leq d_{H}(v)\leq b$,
for each $v$ in $V$. There are many results on sufficiency conditions for a
graph to have a connected $[a,b]$-factor. For example, when
$\delta(G)\geq\frac{n}{2}$ the Graph is Hamiltonian, due to Ore [13] and Dirac
[5]. Also, if the sum of degrees of every pair of non-adjacent vertices is at
least $n-1$, then the graph has a Hamilton path, and this is a connected
$[1,2]$-factor. Similarly, by relating the size of the maximum independent set
and the vertex connectivity of a graph, there are sufficiency conditions for
the existence of connected $[a,b]$-factors. The survey article by Kouider and
Vestergaard [19] and Plummer [14] present more results on connected
$f$-factors.
Our Work. To the best of our knowledge, our study is the first of this kind in
the area of connected factors. We are motivated by this line of study with an
aim to classify functions $f$ for which the connected $f$-factor problem is
polynomial time solvable and those for which the problem is
$\mathsf{NP}$-Complete. In particular, our interest is to obtain a dichotomy
for connected $f$-factor problem based on $f$. To conceptualize the nature of
$f$, $f(v)$ is taken to be at least $n/g(n)$ for each $v$ in $V$ where $g(n)$
is a function in $o(n)$. In [3] we have shown that the problem is
$\mathsf{NP}$-Complete when $g(n)$ is $n^{1-\epsilon}$ for any constant
$\epsilon$ between 0 and 1. In recent work [12], we showed that the problem is
polynomial time solvable if $g(n)=3$. While connected $[a,b]$-factors are
studied extensively from the point of view of identifying sufficient
conditions, our work is on understanding how the computational complexity of
connected $f$-factor problem vary with $f$. We summarize our results as
follows:

  1. (1)

An algorithm running in time $\tilde{\mathcal{O}}(n^{2g(n)})$ for deciding the
existence of connected $f$-factor in a graph $G$ where $f(v)\geq n/g(n)$ for
each $v$ in $V$ and $g(n)$ is in $\mathcal{O}(\textnormal{polylog}($n$))$.
Clearly, the algorithm takes polynomial time when $g(n)$ is a constant and
quasi-polynomial time when $g(n)$ is polylogarithmic in $n$. It is interesting
that connected $\frac{n}{c}$-factor problem is polynomial time solvable for
any constant $c$, as this refines the class of functions $f$ for which the
connected $f$-factor problem is $\mathsf{NP}$-Complete: connected $d$-factor
is $\mathsf{NP}$-Complete for each constant $d$, as shown by Cheah and Corneil
in [2].

  2. (2)

A _refined_ characterization of graphs having connected $f$-factor where
$f(v)\geq n/g(n)$ for every $v$ in $V$ and $g(n)$ is in
$\mathcal{O}(\textnormal{polylog}($n$))$.

  3. (3)

An extension of the above mentioned algorithm to solve the minimum weighted
connected $f$-factor problem where $f(v)\geq n/g(n)$ for every $v$ in $V$ and
$g(n)$ is in $\mathcal{O}(\textnormal{polylog}($n$))$, without increasing the
asymptotic running time.

  4. (4)

Connected $f$-factor problem for $f(v)\geq n/g(n)$ for every $v$ in $V$ and
$g(n)$ is in $\mathcal{O}((\log n)^{1+\epsilon})$ for any constant
$\epsilon>0$, is in $\mathsf{NP}$-Intermediate under the ETH[9]. Thus, this
infinite class of problems parameterized by $\epsilon$ is similar in
complexity to the LOGCLIQUE[10] problem where the goal is to decide whether
there exists a clique of size $\log n$ in an $n$-vertex graph.

As a consequence of this work, we have a better refined understanding of
computational complexity of the connected $f$-factor problem based on the
nature of $f$. The main technique in this work is a natural way of converting
one $f$-factor to another by exchanging a set of edges. This is formalized
using the notion of _Alternating Circuit_ s that we use extensively in this
work. We believe that these techniques for enforcing connectedness along with
the results of Tutte [18] for finding $f$-factors plays an important role in
understanding the nature of the connected $f$-factor problem for different
classes of functions $f$.

##  2\. Preliminaries

###  2.1. Definitions and Notations

We use standard definitions and notations from West [20]. $G=(V,E)$ represents
an undirected graph on $n$ vertices, $d_{G}(v)$ denotes the degree of a vertex
$v$ in a graph $G$ and $N(v)$ denotes the open neighborhood of a vertex $v$.
$g(n)$ is in $\mathcal{O}(\textnormal{polylog}($n$))$ and $f$ is a function
whose domain is the vertex set of $G$ and range is the set $\\{\lceil
n/g(n)\rceil,\ldots,n-1\\}$. Given two subgraphs $G_{1}$ and $G_{2}$ of a
graph $G$, we use the basic definitions of binary operations $G_{1}\cap
G_{2}$, $G_{1}\cup G_{2}$ to be subgraphs obtained by the vertex and edge set
intersection and union operations respectively. We define the symmetric
difference $G_{1}\bigtriangleup G_{2}$ between two spanning subgraphs $G_{1}$
and $G_{2}$ of $G$ to be the spanning subgraph whose edge set is
$E(G_{1})\bigtriangleup E(G_{2})$. Further, the concepts of circuit,
decomposition of a graph $G$, the subgraph of $G$ induced by $S\subseteq V$
denoted by $G[S]$ are standard. We use $w(e)$ to represent weight of an edge
$e$ in a weighted graph and $w(G)$ to denote the sum of weights of edges in
$G$.
Given a partition $\mathcal{Q}=\\{Q_{1},Q_{2},\dots,Q_{r}\\}$ of the vertex
set of $G$, a graph $G/\mathcal{Q}$ is constructed as follows: The vertex set
of $G/\mathcal{Q}$ is $\mathcal{Q}$. Corresponding to each edge $(u,v)$ in $G$
where $u$ in $Q_{i}$, $v$ in $Q_{j}$, $i\neq j$, there exists an edge
$(Q_{i},Q_{j})$ in $G/\mathcal{Q}$. $G/\mathcal{Q}$ is a multigraph without
loops. For a spanning subgraph $G^{\prime}$ of $G$, we say $G^{\prime}$
_connects_ a partition $\mathcal{Q}$ if $G^{\prime}/\mathcal{Q}$ is connected.
A refinement $\mathcal{Q}^{\prime}$ of a partition $\mathcal{Q}$ is a
partition of $V$ where each part $Q^{\prime}$ in $\mathcal{Q}^{\prime}$ is a
subset of some part $Q$ in $\mathcal{Q}$. This concept of partition refinement
is from Kaiser [11]. Whenever we say a spanning tree of $G/\mathcal{Q}$, we
refer to a spanning subgraph $T$ of $G$ having $|\mathcal{Q}|$-1 edges that
connects $\mathcal{Q}$.

###  2.2. Colored Graphs and Alternating Circuits

A colored graph $G$ is one in which each edge is assigned a color from the set
$\\{red,blue\\}$. In a colored graph $G$, we use $R$ and $B$ to denote
subgraphs of $G$ whose edges are the set of red edges ($E(R)$) and blue edges
($E(B)$) of $G$, respectively, and $V(R)=V(B)=V(G)$. We use this coloring in
our algorithm to distinguish between edge sets of two distinct $f$-factors of
the same graph $G$. A main computation step in our algorithm is to consider
the symmetric difference between edge sets of two distinct $f$-factors and
perform a sequence of edge exchanges preserving the degree of each vertex. The
following definition is used extensively in our algorithm.

######  Definition 2.1.

A subgraph $S$ of a colored graph $G$ is an alternating circuit if $S$ is a
circuit, and there exists an Eulerian tour of $S$ in which every pair of
consecutive edges are of different colors.

Clearly, an alternating circuit has an even number of edges and is connected.
Further, $d_{R}(v)=d_{B}(v)$ for each $v$ in $S$. We define a _minimal_
alternating circuit $S$ to be an alternating circuit where each vertex $v$ in
$S$ has at most two red edges and two blue edges incident on it.

######  Definition 2.2.

A spanning subgraph $S$ of $G$ is defined to be a _switch_ on another spanning
subgraph $H$ of $G$ if we could color edges in $S\cap H$ with color red and
those in $S\setminus H$ with color blue such that each component in $S$ is an
alternating circuit.

######  Definition 2.3.

For an $S$ which is a switch on $H$, we define Switching($H$,$S$) to be a
subgraph $G^{\prime}$ of $G$ obtained by removing all edges in $S\cap H$ from
$H$ and adding all the edges in $S\setminus H$ to $H$.

Whenever the operation Switching($H$,$S$) is used, $S$ is assumed to be a
switch on $H$. Finally the weight of an alternating circuit $S$, denoted by
$W(S)$, is $w(B)-w(R)$. This will be used along with switching operation. If
$G^{\prime}=$Switching($H$,$S$), then it implies that
$w(G^{\prime})=w(H)+W(S)$. The weight of a switch $S$ is also similarly
defined to be $w(S\setminus H)-w(S\cap H)$. In our arguments we reason about
an $f$-factor obtained by switching a sequence of alternating circuits, and
for this we introduce the following notation. Let ${\mathcal{S}}$ be a set of
edge disjoint alternating circuits each of which is a switch on $H$. Let
$S^{\prime}=\displaystyle\cup_{S\in{\mathcal{S}}}S$. Then the operation
Switching($H$, ${\mathcal{S}}$) is the $f$-factor that results from
Switching($H$,$S^{\prime}$).

Unless otherwise mentioned, $g(n)$ is a function in
$\mathcal{O}($poly$\log(n))$. We justify why this choice of $g(n)$ is crucial
for our analysis in Lemma 6.1. $f$ is a function $f:V\rightarrow\mathbb{N}$
such that $f(v)\geq\lceil{n}/{g(n)}\rceil$, for each $v$ in $V$ where $n=|V|$.
A consequent fact is that, if $H$ is an $f$-factor of $G$, then the number of
components in $H$ is at most $g(n)-1$. We use two crucial subroutines from the
literature- Tutte’s-Reduction($G$,$f$) is a subroutine which outputs an
$f$-factor of $G$(if one exists) using the reduction in [20, example 3.3.12].
Modified-Tutte’s-Reduction($G$,$f$) is an extension of
Tutte’s-Reduction($G$,$f$), which computes a minimum weighted $f$-factor of
the input weighted graph $G$ by reducing it to the problem of finding a
minimum weighted perfect matching [7, 6]. We assume that both the above
subroutines return empty graphs if they fail to an compute $f$-factor.

##  3\. Outline of the Algorithm and a refined Characterization

The following is a natural characterization of graphs that have a connected
$f$-factor, and it is almost a restatement of the definition of a connected
$f$-factor.

######  Theorem 3.1.

Let $G$ be an undirected graph and $f$ be a function
$f:V\rightarrow\mathbb{N}$. $G$ has a connected $f$-factor if and only if for
each partition $\mathcal{Q}$ of the vertex set $V$, there exists an $f$-factor
$H$ of $G$ that connects $\mathcal{Q}$.

The forward direction of the proof is the observation that a connected
$f$-factor connects any partition of the vertex set. The converse is proved by
applying the hypothesis to the partition
$\mathcal{Q}=\\{\\{v_{1}\\},\\{v_{2}\\},\ldots,\\{v_{n}\\}\\}$. Theorem 3.1
sets up the foundation of our algorithm outlined below.

Outline of the search for connected $f$-factors: Here we set up the template
to search for a connected $f$-factor in an input graph $G$ based on Theorem
3.1. The details are in Algorithm 1 in section 6. Our algorithm constructs a
maximal  sequence of pairs
$(H_{0},\mathcal{Q}_{0}),(H_{1},\mathcal{Q}_{1}),\ldots,(H_{k},\mathcal{Q}_{k})$
satisfying the following properties:

  1. (1)

Each $\mathcal{Q}_{i},0\leq i\leq k$ is a partition of the vertex set $V$, and
$\mathcal{Q}_{0}=\\{V\\}$.

  2. (2)

Each $H_{i},0\leq i\leq k$ is an $f$-factor of $G$, and $H_{i}$ connects
$\mathcal{Q}_{i}$.

  3. (3)

For each $1\leq i\leq k$, Each $\mathcal{Q}_{i}$ is a refinement of
$\mathcal{Q}_{i-1}$ satisfying the following:

    1. (a)

Each part in $\mathcal{Q}_{i}$ is a maximal component in $H_{i-1}[Y]$ for some
$Y$ in $\mathcal{Q}_{i-1}$.

    2. (b)

$\mathcal{Q}_{i}\neq\mathcal{Q}_{i-1}$ and hence
$|\mathcal{Q}_{i}|>|\mathcal{Q}_{i-1}|$ for $1\leq i\leq k$.

The meaning of maximality of the sequence is that the sequence we consider is
not a prefix of a longer sequence satisfying the 3 conditions listed above.
Since $\mathcal{Q}_{i}$ is a refinement of $\mathcal{Q}_{i-1}$, it follows
that $k$ can be at most $n$. The following is an interesting and useful fact.

######  Fact 1.

Let $H$ be an $f$-factor of $G$ and let $\mathcal{Q}$ be a partitioning of the
vertex set $V$. If $H/\mathcal{Q}$ is connected and $H[Q]$ is connected for
each $Q$ in $\mathcal{Q}$, then $H$ is a connected $f$-factor.

If a refinement of $\mathcal{Q}_{k}$ satisfies conditions 1 and 3(a), is same
as $\mathcal{Q}_{k}$, then it follows from Fact 1, that $H_{k}$ is a connected
$f$-factor of $G$. On the other hand, if $H_{k}$ is not a connected
$f$-factor, then any refinement of $\mathcal{Q}_{k}$ has the property that
there is no $f$-factor of $G$ that connects it. Otherwise, if there was some
refinement that can be connected by some $f$-factor of $G$, there would be a
violation to the maximality of the sequence. In this case, from Theorem 3.1 we
can conclude that $G$ does not have a connected $f$-factor.

The algorithm we design directly evolves from Theorem 3.1 and it essentially
computes a maximal sequence $(H_{i},\mathcal{Q}_{i}),0\leq i\leq k$ of pairs
satisfying the conditions outlined above. The algorithm initializes
$\mathcal{Q}_{0}={V(G)}$, and $H_{0}$ to an arbitrary $f$-factor of $G$. The
computation of the next pair in sequence is done by the subroutine
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$) (described later in
Section 6) which computes $\mathcal{Q}_{i}$ from $\mathcal{Q}_{i-1}$ and
$H_{i-1}$. Further the algorithm performs a computation of $H_{i}$ from
$H_{i-1}$ and $\mathcal{Q}_{i}$. The procedure
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$) mainly involves three
computational subtasks for each $1\leq i\leq k$.

  1. (1)

Computes $\mathcal{Q}_{i}$ from $\mathcal{Q}_{i-1}$ by considering the
subgraph $H_{i-1}[Q]$ and finds components in $H_{i-1}[Q]$ for each $Q$ in
$\mathcal{Q}_{i-1}$. These components are all the parts in $\mathcal{Q}_{i}$.

  2. (2)

A set of steps referred to as Partition-Connector($\mathcal{Q}_{i}$) in the
recursive procedure Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$) does
the following: takes the partition $\mathcal{Q}_{i}$ as input and returns an
$f$-factor $H$ such that $H/\mathcal{Q}_{i}$ is connected. This is achieved as
follows: for each spanning tree $T$ of $G/\mathcal{Q}_{i}$(recall definition),
the procedure Partition-Connector($\mathcal{Q}_{i}$) checks for an $f$-factor
$H^{\prime}_{i}$ containing $E(T)$. If there exists one, then it returns
$H^{\prime}_{i}$ and an empty graph otherwise. The correctness of procedure
Partition-Connector($\mathcal{Q}_{i}$) uses Lemma 5.4.

  3. (3)

A sequence of steps referred to as Next-
Factor($H_{i-1}$,$H^{\prime}_{i}$,$\mathcal{Q}_{i}$) in procedure
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$) computes $H_{i}$ from
$H_{i-1}$, $H^{\prime}_{i}$ and $\mathcal{Q}_{i}$ where $H^{\prime}_{i}$ is an
$f$-factor that connects $\mathcal{Q}_{i}$. To compute $H_{i}$ we color edges
in $H_{i-1}$ with color red and those in $H^{\prime}_{i}$ with color blue.
Then we consider the symmetric difference $S$ between $H_{i-1}$ and
$H^{\prime}_{i}$. Further we pick a set $\mathcal{S}$ of at most
$|\mathcal{Q}_{i}|-1$ minimal alternating circuits in $S$ such that
Switching($H_{i-1}$,$\mathcal{S}$) connects $\mathcal{Q}_{i}$ and this is the
required $H_{i}$. The correctness proof of the computation of $H_{i}$ from
$H_{i-1}$ and $H^{\prime}_{i}$ follows from Lemmas 5.3 and 5.5.

Using the above three subtasks in
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$), we ensure that at least
$f(v)-2(g(n)-1)$ edges incident on $v$ in $H_{i-1}$ is present in $H_{i}$ for
each $v$ in $V$. We use this constructive computation of $H_{i}$ from
$H_{i-1}$ to place a lower bound the size of the smallest part in
$\mathcal{Q}_{i}$ for every $i<k$. This gives an upper bound on the number of
parts in $\mathcal{Q}_{i}$ and this consequently bounds the number of
recursive calls made to Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$),
as $|\mathcal{Q}_{i}|>\mathcal{|}Q_{i-1}|$. These bounds are presented in
Lemmas 6.4 and 6.6. Based on our algorithm, we come up with a refined
characterization for graphs having a connected $f$-factor, which is proved in
Section 6.

######  Theorem 3.2.

Let $G$ be a graph and $f$ be a function where $f(v)\geq n/g(n)$ for every $v$
in $V$ and $g(n)$ is a function in $\mathcal{O}(\textnormal{polylog}($n$))$.
$G$ has a connected $f$-factor if and only if for each partition $\mathcal{Q}$
of size at most $g(n)$, there exists an $f$-factor that connects
$\mathcal{Q}$. Further, Algorithm 1 decides the existence of a connected
$f$-factor in an input graph $G$ in time $\tilde{\mathcal{O}}(n^{2g(n)})$.

##  4\. A spectrum of $f$ for which Connected $f$-factor is in
$\mathsf{NP}$-Intermediate under ETH

Let $\epsilon>0$ be a fixed number, and let $g(n)$ is in $\mathcal{O}((\log
n)^{1+\epsilon})$. We consider the case when $f(v)\geq n/g(n)$ for all $v$ in
$V$. In this section we show that for each such $f$, the connected $f$-factor
problem is in $\mathsf{NP}$-Intermediate under the ETH.
Connected $n/\mathcal{O}(\textnormal{polylog}($n$))$-factor is unlikely to be
$\mathsf{NP}$-Complete. Assume that the connected $f$-factor problem is
$\mathsf{NP}$-Complete for some $f$ satisfying the condition mentioned above.
This implies there exists a polynomial time reduction from 3-$\mathsf{SAT}$ to
the connected $f$-factor problem where the reduction algorithm outputs the
graph $G$ and the function $f$ on the vertex set, both of which are polynomial
in size of the instance of 3-$\mathsf{SAT}$. Further, we reiterate, $f$
satisfies the condition outlined above. From this reduction and the guarantee
on our Algorithm in Theorem 3.2 for connected $f$-factor, it follows that we
have an algorithm which decides 3-$\mathsf{SAT}$ that runs in time
$\tilde{\mathcal{O}}(n^{\textnormal{polylog}(n)})$, and this is impossible
under the ETH. The following lemma states this observation.

######  Lemma 4.1.

The connected $f$-factor problem where $f(v)\geq n/g(n)$ for every $v$ in $V$
and $g(n)$ in $\mathcal{O}((\log n)^{1+\epsilon})$ is not
$\mathsf{NP}$-Complete for any $\epsilon\geq 0$ unless the ETH is false.

Connected $(n/\mathcal{O}((\log n)^{1+\epsilon})$-factor is unlikely to be in
$\mathsf{P}$. Here we assume that $f(v)\geq n/g(n)$ where $g(n)$ is in
$\mathcal{O}((\log{n})^{1+\epsilon})$ for some $\epsilon>0$. Note that here
$\epsilon>0$ and in claim that it is unlikely to be $\mathsf{NP}$-Complete, we
had assumed that $\epsilon\geq 0$. We now present a sub-exponential time
reduction R from the Hamiltonian cycle problem to the connected $f$-factor
problem. The reduction algorithm takes $G$ on $N$ vertices and $\epsilon>0$ as
input and outputs a set $\mathcal{G}$ of $\mathcal{(}|V(G)|^{3})$ pairs. Each
pair in $\mathcal{G}$ is of the form $(G^{\prime},f)$ where $f$ is a function
and $G^{\prime}$ is a graph. The set $\mathcal{G}$ satisfies the following:

  1. (1)

For each pair $(G^{\prime},f)$ in $\mathcal{G}$, $G^{\prime}$ is a graph
having $n$ vertices and $f(v)\geq n/\log^{1+\epsilon}n$ for every $v$ in
$G^{\prime}$.

  2. (2)

$G$ has a Hamiltonian cycle if and only if there exists a pair
$(G^{\prime},f)$ in $\mathcal{G}$ such that $G^{\prime}$ has a connected
$f$-factor.

  3. (3)

For each $G^{\prime}$ output by R, the number of edges in $G^{\prime}$ is
$2^{o(N)}$ where $N$ is the number of vertices in $G$.

The reduction R is as follows-

  1. (1)

Compute $n=\lceil 2^{N^{1/(1+\epsilon)}}\rceil$ where $N=|V(G)|$.

  2. (2)

Construct an empty graph $G^{\prime}$ containing $n$ vertices.

  3. (3)

Define a partition $\mathcal{Q}$ of vertices in $G^{\prime}$ where each part
contains at least $\lceil\frac{n}{\log^{1+\epsilon}n}\rceil+1$ vertices and
$|\mathcal{Q}|=N-2$. The existence of partition $\mathcal{Q}$ is proved in
lemma 4.2.

  4. (4)

For each $Q$ in $\mathcal{Q}$, make $G^{\prime}[Q]$ a clique. For each $v\in
Q$, define $d_{G^{\prime}}(v)=|Q|-1$.

  5. (5)

Let $A$ be a set consisting of exactly one vertex from each $Q$ in
$\mathcal{Q}$, $|A|=N-2$.

  6. (6)

Let $f(v)=d_{G^{\prime}}(v)+2$ for each vertex $v$ in $A$ and
$f(v)=d_{G^{\prime}}(v)$ for each $v$ in $G^{\prime}\setminus A$.

  7. (7)

Let $u_{1}$ be a vertex in $G$.

  8. (8)

For each 4-vertex path $u_{0},u_{1},u_{2},u_{3}$ in $G$, do the following:

    1. (a)

Let $\sigma$ be a bijection from $V(G)\setminus\\{u_{1},u_{2}\\}$ to $A$.

    2. (b)

For each edge $\\{u,v\\}$ in $G\setminus\\{u_{1},u_{2}\\}$, add edge
$\\{\sigma(u),\sigma(v)\\}$ to $G^{\prime}$.//Make
$G\setminus\\{u_{1},u_{2}\\}$ isomorphic to $G^{\prime}[A]$ under $\sigma$

    3. (c)

Fix $f(\sigma(u_{0}))=d_{G^{\prime}}(v)+1$ and
$f(\sigma(u_{3}))=d_{G^{\prime}}(v)+1$. //For a connected $f$-factor
$H^{\prime}$ in $G^{\prime}$, the graph $H^{\prime}[A]$ is a spanning path
with $sigma(u_{0})$ and $sigma(u_{3})$ as end points

    4. (d)

Output $(G^{\prime},f)$.

    5. (e)

//resetting $G^{\prime}$ for the next iteration

    6. (f)

Remove all the edges in $G^{\prime}[A]$ from $G^{\prime}$.

    7. (g)

Fix $f(\sigma(u_{0}))=d_{G^{\prime}}(v)+2$ and
$f(\sigma(u_{3}))=d_{G^{\prime}}(v)+2$.

Observe that if the number of vertices $N$ in $G$ is sufficiently large
(depending on $\epsilon$), the total space required to hold $\mathcal{G}$
output by R is $2^{o(N)}$.

######  Lemma 4.2.

Let $m$ be an integer and let $k<\sqrt{m}$. Then $\lfloor{m}/{(\lceil
m/k\rceil+1})\rfloor\geq k-2$.

Proof in Appendix.
The following lemma proves the correctness of the reduction.

######  Lemma 4.3.

The graph $G$ has a Hamiltonian cycle $H$ if and only if R outputs a pair
$(G^{\prime},f)$ such that $G^{\prime}$ has a connected $f$-factor
$H^{\prime}$.

Proof in Appendix.
If we have a polynomial time algorithm for the connected $f$-factor problem
for a given constant $\epsilon>0$, then we test for the existence of a
connected $f$-factor of $G^{\prime}$ for each $(G^{\prime},f)$ in
$\mathcal{G}$. The size of the set $\mathcal{G}$ is $\mathcal{O}(N^{3})$ where
$N=|V(G)|$. Computation of each $G^{\prime}$ takes $2^{o(N)}$ time. Thus, in
time $2^{o(N)}$, we check for the existence of a pair $(G^{\prime},f)$ in
$\mathcal{G}$ such that $G^{\prime}$ has a connected $f$-factor.

######  Lemma 4.4.

Let $\epsilon>0$ and let $f(v)\geq n/g(n))$ for every $v$ in $V$ and $g(n)$ is
in $\mathcal{O}((\log{n})^{1+\epsilon})$. Then the connected $f$-factor
problem is not in $\mathsf{P}$unless the ETH is false.

From lemmas 4.1 and 4.4, we come up with the following theorem.

######  Theorem 4.5.

Let $G$ be a graph having $n$ vertices and $f$ be a function where $f(v)\geq
n/g(n)$ for each $v$ in $V$. For each $\epsilon>0$ and each $g(n)$ in
$\mathcal{O}((\log{n})^{1+\epsilon})$, the connected $f$-factor problem is in
$\mathsf{NP}$-Intermediate unless the ETH is false.

##  5\. Properties of alternating circuits and $f$-factors

To start with, we present properties of alternating circuits which we use
extensively. Alternating circuits are intricately related to $f$-factors as
they provide a way of moving from one $f$-factor to another. We present the
following lemmas from our previous work in [12] and the proofs of the lemmas
in this section, which are necessary are in the appendix.

######  Lemma 5.1.

Let $T$ be a graph in which each edge is assigned a color from the set
$\\{red,blue\\}$. Each component in $T$ is an alternating circuit if and only
if $d_{R}(v)=d_{B}(v)$ for every $v$ in $T$.

Consider two $f$-factors $H_{1}$ and $H_{2}$ of a graph $G$. If color the
edges in $H_{1}$ with color red and those in $H_{2}$ with color blue, then
each component in $H_{1}\bigtriangleup H_{2}$ is an alternating circuit. Note
that if two alternating circuits $T_{1}$ and $T_{2}$ have a vertex in common,
then $T_{1}\cup T_{2}$ is an alternating circuit.

######  Lemma 5.2.

Let $H$ and $H^{\prime}$ be two $f$-factors of $G$. If $T=H\bigtriangleup
H^{\prime}$ (symmetric difference of the edge sets) then $T$ is a switch on
both $H$ and $H^{\prime}$.

######  Lemma 5.3.

Let $H$ be a subgraph of $G$ and let $T$ be a switch on $H$. Assign color red
to edges in $T\cap H$ and blue to those in $T\setminus H$. If $T$ is a minimal
alternating circuit and $G^{\prime}=$Switching($H$,$T$), then $|N_{H}(v)\cap
N_{G^{\prime}}(v)|\geq d(v)-2$, for each $v$ in $V$.

######  Lemma 5.4.

Let $S\subseteq E(G)$. An $f$-factor $H$ containing all the edges in $S$, if
one exists, can be computed in polynomial time.

Decomposing an alternating circuit into minimal alternating circuits. In our
algorithm we repeatedly take an alternating circuit and decompose into a set
of minimal alternating circuits containing a given set of edges. The function
Min-AC-Set($U$,$S$) in [12] take an alternating circuit $U$ and a set of edges
$S\subseteq U$ as input and output a set $\mathbb{U}$ of edge disjoint minimal
alternating circuits each of which is present in $U$. Further, each edge in
$S$ is present in some minimal alternating circuit $C$ in $\mathbb{U}$. Min-
AC-Set($U$,$S$) identifies an alternating circuit $C$ having $d_{R}(v)$ and
$d_{B}(v)$ at most 2 and adds it to $\mathbb{U}$ only if some edge in $S$ is
present in $C$. Further it removes the identified $C$ from $U$. This step is
repeated until $U$ is empty. The crucial step in Min-AC-Set($U$,$S$) is to
find a minimal alternating circuit in $U$. This is presented in the recursive
Procedure Find-Min-AC($U$)(in Appendix).

######  Lemma 5.5.

The procedure Min-AC-Set($U$,$S$) outputs a set $\mathbb{U}$ of edge disjoint
minimal alternating circuits each of which has at least one edge from $S$.

##  6\. Algorithm for computing a Connected $f$-factor

In this section we complete the algorithm outlined in Section 3. The algorithm
takes an unweighted graph $G$ and a function $f$ as input and outputs a
connected $f$-factor of $G$ if it exists. When the function $f(v)\geq n/g(n)$
for each $v$ in $V$ and $g(n)$ is polylogarithmic in $n$, the algorithm runs
in time $\tilde{\mathcal{O}}(n^{2g(n)})$. We start with a justification of why
$g(n)$ being polylogarithmic in $n$ is crucial for our analysis.

######  Lemma 6.1.

Let $g$ be a function on the set of positive integers. Let there be a positive
constant $b$ such that for each positive integer $n$, $g(n)\leq b(\log
n)^{b}$. Then for each $n\geq n_{0}$, $2(g(n))^{4}$ is at most $n$ for a
sufficiently large constant $n_{0}$.

The proof of the above lemma is easy as $n/2b^{4}$ is asymptotically larger
than $(\log n)^{4b}$ for any constant $b$. Lemma 6.1 is crucial in the
analysis of our algorithm. Algorithm 1 processes the input graph based on $n$.
If $n$ is smaller than $n_{0}$, it exhaustively checks for a connected
$f$-factor. If $n$ is at least $n_{0}$, then by Lemma 6.1, $n\geq 2(g(n))^{4}$
and we use this to bound the running time of our algorithm.
Description of the Algorithm The idea is to start with an arbitrary $f$-factor
$H_{0}$ of $G$ and compute a connected $f$-factor using the template in
Section 3. We use a recursive subroutine
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$) which returns a connected
$f$-factor if it exists or it returns an empty graph otherwise.

1 Input:$G(V,E)$,$f$

2 Output:$G^{\prime}$, a connected $f$-factor of $G$ if exists, and outputs
failure otherwise.

3 if _$n\leq n_{0}$ _ then

4 exhaustively search for a connected $f$-factor.

5 Return the connected $f$-factor if it is found, else return failure.

6 end if

7 $H_{0}$=Tutte’s-Reduction($G$,$f$).

8 if _$H_{0}=empty$_ then

9 then exit reporting failure.

10 end if

11 if _$H_{0}$ is connected_ then

12 Output $H_{0}$ and exit.

13 end if

14 $\mathcal{Q}_{0}$=$\\{V(G)\\}$. // Initialize the root partition
$\mathcal{Q}_{0}$ with a single part $V(G)$

15 $G^{\prime}$=Restricted-$f$-Factor$(H_{0},\mathcal{Q}_{0})$.

16 if _$G^{\prime}$ is nonempty _ then

17 Output $G^{\prime}$ and exit.

18 end if

Output failure.

Algorithm 1 The Algorithm for deciding connected $f$-factor when $g(n)$ is in
$\mathcal{O}(\textnormal{polylog}($n$))$

The following lemma plays a critical role in the correctness of our subroutine
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$).

######  Lemma 6.2.

Let $G$ be a graph having a connected $f$-factor. Let $\mathcal{Q}$ be a
partition of the vertex set $V$. There exists a spanning tree $T$ of
$G/\mathcal{Q}$ and an $f$-factor $H$ of $G$ such that $E(T)\subseteq E(H)$.
Further given $T$, $H$ can be computed in polynomial time.

######  Proof 6.3.

Let $G^{\prime}$ be a connected $f$-factor of $G$. For any partition
$\mathcal{Q}$ of the vertex set, $G^{\prime}/\mathcal{Q}$ is connected.
Consider a spanning tree $T$ of $G^{\prime}/\mathcal{Q}$. Clearly, there
exists at least one $f$-factor $H$ containing $E(T)$ and hence $H/\mathcal{Q}$
is connected. Once we have $E(T)$, $H$ can be computed in polynomial time
using Lemma 5.4.

We now present the recursive procedure Restricted-$f$-Factor() which expands
the outline in Section 3.

1 Procedure  _Restricted- $f$-Factor(_$H_{i-1}$ ,$\mathcal{Q}_{i-1}$_)_

2

3 $\mathcal{Q}_{i}$=$empty$.

4 for _each $X\in\mathcal{Q}_{i-1}$_ do

5 $\mathcal{Q}_{1}$=$\mathcal{Q}_{i}\cup\\{Y|Y$ is vertex set of a maximal
component in $H[X]\\}$.

6

7 end for

8

9 if _$\mathcal{Q}_{i}=\mathcal{Q}_{i-1}$_ then

10 return $H_{i-1}$ and exit. // $H_{i-1}$ is a connected $f$-factor

11 end if

12 $G^{\prime}$=$empty$.

13 $H^{\prime}_{i}$=$empty$.

14 // BEGIN Partition-Connector($\mathcal{Q}_{i}$)

15 for _each spanning tree $T$ of $G/\mathcal{Q}_{i}$_ do

16 $T$=$T\setminus H_{i-1}$.// Ignore edges that are already there in
$H_{i-1}$

17 if _an $f$-factor $H^{\prime}_{i}$ containing $E(T)$ exists_ then

18 exit Loop 2.// $steps$ $12\ldots 18$

19 end if

20

21 end for

22 if _$H^{\prime}_{i}$ ==$empty$_ then

23 exit and return empty.// There does not exist an $f$-factor that connects
$\mathcal{Q}_{i}$

24 end if

25 // END Partition-Connector($\mathcal{Q}_{i}$)

26 // BEGIN Next-Factor($H_{i-1}$,$H^{\prime}_{i}$,$\mathcal{Q}_{i}$)

27 $S$=$E(H_{i-1})\bigtriangleup E(H^{\prime}_{i})$.

28 $\mathcal{S}$=$empty$.// Set of minimal alternating circuits containing
$E(T)$

29 for _each component $U\in S$_ do

30 $\mathcal{S}$=$\mathcal{S}\cup$Min-AC-Set($U$,$T$)

31 end for

32 $H_{i}=$Switching($H_{i-1}$,$\mathcal{S}$). // $H_{i}$ is an $f$-factor
containing $E(T)$

33 // END Next-Factor($H_{i-1}$,$H^{\prime}_{i}$,$\mathcal{Q}_{i}$)

34 $G^{\prime}$=Restricted-$f$-Factor($H_{i}$,$\mathcal{Q}_{i}$).

35 return $G^{\prime}$.

36

37

Algorithm 2 The procedure Restricted-$f$-Factor() recursively compute a
connected $f$-factor of $G$, if it exists.

We use the following lemma in arguing the correctness of our algorithm.

######  Lemma 6.4.

If $G$ has at least $2(g(n))^{4}$ vertices, then in each recursive call to
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$), the number of parts in
$\mathcal{Q}_{i-1}$ is at most $g(n)$.

######  Proof 6.5.

Consider the computation of $H_{i}$ from $H_{i-1}$ in the first call to the
subroutine with parameters $H_{0}$ and $\mathcal{Q}_{0}$ from Algorithm 1. In
each iteration of loop 2, the number of edges in $T$ is at most $g(n)-2$. This
is because the number of components in $H_{0}$ is at most $g(n)-1$. Consider
$\mathcal{S}$ computed in step 24. We color edges in $H_{i-1}\cap\mathcal{S}$
with color red and those in $H^{\prime}_{i}\cap\mathcal{S}$ with color blue.
From Lemma 5.5, minimality of each $s$ in $\mathcal{S}$ computed in step 27
and Lemma 5.3, $|N_{H_{i-1}}(v)\cap N_{H_{i}}(v)|$ is at least
$n/g(n)-2(g(n)-2)$ for each vertex $v$ in $V$.

Assume that there exists a recursive call in which the number of parts in
$\mathcal{Q}_{i-1}$ is more than $g(n)$. We prove that this contradicts our
premise that $G$ has at least $2(g(n))^{4}$ vertices. Let the pairs
$(H_{0},\mathcal{Q}_{0}),(H_{1},\mathcal{Q}_{1}),\ldots,(H_{k},\mathcal{Q}_{k}),\ldots$
be the sequence of arguments to
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$). Let the number of parts
in $\mathcal{Q}_{k}$ be larger than $g(n)$ and for each $0\leq i\leq k-1$,
$|\mathcal{Q}_{i}|\leq g(n)$. As discussed above, $k$ can not be $0$. Observe
that for each $1\leq i\leq k$, $|\mathcal{Q}_{i}|>|\mathcal{Q}_{i-1}|$ and
$|\mathcal{Q}_{0}|=1$. This implies $|\mathcal{Q}_{i}|\geq i+1$ for every $i$.
Thus the level number $k-1$ is at most $g(n)-1$ and hence $k$ is at most
$g(n)$. Let $T$ be a spanning tree in $G/\mathcal{Q}_{i}$ and let
$H^{\prime}_{i}$ be the $f$-factor in the $i$-th recursion that contains
$T$(connects $\mathcal{Q}_{i}$). Let $S$ be the symmetric difference
$E(H_{i-1})\bigtriangleup E(H^{\prime}_{i})$, and let $\mathcal{S}$ be the
subset of decomposition of $S$ into minimal alternating circuits which we use
for switching in step 29. For each $0\leq i\leq k-1$, $\mathcal{Q}_{i}$ has at
most $g(n)$ parts. The number of parts in $\mathcal{Q}_{k-1}$ computed in the
recursive call Restricted-$f$-Factor($H_{k-2}$,$\mathcal{Q}_{k-2}$) is at most
$g(n)$. This implies in each of those recursive calls
Restricted-$f$-Factor($H_{i}$,$\mathcal{Q}_{i}$) where $0\leq i\leq k-2$, the
number of edges in $T$ computed in step 13 is at most $g(n)-1$. Consequently,
from Lemma 5.5, the number of minimal alternating circuits in $\mathcal{S}$ is
at most $g(n)-1$ for each recursive call with parameters
($H_{i}$,$\mathcal{Q}_{i}$) for $0\leq i<k-1$. Thus, from Lemma 5.3, the size
of $\displaystyle\cap_{0\leq i\leq k-1}N_{H_{i}}(v)$ is at least
$n/g(n)-2(g(n)-1)(k-1)$. Further, $|N_{H_{0}}(v)\cap N_{H_{k-1}}(v)|\geq
n/g(n)-2(g(n)-1)(k-1)$ where $H_{k-1}$ computed at the end of the call
Restricted-$f$-Factor($H_{k-2}$,$\mathcal{Q}_{k-2}$). This means for each
vertex $v$ in $V$, at least $n/g(n)-2(g(n)-1)(k-1)$ edges incident on $v$ in
$H_{k-1}$ were also present in $H_{0}$. Since $k\leq g(n)$, we get the size of
$N_{H_{0}}(v)\cap N_{H_{k-1}}(v)$ to be at least $n/g(n)-2(g(n)-1)(g(n)-1)$.
Further, each part in $\mathcal{Q}_{k}$ computed in the call
Restricted-$f$-Factor($H_{k-1}$,$\mathcal{Q}_{k-1}$) has more than
$n/g(n)-2(g(n)-1)(g(n)-1)$ vertices. This implies that the total number of
vertices counted in the parts of $\mathcal{Q}_{k}$ is more than
$(g(n)+1)\cdot(n/g(n)-2(g(n)-1)(g(n)-1))$. Clearly, the total number of
vertices $n$ should be larger than $\frac{g(n)+1}{g(n)}(n-2(g(n))^{3})$. By
rearranging the terms we get $n<2(g(n))^{4}$. This contradicts our premise
that $G$ has at least $2(g(n))^{4}$ vertices. Therefore, our assumption that
$|\mathcal{Q}_{k}|>g(n)$ is wrong. Hence the lemma.

######  Lemma 6.6.

Let $n$ be at least $2(g(n))^{4}$. The number of times the subroutine
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-i}$) gets invoked recursively
is at most $g(n)-1$.

######  Proof 6.7.

This follows immediately from Lemma 6.4, as the number of parts in
$\mathcal{Q}_{i}$ is at most $g(n)$, and between two consecutive reclusive
calls to Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$), either a
connected $f$-factor is found or we have a $\mathcal{Q}_{i}$ larger than
$\mathcal{Q}_{i-1}$ to work with.

Rest of the section contains the proof of the results discussed in Section 3.

  * Proof of Running time in Theorem 3.2.

If $G$ has an $f$-factor, then step 7 of Algorithm 1 computes an arbitrary
$f$-factor $H_{0}$. The first call to
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$) is made with arguments
$H_{0}$ and $\mathcal{Q}_{0}=\\{V(G)\\}$. In the $i$-th recursive call: if
$\mathcal{Q}_{i}$ and $\mathcal{Q}_{i-1}$ are the same, then a connected
$f$-factor is found, and this check can be done in polynomial time, and the
correctness is by Fact 1. If there does not exist a $f$-factor
$H^{\prime}_{i}$ that connects $\mathcal{Q}_{i}$, then the algorithm exits at
this step. This check is done by loop 2, and since the number of parts is
upper bounded by $g(n)$, the time taken is at most $\binom{m}{g(n)-1}$, where
$m$ is the number of edges in $G$. This is the time taken to enumerate all
spanning trees $T$ of $G/\mathcal{Q}_{i}$ and to check if there is a
$f$-factor that contains the edges of $T$. Thus Algorithm 1 completes in time
$\tilde{\mathcal{O}}(n^{2g(n)})$. If $G$ has a connected $f$-factor, then in
at most $g(n)$-recursive calls, the
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$) will succeed due to
Theorem 3.1. Further, by the same theorem, if $G$ does not have a connected
$f$-factor, the procedure will terminate by identifying a partition
$\mathcal{Q}$ that cannot be connected by an $f$-factor of $G$. Hence the
theorem.

∎

  * Proof of Characterization in Theorem 3.2.

The forward direction of the proof is implied by Theorem 3.1 as a connected
$f$-factor connects any partition, independent of the size of the partition.
The reverse direction of the proof is from Algorithm 1. For each partition
$\mathcal{Q}$ of size at most $g(n)$, if there exists an $f$-factor that
connects $\mathcal{Q}$ then clearly the algorithm computes a connected
$f$-factor with in at most $g(n)-1$ recursions. ∎

##  7\. Computing a minimum weighted connected $f$-factor

In this section we consider a variant where the input graph $G$ has positive
weights on the edges, and the objective is to compute a minimum weighted
connected $f$-factor. We consider the case where $f(v)\geq n/g(n)$ for some
function $g(n)$ in $\mathcal{O}(\textnormal{polylog}($n$))$. We extend
Algorithm 1 to solve this minimization problem as follows-

  1. (1)

In step 7 of Algorithm 1, instead of initializing $H_{0}$ with an arbitrary
$f$-factor, we use Modified-Tutte’s-Reduction($G$,$f$) to initialize $H_{0}$
with a minimum weighted $f$-factor of $G$.

  2. (2)

Further in loop 2 in Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$),
$H^{\prime}_{i}$ is the minimum weighted $f$-factor that connects
$\mathcal{Q}_{i}$, if there exists one.

It is clear, from the arguments in Theorem 3.2, that these modifications still
guarantee that the output will be a connected $f$-factor if one exists, and we
have to show that the procedure computes an $f$-factor of minimum cost. We
refer to the above extension of
Restricted-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$) as Restricted-
Min-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$).

To understand the behavior of the modification, recall that $H_{0}$ is a
minimum weight $f$-factor of $G$. Secondly, let $H^{\prime}_{i}$ be a minimum
weighted $f$-factor that connects $\mathcal{Q}_{i}$ identified in the $i$-th
recursion. The procedure builds $H_{i}$ from $H_{i-1}$ and $H^{\prime}_{i}$.
The following lemma is used in bounding the cost of $H_{i}$ in the $i$-th
recursive call to Restricted-Min-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$).

######  Theorem 7.1.

Let $H$ be a minimum weighted $f$-factor of $G$ and let $T\subseteq
E(G)\setminus E(H)$. Let $H^{\prime}$ be a minimum weighted $f$-factor among
all $f$-factors containing $T$. Let $S=E(H)\bigtriangleup E(H^{\prime})$ and
let the edges of $S\cap H$ be colored red and the edges of $S\cap H^{\prime}$
be colored blue. Let $\mathcal{S}$ be a partition of $E(S)$ into minimal
alternating circuits. The following are true:

  1. (1)

For each $s$ in $\mathcal{S}$, if $W(s)>0$ then $s\cap T\neq\phi$.

  2. (2)

For any $\mathcal{S^{\prime}}\subseteq\mathcal{S}$ satisfying
$T\subseteq\displaystyle\cup_{s\in\mathcal{S^{\prime}}}s$,
Switching($H$,$\mathcal{T^{\prime}}$) is an $f$-factor of weight exactly equal
to $w(H^{\prime})$.

The proof of Theorem 7.1, which is also in our recent paper [12], is in the
Appendix. The following lemma highlights an invariant which plays a critical
role in arguing the correctness of the subroutine Restricted-Min-$f$-Factor().

######  Lemma 7.2.

Consider the sequence of arguments
$(H_{0},\mathcal{Q}_{0}),(H_{1},\mathcal{Q}_{1}),\ldots,(H_{k},\mathcal{Q}_{k})$
to the procedure Restricted-Min-$f$-Factor(). Let the input graph $G$ has a
connected $f$-factor. The cost of $H_{k}$ is equal to that of $H^{\prime}_{k}$
in the $k$-th recursive call to Restricted-Min-$f$-Factor().

######  Proof 7.3.

For $k=1$, Theorem 7.1 directly completes the proof. For $k>1$, we prove by
induction on the recursion level $i$. We assume the claim to be true for $k-1$
and we show this to be true for $k$. We use $\mathcal{S}_{i}$ and $S_{i}$ to
address the value of variables $\mathcal{S}$ and $S$ respectively, computed in
step 28 of the function Restricted-
Min-$f$-Factor($H_{i-1}$,$\mathcal{Q}_{i-1}$). Assume that there exists a
minimal alternating circuit $s$ in $H^{\prime}_{k}\bigtriangleup H_{k}$ which
is a switch on $H_{k}$ of negative weight.
We now derive a contradiction to the optimality of $H^{\prime}_{k-1}$. Note
that $s$ is edge disjoint from
$\bigcup_{s^{\prime}\in\mathcal{S}_{k}}E(s^{\prime})$. This is because,
$H^{\prime}_{k}\bigtriangleup H_{k}$ is
$S_{k}\setminus\mathcal{\bigcup}_{s^{\prime}\in\mathcal{S}_{k}}E(s^{\prime})$.
Thus $s$ is a switch on Switching($H_{k}$,$\mathcal{S}_{k}$) of negative
weight. Further, Switching($H_{k}$,$\mathcal{S}_{k}$) is $H_{k-1}$. By
induction, $H_{k-1}$ is of weight $H^{\prime}_{k-1}$ computed in the previous
level of recursion. From the algorithm, Switching($H_{k-1}$,$s$) connects
$\mathcal{Q}_{k}$. From the fact that $\mathcal{Q}_{k}$ is a refinement of
$\mathcal{Q}_{k-1}$, it follows that Switching($H_{k-1}$,$s$) is an $f$-factor
that connects $\mathcal{Q}_{k-1}$ and is of weight less than that of
$H^{\prime}_{k-1}$, and this contradicts the optimality of $H^{\prime}_{k-1}$.
We now assume that there does not exist a minimal alternating circuit $s$ of
negative weight in $H_{k}\bigtriangleup H^{\prime}_{k}$ which is a switch on
$H_{k}$. We show that such a switch $s$ of positive weight also cannot occur.
Note that such a positive weighted switch $s$ is a switch on $H^{\prime}_{k}$
of negative cost. As described above, $s$ is edge disjoint from
$\bigcup_{s^{\prime}\in\mathcal{S}_{k}}E(s^{\prime})$. From the algorithm,
Switching($H^{\prime}_{k}$,$s$) connects $\mathcal{Q}_{k}$ and is of lower
cost than $H^{\prime}_{k}$. Thus, We have a contradiction to the optimality of
$H^{\prime}_{k}$. Therefore, the cost of $H_{k}$ is equal to that of
$H^{\prime}_{k}$ in the $k$-th recursive call to Restricted-Min-$f$-Factor().

## References

  * [1] R.P Anstee.  An algorithmic proof of tutte’s f-factor theorem.  Journal of Algorithms, 6(1):112 – 131, 1985.
  * [2] F. Cheah and D. G. Corneil.  The complexity of regular subgraph recognition.  Discrete Applied Mathematics, 27(1-2):59–68, 1990.
  * [3] Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N.S. Narayanaswamy, and C.S. Rahul.  Approximability of connected factors.  In Christos Kaklamanis and Kirk Pruhs, editors, Approximation and Online Algorithms, volume 8447 of Lecture Notes in Computer Science, pages 120–131. Springer International Publishing, 2014.
  * [4] G. Cornuéjols.  General factors of graphs.  Journal of Combinatorial Theory, Series B, 45(2):185–198, 1988\.
  * [5] G. A. Dirac.  Some theorems on abstract graphs.  Proceedings of the London Mathematical Society, s3-2(1):69–81, 1952\.
  * [6] J. Edmonds.  Maximum matching and a polyhedron with $0,1$ vertices.  J. of Research of the National Bureau of Standards, 69 B:125–130, 1965.
  * [7] J. Edmonds.  Paths, trees, and flowers.  Canadian Journal of mathematics, 17(3):449–467, 1965.
  * [8] T. Iida and T. Nishimura.  An ore-type condition for the existence of k-factors in graphs.  Graphs and Combinatorics, 7(4):353–361, 1991.
  * [9] Russell Impagliazzo and Ramamohan Paturi.  Complexity of k-sat.  In Computational Complexity, 1999. Proceedings. Fourteenth Annual IEEE Conference on, pages 237–240. IEEE, 1999.
  * [10] Peter Jonsson, Victor Lagerkvist, and Gustav Nordh.  Constructing np-intermediate problems by blowing holes with parameters of various properties.  Theoretical Computer Science, 581(0):67 – 82, 2015.
  * [11] Tomáš Kaiser.  A short proof of the tree-packing theorem.  Discrete Mathematics, 312(10):1689–1691, 2012.
  * [12] NS Narayanaswamy and CS Rahul.  Approximation and exact algorithms for special cases of connected f-factors.  In Computer Science–Theory and Applications, pages 350–363. Springer, 2015.
  * [13] Oystein Ore.  Note on hamilton circuits.  American Mathematical Monthly, pages 55–55, 1960.
  * [14] M. D. Plummer.  Graph factors and factorization: 1985–2003: a survey.  Discrete Mathematics, 307(7):791–821, 2007.
  * [15] T. Tokuda.  Connected [a,b]-factors in k1,n-free graphs containing an [a,b]-factor.  Discrete Mathematics, 207(1–3):293 – 298, 1999.
  * [16] Alan Tucker.  A new applicable proof of the euler circuit theorem.  American Mathematical Monthly, pages 638–640, 1976.
  * [17] W. T. Tutte.  The factors of graphs.  Canadian Journal of Mathematics, 4(3):314–328, 1952.
  * [18] W. T. Tutte.  A short proof of the factor theorem for finite graphs.  Canadian Journal of Mathematics, 6(1954):347–352, 1954.
  * [19] Preben Dahl Vestergaard and Mekkia Kouider.  Connected factors in graphs - a survey.  Graphs and Combinatorics, 21(1):1–26, 2005.
  * [20] D. B. West.  Introduction to Graph Theory.  Prentice Hall, 2001.

Appendix

  * Proof of Lemma 4.2.

Let $l=\lceil m/k\rceil+1$. Then $(l-2)k\leq m$. From $k<\sqrt{m}$,
$(l-2)\geq(k-2)$. We have,

$\displaystyle(l-2)k$ $\displaystyle\leq$ $\displaystyle m$
$\displaystyle(l-2)k-2(l-2)+2(k-2)$ $\displaystyle\leq$ $\displaystyle m$
$\displaystyle l(k-2)$ $\displaystyle\leq$ $\displaystyle m$

∎

  * Proof of Lemma 4.3.

Consider the vertex $u_{1}$ selected in step 7 of R. Corresponding to each
Hamiltonian cycle $H$ in $G$ there exists a unique 4-vertex path
$u_{0},u_{1},u_{2},u_{3}$ in $G$ and an associated iteration of step 8. Note
that $H\setminus\\{u_{1},u_{2}\\}$ is a path $L$ of length $N-2$ whose end
vertices are $u_{0}$ and $u_{3}$. We have a corresponding spanning path
$L^{\prime}$ of length $N-2$ in $G^{\prime}[A]$. Removing all the edges in
$G^{\prime}[A]\setminus L^{\prime}$ from $G^{\prime}[A]$ gives a connected
$f$-factor $H^{\prime}$ of $G^{\prime}$. Conversely, given a connected
$f$-factor $H^{\prime}$, we pick the edge $\\{B^{-1}(u),B^{-1}(v)\\}$ for each
edge $\\{u,v\\}$ in $H^{\prime}[{A}]$. This gives a path $L$ of length $N-2$
whose end vertices are some $u_{0}$ and $u_{3}$. From the reduction algorithm,
there exists another path $u_{0},u_{1},u_{2},u_{3}$ where $u_{1}$ and $u_{2}$
are the vertices that are not present in $V(L)$ and we have a Hamiltonian
cycle in $G$. ∎

  * Proof of Lemma 5.1.

In the forward direction, consider a component $C$ in $T$. Since there is an
Eulerian tour in $C$ in which consecutive edges are of different colors, it
follows that $d_{R}(v)=d_{B}(v)$ for all $v$ in $T$. In the reverse direction,
let $d_{R}(v)=d_{B}(v)$ for all $v$ in $T$. To complete the proof, we point to
an exercise in [20, exercise 1.2.35] which considers the formulation of
Tucker’s algorithm for computing an Eulerian circuit in [16]. First, at each
vertex $v$ in a component $C$ in $T$, we pair each red edge incident on $v$ to
a distinct blue edge incident on $v$. Since $d_{R}(v)=d_{B}(v)$, such a
pairing is guaranteed to exist. Secondly, using this pairing, the required
alternating circuit is the Eulerian circuit constructed by Tucker’s algorithm.
Hence the lemma. ∎

  * Proof of Lemma 5.3.

Since $T$ is minimal, by definition, we know that $d_{R}(v)=d_{B}(v)$ for each
$v$ in $V$. Consequently, not more than 2 edges incident on a vertex will be
removed from $H$ as a result of applying Switching($H$,$T$). Therefore, the
number of common edges incident on $v$ in both $G^{\prime}$ and $H$ is at
least $d(v)-2$. ∎

  * Proof of Lemma 5.4.

Observe that removing the set of edges $S$ from an $f$-factor $H$ containing
$S$, reduces the degree of each vertex $v$ in $H$ by $|\\{(v,u)\in S\\}|$.
This is exactly an $f^{\prime}$-factor of $G(V,E\setminus S)$ where
$f^{\prime}(v)=f(v)-|\\{(v,u)\in S\\}|$, for each $v$ in $V$. Computing
$f^{\prime}$ and then computing an $f^{\prime}$-factor $H^{\prime}$ of
$G(V,E\setminus S)$ is easy. Recall that in polynomial time we can compute an
$f^{\prime}$-factor, if one exists, see West [20]. Further adding the edges in
$S$ to $H^{\prime}$ gives an $f$-factor $H$ of $G$ containing $S$. ∎

  * Proof of Lemma 6.2.

Let $G^{\prime}$ be a connected $f$-factor of $G$. For any partition
$\mathcal{Q}$ of the vertex set, from Theorem 3.1, $G^{\prime}/\mathcal{Q}$ is
connected. Consider a spanning tree $T$ of $G^{\prime}/\mathcal{Q}$. Clearly,
there exists at least one $f$-factor $H$ containing $E(T)$ and hence
$H/\mathcal{Q}$ is connected. Once we have $E(T)$, $H$ can be computed in
polynomial time using Lemma 5.4. ∎

  * Proof of Theorem 7.1.

For any minimal alternating circuit $t$ which is a switch on $H$, recall that
$W(t)$, the weight of $t$, is $w($Switching($H$,$t$)$)-w(H)$. Since $H$ is
optimum, for each $t$ in $\mathbb{T}$, $W(t)=w($Switching($H$,$t$)$)-w(H)\geq
0$. Suppose there exists a minimal alternating circuit $t$ in $\mathbb{T}$
such that $W(t)>0$, and $t$ does not contain any of the edges in $S$. Let us
consider $T^{\prime}=T\setminus t$, that is $T^{\prime}$ is an alternating
circuit obtained by removing the edges of $t$ from $T$, then
$W(T^{\prime})=W(T)-W(t)$. Then Switching($H$,$T^{\prime}$) is an $f$-factor
containing $S$, and
$w($Switching($H$,$T^{\prime}$)$)=w(H)+W(T^{\prime})=w(H)+W(T)-W(t)=w(H^{\prime})-W(t)<w(H^{\prime})$.
This contradicts the optimality of $H^{\prime}$. Therefore, $t\cap S\neq\phi$.
This implies for any subset $\mathbb{T^{\prime}}\subseteq\mathbb{T}$ such that
$S\subseteq\displaystyle\bigcup_{t\in\mathbb{T^{\prime}}}E(t)$,
$w($Switching($H$,$\mathbb{T^{\prime}}$)$)=w(H^{\prime})$. ∎

1 Procedure  _Find-Min-AC(_$U$_)_

2 if _$d_{R}(u)=d_{B}(u)\leq 2$ for each $u$ in $U$._ then

3 Exit and return $U$. // $U$ is a minimal alternating circuit

4 end if

5 For each $u$ in $U$, pair each blue edge incident on $u$ to a distinct red
edge incident on $u$.

6 Run Tucker’s algorithm [20, exercise 1.2.35] on $U$ using the pairing
defined in the previous step to get an Euler tour $\mathcal{T}$ in which
consecutive edges are of different colors.

7 Let $v$ be a vertex with $d_{R}(v)>2$ in $U$.// Such a $v$ exists in $U$

8 Start the tour $\mathcal{T}$ from $v$ and let $e_{1}$ be the edge through
which $\mathcal{T}$ leaves $v$ for the first time and let $e_{2}$ be the edge
through which $\mathcal{T}$ makes the first return to $v$. Let $e_{3}$ be the
edge through which $\mathcal{T}$ continues the tour and let $e_{4}$ be the
edge through which $\mathcal{T}$ makes the next return to $v$

9 if _$color(e_{2})\neq color(e_{1})$_ then

10 $U^{\prime}=v,e_{1},\ldots,e_{2},v$.

11 else if _$color(e_{4})\neq color(e_{3})$_ then

12 $U^{\prime}=v,e_{3},\ldots,e_{4},v$.

13 else

14 $U^{\prime}=v,e_{1},\ldots,e_{4},v$.// $color(e_{1})\neq color(e_{4})$

15 end if

16 end if

17 end if

18 Return Find-Min-AC($U^{\prime}$).

19

Algorithm 3 The procedure Find-Min-AC($U$) returns a minimal alternating
circuit in $U$


Proton Penetration Efficiency
over a High Altitude Observatory in Mexico

S. Miyake1, T. Koi2, Y. Muraki3$\star$, Y. Matsubara3, S. Masuda3, P.
Miranda4, T. Naito5, E. Ortiz6, A. Oshima2, T. Sakai7, T. Sako8, S. Shibata2,
H. Takamaru2, M. Tokumaru3 and J. F. Valdés-Galicia9

1 Ibaragi National College of Technology, Hitachinaka, Ibaraki 312-8508, Japan

2 Engineering Science laboratory, Chubu University, Kasugai, Aichi 487-0027,
Japan

3 Institute for Space, Earth and Environment, Nagoya University, Nagoya
464-8601, Japan

4 Instituto de Investigaciones Fisicas, UMSA, La Paz, Bolivia

5 Information Science laboratory, Yamanashi Gakuin University, Kofu 400-8375,
Japan

6 Escuela Nacional de Ciencias de la Terra, UNAM, Ciudad Mexico 55010, Mexico

7 Physical Science laboratory, Nihon University, Narashino, Chiba 275-0006,
Japan

8 Institute for Cosmic Ray Research, The University of Tokyo, Chiba 277-8582,
Japan

9 Instituto de Geofisica, UNAM, 04510, Mexico D.F., Mexico

*<EMAIL_ADDRESS>
21st International Symposium on Very High Energy Cosmic Ray Interactions
(ISVHE- CRI 2022)
Online, 23-27 May 2022 10.21468/SciPostPhysProc.?

## Abstract

In association with a large solar flare on November 7, 2004, the solar neutron
detectors located at Mt. Chacaltaya (5,250 m) in Bolivia and Mt. Sierra Negra
(4,600 m) in Mexico recorded very interesting events. In order to explain
these events, we have performed a calculation solving the equation of motion
of anti-protons inside the magnetosphere. Based on these results, the Mt.
Chacaltaya event may be explained by the detection of solar neutrons, while
the Mt. Sierra Negra event may be explained by the first detection of very
high energy solar neutron decay protons (SNDPs) around 6 GeV.

##  1 Introduction

An interesting event was registered in association with the large solar flare
on November 7, 2004 by the high altitude solar neutron detectors located at
Mt. Chacaltaya in Bolivia and Mt. Sierra Negra in Mexico [1],[2]. The data are
shown in bf Figure 1 and bf Figure 2 respectively. Counting rate excesses in
both detectors started at the same time around 15:50 UT, however clear
differences were observed in the duration of the respective events. The
Chacaltaya event lasted for 20 minutes, while the Sierra Negra event continued
for 78 minutes. The signal of the Chacaltaya event may be explained by the
detection of solar neutrons. These neutrons were produced at 15:47 UT on the
solar surface instantaneously with the increase of X-ray intensity.

Figure 1: The 5-minute value of the counting rate of the solar neutron
detector located at Mt. Chacaltaya (5,250 m). The first peak at the local time
9 am corresponds to the particle current along the IMF line, the second peak
at 12 LT (the green arrow) was produced by solar neutrons, and the third peak
around 14:30 LT corresponds to the arrival of the CME to the Earth. The
threshold of this channel corresponds to the particles with energy higher than
40 MeV. The flare start time (15:42 UT) is shown by the dotted line. Figure 2:
The 5-minute value of the anti-counter and the lowest proton-neutron channel
(S1) of the Mt. Sierra Negra solar neutron telescope on November 7th of 2004.
The horizontal green line indicates the time span when the excess was observed
($\sim$ 78 minutes).

If the Sierra Negra event was produced by solar neutrons, the excess should
not continue after 25 minutes, since the threshold energy of one of the
channels of the detector (S1) was set at $>$ 30 MeV. Therefore, we have
assumed that the excess of the Sierra Negra detector may be explained by the
detection of Solar Neutron Decay Protons (SNDPs) [3, 4].

If the observed excess counts are really produced by protons, we must show how
they can arrive at Mt. Sierra Negra, passing through the magnetosphere. The
cutoff rigidity of the magnetic latitude of Mexico was originally calculated
as 8 GV [5]. However, an early work by Smart, Shea, and Flückiger [6] suggests
a possibility that low energy protons less than the rigidity of 8 GV could
penetrate into the magnetosphere and arrive over the atmosphere of Mt. Sierra
Negra [7, 8]. Therefore, we estimate the detection efficiency of low energy
protons in the energy range between 4.5 GeV and 20 GeV.

In the next section, we describe details of the calculation and present the
results. Then we compare the results of the calculation with the two
experimental results. We examine whether both events are reasonably explained
by the hypothesis of Solar Neutron Decay Protons.

##  2 Calculation Method and Results

Method: We have injected anti-protons from 20 km above Mt. Sierra Negra. Anti-
protons were emitted every one degree in the north-south direction and the
east-west direction independently. Therefore for one fixed energy of anti-
protons, 32,761 ($181\times 181$) trajectories were examined. The trajectory
of each anti-proton was followed by solving the equation of motion using the
Runge-Kutta-Gill method until they arrive at the magnetopause at $8\,R_{\rm
E}$ (allowed) [9].

Of course some trajectories do not reach at $8\,R_{\rm E}$. Then they were
counted as the forbidden trajectories for proton arrivals. The initial energy
of anti-protons was examined in the energy range between 4.5 GeV and 20 GeV.
In the present calculation, the distance from the Earth center to the head of
the magnetosphere (i.e. magnetopause) is approximated by $8\,R_{\rm E}$ and
examined whether or not anti-protons arrived there. The SNDPs are expected to
come from the day side, so present approximation may be enough for this study.

Results: We found that quite low energy anti-protons, less than 8 GeV, arrived
at the magnetopause as predicted by the earlier work [6]. The proton
penetration probability from all directions at 20 km above Mt. Sierra Negra is
presented by open boxes in Figure 3, while the arrival probability from the
day side ($X>0$) is given by open triangles.

Figure 3: Proton penetration rate is shown as a function of the incident
energy. The open box presents the protons coming into the top of the
atmosphere of Mt. Sierra Negra from all directions. The open triangles
represent protons arriving from the day side. These data are normalized by the
shot number, 32,761 examples. On the other hand, the proton rate entering over
the top of the atmosphere with the incident angle less than 20 degrees is
shown by closed circles. The protons rate coming at the top of the atmosphere
with an incident angle between 20-40 degrees are shown by open circles.

We also take into account the crossing angle between $X$-axis of GSE
coordinate and the momentum (${\bf P}$) of SNDPs. Taking into account the
entrance of charged particles along the IMF direction
(${45}^{\circ}\sim{60}^{\circ}$), the anti-protons to satisfy the two
conditions of $P_{X}>0$ and $\tan^{-1}{(P_{X}/P_{Y})}$ larger than
${45}^{\circ}$ were finally selected. (In other words, the momentum region of
$P_{Y}<P_{X}$ is selected.) The results are shown in Figure 4 on the
$P_{X}-P_{Y}$ plane and $P_{Y}-P_{Z}$ plane of the GSE coordinate
respectively. We require further condition; the incident angle to the
atmosphere of the incident protons is less than $40^{\circ}$. All points
plotted in Figure 4 satisfy these conditions.

Figure 4: The momentum distribution of anti-protons arrived at 8$R_{E}$ is
shown on $P_{X}-P_{Y}$ plane (left) and $P_{Z}-P_{Y}$ plane (right)
respectively. Here the positive $P_{Y}$ is defined to the eastward, while
$P_{Z}$ positive vector points the northward. The $P_{X}$ axis indicates the
solar direction. The IMF direction (${56}^{\circ}\sim{60}^{\circ}$) is shown
by the arrow and by the $\oplus$ mark in the plots respectively.

Furthermore, we take into account another factor; proton attenuation in the
atmosphere. When protons enter into the air vertically, the survival
probability of proton signal is larger than the arrivals from large zenith
angles. The value is estimated as to be approximately 0.4 for neutrons with
vertical entrance ($\theta<20^{\circ}$) and 0.2 for the entrance with
$40^{\circ}$ respectively. Those results were obtained by using the GEANT4
simulation. Details are given in Supplemmentary Information (S1) [arXiv].

##  3 Boosting factor and Reduction factor

Boosting factor: Figure 5 presents the arrival point of the anti-protons at 8
$R_{E}$. Figure 5 tells us another information. The acceptance area of the
interplanetary protons by the magnetopause does not cover all area of the
magnetopause (not circle as in Figure 5) but the acceptable area is limited
within the rectangular area. Thus total area of acceptance of the magnetopause
for receiving the SNDPs is estimated as to be $1\times{10}^{15}\,{\rm m^{2}}$.
The decay factor of neutrons with the energy of 6 GeV during the flight in the
distance of ${\it l}\sim{\rm 0.067\,au}$, is estimated as 0.0047. More details
are given in Supplementary Information 2 and 3 (S2, S3) [arXiv].

Figure 5: The arrival map of anti-protons of 6 GeV at 8 $R_{\rm E}$ on the
$X-$Y plane, while the right side plot shows the distribution on the $Y-Z$
plane. The $Z$ axis corresponds to the north-south direction, while $X$-axis
directs toward the Sun. Here the equivalent incident angle of protons to the
atmosphere is selected less than 40 degrees. The number of the data points is
126, however when we require a condition of Vy $<$ 0, this number is reduced
to 46.

After we apply the decay factor to the above area, the effective decay area
for accepting the SNDP signals around 6 GeV may be evaluated as to be
$4.7\times{10}^{12}\,{\rm m^{2}}$. The detector areas at Mt. Chacaltaya and
Mt. Sierra Negra are only $4\,{\rm m^{2}}$. Therefore, in comparison with
these small detector areas, a huge collecting area will be expected according
to our estimation that may intensify very weak signal of high energy neutrons.
Here let us call the effect as a Horn effect. Details are also described in
(S3) [arXiv].

Reduction factor: Assume that one high energy neutron decay proton is produced
in a unit long volume in the space (1 SNDP/($\ell\cdot{\rm m^{2}}$)), then
enormous amount of protons will be produced. (Let us imagine a cylinder space
with the base of $1\,{\rm m^{2}}$.) According to the above estimate, the
number of protons must be of the order of $4.7\times{10}^{12}$. But not all of
them can enter into the magnetosphere. The Earth has a capability to protect
“cosmic radiation” through the double gates; (a) by the absorption in the air
and (b) by the rejection with the magnetic field. By the former process of
(a), the flux of incident protons will be reduced by an order of
$0.1\,\sim\,0.4$ depending on the incident angle to the atmosphere (see S1),
while by the latter process of (b), incoming protons will be rejected by the
condition of, i.e., the incoming proton trajectory must be continiously
connected with the trajectory inside the magnetosphere.

As is shown in S1, the reduction factor by the absorption in the air depends
on the incident angle. In case protons enter within $40^{\circ}$, the
candidates of the well connected trajectory may be reduced to 46 among the
32,761 simulated trajectories as shown in Figures 4 and 5. Thus, the entrance
probability will be reduced to be less than $1.4\times{10}^{-3}$. If we
require the entrance condition of protons into the air less than $20^{\circ}$,
only 10 events are left.

The momentum vector of the anti-protons must match with the momentum vector of
protons arriving from the outside of the magnetosphere. As shown in Figure 4,
the matching probability of the two tracks is very few and actually no optimum
vector is found in the $P_{X}-P_{Y}$ plane of Figure 4 that matches with the
IMF direction. Therefore, we postultate here the number of matching trajectory
is less than one. Then actual rejection factor by above condition reduces the
acceptable flux to be less than $3.1\times{10}^{-5}$ (= 1/32,761). We should
collect more samples of the simulation around the allowed condition region to
get a finite number.

In addition, we require another condition of the smooth connection to the
momentume vector in the $P_{Z}-P_{Y}$ plane, Because protons will make gyro-
motion along the IMF direction. The momentum vector of the $Z$-direction
varies to the north-south direction. Details are given in Supplementary
Information (S4) [arXiv]. As a result, the total reduction factor can be
estimated as to be $9.6\times{10}^{-10}$ ($=3.1\times{10}^{-5}\times
3.1\times{10}^{-5}\times 1.4{10}^{-3}$). Therefore when we multiply this
reduction factor to the boositing fcator, we may get the “effective” boosting
factor of SNDPs as to be 450 ($=9.6\times{10}^{-10}\times
4.7\times{10}^{12}$).

In summary, the detection efficiency of SNDPs can be described by the
production of the two factors; the entrance probability of the SNDPs into the
magnetosphere from the interplanetary space by the attenuation of the SNDPs
inside the atmosphere.

##  4 Application of Results to Actual Data

Let us compare our prediction with the observed results. In this chapter, we
examine whether current estimation may explain the observed results.

From the observed data of Mt. Chacaltaya, the neutron intensity is estimated
as $1.5\times{10}^{6}/{\rm m^{2}}$ at 100 MeV and $3,000/{\rm m^{2}}$ at 1,000
MeV (1 GeV) respectively. These intensities were already converted into the
flux at the top of the atmosphere, taking into account the attenuation in the
atmosphere. However the Chacaltaya detector did not measure the high energy
region beyond 1 GeV. Therefore, we estimate the flux at 6 GeV by extending the
Chacaltaya spectrum into high energies. We estimate the flux to the three
cases of the spectra beyond 1 GeV, assuming the integral spectrum of the power
law as $E_{n}^{-\gamma}$, with the power index of $\gamma$. Case (1) simple
extension from 1 to 10 GeV with $\gamma=2.7$, Case (2) moderate case;
$\gamma=3.7$, and Case (3) Soft case; $\gamma=4.7$. Then we may estimate the
probable flux at 6 GeV for Case (1) = $23.7/{\rm m^{2}}$, Case (2) = $4.0/{\rm
m^{2}}$, and Case (3) = $0.66/{\rm m^{2}}$ respectively. See also
Supplementary Information (S5) [arXiv].

Now we compare the extended flux of neutrons at 6 GeV with the flux of the
SNDPs observed at Mt. Sierra Negra. From the actual data of the S1 channel,
the total flux of SNDPs may be estimated as $(45,000\pm 900)/{\rm m^{2}}$ or
the first one-minute value may be deduced as $(360\pm 125)/({\rm m^{2}\cdot
min.})$. The latter flux may correspond to the observed events in early time.
They were the decay product of neutrons with the energy greater than 6 GeV
between 0.934 au and 1.0 au ($\approx$ 0.066 au).

Then we find that the observed one-minute value of Mt. Sierra Negra is
14$\sim$ 1,130 times higher than the extended flux of Chacaltaya. Taking into
account present calculation of the boosting factor intensified by $\sim$ 450
times, the observed results could fairly well reproduce the experimental
result. The expected boosting factor can explain actual observed data.

## Acknowledgements

The authors acknowledge the staffs of Mt. Chacaltaya cosmic ray observatory
and Mt. Sierra Negra observatory for keeping the detectors in good condition.
This event was re-analyzed, being inspired after a lecture by Prof. Sunil
Gupta and Dr. Pravata Mohanty when they visited Nagoya University in February
2020.

## References

  * [1] Y. Muraki et al., Solar Neutron Decay Protons observed on November 7, 2004, Proceeding of ICRC2021 (Berlin), PoS 1264 (2021), https://pos.sissa.it/395/1264/pdf.
  * [2] Y. Muraki et al., Solar Neutron Decay Protons observed on November 7, 2001, arXiv:2012.15623 (astro-ph.SR) (2020). http://arxiv.org/abs/2012.15623
  * [3] P. Evenson et al, Protons from the Decay of Solar Flare Neutrons, Ap. J. 274, 875 (1983), https://adsabs.harvard.edu/pdf/1983ApJ...274..875E.
  * [4] W. Dröge, D. Ruffolo, and Klecker, Observation of Electrons from the Decay of Solar Flare Neutrons, Ap. J. 464L, 87 (1996), https://adsabs.harvard.edu/full/1996ApJ...464L..87D.
  * [5] C. Störmer, The Polar Aurora, The Quarterly Journal of The Royal Meteological Society 82, 115 (1956), https://doi.org/10.1002/qj.49708235123.
  * [6] D. F. Smart, M.A. Shea, and E. O. Flückiger, Magnetospheric Models and Trajectory Computations, Space Science Review 93, 305 (2000), doi:10.1023/A:1026556831199.
  * [7] B. V. Cárdenas and J. F. Valdés-Galicia, Identification of high energy solar particle signals on the Mexico City Neutron Monitor database, Advances in Space Research 49, 1593 (2012), https://doi.org/10.1016/j.asr.2012.02.016.
  * [8] L. X. González et al., Re-Evaluation of the Neutron emission from the Solar flare of 2005 September 7, detected by the Solar Neutron Telescope at Sierra Negra, Astrophys. J. 814, 136 (2015), https://doi.org/10.1088/0004-637X/814/2/136.
  * [9] S. Miyake, R. Kataoka, and T. Sato, Cosmic Ray Modulation and Radiation dose of Aircrews during the Solar Cycle 24/25, Space Weather 15, 589 (2017), https://doi.org/10.1002/2016SW001588.
  * [10] ACE satellite data, AC_H1_MF1 data,
https://cdaweb.gsfc.nasa.gov/

  * [11] Geotail satellite data, GE_EDB12SECEC_LEP data,
https://cdaweb.gsfc.nasa.gov/.

##  5 Supplementary Information

Supplementary Information 1

Incident protons make nuclear interactions at the top of the atmosphere and
lose the energy. As a result, the arrival signals are lost and not received by
the detectors located at the ground level. We have examined the attenuation
rate of a few GeV proton in the atmosphere by the GEANT4 simulation code.

The results are given in Figure 6 and Figure 7. The Figure 6 presents the
detection efficiency of signal of low energy protons at 4,600m altitude. In
the Figure 6, we assumed that protons enter into the atmosphere vertically
($\theta\approx\,{0}^{\circ}$) and the detection is made either by using the
“anti-all” channel or by the “channel 1”. In the anti-all channel, shower
debris like soft gamma-rays are detected by PR-counter, while in the channel
ch-1, neutral particles with energy higher than 30 MeV are detected by the
thick plastic scintillator. For 6 GeV protons by the ch-1, the detection
efficiency is predicted as about 0.4 for the vertical entrance.

The attenuation rate strongly depends on the incident angle. Therefore we have
calculated the attenuation of the proton signal as a function of the incident
angle. Figure 7 shows the angular dependence of $E_{p}=4$ GeV and 6 GeV
protons. In the case, protons enter with the zenith angle of 40 degrees, only
10 percent of signals are recorded by the ground based detector located at Mt.
Sierra Negra.

Figure 6: The detection efficiency of low energy gamma rays ($\bigtriangleup$)
and neutrons ($\bullet$) by the Sierra Negra solar neutron telescope for
vertical entrance into the air is shown as a function of the incident energy
of protons. The discrimination level of gamma-rays and neutrons is set at
larger than 2 MeV and 32 MeV respectively. Figure 7: The detection efficiency
of incident protons is shown as a function of the incident angle on the top of
the atmosphere. Open circle and closed circle correspond to neutrons with the
energy higher than 32 MeV for the incident energy 4 GeV ($\circ$) and 6 GeV
($\bullet$) respectively, while the triangles correspond to the gamma-rays
with the energy higher than 2 MeV for the incident energy of protons of 4 GeV
($\triangle$) and 6 GeV ($\bullet$) respectively.

Supplementary Information 2

Figure 8 shows the momentum distribution of anti-protons arrived at
$6\,R_{E}$. In this plot, we do not require any condition on the incident
angle, so that in the plot all anti-protons are included. They were injected
even almost horizontally from 20 km above Mt. Sierra Negra.

Figure 9 presents the arrival map of anti-protons at $8\,R_{E}$ with the
energy of 4.7, 5, 6 GeV respectively. Quite a lot of anti-protons arrived to
the night region of the Earth (the blue side) in the low energy, while the
proton energy increases from 10, 15, to 20 GeV, the arrival direction
concentrates into the day side (the pink area).

Figure 8: (left side) Among 32,761 shots, 374 events were selected to satisfy
the condition of $\tan^{-1}{(P_{X}/P_{Y})}>45$ degrees and $P_{X}>0$ for
$E_{p}={\rm 6\,GeV}$ anti-protons. They are plotted on the $P_{Z}-P_{Y}$
plane. (right side) The same events are plotted on the $P_{Z}-P_{Y}$ momentum
space. No incident angular cut of the incoming protons to the air was applied.
The data involve all arrival directions at 20 km above Mt. Sierra Negra. The
IMF direction is shown by the arrow. Figure 9: The outgoing points of anti-
protons at $8\,R_{\rm E}$ (radius of the Earth) and $15\,R_{\rm E}$ at the
magnetopause are shown by dots. The right side corresponds to the day side of
the Earth, while left side corresponds to the night side. In the low energy
region, a number of protons are coming from the night side. On the other hand,
the incident momentum increases, they are arriving to the Earth only from the
day side.

Supplementary Information 3

In this event, it is quite important to understand general situation of the
solar terrestrial environment. Just one day before of X2 solar flare, M9 class
solar flare occurred at the Sun. Following this M9 flare, a large CME was
emitted. Here we call the CME as CME1. The CME1 approaches up to
$\ell\approx\,10^{7}\,{\rm km}$ in front of the Earth. The strength of the
magnetic field was measured by the magnetometer of the ACE satellite [10] and
the GEOTAIL satellite [11]. The measured field strength of the CME rope was 50
nT, while the field strength near the Earth between 16:00-18:30 UT was
measured as 20 nT.

The decay probability of neutrons with $E_{n}=6$ GeV is estimated as 0.0047.
The probability is very small. If we put the field strength of $H={\rm
20\,nT}$ and proton energy of $p=6$ GeV in the formula of $p_{\perp}[{\rm
GeV}]=0.3H[{\rm T}]\rho[{\rm m}]$, the rotation radius of protons is
$1\times\,10^{6}$ km. In comparison with $\ell$, it is about 10 times shorter.
Therefore, until they arrived at the magnetopause, the protons rotated about
$\sim$ 8 times as the maximum case.

We also know the field strength in the CME as 50 nT. Protons less than 60 GeV
may be trapped in the CME rope. For this reason, the SNDPs that appeared
between the Sun and the CME1 could not come to the Earth. This scenario leads
us to establish the decay length of neutrons as $\ell\approx\,10^{7}\,{\rm
km}$ or 0.067 au.

In comparison with low energy protons produced by the solar neutron decay
process, the behavior is quite different from previous low energy events [3,
4]. Therefore we list the numerical values to estimate the difference in Table
1. The situation is summarized and depicted in Figure 10.

Table 1: The gyro-radius of protons in the magnetic field at the magnetopause and magnetosheath $B\quad|\quad E_{\rm p}$ | 10 MeV | 100 MeV | 1 GeV | 6 GeV
---|---|---|---|---
5 nT | $7\times{10^{3}\,{\rm km}}$ | $7\times{10^{4}\,{\rm km}}$ | $7\times{10^{5}\,{\rm km}}$ | $4\times{10^{6}\,{\rm km}}$
|  |  | (0.005 au) | (0.027 au)
20 nT |  |  |  | $1\times{10^{6}\,{\rm km}}$
50 nT | 700 km | 7,000 km | $7\times{10^{4}\,{\rm km}}$ | $4\times{10^{5}\,{\rm km}}$
decay probability | 0.0061 | 0.0250 | 0.0153 | 0.0047
in 0.066 au |  |  |  |
decay upto 0.934au | 0.9732 | 0.6731 | 0.2541 | 0.0698
up to 1au | 0.9793 | 0.6980 | 0.2694 | 0.0745
Figure 10: The interplanetary space around 16 UT on November 7th, 2004 is
pictorially presented. The CME1 was produced one day before in association
with a M9.7 flare. On the other hand, the CME2 was emitted on 16 UT of
November 7th 2004, by the X2.0 flare. The neutron beam penetrates these plasma
wave, however protons, the decay products of solar neutrons, cannot penetrate
the CME wall (CME1) due to its strong magnetic field. Therefore, the decay
length is estimated as $1\times 10^{7}km$. The effective decay space is also
shown by the blue box.

Supplementary Information 4

Now let us examine the motion of the SNDPs. Neutrons cross the interplanetary
space almost straightforwardly between the Sun and the Earth. However as soon
as they decay in the distance of $\ell$, the protons of the decay product
immediately receive the electro-magnetic force, so that the direction of the
motion will be largely deflected from the initial direction. At that time the
IMF direction crossed to $X$-axis with $56^{\circ}$ to $60^{\circ}$.
Therefore, those protons received the equivalent transverse momentum as 5
GeV/$c$. The rotation radius is estimated as about $1\times 10^{6}$ km or
0.0067 au. By this reason, before arrival at the magnetopause (the head of the
magnetosphere), the SNDPs of 6 GeV may rotate a few times before their
arrival, depending on the decay position. A schematic view is shown in Figure
11.

Figure 11: The proton motion after neutron decay is pictorially shown.
Neutrons that are coming from the solar direction (the dashed line)
spontaneously decay into protons. Then these protons receive the magnetic
force by the IMF. At that time the intensity of IMF was estimated as 20 nT. So
protons with $Ep={\rm 6\,GeV}$ start the gyration motion with a radius of
$1\times{10^{6}}$ km. The equivalent $p_{\perp}$ is about 5 GeV/$c$. After a
few rotations, these protons arrive at the limit of the magnetosphere. The IMF
direction ($B$) and the GSE coordinate are also shown in the figure.

Supplementary Information 5

In Figure 12, we present the solar neutron spectrum measured at Mt.
Chacaltaya. The extended flux beyond 1 GeV are also given for the three cases
of the spectrum and we estimate the flux at 6 GeV for each case. The total
intensity of 6 GeV neutrons estimated by the Mt. Sierra Negra detector is also
plotted on the line of $E_{n}=6$ GeV. The Chacaltaya neutron spectrum is
presented by the integral spectrum and the intensity was already converted
into the flux at the top of the atmosphere.

Figure 12: The neutron production spectrum is shown for the cases of three
integral power index of $\gamma$. The simple extended line shows for the case
of the power spectrum $\gamma=-2.7$, and dashed line corresponds to the
bending case of the power index at 1 GeV from $\gamma=-2.7$ to -3.7. The
dotted line represents the case when the spectrum can be expressed by
$\gamma=-4.7$ in the energy range between 1 GeV and 10 GeV (quite soft
spectrum). The estimated intensity at the space integrated from the counting
rate of Mt. Sierra Negra is also shown by the star. However the point
represents the one-minute value of the integrated flux. It corresponds to
($360\pm 125\,{\rm neutrons/m^{2}\cdot min.}$).