text:
\section{Introduction}

\subsection{FPT Algorithms and Kernels}
In the theory of parameterized complexity, we introduce parameters to problems and analyze the complexity with respect to both the input length $n=|x|$ and the parameter value $k$.
If an algorithm runs in $f(k)n^{O(1)}$ time for any input of length $n$ and a parameter $k$, it is called a \emph{fixed-parameter tractable (FPT) algorithm}.
If the $n^{O(1)}$ factor is linear, it is called a \emph{linear-time FPT}.
The typical goal of parameterized algorithms is to develop FPT algorithms with a small $f(k)$ (e.g., $c^k$ for a small constant~$c$) and a small $n^{O(1)}$ (e.g., linear in $n$).
Although there are many algorithms that have been developed with smaller $f(k)$ \emph{or} $n^{O(1)}$, achieving the smallest $f(k)$ and $n^{O(1)}$ \emph{simultaneously} is a very difficult task,
and the smallest $f(k)$ factors and the smallest $n^{O(1)}$ factors are often achieved by different algorithms.
Moreover, when trying to improve the $f(k)$ factor, the $n^{O(1)}$ factor is often ignored by using the $O^*$ notation, which hides factors polynomial in $n$,
and when trying to improve the $n^{O(1)}$ factor, the $f(k)$ factor is often ignored by assuming $k$ is a constant.

If we take into account not only whether $f(k)$ is a single exponential ($f(k)=c^k$) or not, but also the base of
exponent $c$, achieving the smallest $c$ and the smallest $n^{O(1)}$ simultaneously becomes much more difficult.
For example, in recent papers, Iwata, Oka, and Yoshida~\cite{DBLP:conf/soda/IwataOY14}, and Ramanujan and Saurabh~\cite{DBLP:conf/soda/RamanujanS14}
have independently obtained $O(4^k m)$-time algorithms for \problem{Almost 2-SAT}, which is a parameterized version of \problem{Max 2-SAT} where a parameter is the number of unsatisfied clauses;
on the other hand, when allowing the $n^{O(1)}$ factor to be super-linear, there exists an $O^*(2.32^k)$-time algorithm~\cite{DBLP:journals/talg/LokshtanovNRRS14}.
These two algorithms are not comparable: the former runs faster when the input is large but the latter runs faster when the parameter is large.
Typically, only algorithms with the smallest $f(k)$ factor or the smallest $n^{O(1)}$ factor have been studied.
However, if there were three algorithms running in time $O(8^k n)$, $O(4^k n^2)$, and $O(2^k n^3)$, all of them are
incomparable: the first is fastest when $4^k<n$, the second is fastest when $2^k<n<4^k$, and the third is fastest when $n<2^k$.
Do we need to develop algorithms with the smallest possible $f(k)$ factor for each $n^d$?
We observe that \emph{kernelization}, which is another basic research object of the parameterized complexity, is useful for avoiding this Pareto optimality.

A kernelization algorithm (or \emph{kernel}) for a parameterized problem is an algorithm that, given an instance $(x,k)$ in time polynomial in $n=|x|$ and $k$,
returns an equivalent instance $(x',k')$ of the same problem
such that $k'\leq k$ and $|x'|\leq g(k)$ for some function $g$.
When the $n^{O(1)}$ factor in the running time is linear in $n$ (i.e., $k^{O(1)}n$), it is called a \emph{linear-time kernel}.
If there is a kernel, by solving the reduced instance exhaustively, we can obtain an FPT algorithm.
Actually, the converse is also true; if there exists an $f(k)n^{O(1)}$-time FPT algorithm, there also exists a kernel of size $f(k)$.
On the other hand, the existence of a polynomial-size (i.e., $|x'|\leq k^{O(1)}$) kernel is non-trivial and, actually,
there are known to exist FPT problems which (unconditionally) do not have any sub-exponential-size kernels~\cite{DBLP:journals/jcss/BodlaenderDFH09}.
As in the case of FPT algorithms, the typical goal is to develop kernelization algorithms with a small size $g(k)$ (e.g.,
linear in $k$) and a fast running time (e.g., linear in $n$).

Although several simple kernels, including the $2k$-vertex kernel for \problem{Vertex Cover}~\cite{NemhauserT75}, are linear-time kernels,
compared with linear-time FPT algorithms, there are only a small number of studies for linear-time polynomial-size kernels.
Examples include \problem{$d$-Hitting Set}~\cite{DBLP:journals/algorithmica/Bevern14},
\problem{Dominating Set} on planar graphs~\cite{DBLP:conf/iwpec/BevernHKNW11,DBLP:conf/iwpec/Hagerup11},
and \problem{$n - k$ Clique Covering}~\cite{DBLP:conf/wg/ChorFJ04}.
There are two reasons for this.
First, obtaining a polynomial-size kernel is already more difficult than obtaining FPT algorithms; there are many problems in FPT for which no polynomial-size kernels are known.
Second, when assuming the parameter $k$ is a constant, which is often done when studying linear-time FPT algorithms,
kernels become uninteresting because we cannot distinguish between $f(k)$ and $k^{O(1)}$.

Nevertheless, improving the $n^{O(1)}$ factor in the running time of kernels is very important because such kernels
can be used as preprocessing for FPT algorithms.
Let us assume that we have a $k^{O(1)}n^d$-time polynomial-size kernel and an $f(k)n^{O(1)}$-time FPT algorithm.
Then, by applying the FPT algorithm against the instance reduced by the kernel, we obtain a
$k^{O(1)}(f(k)+n^d)$-time FPT algorithm.
Thus, the $n^{O(1)}$ factor of any FPT algorithm can be replaced by $n^d$.
Therefore, if we have a linear-time polynomial-size kernel, we obtain a linear-time FPT algorithm that
simultaneously achieves the smallest possible $f(k)$ factor (ignoring factors polynomial in $k$).
This also implies that after obtaining a linear-time polynomial-size kernel, we can safely ignore the $n^{O(1)}$ factor
and focus on improving the $f(k)$ factor only.
Moreover, it can also be combined with another kernel of smaller size.
Let us assume that we have a $k^{O(1)}n^d$-time polynomial-size kernel and a $g(k)$-size kernel.
Then, by applying the second kernel against the instance reduced by the first kernel, we obtain a $k^{O(1)}n^d$-time
$g(k)$-size kernel.
Therefore, in contrast to the case of FPT algorithms, we can always achieve the smallest size and the fastest running time
simultaneously.

\subsection{Our Contribution}

In this paper, we propose a linear-time quadratic-size kernel for \problem{Feedback Vertex Set}.
This is the first linear-time polynomial-size kernel for this problem.
\problem{Feedback Vertex Set} is a problem to decide whether a given undirected graph has a vertex set of size at most a given parameter $k$
whose removal makes the graph a forest.
\problem{Feedback Vertex Set} is one of the most comprehensively studied problems in the field of parameterized complexity and many different FPT algorithms and
kernels have been developed.
Moreover, the problem was chosen as a target problem of the 1st Parameterized Algorithms and Computational Experiments (PACE) challenge\footnote{\url{https://pacechallenge.wordpress.com/}}.
Actually, this research is strongly motivated by the PACE challenge.
The proposed methods are easy to implement, and a solver\footnote{\url{https://github.com/wata-orz/fvs}} based on the proposed methods won first place in the challenge.

The first FPT algorithm for \problem{Feedback Vertex Set} was given by Downey and Fellows~\cite{DBLP:conf/dagstuhl/DowneyF92}.
This algorithm and subsequent improved algorithms~\cite{DBLP:conf/iwpec/KanjPS04,DBLP:journals/talg/RamanSS06} use the
strategy to branch on short cycles and the $f(k)$ factor of the running time is not a single exponential in $k$.
The first single-exponential FPT algorithms were obtained independently by
Dehne~et~al.~\cite{DBLP:journals/mst/DehneFLRS07} and Guo~et~al.~\cite{DBLP:journals/jcss/GuoGHNW06}, and
several improved algorithms have been
obtained~\cite{DBLP:journals/jcss/ChenFLLV08,DBLP:journals/algorithmica/CaoC015,DBLP:journals/ipl/KociumakaP14}.
The current smallest $f(k)$ factor for deterministic algorithms is $3.62^k$ given by Kociumaka and
Pilipczuk~\cite{DBLP:journals/ipl/KociumakaP14}.
These single-exponential FPT algorithms use the \emph{iterative compression} technique.
For a graph with $n$ vertices and $m$ edges\footnote{If a graph has a feedback vertex set of size at most $k$, we
have $m=O(kn)$.}, a naive implementation of iterative compression requires
$n$ iterations and each iteration takes $f(k)\Omega(m)$ time.
Therefore, the total running time is $f(k)\Omega(nm)$.
For the case of \problem{Feedback Vertex Set}, by combining it with 2-approximation
algorithms~\cite{DBLP:journals/siamdm/BafnaBF99,DBLP:journals/ai/BeckerG96}, we can solve the problem using only a single
iteration; however, this increases the running time for one iteration to $f(2k)\Omega(m)$.
Thus, for obtaining a linear-time FPT algorithm, the $f(k)$ factor needs to grow from $3.62^{k}$ to $3.62^{2k}$.
When allowing randomness, a simple $O(4^k km)$-time FPT algorithm using random sampling of edges was given by
Becker~et~al.~\cite{DBLP:journals/jair/BeckerBG00}
The current smallest $f(k)$ factor for randomized FPT algorithms is $3^k$ given by
Cygan~et~al.~\cite{DBLP:conf/focs/CyganNPPRW11}
This algorithm uses dynamic programming on tree-decompositions and takes $3^k k^{O(1)}n^2$ time after obtaining a
tree-decomposition of width at most $k$.
As discussed above, by using our linear-time polynomial-size kernel, we can obtain a $k^{O(1)}(3.62^k+m)$-time
deterministic FPT algorithm and a $k^{O(1)}(3^k+m)$-time randomized FPT algorithm.

The first polynomial-size kernel was given by Burrage~et~al.~\cite{DBLP:conf/iwpec/BurrageEFLMR06}
The size of this kernel is $O(k^{11})$, which was improved to $O(k^3)$ by Bodlaender and van
Dijk~\cite{DBLP:journals/mst/BodlaenderD10}, and to $O(k^2)$ by Thomass\'e~\cite{DBLP:journals/talg/Thomasse10}.
Finally, Dell and van Melkebeek~\cite{DBLP:journals/jacm/DellM14} showed that there are no kernels of size
$O(k^{2-\epsilon})$ for any constant $\epsilon>0$ unless $\cclass{NP}\subseteq\cclass{coNP}/\cclass{poly}$.
The size of the current smallest kernel by Thomass\'e is $4k^2$ vertices and $8k^2$ edges.
As discussed above, if there is a linear-time polynomial-size kernel, by combining it with the smallest kernel, we can
achieve the linear running time and the smallest kernel size simultaneously.
However, our linear-time quadratic-size kernel does not rely on such a combination.

Before providing a description of our kernel, we first give a brief description of a key idea behind the existing kernels.
All the existing kernels for \problem{Feedback Vertex Set} exploit \emph{$s$-flowers}.
A set of simple cycles is called an $s$-flower if each cycle contains the vertex $s$ and none of two cycles share a
vertex different from $s$.
If the degree of $s$ is large and the graph is well-connected, there exists a large $s$-flower.
Because the size of an $s$-flower (i.e., the number of cycles) gives a lower bound of the size of the minimum feedback
vertex set that does not contain $s$, if it is larger than the parameter $k$, we can remove $s$.
Otherwise, the degree of $s$ is small, or the graph is not well-connected.
In the former case, we know that the graph is small, and in the latter case, we can apply another reduction rule.

In our kernel, instead of $s$-flowers, we exploit \emph{$k$-submodular relaxation}, which is a recently developed
technique for obtaining efficient FPT algorithms for various problems.
The concept of $k$-submodular relaxation was independently discovered by Wahlstr\"om~\cite{DBLP:conf/soda/Wahlstrom14}
and by Iwata and Yoshida, and two results are combined in the full version~\cite{DBLP:journals/corr/Wahlstrom13}.
The $k$-submodular relaxation is a technique to obtain \emph{half-integral} and \emph{persistent} relaxations and many
existing half-integral LP relaxations (e.g., the LP relaxation of \problem{Vertex Cover}~\cite{NemhauserT75}) can be re-derived by this
technique.
If a problem admits such a relaxation, the branch-and-bound method gives an FPT algorithm.
By applying $k$-submodular relaxation, Wahlstr\"om~\cite{DBLP:conf/soda/Wahlstrom14} obtained an $O^*(4^k)$-time FPT
algorithm for \problem{Feedback Vertex Set}.
The detail description of the $k$-submodular for \problem{Feedback Vertex Set} is given in Section~\ref{sec:pre}.
By exploiting $k$-submodular relaxation, we obtain a very simple kernel for \problem{Feedback Vertex Set}.
The size of our kernel is $2k^2+k$ vertices and $4k^2$ edges, which is smaller than the previous best
of $4k^2$ vertices and $8k^2$ edges~\cite{DBLP:journals/talg/Thomasse10}.

We observe that there is a strong relationship between the $k$-submodular relaxation of \problem{Feedback Vertex Set} and $s$-flowers;
the problem of computing a maximum $s$-flower is the integral dual of the $k$-submodular relaxation of \problem{Feedback Vertex Set}.
This resembles the situation for \problem{Almost 2-SAT}.
For \problem{Almost 2-SAT}, Raman~et~al.~\cite{DBLP:conf/esa/RamanRS11} obtained an $O^*(9^k)$-time FPT algorithm by a reduction to
\problem{Vertex Cover above Maximum Matching}, and then both the $f(k)$
factor~\cite{DBLP:journals/talg/LokshtanovNRRS14} and $n^{O(1)}$
factor~\cite{DBLP:conf/soda/IwataOY14,DBLP:conf/soda/RamanujanS14} were improved by a reduction to \problem{Vertex Cover above LP}.
Here, the maximum matching is the integral dual of the LP relaxation of \problem{Vertex Cover}.
Because the fractional minimum of the primal LP is always at least the integral maximum of the dual LP, by using the
half-integral relaxation instead of the integral dual, we can obtain a better lower bound.
Moreover, by using the half-integral relaxations, we can directly exploit the persistency of the relaxations.

For obtaining linear-time kernel, we need to solve the $k$-submodular relaxation of \problem{Feedback Vertex Set} efficiently.
Iwata, Wahlstr\"om, and Yoshida~\cite{DBLP:journals/corr/Wahlstrom13} showed that various cases of $k$-submodular
relaxations can be solved efficiently by a reduction to the minimum cut problem, and by using this method, they obtained
linear-time FPT algorithms for various problems including \problem{Unique Label Cover}.
 However, this method cannot be applied to the $k$-submodular relaxation of \problem{Feedback Vertex Set} for two reasons:
the method can be applied only to edge-deletion problems and, moreover, when applied to \problem{Feedback Vertex Set}, the size of the network
for the minimum cut problem becomes exponential in $m$.

For solving the $k$-submodular relaxation of \problem{Feedback Vertex Set} efficiently,
we propose a max-flow-like augmenting-path algorithm.
This is the most technical part of the paper.
Our algorithm can compute a minimum solution in $O(km)$ time.
We note that this algorithm can be used not only for the linear-time kernel but also for improving the $n^{O(1)}$ factor
of the $O^*(4^k)$-time FPT branch-and-bound algorithm for \problem{Feedback Vertex Set}.
Wahlstr\"om~\cite{DBLP:conf/soda/Wahlstrom14} applied $k$-submodular relaxation to two general
versions, \problem{Subset Feedback Vertex Set} and \problem{Group Feedback Vertex Set}, and obtained $O^*(4^k)$-time FPT
algorithms for both problems.
Extending our algorithm for solving the $k$-submodular relaxation of these two general versions would be a possible
approach for obtaining linear-time FPT algorithms for these problems.
We note that for \problem{Subset Feedback Vertex Set}, an $O(25.6^k m)$-time randomized FPT algorithm and a $(2^{O(k\log
k)}m)$-time deterministic FPT algorithm have been obtained using a very different
approach~\cite{DBLP:conf/icalp/LokshtanovRS15}.

\subsection{Relation to $A$-path Packing}
Because $s$-flower is the integral dual of the $k$-submodular relaxation of \problem{Feedback Vertex Set}, one may think that, by creating a copy of each vertex, we
can compute the maximum half-integral $s$-flower which would be a fractional dual of the $k$-submodular relaxation.
However, this is not true.
In the fractional dual of the $k$-submodular relaxation, we need to avoid U-turns (see Section~\ref{sec:flower}
for a detailed description of the fractional dual of the $k$-submodular relaxation).
For example, $s$--$a$--$b$--$c$--$d$--$a$--$s$ is a valid cycle\footnote{This cycle contains the vertex $a$ twice but can be packed half-integrally. When focusing on integral packings, this cycle also becomes invalid.}
but $s$--$a$--$b$--$c$--$b$--$a$--$s$ is invalid;
however, after creating a copy $v'$ for each vertex $v$, we cannot distinguish between a valid cycle $s$--$a$--$b$--$c$--$d$--$a'$--$s$ and an
invalid cycle $s$--$a$--$b$--$c$--$b'$--$a'$--$s$.

Given a set of vertices $A$, a path is called an \emph{$A$-path} if the two end points are in $A$.
Although the maximum $s$-flower can be computed by a reduction to the $A$-path packing problem~\cite{DBLP:journals/talg/Thomasse10},
the $k$-submodular relaxation of \problem{Feedback Vertex Set} cannot be solved by the reduction to $A$-path packing due to the above reason.
We observe that by a reduction to a more general problem, $A$-path packing in group labelled graphs, we can avoid U-turns
and thus the $k$-submodular relaxation of \problem{Feedback Vertex Set} can be solved.
However, the current fastest algorithm for this general problem~\cite{DBLP:journals/siamdm/Yamaguchi16} is not enough
for obtaining linear-time kernel.
Our augmenting-path algorithm is actually solving a special case of the fractional group-labelled $A$-path packing,
and it might be useful for obtaining a fast algorithm for the general case.

\subsection{Organization}
First, in Section~\ref{sec:pre}, we give definitions used in this paper, introduce common techniques of kernelization of \problem{Feedback Vertex Set},
and introduce the $k$-submodular relaxation of \problem{Feedback Vertex Set}.
In Section~\ref{sec:simple}, we give a simple quadratic-size kernel by exploiting the $k$-submodular relaxation.
In Section~\ref{sec:flower}, we give an $O(km)$-time augmenting-path algorithm for solving the $k$-submodular
relaxation.
Finally, in Section~\ref{sec:linear}, we give a linear-time quadratic-size kernel by combining these two results.

\section{Preliminaries}\label{sec:pre}

\subsection{Definitions}

A \emph{multiplicity function} of a multiset $S$ is denoted by $\mathbf{1}_S$;
e.g., when $S=\{a,a,b\}$, $\mathbf{1}_S(a)=2$, $\mathbf{1}_S(b)=1$, and $\mathbf{1}_S(c)=0$.
Let $f:U\rightarrow\mathbb{R}$ be a function.
For a multiset $S$, we write the sum of $f(a)$ over $a\in S$ as $f(S)=\sum_{a\in S}f(a)$;
e.g., when $S=\{a,a,b\}$, $f(S)=2f(a)+f(b)$.
We denote the preimage of $i\in\mathbb{R}$ under $f$ by $f^{-1}(i)=\{a\in U\mid f(a)=i\}$.

Let $G=(V,E)$ be an undirected graph.
We assume that $G$ may contain a self-loop and multiple edges.
We will often denote the number of vertices by $n$ and the number of edges by $m$.
We denote the set of edges incident to a vertex $v$ by $\delta_G(v)$ and define the \emph{degree} of $v$ as $d_G(v)=|\delta_G(v)|$.
Here, we note that multiple edges contribute to the degree by its multiplicity, and we never refer to the degree of a vertex having a self-loop.
We omit the subscript $G$ if it is clear from the context.
An edge $e\in E$ is called a \emph{bridge} if its removal increases the number of connected components.

For a vertex set $S$, we denote the graph obtained by removing $S$ and their incident edges by $G-S$.
When $S$ is a singleton $\{v\}$, we simply write $G-v$.
A vertex set $S\subseteq V$ is called a \emph{feedback vertex set} if $G-S$ is a forest.
We denote the size of the minimum feedback vertex set of $G$ by $\mathrm{fvs}(G)$.

A \emph{walk} is an ordered list $(v_0,e_1,v_1,e_2,\ldots,v_{l-1},e_l,v_l)$ such that $l\geq 1$ and each edge $e_i$ connects vertices $v_{i-1}$ and $v_i$.
Note that it may contain a vertex or an edge multiple times.
For a walk $W=(v_0,e_1,\ldots,v_l)$, we denote the multiset of vertices appearing on $W$ by $V(W)=\{v_0,\ldots,v_l\}$
and the multiset of edges appearing on $W$ by $E(W)=\{e_1,\ldots,e_l\}$.

\subsection{Basic Reductions}
We introduce basic reductions that have been commonly used in kernelization algorithms for
\problem{Feedback Vertex Set}~\cite{DBLP:conf/iwpec/BurrageEFLMR06,DBLP:journals/mst/BodlaenderD10,DBLP:journals/talg/Thomasse10}.
The correctness of these reductions is almost trivial.

\begin{enumerate}
  \setlength{\parskip}{0.05cm}
  \setlength{\itemsep}{0.05cm}
  \item If there is a vertex $v$ containing a self-loop, remove $v$ and decrease $k$ by one.
  \item If there is a vertex of degree at most one, remove it.
  \item If there is a vertex of degree two, remove it and connect its two neighbors by an edge.
  \item If two vertices are connected by more than two edges, replace these edges with a double edge.
\end{enumerate}

Note that rule 3 can remove a vertex that is only incident to a double edge; in this case, it creates a self-loop on its neighbor.
These basic reductions never increase the degree of any vertex and can be fully applied in $O(m)$ time.
After the reduction, the obtained graph has no self-loops and has minimum degree at least three.

We will use the following lemma to bound the size of the kernel.
Because this is a general version of the lemma in \cite{DBLP:journals/talg/Thomasse10}, we give a modified proof.

\begin{lemma}[Thomass\'e~\cite{DBLP:journals/talg/Thomasse10}]\label{lem:size}
If a graph without self-loops satisfies both of the following for an integer $d$, the size of the minimum feedback vertex set is larger than $k$:
\begin{itemize}
  \setlength{\parskip}{0.05cm}
  \setlength{\itemsep}{0.05cm}
  \item At least one of $n>dk+k$ or $m>2dk$ holds; and
  \item for any $v\in V$, it holds that $3\leq d(v)\leq d$.
\end{itemize}
\end{lemma}
\begin{proof}
Let us assume that a graph $G=(V,E)$ has a feedback vertex set $S$ of size $k$ and each vertex satisfies $3\leq d(v)\leq d$.
Because the subgraph on $V\setminus S$ is a forest, the number of edges inside $V\setminus S$ is at most $n-k-1$.
Because each vertex has degree at least three, there are at least $3(n-k)-2(n-k-1)=n-k+2$ edges between $S$ and $V\setminus S$.
On the other hand, because each vertex has degree at most $d$, there can exist at most $dk$ edges between $S$ and $V\setminus S$.

When $n>dk+k$, we have $n-k+2>dk$, which is a contradiction.
Thus, the size of the minimum feedback vertex set is larger than $k$.

Because the total degree of $V$ is $2m$ and the total degree of $S$ is at most $dk$, the total degree of $V\setminus S$ is at least $2m-dk$.
Therefore, there must exist at least $2m-dk-2(n-k-1)$ edges between $S$ and $V\setminus S$.
When $n\leq dk+k$ and $m>2dk$, we have $2m-dk-2(n-k-1)>dk$, which is a contradiction.
Thus, the size of the minimum feedback vertex set is larger than $k$.
\end{proof}

In \cite{DBLP:journals/talg/Thomasse10}, a kernel of $4k^2$ vertices and $8k^2$ edges is obtained by applying the
lemma against $d=4k-1$.
In the next section, we obtain a kernel of $2k^2+k$ vertices and $4k^2$ edges by applying the lemma against $d=2k$.

\subsection{k-submodular Relaxation of \problem{Feedback Vertex Set}}
A walk $W=(v_0,e_1,\ldots,v_l)$ is called an \emph{$s$-cycle} if $v_0=v_l=s$, $v_i\neq s$ for all $i\in\{1,\ldots,l-1\}$, $e_i\neq e_{i+1}$ for any $i\in\{1,\ldots,l-1\}$ (i.e., there are no U-turns), and each edge is contained in the walk at most twice.
For example, walks $(s,e_1,u,e_2,v,e_3,s)$ and $(s,e_1,u,e_2,v,e_3,w,e_4,u,e_1,s)$ are $s$-cycles but a walk $(s,e_1,u,e_2,v,e_2,u,e_1,s)$ is not.
Note that in this definition, we distinguish each of multiple edges;
e.g., if there is only a single edge $e$ between $s$ and $v$, a walk $(s,e,v,e,s)$ is not an $s$-cycle; however, if there is a double edge $\{e_1,e_2\}$ between $s$ and $v$, a walk $(s,e_1,v,e_2,s)$ is an $s$-cycle.

For a graph $G=(V,E)$ without self-loops and a vertex $s\in V$, a function $x: V\rightarrow\mathbb{R}_{\geq 0}$ is called an \emph{$s$-cycle cover}
if it satisfies that (1) $x(s)=0$ and (2) for any $s$-cycle $C$, $x(V(C))\geq 1$.
Note that $V(C)$ is the multiset of vertices on $C$, and therefore if $x(v)=\frac{1}{2}$ holds for a vertex $v$ contained twice in $C$, we have $x(V(C))\geq 1$.
The \emph{size} of an $s$-cycle cover $x$ is defined as $x(V)$, and when the size $x(V)$ is minimum among all the possible $s$-cycle covers,
it is called a \emph{minimum $s$-cycle cover}.

By introducing the idea of $k$-submodular relaxation, Wahlstr\"om~\cite{DBLP:conf/soda/Wahlstrom14} obtained the
following lemma.
\begin{lemma}[Wahlstr\"om~\cite{DBLP:conf/soda/Wahlstrom14}]\label{lem:ksub}
For any graph $G=(V,E)$ without self-loops and $s\in V$, the following holds:
\begin{itemize}
  \item The size of any feedback vertex set of $G$ that does not contain $s$ is at least the size of the minimum $s$-cycle cover.
  \item There exists a minimum $s$-cycle cover that takes values $\{0,\frac{1}{2},1\}$ (half-integrality).
  \item If there exists a minimum feedback vertex set that does not contain $s$,
  then for any half-integral minimum $s$-cycle cover $x$, there also exists a minimum feedback vertex set $S$ such that
  $x^{-1}(1)\subseteq S$ and $s\not\in S$ (persistency).
\end{itemize}
\end{lemma}

Although the problem of computing a minimum $s$-cycle cover has exponential number of constraints,
Wahlstr\"om~\cite{DBLP:conf/soda/Wahlstrom14} showed that we can compute a half-integral minimum $s$-cycle cover in polynomial time by using the ellipsoid method.

\section{Simple Quadratic-size Kernel}\label{sec:simple}

In this section, we propose a simple polynomial-time quadratic-size kernel for \problem{Feedback Vertex Set}.
By exploiting the persistency of the $k$-submodular relaxation, we propose the following reduction rule called \emph{$s$-cycle cover reduction}.

For a graph $G=(V,E)$, a vertex $s\in V$, and a half-integral minimum $s$-cycle cover $x$, create a graph $G'=(V,E')$ as follows.
Let $X=x^{-1}(1)$ and let $B\subseteq\delta(s)$ be the set of bridges of $G-X$ connecting $s$ and tree components of $G-X-s$.
Then, $G'$ is obtained from $G$ by inserting a double edge between $s$ and each of $v\in X$ and removing the edges $B$.

\begin{lemma}\label{lem:reduction}
For a graph $G=(V,E)$, a vertex $s\in V$, and a half-integral minimum $s$-cycle cover $x$,
let $G'=(V,E')$ be a graph obtained by applying the $s$-cycle cover reduction.
Then, $\mathrm{fvs}(G)=\mathrm{fvs}(G')$ holds.
\end{lemma}
\begin{proof}
($\geq$)
Let $S$ be a minimum feedback vertex set of $G$.
Observe that all the inserted edges are between $s$ and $X=x^{-1}(1)$.
If $s\in S$, $S$ is also a feedback vertex set of $G'$.
Otherwise, from the persistency, we can assume that $S$ contains all the vertices of $X$.
Thus, $S$ is also a feedback vertex set of $G'$.

($\leq$)
Let $S$ be a minimum feedback vertex set of $G'$.
If $s\in S$, $S$ is also a feedback vertex set of $G$.
Otherwise, because all the vertices of $X$ are connected to $s$ by double edges in $G'$, $S$ must contain all of $X$.
Because all the deleted edges are bridges in $G-X$, $S$ is also a feedback vertex set of $G$.
\end{proof}

After applying this reduction, the degree of $s$ can be bounded as the following shows.

\begin{lemma}\label{lem:degree_bound}
For a graph $G=(V,E)$, a vertex $s\in V$, and a half-integral minimum $s$-cycle cover $x$,
let $G'=(V,E')$ be a graph obtained by applying the $s$-cycle cover reduction.
Then, $d_{G'}(s)\leq 2x(V)$ holds.
\end{lemma}
\begin{proof}
First, we show that $x$ is also an $s$-cycle cover of $G'$.
Let us assume that there is an $s$-cycle $C$ of $G'$ such that $x(C)<1$.
Because $x(v)=1$ for $v\in X=x^{-1}(1)$, $C$ contains none of $X$.
Because all the inserted edges are incident to $X$, $C$ is also an $s$-cycle of $G$, which is a contradiction.

For $i\in\{1,2\}$, let $N_i$ denote the set of vertices that are connected to $s$ by edges of multiplicity $i$ in $G'$.
For each $v_i\in N_1$, we define a vertex $w_i$ as follows.

If the edge $sv_i$ is a bridge in $G'-X$, let $C_i$ be the connected component of $G'-X-s$ containing $v_i$.
Because the reduction removes all the bridges between $s$ and tree components, $C_i$ is not a tree.
Thus, there exists an $s$-cycle contained in $C_i\cup\{s\}$ and, therefore, there must exist a vertex $w_i\in C_i$ with $x(w_i)=\frac{1}{2}$.

If $sv_i$ is not a bridge in $G'-X$, there exists a path $P_i$ from $v_i$ to $N_1\setminus \{v_i\}$ in $G'-X-s$.
Fix an arbitrary path $P_i$ and let $w_i$ be the first vertex on the path such that $x(w_i)=\frac{1}{2}$.
Because $x$ is an $s$-cycle cover, there always exists such a vertex.

If $w_i=w_j$ holds for some $i\neq j$, there exists an $s$-cycle $C$ such that $x(C)=\frac{1}{2}$, which is a contradiction.
Therefore, all $w_i$ are distinct.
Thus, we have $d_{G'}(s)=|N_1|+2|N_2|\leq |x^{-1}(\frac{1}{2})|+2|x^{-1}(1)|= 2x(V)$.
\end{proof}

\begin{algorithm}[t]
\caption{Simple quadratic-size kernelization for \problem{Feedback Vertex Set}}
\label{alg:simple}
\begin{algorithmic}[1]
\Procedure{Kernelize}{$G,k$}
	\While{true}
		\State Apply the basic reductions
		\If{$k<0$}
			\Return NO
		\EndIf
		\If{$n\leq 2k^2+k$ and $m\leq 4k^2$}
			\Return $(G,k)$
		\EndIf
		\If{$\forall v\in V, d(v)\leq 2k$}
			\Return NO\label{line:small_degree}
		\EndIf
		\State Pick a vertex $s$ of degree larger than $2k$
		\State Compute a half-integral minimum $s$-cycle cover $x$
		\If{$x(V)>k$}
			$G\gets G-s$; $k\gets k-1$\label{line:large_x}
		\Else{}
			apply the $s$-cycle cover reduction\label{line:cycle_cover_reduction}
		\EndIf
	\EndWhile
\EndProcedure
\end{algorithmic}
\end{algorithm}

Now, we describe our simple quadratic-size kernelization algorithm (see Algorithm~\ref{alg:simple}).
First, we apply the basic reduction.
If $k$ becomes negative, we return a NO instance.
If the graph becomes small enough, we return it.
If all the vertices have degree at most $2k$, we return a NO instance.
Otherwise, pick an arbitrary vertex $s$ of degree larger than $2k$, and compute a half-integral minimum $s$-cycle cover $x$.
If the size of the $s$-cycle cover is larger than $k$, we remove $s$ and decrement $k$.
Otherwise, we apply the $s$-cycle cover reduction.

\begin{lemma}
Algorithm~\ref{alg:simple} runs in $(k+m)^{O(1)}$ time and correctly computes $(G',k')$ satisfying $k'\leq k$ and $\mathrm{fvs}(G)\leq k\Leftrightarrow\mathrm{fvs}(G')\leq k'$.
The size of $G'$ is at most $2k^2+k$ vertices and $4k^2$ edges.
\end{lemma}
\begin{proof}
It obviously holds that $k'\leq k$ and the size of $G'$ is at most $2k^2+k$ vertices and $4k^2$ edges.
From Lemma~\ref{lem:degree_bound}, after applying the $s$-cycle cover reduction,
the degree of $s$ changes from more than $2k$ to at most $2k$.
Therefore, the number of edges strictly decreases for each iteration.
Thus, it stops in at most $m$ iterations.
Because each iteration can be done in time polynomial in $k$ and $m$, the total running time is also polynomial in $k$ and $m$.

Next, we show the correctness.
By applying Lemma~\ref{lem:size} against $d=2k$, when the maximum degree is at most $2k$ and at least one of $n>2k^2+k$ and $m>4k^2$ holds,
$\mathrm{fvs}(G)>k$ holds.
Thus, we can safely return a NO instance (line~\ref{line:small_degree}).
From Lemma~\ref{lem:ksub}, if $x(V)>k$, there is no feedback vertex set of size at most $k$ that does not contain $s$.
Thus, we can safely remove $s$ (line~\ref{line:large_x}).
The correctness of the $s$-cycle cover reduction follows from Lemma~\ref{lem:reduction}.
\end{proof}

\section{Efficient Computation of a Half-integral Minimum s-cycle Cover}\label{sec:flower}

In this section, we prove the following theorem.
\begin{theorem}\label{thm:main2}
Given a graph $G=(V,E)$ without self-loops, a vertex $s\in V$, and an integer $k$, in $O(km)$ time,
we can compute a half-integral minimum $s$-cycle cover or conclude that there are no $s$-cycle covers of size at most $\frac{k}{2}$.
\end{theorem}

First, we give several definitions.
Let $\mathcal{C}_s$ denote the set of all $s$-cycles.
A function $y:\mathcal{C}_s\rightarrow\mathbb{R}$ is called an \emph{$s$-cycle packing} if
for any vertex $v\in V\setminus\{s\}$, it holds that $\sum_{C\in \mathcal{C}_s} \mathbf{1}_{V(C)}(v) y(C)\leq 1$.
The \emph{size} of an $s$-cycle packing $y$ is defined as $y(\mathcal{C}_s)$, and when the size $y(\mathcal{C}_s)$ is the maximum among all the possible
$s$-cycle packings, it is called a \emph{maximum $s$-cycle packing}.
Because the problem of finding a maximum $s$-cycle packing is the LP dual of the problem of finding a minimum $s$-cycle cover,
the size of the minimum $s$-cycle cover is equal to the size of the maximum $s$-cycle packing.
Thus, if we can find a pair of an $s$-cycle cover $x$ and an $s$-cycle packing $y$ of the same size,
we can confirm that $x$ is a minimum $s$-cycle cover and $y$ is a maximum $s$-cycle packing.

\begin{definition}\label{def:basic}
A function $f:E\rightarrow\{0,\frac{1}{2},1\}$ is called a \emph{basic $s$-cycle packing} if it satisfies the following three conditions.
\begin{enumerate}
  \setlength{\parskip}{0.05cm}
  \setlength{\itemsep}{0.05cm}
  \item For any $e\in\delta(s)$, $f(e)\in\{0,1\}$.
  \item Each vertex $v\in V\setminus\{s\}$ satisfies exactly one of the following four conditions (see Figure~\ref{fig:types}):
  \begin{enumerate}
    \item $f(e)=0$ for all edges $e\in\delta(v)$ (called type-O);
    \item $f(e)=1$ for exactly two edges $e\in\delta(v)$ and $f(e)=\frac{1}{2}$ for none of $e\in\delta(v)$ (called type-I);
    \item $f(e)=1$ for none of $e\in\delta(v)$ and $f(e)=\frac{1}{2}$ for exactly two edges $e\in\delta(v)$ (called type-H);
    \item $f(e)=1$ for exactly one edge $e\in\delta(v)$ and $f(e)=\frac{1}{2}$ for exactly two edges $e\in\delta(v)$ (called type-T).
  \end{enumerate}
  \item For each vertex $v\in V\setminus\{s\}$ of type-H or type-T, the cycle obtained by following edges of value $\frac{1}{2}$ from $v$
  contains an odd number of type-T vertices.
\end{enumerate}
\end{definition}

We call the cycle in the third condition the \emph{half-integral cycle of $v$}.
The size of a basic $s$-cycle packing $f$ is defined as $\frac{1}{2}f(\delta(s))$.
Figure~\ref{fig:basic} illustrates an example of the basic $s$-cycle packing, where solid lines denote edges of value $1$, and dotted lines denote edges of value $\frac{1}{2}$.

\begin{figure}[t]
  \begin{minipage}{0.49\hsize}
	  \centering
	  \includegraphics[scale=0.5]{fig/1-crop.pdf}
	  \caption{Four types of vertices}
	  \label{fig:types}
  \end{minipage}
  \begin{minipage}{0.49\hsize}
	  \centering
	  \includegraphics[scale=0.8]{fig/2-crop.pdf}
	  \caption{Example of the basic $s$-cycle packing}
	  \label{fig:basic}
  \end{minipage}
\end{figure}

\begin{lemma}\label{lem:basic_atmost}
If there exists a basic $s$-cycle packing of size $k$, there also exists an $s$-cycle packing of size $k$.
\end{lemma}
\begin{proof}
Given a basic $s$-cycle packing $f$, we construct an $s$-cycle packing $y$ of the same size as follows.
Initially, set $y(C)=0$ for all $s$-cycles $C\in\mathcal{C}_s$.
First, we modify $f$ as follows.
For each type-T vertex $v\in V\setminus\{s\}$, compute a path by following edges of value one from $v$.
If it reaches to $s$, we do nothing.
Otherwise, it reaches to another type-T vertex $u$.
In this case, set $f(e)=0$ for all edges $e$ on the path.
This modification may break the third condition of Definition~\ref{def:basic};
however, it still preserves the first two conditions
($v$ and $u$ change from type-T to type-H and the other vertices on the path change from type-I to type-O)
and does not change the size of $f$.

While $f(\delta(s))>0$, we repeat the following process.
By following edges of value one from $s$, we obtain a (simple) $s$-cycle $C$ or a path from $s$ to a type-T vertex $v$.
In the former case, set $f(e)=0$ for all edges $e$ on $C$ and set $y(C)=1$.
This modification preserves the first two conditions for $f$ (all the vertices on $C$ become type-O).
Because the cycle $C$ is simple, $y$ remains an $s$-cycle packing after the modification.
In the latter case, let $C$ be the half-integral cycle of $v$ and let $\{t_0,\ldots,t_{q-1}\}$ be the type-T vertices on the cycle $C$ in order (the direction is chosen arbitrary from the two).
Observe that each vertex $t_i$ is connected to $s$ by a path $P_i$ consisting of edges of value one.
We use the notation $t_q=t_0$ and $P_q=P_0$.
For each $i\in\{0,\ldots,q-1\}$, let $C_i$ be an $s$-cycle obtained by concatenating the path $P_i$, the path from $t_i$ to $t_{i+1}$ along the cycle $C$, and the path $P_{i+1}$
(when $q=1$, this creates an $s$-cycle obtained by concatenating the path $P_0$, the cycle $C$, and the path $P_0$ again).
For each $s$-cycle $C_i$, set $f(e)=0$ for all edges $e$ on $C_i$ and set $y(C_i)=\frac{1}{2}$.
This modification preserves the first two conditions for $f$ (all the vertices on $C$ or $P_i$'s become type-O).
Because each vertex $v\in V\setminus\{s\}$ is contained in at most two of $C_i$'s, $y$ remains an $s$-cycle packing after the modification.

During the repetition, the sum $\frac{1}{2}f(\delta(s))+y(\mathcal{C}_s)$ does not change.
Thus, when $f(\delta(s))$ becomes zero, the size of $y$ becomes $k$.
\end{proof}

Note that this lemma only says that the size of the maximum basic $s$-cycle packing is always at most the size of the
maximum $s$-cycle packing and does not imply these two are equal;
there might exist an $s$-cycle packing whose size is strictly larger than the size of any basic $s$-cycle packing.
The equality is shown at the end of this section.

\begin{definition}\label{def:augmenting}
For a basic $s$-cycle packing $f$, a walk $W=(v_0,e_1,\ldots,v_l)$ is called an \emph{$f$-augmenting walk} if it satisfies all the following conditions.
\begin{enumerate}
  \setlength{\parskip}{0.05cm}
  \setlength{\itemsep}{0.05cm}
  \item We have $v_0=s$.
  \item We have $f(e_1)=0$.
  \item All the edges $\{e_1,\ldots,e_l\}$ are distinct.
  \item The vertices $\{v_0,\ldots,v_{l-1}\}$ are distinct (the last vertex $v_l$ can be identical to $v_i$ for some $i<l$).
  \item For each $i\in\{1,\ldots,l-1\}$, exactly one of the following holds:
  \begin{enumerate}
    \item $v_i$ is type-O;
    \item $v_i$ is type-I and $f(e)=1$ holds for at least one of $e\in\{e_i, e_{i+1}\}$.\label{cond:typeI}
  \end{enumerate}
  \item If $v_l=v_i$ for some $i<l$, exactly one of the following holds:
  \begin{enumerate}
    \item $v_l=s$ and $f(e_l)=0$;
    \item $v_l$ is type-O;
    \item $v_l$ is type-I and $f(e)=1$ holds for at least one of $e\in\{e_i,e_l\}$.
  \end{enumerate}
  \item If $v_l\not\in\{v_0,\ldots,v_{l-1}\}$, $v_l$ is type-H or type-T.
\end{enumerate}
\end{definition}

For a basic $s$-cycle packing $f$ and an $f$-augmenting walk $W=(v_0,e_1,\ldots,v_l)$, let $f_W:E\rightarrow\{0,\frac{1}{2},1\}$ be a function defined as follows.
First, set $f_W(e)=f(e)$ for all edges $e\in E$.
If $v_l\neq s$ and $v_l=v_i$ holds for some $i<l$, let $h=i$; otherwise, let $h=l$.
Then, for each edge $e\in\{e_1,\ldots,e_h\}$, set $f_W(e)=1-f(e)$.
If $v_l=s$, we finish (see Figure~\ref{fig:augments}-(a)).
Otherwise, we further modify $f_W$ depending on the type of $v_l$.

(Case 1) If $v_l$ is type-O or type-I, for each edge $e\in\{e_{h+1},\ldots,e_l\}$, set $f_W(e)=\frac{1}{2}$ (see Figure~\ref{fig:augments}-(b)).

(Case 2) If $v_l$ is type-H, let $C$ be the half-integral cycle of $v_l$ and let $\{t_0=v_l,t_1,\ldots,t_{q-1}\}$
be the vertex set consisting of the vertex $v_l$ and the type-T vertices on $C$ ordered along $C$
(i.e., $v_l$ is located on the path from $t_{q-1}$ to $t_1$ along the cycle $C$).
We use the notation $t_q=t_0$.
Let $P_i$ be the path from $t_i$ to $t_{i+1}$ along the cycle $C$.
For each even $i$, set $f_W(e)=0$ for all the edges on $P_i$,
and for each odd $i$, set $f_W(e)=1$ for all the edges on $P_i$ (see Figure~\ref{fig:augments}-(c)).

(Case 3) If $v_l$ is type-T, let $C$ be the half-integral cycle of $v_l$ and let $\{t_0=v_l,t_1,\ldots,t_{q-1}\}$
be the type-T vertices on $C$ ordered along $C$.
Then, we proceed in exactly the same way as in case 2 (see Figure~\ref{fig:augments}-(d)).
We note that, in case 2, $q$ is even; thus, $v_l$ is connected to $t_{q-1}$ by edges of value one in $f_W$.
On the other hand, in case 3, $q$ is odd; thus, $v_l$ is connected to none of $t_1$ and $t_{q-1}$.

\begin{figure}[t]
  \centering
  \includegraphics[scale=0.55]{fig/3-crop.pdf}
  \caption{Examples of augmenting walks}
  \label{fig:augments}
\end{figure}

We call this operation that creates $f_W$ from $f$ as \emph{augmenting $f$ along $W$}.

\begin{lemma}\label{lem:augment}
For a basic $s$-cycle packing $f$ and an $f$-augmenting walk $W=(v_0,e_1,\ldots,v_l)$, let $f_W:E\rightarrow\{0,\frac{1}{2},1\}$
be the function obtained by augmenting $f$ along $W$.
Then, $f_W$ is a basic $s$-cycle packing.
Moreover, if $v_l=s$, the size of $f_W$ is the size of $f$ plus one; and otherwise, the size of $f_W$ is the size of $f$ plus $\frac{1}{2}$.
\end{lemma}
\begin{proof}
First, we show the size of $f_W$.
When $v_l=s$, only the edges $e_1$ and $e_l$ are incident to $s$.
Because it holds that $f(e_1)=f(e_l)=0$, $f_W(e_1)=f_W(e_l)=1$, and $f(e)=f_W(e)$ for all the other edges $e\in\delta(s)$, the size of $f_W$ is the size of $f$ plus one.
When $v_l\neq s$, only the edge $e_1$ is incident to $s$.
Because it holds that $f(e_1)=0$, $f_W(e_1)=1$, and $f(e)=f_W(e)$ for all the other edges $e\in\delta(s)$, the size of $f_W$ is the size of $f$ plus~$\frac{1}{2}$.

Next, we prove that $f_W$ is a basic $s$-cycle packing.
For each edge $e\in\delta(s)$, one of $f_W(e)=f(e)$ or $f_W(e)=1-f(e)$ holds.
Thus, the first condition of Definition~\ref{def:basic} is satisfied.

If $v_l\neq s$ and $v_l=v_i$ holds for some $i<l$, let $h=i$; otherwise, let $h=l$.
We show that $f_W$ satisfies the second condition for each vertex $v\in\{v_1,\ldots,v_{h-1}\}$.
From condition 5 of Definition~\ref{def:augmenting}, $v$ must be type-O or type-I in $f$.
If $v$ is type-O in $f$, it changes to type-I in $f_W$.
If $v$ is type-I in $f$, at least one of $f(e_i)=1$ or $f(e_{i+1})=1$ holds from condition 5(b).
If $f(e_i)=f(e_{i+1})=1$, $v$ changes to type-O in $f_W$; otherwise, it remains type-I.

When $v_l=s$, this concludes the proof.
Let us consider the case where $v_l$ is type-O or type-I in $f$.
If $v_l$ is type-O in $f$, it changes to type-T in $f_W$.
If $v_l$ is type-I in $f$, from condition 5(b) and 6(c) of Definition~\ref{def:augmenting}, there are three possibilities:
(1) $f(e_h)=1$ and $\{f(e_{h+1}), f(e_l)\}=\{0,1\}$;
(2) $f(e_h)=1$ and $f(e_{h+1})=f(e_l)=0$; or
(3) $f(e_h)=0$ and $f(e_{h+1})=f(e_l)=1$.
In the first case, $v_l$ changes to type-H in $f_W$, and in the other two cases, it changes to type-T.
From condition 5 of Definition~\ref{def:augmenting}, each vertex $v\in\{v_{h+1},\ldots,v_{l-1}\}$ must be type-O or type-I in $f$.
If $v_i$ is type-O in $f$, it changes to type-H in $f_W$.
If $v_i$ is type-I in $f$, there are two possibilities: $f(e_i)=f(e_{i+1})=1$ or $\{f(e_i),f(e_{i+1})\}=\{0,1\}$.
In the former case, $v_l$ changes to type-H in $f_W$, and in the latter case, it changes to type-T.

Now, let us count the number of type-T vertices in the created half-integral cycle $(v_h,e_{h+1},\ldots,e_l,v_l=v_h)$.
On this cycle, let $\alpha$ be the number of segments of consecutive edges of value one in $f$.
Remember that a vertex $v_i\in\{v_{h+1},\ldots,v_{l-1}\}$ becomes type-T in $f_W$ if and only if it satisfies $\{f(e_i),f(e_{i+1})\}=\{0,1\}$;
in other words, vertices on endpoints of consecutive edges of value one become type-T in $f_W$.
If $f(e_h)=1$ and $\{f(e_{h+1}),f(e_l)\}=\{0,1\}$, $v_l$ becomes type-H in $f_W$ and $2\alpha-1$ vertices in $\{v_{h+1},\ldots,v_{l-1}\}$ become type-T in $f_W$.
Otherwise, $v_l$ becomes type-T in $f_W$ and $2\alpha$ vertices in $\{v_{h+1},\ldots,v_{l-1}\}$ become type-T in $f_W$.
Thus, in both cases, the third condition of Definition~\ref{def:basic} is satisfied.

Finally, let us consider the case where $v_l$ is type-H or type-T in $f$.
If $v_l$ is type-T and $f(e_l)=1$, it changes to type-O in $f_W$.
Otherwise, it changes to type-I in $f_W$.
The other vertices on the half-integral cycle of $v_l$ changes from type-T to type-I, and from type-H to type-O or type-I.
\end{proof}

Now, we give an algorithm to compute an $f$-augmenting walk (see Algorithm~\ref{alg:augment_search}).
First, we initialize a set $S$ and a table $\mathrm{prev}:V\rightarrow E\cup\{\epsilon\}$.
The set $S$ stores vertices we need to process and initialized to $\{s\}$.
We ensure that only the vertex $s$ and vertices of type-O or type-I are stored in $S$.
The table $\mathrm{prev}(v)$ represents an edge to the parent of $v$ in the search tree and initialized to the dummy edge $\epsilon$,
which indicates that the vertex is not visited (or the vertex is the root $s$).
Then, while $S$ is not empty, pick up an arbitrary vertex $u$ from $S$ and process each incident edge $e=uv\in\delta(u)$ as described below.
If $S$ becomes empty, the algorithm returns NO.

First, we check whether the edge $e=uv$ is valid by testing the following three conditions.
If $e=\mathrm{prev}(u)$, because we have already processed this edge, we skip it.
If $e$ is incident to $s$ and $f(e)=1$, because such an edge cannot be used in an augmenting walk, we skip it.
Note that, when $v=s$, at least one of these two conditions are satisfied.
Similarly, if $u$ is type-I and both of $f(\mathrm{prev}(u))$ and $f(e)$ are zero, because we cannot use both of $\mathrm{prev}(u)$ and $e$ simultaneously,
we skip it.

If $v$ is type-H, or type-T, we return the walk from $s$ to $v$ in the search tree by using the table $\mathrm{prev}$.
If $\mathrm{prev}(v)=\epsilon$, we set $\mathrm{prev}(v)=e$ and insert it to $S$.
If $v$ is already visited and $v$ is type-O, let $w$ be the lowest common ancestor of $u$ and $v$ in the search tree.
Then, we return the walk obtained by going down from $s$ to $u$ along the search tree, jumping from $u$ to $v$ by the edge $e$,
and then by going up from $v$ to $w$ along the search tree.
If $v$ is already visited and $v$ is type-I, we basically do the same; however, we need one additional constraint.
If both of $f(\mathrm{prev}(v))$ and $f(e)$ are zero, the walk created as above does not satisfy the condition 6(c) of Definition~\ref{def:augmenting}; thus, we skip the edge without returning the walk.

\begin{algorithm}[t]
\caption{Algorithm for computing an $f$-augmenting walk}
\label{alg:augment_search}
\begin{algorithmic}[1]
\Procedure{FindAugmentingWalk}{$G,s,f$}
	\State $S\gets\{s\}$
	\State $\mathrm{prev}(v)=\epsilon$ for all $v\in V$
	\While{$S\neq\emptyset$}
		\State Pick a vertex $u\in S$ and remove $u$ from $S$
		\For{$e=uv\in\delta(u)$}
			\If{$e=\mathrm{prev}(u)$}
				\textbf{continue}
			\EndIf
			\If{$e\in\delta(s)$ and $f(e)=1$}
				\textbf{continue}
			\EndIf
			\If{$u$ is type-I and $f(\mathrm{prev}(u))=f(e)=0$}
				\textbf{continue}
			\EndIf
			\If{$v$ is type-H or type-T}
				\State $\mathrm{prev}(v)\gets e$
				\State \Return the walk from $s$ to $v$ along the search tree\label{line:augment_search:walk}
			\ElsIf{$\mathrm{prev}(v)=\epsilon$}
				\State $\mathrm{prev}(v)\gets e$; $S\gets S\cup\{v\}$
			\ElsIf{$v$ is type-O or $f(\mathrm{prev}(v))+f(e)\geq 1$}
				\State \Return the walk $s\rightarrow u\rightarrow v\rightarrow w$ along the search tree\label{line:augment_search:walk2}
			\EndIf
		\EndFor
	\EndWhile
	\State \Return NO
\EndProcedure
\end{algorithmic}
\end{algorithm}

From the construction of our algorithm, we obtain the following lemma.
\begin{lemma}
A walk returned by Algorithm~\ref{alg:augment_search} is an $f$-augmenting walk.
\end{lemma}

Note that this lemma does not say that Algorithm~\ref{alg:augment_search} returns an $f$-augmenting walk whenever there exists an $f$-augmenting walk;
it only says that if the algorithm returns a walk, it is an $f$-augmenting walk, and the algorithm might return NO even when there exists an $f$-augmenting walk.
We now show that, if the algorithm returns NO, we can construct an $s$-cycle cover $x$ whose size is equal to the size of $f$.
From Lemma~\ref{lem:basic_atmost} and the LP duality of $s$-cycle packings and $s$-cycle covers, the size of a basic $s$-cycle packing is always at most the size of an $s$-cycle cover.
Therefore, this equality implies that the current basic $s$-cycle packing $f$ is the maximum and the constructed $s$-cycle packing $x$ is the minimum.
This also implies that when the algorithm returns NO, there are no $f$-augmenting walks.

To construct such an $s$-cycle cover $x$, we first prove a property of the table $\mathrm{prev}$.
We call a vertex $v\in V$ \emph{reachable} if $v=s$ or $\mathrm{prev}(v)\neq\epsilon$.
For each edge $e\in\delta(s)$ with $f(e)=1$, by following edges of value 1 from $e$, we can obtain a simple cycle returning to $s$ or a simple path to a type-T vertex.
We denote such a cycle or a path by $W_e$.
Note that when $W_e$ is a cycle, $W_e=W_{e'}$ for another edge $e'\in\delta(s)$.

\begin{lemma}\label{lem:property_prev}
If Algorithm~\ref{alg:augment_search} returns NO, exactly one of the following holds for each edge $e\in\delta(s)$ with $f(e)=1$:
\begin{enumerate}
  \item $\mathrm{prev}(v)=\epsilon$ for any vertex $v\in V(W_e)$;
  \item $W_e$ is a cycle, all the vertices on $W_e$ are reachable, and exactly one vertex $v\in V(W_e)\setminus\{s\}$ satisfies $\mathrm{prev}(v)\not\in E(W_e)$.
\end{enumerate}
\end{lemma}
\begin{proof}
Let us assume that $\mathrm{prev}(v)\neq\epsilon$ holds for at least one of $v\in V(W_e)$.
If a type-I vertex is reachable, the algorithm makes its adjacent type-I vertices connected by edges of value one reachable.
Thus, all the vertices on $W_e$ are reachable.
If $W_e$ is a path, the algorithm makes the type-T endpoint of the path reachable, and therefore the algorithm returns an $f$-augmenting walk at line~\ref{line:augment_search:walk}.
Thus, $W_e$ must be a cycle.
Let $W_e=(v_0=s,e_1,\ldots,v_l=s)$ be the cycle.
If there exists an integer $i\in\{2,\ldots,l-1\}$ such that $\mathrm{prev}(v_{i-1})\neq e_i$ and $\mathrm{prev}(v_i)\neq e_i$, the algorithm returns an $f$-augmenting walk at line~\ref{line:augment_search:walk2}.
Thus, the edges $\{e_2,\ldots,e_{l-1}\}$ must be contained in the set $\{\mathrm{prev}(v_1),\ldots,\mathrm{prev}(v_{l-1})\}$.
Because all the $e_i$'s are distinct, this implies that exactly one of $i\in\{1,\ldots,l-1\}$ satisfies $\mathrm{prev}(v_i)\not\in \{e_2,\ldots,e_{l-1}\}$.
Because $\mathrm{prev}(v)$ cannot be $e_1$ nor $e_l$, we have $\mathrm{prev}(v_i)\not\in E(W_e)$.
\end{proof}

When Algorithm~\ref{alg:augment_search} returns NO, by using the obtained table $\mathrm{prev}$, we construct a function $x: V\rightarrow\{0,\frac{1}{2},1\}$ as follows.
For each edge $e=su\in\delta(s)$ with $f(e)=1$, if $W_e$ is a cycle satisfying the second condition of Lemma~\ref{lem:property_prev},
we set $x(v)=1$ for the unique vertex $v$ satisfying $\mathrm{prev}(v)\not\in E(W_e)$.
Otherwise, we set $x(u)=\frac{1}{2}$.
If $x(u)$ is already set to $\frac{1}{2}$, e.g., $W_{e_1}=W_{e_2}=(s,e_1,u,e_2,s)$ for a double edge $\{e_1,e_2\}$, we set $x(u)=1$.

\begin{lemma}\label{lem:dual}
If Algorithm~\ref{alg:augment_search} returns NO, the function $x$ is a minimum $s$-cycle cover.
\end{lemma}
\begin{proof}
First, we show that $x$ is an $s$-cycle cover.
Let $C=(v_0=s,e_1,\ldots,v_l=s)$ be an $s$-cycle.
If $f(e_1)=f(e_l)=1$ and both of $W_{e_1}$ and $W_{e_l}$ satisfy the first condition of Lemma~\ref{lem:property_prev}, we have $x(C)\geq \frac{1}{2}+\frac{1}{2}=1$.
Otherwise, there are two cases: (1) $f(e)=0$ for at least one of $e\in\{e_1,e_l\}$ or (2) $f(e_1)=f(e_l)=1$ and $W_e$ satisfies the second condition of Lemma~\ref{lem:property_prev} for at least one of $e\in\{e_1,e_l\}$.

(Case 1)
If $f(e_1)=0$ holds (the case of $f(e_l)=0$ is symmetric), the vertex $v_1$ is reachable.
If a vertex $v_i$ is reachable and type-O, the vertex $v_{i+1}$ is also reachable.
If all the vertices $\{v_1,\ldots,v_{l-1}\}$ are type-O, the algorithm returns an $f$-augmenting walk at line~\ref{line:augment_search:walk2},
and if there exists a reachable type-H or type-T vertex, the algorithm returns an $f$-augmenting walk at line~\ref{line:augment_search:walk}.
Therefore, there must exist a reachable type-I vertex on $C$.
Let $v_i$ be the first such vertex and let $W_e$ be the value-one cycle containing $v_i$.
Note that $v_i$ must be contained in a cycle because otherwise it is connected to a type-T vertex by edges of value one and this type-T vertex becomes reachable, which is a contradiction.
If $\mathrm{prev}(v_i)\in E(W_e)$, the algorithm returns an $f$-augmenting walk at line~\ref{line:augment_search:walk2}.
Thus, we have $x(C)\geq x(v_i)=1$.

(Case 2)
If $f(e_1)=f(e_l)=1$ and $W_{e_1}$ satisfies the second condition of Lemma~\ref{lem:property_prev} (the case of $W_{e_l}$ is symmetric), all the vertices on $W_{e_1}$ are reachable.
Let $v_a$ be the first vertex on $C$ satisfying $f(e_{a+1})=0$.
If there is no such vertex, $W_e$ is completely contained in $C$, and therefore, we have $x(C)\geq x(W_{e_1})=1$.
If $\mathrm{prev}(v_a)\not\in E(W_{e_1})$, we have $x(C)\geq x(v_a)=1$.
Otherwise, $v_{a+1}$ is reachable.
Thus, by the same argument as in case 1, there must exist a reachable type-I vertex $v_b$ on $C$ for $b>a$.
Let $W_{e'}$ be the value-one cycle containing $v_b$.
If $\mathrm{prev}(v_b)\in E(W_{e'})$, the algorithm returns an $f$-augmenting walk at line~\ref{line:augment_search:walk2}.
Thus, we have $x(C)\geq x(v_b)=1$.

From Lemma~\ref{lem:property_prev}, the vertex $v$ satisfying $\mathrm{prev}(v)\not\in E(W_e)$ is unique for each cycle $W_e$.
Therefore, the size of $x$ is $\frac{1}{2}f(\delta(s))$, which is equal to the size of $f$.
Thus, $x$ is a minimum $s$-cycle cover.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main2}]
Because each augmentation increases the size of $f$ by at least $\frac{1}{2}$, after $k+1$ steps, we can obtain a half-integral minimum $s$-cycle cover of size at most $\frac{k}{2}$,
or conclude that there are no $s$-cycle covers of size at most $\frac{k}{2}$.
Because Algorithm~\ref{alg:augment_search} runs in $O(m)$ time, the total running time is $O(km)$.
\end{proof}

Figure~\ref{fig:execute} illustrates an example execution of the augmenting-path algorithm.
Solid orange-colored lines denote edges of value one and dotted orange-colored lines denote edges of value $\frac{1}{2}$.
In each step, the algorithm searches an augmenting walk, which is denoted by arrows in the figure, and augments along the obtained walk.
Finally, when the algorithm fails to find an augmenting walk (see the lower left figure), only vertices $\{s,1,2,4\}$ are reachable from $s$.
The $\mathrm{prev}$ of vertex $1$ is edge $1$--$2$, which is contained in the cycle $s$--$1$--$2$--$s$, and the $\mathrm{prev}$ of vertex $2$ is edge $4$--$2$, which is not contained in the cycle.
Thus, we can construct a function $x$ such that $x(2)=1$, $x(3)=x(5)=x(6)=x(7)=x(8)=\frac{1}{2}$, and $x(1)=x(4)=0$.
This is actually an $s$-cycle cover of the graph, and the size of $x$ is $\frac{7}{2}$, which is equal to the size of the constructed basic $s$-cycle packing.
Therefore, $x$ is the minimum $s$-cycle cover.
\begin{figure}[t]
  \centering
  \includegraphics[scale=0.6]{fig/4-crop.pdf}
  \caption{Example execution of the algorithm}
  \label{fig:execute}
\end{figure}

\section{Linear-time Quadratic-size Kernel}\label{sec:linear}

In this section, we improve the running time of the quadratic-size kernel presented in Section~\ref{sec:simple} to $O(k^4 m)$.
By using the $O(km)$-time algorithm for computing the minimum $s$-cycle cover presented in Section~\ref{sec:flower}, each iteration can be done in $O(km)$ time.
However, because the number of iterations is only bounded by $O(m)$, the total running time becomes $O(km^2)$.
We show that, by a slight modification to Algorithm~\ref{alg:simple}, the number of iteration can be bounded by $O(k^3)$;
thus, the total running time becomes $O(k^4 m)$.

We add the following two rules just after line~\ref{line:small_degree} of Algorithm~\ref{alg:simple}.
\begin{itemize}
  \item If there is a vertex $v$ incident to more than $k$ double edges, remove $v$, decrement $k$, and continue the iteration.
  \item If there are more than $k^2$ double edges, return NO.
\end{itemize}

The safeness of these two rules can be shown as follows.
Because any feedback vertex set must contain at least one of the two end points of a double edge,
if there is a vertex $v$ incident to more than $k$ double edges, it must be contained in any feedback vertex set of size at most $k$.
After applying this rule, each vertex can be incident to at most $k$ double edges.
Therefore, any feedback vertex set of size $k$ can delete at most $k^2$ double edges.
Thus, if there are more than $k^2$ double edges, there are no feedback vertex sets of size at most $k$.

For bounding the number of iterations, we use the following lemma.
\begin{lemma}\label{lem:no_double}
For a graph $G=(V,E)$ of minimum degree at least three, a vertex $s\in V$, and a half-integral minimum $s$-cycle cover $x$, if $2x(V)<d_G(s)$ holds, then $x^{-1}(1)\neq\emptyset$.
\end{lemma}
\begin{proof}
From Lemma~\ref{lem:degree_bound}, for a graph $G'$ obtained by applying the $s$-cycle cover reduction, it holds that $d_{G'}(s)\leq 2x(V)$.
When $x^{-1}(1)=\emptyset$, the reduction inserts no new edges and only removes the bridges of $G$ connecting $s$ and tree components of $G-s$.
Because the graph $G-s$ has minimum degree at least two, it has no tree components.
Thus, we have $G'=G$, which is a contradiction.
\end{proof}

Now, we can prove the upper bound on the number of iterations.
\begin{lemma}\label{lem:linear}
The modified Algorithm~\ref{alg:simple} stops in $O(k^3)$ iterations.
\end{lemma}
\begin{proof}
We color each double edge red or blue.
Initially, all the double edges are blue, and after applying the $s$-cycle cover reduction, we color all the double edges incident to $s$ red
(not only newly inserted double edges but also blue colored edges are recolored to red).
The other double edges, which are created by the deletion of degree two vertices in the basic reductions, are colored blue.
Let $\alpha$ denote the number of red double edges and $\beta$ denote the number of vertices of degree larger than $2k$ and incident to at least one red double edge.
Let $k_0$ be the initial value of $k$ and $\phi$ be a potential defined as $\phi=2k_0^2k+4k_0k+3k-2\alpha+\beta$.
Observe that, because red double edges are created only by the $s$-cycle cover reduction, each vertex can be incident to at most $k_0+1$ red double edges,
and that the number of red double edges is always at most $k_0^2+k_0$
(at most $k_0^2$ edges before applying the $s$-cycle cover reduction and the reduction can create at most $k_0$ red double edges).

Initially, there are no red edges; thus, the initial potential is $2k_0^3+4k_0^2+3k_0=O(k_0^3)$.
If $\phi$ becomes negative, we have $k<0$ or $\alpha>k_0^2k\geq k^2$.
Thus, the algorithm returns NO.

When $k$ is decremented, $\alpha$ can decrease by at most $k_0+1$.
Because there are at most $k_0^2+k_0$ red double edges, $\beta$ can increase by at most $2k_0^2+2k_0$.
Thus, $\phi$ decreases by at least
\[
2k_0^2k+4k_0k+3k-2\alpha+\beta-(2k_0^2(k-1)+4k_0(k-1)+3(k-1)-2(\alpha-k_0-1)+(\beta+2k_0^2+2k_0))\geq 1
\]

When applying the $s$-cycle cover reduction, if the reduction creates $c\enspace (\geq 1)$ new red double edges, $\alpha$ increases by $c$ and $\beta$ can increase by at most $c$.
Thus, $\phi$ decreases by at least
\[
2k_0^2k+4k_0k+3k-2\alpha+\beta-(2k_0^2k+4k_0k+3k-2(\alpha+c)+(\beta+c))\geq c\geq 1
\]
After applying the $s$-cycle cover reduction, from Lemma~\ref{lem:no_double}, $s$ is incident to at least one double edge.
Thus, if the reduction does not create any new red double edges, $s$ must be incident to at least one red double edge before the reduction.
From~\ref{lem:degree_bound}, the degree of $s$ becomes at most $2k$ after the reduction.
Therefore $\beta$ decreases by one; thus, $\phi$ decreases by one.

Now, we have shown that each iteration decreases the potential $\phi$ by at least one.
Because $\phi$ is initially $O(k^3)$ and is always non-negative, the number of iterations is $O(k^3)$.
\end{proof}

	\bibliographystyle{abbrv}

redpajama_set_name: RedPajamaArXiv


text:
Home Admissions
Why Apply to GWSB?
Students at the George Washington University School of Business (GWSB) are at the forefront of smarter business — business that considers its impact on the world as well as the bottom line. In addition to rigorous training in traditional business competencies, every one of our programs is infused with ethical leadership, sustainability, social responsibility and corporate citizenship, all taught from a global perspective.
#1 region in the country for fastest-growing private companies
#1 city in the country for producing and attracting business founders
Ranked #1 new tech hot spots
Ranked #3 for female entrepreneurs in the country
Apply to a Graduate Program
In the heart of one of the most dynamic and influential cities in the world, the GW School of Business puts you in touch with the power to challenge ideas, asks you to look ahead, and prepares you to lead the way. Our graduate programs not only ground students in theory and research, but also connect them to the realities of their profession.
Through theoretical and applied learning, our programs combine curriculum from accounting, finance, project management, and other traditional business concentrations with industry specific knowledge. You will gain experience on and off campus, through laboratory work, classroom-based courses, and online classes, and be given access to a large number of networking opportunities through GWSB's alumni and student organizations. Because these days, the last thing any of us should do is conduct business as usual.
View Graduate Admissions Information & Learn How to Apply
Explore Tuition and Financial Planning
Find Assistantship and Fellowship Opportunities
Visit GW's Office of Graduate Admissions
Apply to an Undergraduate Program
Our students gain an understanding and appreciation of how business can lead to smarter solutions. With this mindset, they are driven to be socially conscious and to develop the skills to conduct both influential and important work throughout their careers.
The future of business education is rooted in global, societal, and political needs, and is measured by its global impact. At the GW School of Business, we're preparing our students to confront challenges, while making organizations more competitive and responsible.
GWSB students are educated in the liberal arts alongside concentrated study in business concepts and practice. They work collaboratively, conduct independent and team research, volunteer throughout Washington, D.C. and at campus events, and learn to manage their future careers.
View Undergraduate Admissions Information
Find Scholarship Opportunities
Visit GW's Office of Undergraduate Admissions

redpajama_set_name: RedPajamaCommonCrawl


Stop by your nearby Firestone Complete Auto Care for the best 1991 Volvo 940 tires at a great price. Explore our wide range of 1991 940 tires and compare by tire brand, size, price, and type. Whether you're shopping for tires that will maximize your fuel-efficiency or vehicle speed, you'll find the right ones for your vehicle and budget. Conveniently shop online and schedule an appointment with one of our certified technicians today! We're open late and on weekends, so when you need new tires, we're ready!


text:
The Simpsons Season 30 Episode 13
Homer angers Marge by binging their favorite show without her, and has to pick up a new skill in order to make amends. Meanwhile, Bart prepares to compete in "Krusty's Holiday Trample".
Serie: The Simpsons
Episode Title: I'm Dancing as Fat as I Can
Air Date: 2019-02-10
TMDb: 10
For 10 years Sally has lived a dull suburban life with David. But on the night he asks her to marry him, Sally has a crisis and embarks on a…
Status: Returning Series
Watch Series
TMDb: 6.4
43,45 min
Ichabod Crane is resurrected and pulled two and a half centuries through time to unravel a mystery that dates all the way back to the founding fathers.
Status: Canceled
Genre: Drama, Mystery, Sci-Fi & Fantasy
Back to Life
After 10 years in prison, a woman returns to her small hometown wondering if anyone will let her move on.
In the near future a family must make difficult decisions as they balance staying together with trying to survive. They live in Los Angeles, which has been occupied by a…
Eric Beaumont's crisis negotiator team is brought in to save lives and resolve the most difficult kidnap and ransom cases when no one else can.
In a small rust belt town in post-recession America, a one-dollar bill changing hands connects a group of characters involved in a shocking multiple murder.
Inexperienced Otis channels his sex therapist mom when he teams up with rebellious Maeve to set up an underground sex therapy clinic at school.
Eps173
After a serial killer imitates the plots of his novels, successful mystery novelist Richard "Rick" Castle receives permission from the Mayor of New York City to tag along with an…
Follow Sarah Silverman as she looks to connect with people who may not agree with her personal opinions through honesty, humor, genuine interest in others and not taking herself too…
Genre: Comedy, Talk
When a controversial cult leader builds a utopian city in the Oregon desert, conflict with the locals escalates into a national scandal.
Status: Ended
The impossible-to-believe, often absurd, true stories about the most unexpected women — PTA moms, country-club chairwomen, and more — who took big risks, pocketed big cash and then served hard…
John Adams is a 2008 American television miniseries chronicling most of U.S. President John Adams' political life and his role in the founding of the United States. Paul Giamatti portrays…
Putlocker new site 2018 - Free movies online
Freely available to watch all movies and tv-shows online in HD resolution on your PC, Smartphone or TV without additional software. No annoying advertising or registration, no broken links. Bigger movie database than netflix and netu. Just press play and enjoy. Movies on this website are hosted on third party servers openload and streamango.
Copyright © 2018 Putlocker.io All Rights Reserved
Putlocker Watch Movies Online GoMovies Watch Free Movies Putlockers Watch Series Online


Apr. 7, 2019 5:40 p.m.
A new play from the Theatre Kelowna Society invites audiences to dive into a world of espionage and intrigue with a touch of murder.
Black Coffee by Agatha Christie sports a cast of theatre veterans and some new faces to Theatre Kelowna.
Graham Daley takes on the role of Christie's signature detective as Hercule Poirot in this classic whodunit.
"The conviction of the characters drives the plot of the story. This show gives opportunity to really see what these people are made of in their world," said Tate Adrian, director.
The show takes place in 1929 and centres on a significant discovery that renowned scientist Sir Claude Amory wants to keep out of the hands of England's enemies. Can he get his secret formula to the British Officials before his beans are roasted? Can the newlyweds Richard and Lucia stand the strain on their relationship as they're confronted with a host of envy, lies and strange visitors in a time of dread? It's a superbly crafted whodunit with endless red herrings, subplots of infamous spies and an astonishingly prophetic story line about weapons created through 'bombarding the atom'. One of Christie's most gripping country house murder mysteries.
"The truth is never horrible, only interesting," said Agatha Christie.
Tickets are available at rotarycentreforthearts.com The play will run April 17 to 18 at 2 p.m. and 7:30 p.m.


text:
You are here:Home-DSE, News from Melanesia, Pasifika Rising News, Vatu Mauri Consortium-CSOs take on corruption
Civil Society Organisation (CSO) representatives last week travelled to Honiara from across the nation to develop a powerful policy position on corruption and good governance.
"Corruption is eating our beautiful country," said Inia Barry, Chairman of the Development Services Exchange.
"This is the number one issue affecting Pacific Island nations as a whole," he added.
"There are many other issues that we are working on, but unless we stop corruption, then things will never change."
The national CSO network has agreed on three key solutions and recommendations, which they will be advocating for at the regional level in the lead up to this year's Pacific Island Forum (PIFs) leaders meeting in February 2018.
1. Develop mechanisms to monitor the regional good governance framework – Establish a monitoring agency and include support budget for the implementation of the agency action plan.
2. Develop Regional Anti-Corruption convention – Develop one convention document that summarizes the Pacific Islands Forum Governance framework and the United Nation Convention on Anti-Corruption (UNCAC)
3. Accountable Gender & Youth budgeting – 20% of fixed gender and youth accountable national budgets across pacific countries.
Mr Barry said this important work builds on PIFS phase 1 workshop in 2016 "Making regional policies accessible to CSOs".
He said during the workshops CSOs identified and prioritised key themes such as corruption, good governance and indigenous rights as priorities issues they would like to collectively advocate at national and regional level.
The avenues has also supported CSOs to better understand regional framework and spaces to be able to bring their agendas to the leaders platforms for political commitment
The key CSOs coordinated by Development Service Exchange (DSE) were also part of the hugely successful "Bring It Back" campaign that fought to bring the Anti-Corruption Bill back to parliament late last year.
"My dream is that Solomon Islanders in particular women, girls, children including people with special needs have equal rights and opportunities and, are able to access quality health services and education," said Julia Fationo-Cutforth of Oxfam in Solomon Islands.
"Bad governance and corruption is the underlying cause of unequal distribution of resources resulting in poor public services in our urban and rural communities," she added.
This important work forms part of EU funded 'Making Regional Policy Accessible for Non-State Actors' program, led by Oxfam in the Pacific and happening in Vanuatu and Solomon Islands and Oxfam's Herem Staka Vois program, funded by Australian Aid.


Last weekend was the Hypnosis Motivation Institute (HMI) graduation ceremony. Out in the Malibu hills, a new crop of hypnotherapists celebrated their studies and accomplishments.There was food and drink and dancing. But, more importantly, there was a ritual marking completion, achievement and transition. The next morning, I woke up in the same bed as the day before and went about my day. I hadn't substantially changed from the day before. In fact, I still have a couple of classes and clinic hours to finish before I'm officially a graduate of the HMI hypnotherapy training program.
But the ceremony marked a change. I marched in robes, shook hands, accepted hugs, and was handed a rolled up piece of paper. I am different today. Waking up to a new life should happen every day.
In one way, it does, whether we acknowledge the fact or not. Rituals and ceremonies help us mark events and be able to say "yes" to the differences and change we are constantly undergoing in our lives. "My birthday is today so I am older" "We married each other and so now our relationship is different."
These ceremonies acknowledge the change while tricking us into thinking that change isn't occurring constantly. I'm not a better hypnotherapist today because I marched in my graduation ceremony. But I am a better hypnotherapist today then I was yesterday. Because I seek to welcome change into my life.
Every day I am becoming more comfortable with the new, healthier life into which I am moving.


text:
<< January >>
<< February >>
<< March >>
<< April >>
<< May >>
<< June >>
<< July >>
<< August >>
<< September >>
<< October >>
<< November >>
August 18 is the 230th day of the year (231st in leap years) in the Gregorian calendar. There are 135 days remaining until the end of the year.
1.1 Up to 1900
1.2 From 1901
2 Births
2.2 1901 – 1950
3 Deaths
4 Observances
Events[change | change source]
Up to 1900[change | change source]
1201 – The city of Riga in present-day Latvia is founded.
1487 - The Siege of Malaga comes to an end, with the taking of the city by Castilian and Aragonese forces.
1572 – Henry IV of France and Margaret of Valois marry.
1587 - Virginia Dare, granddaughter of Governor John White of the Colony of Roanoke, Virginia, becomes the first child of English parents to be born in the Americas. Exactly three years later, White returns from a supply trip to England to find that everyone from the colony had disappeared.
1612 - The trial of the Pendle witches, one of England's most well-known witch trials, begins at Lancaster Assizes.
1634 - Urbain Grandier, accused and convicted of sorcery, is burned alive in Loudon, France.
1783 - A huge fireball meteor is seen across Great Britain as it passes over the east coast.
1807 - Napoleon Bonaparte creates the Kingdom of Westphalia and installs his brother Jerome Bonaparte as its king.
1864 - American Civil War: Battle of Globe Tavern.
1868 - French astronomer Pierre Janssen discovers helium.
1870 - Franco-Prussian War: Battle of Gravelotte.
1877 – Mars' moon Phobos is discovered by Asaph Hall.
1891 – A major hurricane strikes Martinique, killing around 700 people.
From 1901[change | change source]
1917 – The city of Thessaloniki in present-day Greece is largely destroyed by fire.
1920 - The Nineteenth Amendment to the United States Constitution is ratified, guaranteeing women the right to vote.
1940 - World War II: Battle of Britain's "Hardest Day", on which both sides suffer their heaviest losses.
1945 - Sukarno becomes President of Indonesia, a day after declaring Indonesia independent from the Netherlands.
1946 - The Vergarolla explosion in Croatia kills 70 people.
1948 - The Australian cricket team completes a 4-0 Ashes series win over England during its undefeated "Invincibles" tour.
1950 - Julien Lahaut, chairman of the Belgian Communist Party, is murdered by far-right extremists.
1958 - Vladimir Nabokov's controversial novel Lolita is published in the United States.
1958 - Brojen Das from Bangladesh becomes the first Asian to swim across the English Channel.
1959 – The Mini automobile goes on sale.
1960 - The combined oral contraceptive pill becomes available in the United States.
1963 - James Meredith becomes the first African American to graduate from the University of Mississippi.
1965 - Vietnam War: Operation Starlite begins - US marines destroy a Viet Cong stronghold on the Van Tuong peninsula in the major American ground battle of the war.
1966 - Vietnam War: The Battle of Long Tan ensues after a patrol from the 6th Battalion, Royal Australian Regiment clashes with a Viet Cong force in Phuoc Tuy province.
1971 - Vietnam War: Australia and New Zealand decide to withdraw their troops from Vietnam.
1976 - The Soviet Luna 24 probe lands on the Moon.
1976 - In the Korean Demilitarized Zone at Panmunjom, the axe murder incident results in the deaths of two US soldiers.
1977 – Steve Biko is arrested. His death a few weeks later, at the hands of the police, makes him a symbol of the brutality of South Africa's apartheid system.
1983 – Hurricane Alicia hits Texas, killing 22 people.
1988 – George H. W. Bush makes his campaign promise Read my lips, no new taxes during a speech in Louisiana.
1989 - Leading Presidential hopeful Luis Carlos Galan is murdered near Bogota, Colombia.
1991 – The August Coup against Mikhail Gorbachev begins.
1994 - A magnitude 5.9 earthquake kills 159 people in Algeria.
2005 – A massive power blackout hits the Indonesian island of Java, affecting around 100 million people.
2008 – Pervez Musharraf announces his resignation as President of Pakistan. Asif Ali Zardari succeeds him in September.
2017 - Two people are killed and several are injured in a stabbing attack in Turku, Finland.
2018 - The 2018 Asian Games, co-hosted by the cities of Jakarta and Palembang (in Indonesia), begin.
2018 - Former cricketer Imran Khan becomes Prime Minister of Pakistan.
Births[change | change source]
1414 - Jami, Persian poet (d. 1492)
1450 - Marko Marulic, Croatian poet (d. 1524)
1497 - Francesco Canovada Milano, Italian composer (d. 1543)
1587 – Virginia Dare, first child of English parents to be born in what is now the United States (d. before 1591)
1596 - Jean Bolland, Flemish painter (d. 1665)
1606 - Maria Anna of Spain (d. 1646)
1611 - Marie Louise Gonzaga, Queen Consort of Poland (d. 1667)
1657 - Ferdinando Galli-Bibiena, Italian architect and painter (d. 1743)
1685 – Brook Taylor, English mathematician (d. 1731)
1692 - Louis Henri, Duke of Bourbon (d. 1740)
1700 - Baji Rao I, Indian Emperor (d. 1740)
1748 - Pierre Sonnerat, French naturalist and explorer (d. 1814)
1750 – Antonio Salieri, Italian composer (d. 1825)
1774 – Meriwether Lewis, American explorer (d. 1809)
1786 - Jean Guillaume Lugol, French physician (d. 1851)
1792 – John Russell, 1st Earl Russell, Prime Minister of the United Kingdom (d. 1878)
1803 - Nathan Clifford, 19th United States Attorney General (d. 1881)
1807 - Charles Francis Adams, Jr., American lawyer, politician, diplomat and writer (d. 1886)
1819 - Grand Duchess Maria Nikolaevna of Russia (d. 1876)
1822 - Isaac P. Rodman, American general (d. 1862)
1830 – Emperor Franz Joseph I of Austria (d. 1916)
1855 - Alfred Wallis, British painter (d. 1942)
1856 - Ahad Ha'am, Hebrew essayist and Zionist thinker (d. 1927)
1857 - Eusebius Mandyczewski, Austrian composer and musicologist (d. 1929)
1859 – Anna Ancher, Danish painter (d. 1935)
1870 - Lavr Kornilov, Russian general (d. 1918)
1875 – King Prithvi of Nepal (d. 1911)
1877 - Jimmy Michael, Welsh cyclist (d. 1904)
1879 - Aleksandr Rodzyanko, Russian general (d. 1970)
1879 - Manuel Arce y Ochoterena, Spanish cardinal, Archbishop of Tarragona (d. 1948)
1882 - Herman Groman, American runner (d. 1954)
1883 - Sidney Hatch, American runner (d. 1966)
1890 – Walther Funk, Nazi politician (d. 1960)
1892 - Hal Foster, Canadian-American illustrator (d. 1982)
1893 - Burleigh Grimes, American baseball player and manager (d. 1985)
1896 - Jack Pickford, Canadian-American actor (d. 1933)
1900 - Vijaya Lakshmi Pandit, Indian politician ans diplomat (d. 1990)
1901 – 1950[change | change source]
1901 - Arne Borg, Swedish swimmer (d. 1987)
1901 - Jean Guitton, French philosopher and writer (d. 1999)
1904 – Max Factor, Polish-born cosmetics entrepreneur (d. 1996)
1908 - Edgar Faure, French politician and historian (d. 1988)
1908 - Sam English, Irish footballer (d. 1967)
1911 - Amelia Boynton Robinson, American activist (d. 2015)
1912 – Ertugrul Osman, head of the Ottoman dynasty (d. 2009)
1913 - Romain Maes, Belgian cyclist (d. 1983)
1915 - Joseph Arthur Ankrah, leader of Ghana (d. 1992)
1916 - Neagu Djuvara, Romanian historian, journalist and diplomat (d. 2018)
1916 - Don Keefer, American actor (d. 2014)
1917 – Caspar Weinberger, American politician (d. 2006)
1919 – Wally Hickel, American politician, 2nd and 8th Governor of Alaska (d. 2010)
1920 - Shelley Winters, American actress (d. 2006)
1921 - Lydia Litvyak, Soviet pilot (d. 1943)
1921 - Zdzislaw Zigulski, Jr., Polish art historian (d. 2015)
1922 – Alain Robbe-Grillet, French writer and movie maker (d. 2008)
1924 - Julien Bogaert, Belgian cartoonist (d. 2018)
1925 – Brian Aldiss, British science-fiction writer (d. 2017)
1927 – Rosalynn Carter, former First Lady of the United States
1929 - Hugues Aufray, French singer
1930 - Bo Hi Pak, South Korean church leader
1930 - Liviu Librescu, Romanian-American scientist (d. 2007)
1931 - Bramwell Tillsley, 14th General of the Salvation Army
1931 - Hans van Mierlo, Dutch politician (d. 2010)
1932 - Luc Montagnier, French microbiologist
1933 – Just Fontaine, French footballer
1933 – Roman Polanski, movie director
1934 - Roberto Clemente, Puerto Rican baseball player (d. 1972)
1934 - Ronnie Carroll, Northern Irish singer, entertainer and political candidate (d. 2015)
1935 – Hifikepunye Pohamba, 2nd President of Namibia
1935 - Rafer Johnson, American athlete and actor
1936 - Gulzar, Indian director, producer and songwriter
1936 – Robert Redford, American actor
1939 – Johnny Preston, American singer (d. 2011)
1940 - Stanley Johnson, British author and politician, father of Boris Johnson
1941 – Mohamed Ghannouci, former Prime Minister of Tunisia
1941 - Christopher Jones, American actor (d. 2014)
1943 - Norma Pons, Argentine actress (d. 2014)
1943 – Gianni Rivera, Italian footballer and politician
1943 – Roberto Rosato, Italian footballer (d. 2010)
1943 - Carl Wayne, British singer and actor (d. 2004)
1945 - Paula Danziger, American author (d. 2004)
1950 - Dennis Elliott, English drummer and sculptor
1952 – Patrick Swayze, American actor, singer and dancer (d. 2009)
1952 - Ricardo Villa, Argentine footballer
1952 - Mohammad Sarwar, British-Pakistani politician, former Glasgow MP and two-time Governor of the Punjab.
1953 - Sergio Castellitto, Italian actor, screenwriter and director
1954 - Umberto Guidoni, Italian astronaut
1954 - Rustem Khamitov, Russian politician
1957 – Denis Leary, American actor
1957 - Carole Bouquet, French actress and model
1957 - Harald Schmidt, German television presenter
1958 - Reg E. Cathey, American actor (d. 2018)
1958 - Sergei Treshchov, Soviet-Russian cosmonaut
1958 – Madeleine Stowe, American actress
1961 - Huw Edwards, Welsh journalist and news presenter
1961 - Timothy Geithner, 75th United States Secretary of the Treasury
1962 – Felipe Calderon, former President of Mexico
1963 - Billy Reid, Scottish footballer
1964 - Kenny Walker, American basketball player
1968 - Lee Seung-yeon, South Korean actress and talk show host
1969 – Edward Norton, American actor
1969 – Christian Slater, American actor
1970 - Malcolm-Jamal Warner, American actor
1971 – Aphex Twin, Irish-born musician
1972 - Masahiro Nakai, Japanese actor, singer and television presenter
1972 - Keiko Yamada, Japanese singer
1972 - Victoria Coren Mitchell, British television presenter and poker player
1973 - Paulo Schroeber, Brazilian guitarist (d. 2014)
1975 - Kaitlin Olson, American actress
1977 - Régine Chassagne, Canadian singer-songwriter (Arcade Fire)
1978 - Steve Chen, Taiwanese-American internet entrepreneur, co-founder of YouTube
1978 - Andy Samberg, American actor and comedian
1980 – Esteban Cambiasso, Argentine footballer
1981 – Dimitris Salpingidis, Greek footballer
1981 – Jan Frodeno, German triathlete
1982 – Florian Kringe, German footballer
1983 – Kris Boyd, Scottish footballer
1983 – Mika, Lebanese-English singer
1983 - Georgina Bardach, Argentine swimmer
1983 - Danny!, American rapper and producer
1984 – Robert Huth, German footballer
1985 - Bryan Ruiz Gonzalez, Costa Rican footballer
1986 – Ross McCormack, Scottish footballer
1987 - Tine Thing Helseth, Norwegian trumpeter
1987 - Mika Boorem, American actress
1988 - Luke Jackson, British author
1988 - Eggert Jónsson, Icelandic footballer
1988 - G-Dragon, South Korean rapper, singer-songwriter and record producer
1992 - Elizabeth Beisel, American swimmer
1992 - Amy Willerton, English model
1992 – Frances Bean Cobain, daughter of Kurt Cobain and Courtney Love
1993 - Maia Mitchell, Australian actress
1995 - Parker McKenna Posey, American actress
1997 - Renato Sanches, Portuguese footballer
Deaths[change | change source]
353 - Decentius, Roman usurper
440 - Pope Sixtus III
472 - Ricimer, Roman general (b. 405)
673 - Kim Yu-shin, Korean general (b. 595)
1095 – Olaf I of Denmark (b. 1050)
1227 – Genghis Khan, Mongol ruler (b. around 1160)
1258 - Theodore II Laskaris, Byzantine-Greek Emperor (b. 1222)
1276 - Pope Adrian V (b. 1520)
1503 – Pope Alexander VI (b. 1431)
1559 – Pope Paul IV (b. 1476)
1613 - Giovanni Artusi, Italian composer, theorist and thinker (b. 1540)
1620 – Wanli, Chinese emperor (b. 1563)
1642 – Guido Reni, Italian painter (b. 1775)
1645 - Eudoxia Streshneva, Russian Empress (b. 1608)
1648 - Ibrahim of the Ottoman Empire (b. 1615)
1707 - William Cavendish, 1st Duke of Devonshire, English soldier and politician (b. 1640)
1765 – Francis I, Holy Roman Emperor (b. 1708)
1842 – Louis de Freycinet, French explorer (b. 1779)
1850 – Honoré de Balzac, French writer (b. 1799)
1886 - Eli Whitney Blake, American inventor (b. 1795)
1919 - Joseph E. Seagram, Canadian businessman and politician (b. 1841)
1939 - Frank Wild, English explorer (b. 1873)
1940 – Walter Chrysler, American automobile executive (b. 1875)
1942 - Rafaela Ottiano, Italian-American actress (b. 1888)
1944 - Ernst Thalmann, German politician (b. 1886)
1945 – Subhas Chandra Bose, Indian independence fighter (b. 1897)
1950 - Julien Lahaut, Belgian politician (b. 1884)
1952 - Alberto Hurtado, Chilean priest, lawyer, writer and saint (b. 1901)
1963 - Clifford Odets, American playwright (b. 1906)
1968 - Cy Walter, American pianist (b. 1915)
1970 - Soledad Miranda, Spanish actress (b. 1943)
1981 - Anita Loos, American screenwriter and author (b. 1889)
1989 - Luis Carlos Galan, Colombian politician (b. 1943)
1990 – B. F. Skinner, American psychological theorist (b. 1904)
1992 – John Sturges, American director (b. 1910)
1994 – Richard Laurence Millington Synge, British chemist (b. 1914)
2003 - Tony Jackson, British musician (b. 1938)
2004 – Hiram Fong, United States Senator for Hawaii (b. 1906)
2005 - Gao Xiumin, Chinese actress (b. 1959)
2009 – Kim Dae Jung, President of South Korea (b. 1925)
2010 - Hal Connolly, American hammer thrower (b. 1931)
2010 – Carlos Hugo of Bourbon-Parma, Spanish aristocrat (b. 1930)
2012 - Jesse Robredo, Filipino politician (b. 1958)
2012 - Scott McKenzie, American singer (b. 1939)
2013 - Rolv Wesenlund, Norwegian actor (b. 1936)
2013 - Dezso Gyarmati, Hungarian polo player (b. 1927)
2014 - Jim Jeffords, United States Senator for Vermont (b. 1934)
2014 - Don Pardo, American radio and television announcer (b. 1918)
2014 - Levente Lengyel, Hungarian chess player (b. 1933)
2014 - Gordon Faber, American politician (b. 1931)
2014 - Hashim Khan, Pakistani squash player (b. 1914)
2015 - Suvra Mukherjee, Indian philosopher and dancer, First Lady of India (b. 1940)
2015 - Khaled Asaad, Syrian scholar (b. 1932)
2015 - Louis Stokes, American politician (b. 1925)
2015 - William Jay Smith, American poet (b. 1918)
2017 - Pertti Alaja, Finnish footballer (b. 1952)
2017 - Alfonso Azpiri, Spanish comic artist (b. 1947)
2017 - Dave Creighton, Canadian ice hockey player (b. 1930)
2017 - Bruce Forsyth, English entertainer and television presenter (b. 1928)
2017 - Venero Mangano, American mobster (b. 1921)
2017 - Duncan Russell, English football manager (b. 1958)
2017 - Don Shepherd, Welsh cricketer (b. 1927)
2017 - Sonny Burgess, American rockabilly singer (b. 1929)
2017 - Vicente Iturat, Spanish racing cyclist (b. 1928)
2018 - Kofi Annan, Ghanaian diplomat, 7th Secretary-General of the United Nations (b. 1938)
2018 - Jack Costanzo, American percussionist and actor (b. 1919)
2018 - Ronnie Moore, Australian-born New Zealand speedway rider (b. 1933)
2018 - Peter Tapsell, British politician (b. 1930)
2018 - Henk Wesseling, Dutch historian (b. 1937)
2019 - Kathleen Blanco, American politician, Governor of Louisiana (b. 1942)
2019 - Karel Kuklík, Czech photographer (b. 1937)
2019 - Encarna Paso, Spanish actress (b. 1931)
2019 - Jack Whitaker, American sportscaster (b. 1924)
Observances[change | change source]
National Science Day (Thailand)
Retrieved from "https://simple.wikipedia.org/w/index.php?title=August_18&oldid=6683856"
This page was last changed on 6 October 2019, at 13:38.


Description: Farmer's Quest is new driving game where you have to drive your farmer truck on challenging bumpy tracks and reach the endpoint to clear the level. Control and balance your farm truck by using your arrow keys and make sure you have good speed and balance to skip over anything which comes on your way. In each level, you must drive your farm truck and overcome all obstacles to reach the endpoint safely, use your driving skills and beat all the challenges on bumpy tracks. Collect as many stars as you can to make your score huge. There are five levels available for you to play, clear all levels and win the game.


In product liability cases, multiple parties could be held liable for your damages. For example, in cases involving dangerous drugs or defective medical devices, the manufacturer marketing, prescribing doctor and distributor might all be aware of a product's shortcomings. The only way to get full compensation from all four responsible parties is to prepare to win your case at trial.


Rasmussen now reports that their electoral college tracking has Barack Obama leading by just ten electoral votes. Based on that projection, all John McCain would need to do would be to carry Virginia and Nevada to be assured of victory. Gallup now reports that McCain has a five point lead over Obama nationally, and that means that the August turnaround which ended with the Republican National Convention is now complete.
These trends are eerily similar to 1988, when Michael Dukakis' lead collapsed after he held one for much of the late spring and through the summer. The lead, which was ten points at one point, gave way after both conventions were complete and Dukakis never recovered.
On a personal note, I want to encourage our friends in the party opposite to continue their baseless, hate-filled, and desperate personal tirade against the next Vice President of the United States. Our Democratic collegues just don't know when to shut up, and that could be very good news for the GOP. Some of our friends are well-meaning, such as Sharon Cobb being bound and determined to somehow prove that the Palins are unAmerican (McCarthyism anyone?) because the First Dude was once a member of the Alaska Independence Party and Sarah Palin gave a speech to the group. We won't bother to explain that the States created the federal government, not the other way around, and that the very notion that Washington is the arbiter of what constitutes Americanism or American ideals is itself unAmerican. We won't even mention that there is something in the Constitution called the Tenth Amendment, and that Alaska joined the Union voluntarily.
Nonetheless, keep it up! Your efforts have dug your man into a hole. Every piece of vitriole, falsehood, half-truth, and outright hate that the press and the Left spew at the Vice President-to-be digs the Democratic Party even further into the hole that it has created for itself. At this rate, the Democrats will have managed to completely destroy themselves by Election Day. Roll out the barrel for that victory party!
Repubs questioned Obama's patriotism over FLAG LAPEL pins - trivia at best. Mr. Palin gets questioned over his verified membership in the fringe and UnAmerican Alaska Independence Party and that's grounds for you to go ballistic? No. It's true, it's a fact, he was a member, so deal with it. And deal with the fact that she has addressed their meetings. Deal with the fact that she thinks (or thought, oresumably someone on the McCain team has corrected her) that the Founding Fathers said the Pledge of Alligance, it's afact, deal with it. Deal with the fact that her Foriegn Policy experience is based solely on Alaska's proximity to Russia (an arguement so silly on its face that it should have never been made in the first place). It's afact, deal with it. Deal with the fact that she is so clueless on National Affairs that the McCain campaign will not trust her to do media interviews on her own - yes, Charlie Gibson of ABC has just been granted one, but who really expects Charlie to ask her anything tough?
You're whining David. When the spotlight was on Sen. Obama you were right there cheering every tough question - Now that the shoe is other foot, you're crying about how "evil" and "bad" the other party is.
David, stop acting like you're smoking dope and realize that the Dems are starting to play the same hard ball the Repubs have been playing since Lee Atwater.
You can't deal with the issues so you character assinate, you can't deal with facts so you cry. Keep crying.
Sara Palin makes me realize that you can coat a nut with lots of things but you stll just have a nut.
I was very concerned before her nomination that McCain would pick a wingnut who would encourage the Wingnut fringe of his party and Corporate America to remove the elderly McCain as they tried to do Roosevelt during the 1930's and install a Messiah of the Right Wing and destroy America in order to save it. She fits the bill to a "T"


text:
Escadrila de aviație este o unitate militară  de aviație a armatei aeriene, marinei militare sau a trupelor de uscat.

Escadrila  de aviație  cuprinde de la două la șase avioane împreună cu piloții  și personal aferent la sol, dar de obicei sunt formate  din 4 avioane și face parte dintr-o unitate mai mare, escadron,  ca în aviația SUA.  Totuși, în câteva exemple specifice pot cuprinde chiar 12 sau 16 avioane cum e  în cazul cu  Battle of Britain Memorial Flight. Echivalentele în alte limbi sunt : escadrille (franceză), escuadrilla (spaniolă), esquadrilha (portugheză), zveno (rusă), and Schwarm (germană), Flight (engleză)

Structuri organizatorice  de aviație în unele țări NATO

Franța
Primele escadrile aeriene s-au format în Franța înainte de Primul Război Mondial, în 1912. Inițial, acestea au fost un grup vag definit de aeronave capabile de sarcini similare, în majoritatea cazurilor nu mai mult de șase avioane în fiecare. În timpul războiului, escadrila a devenit unitatea independentă de bază a aviației în cadrul forțelor armate franceze. O escadrilă era o unitate omogenă, înarmată cu un singur tip de avion, cu personal permanent de zbor și sol atașat, transport motorizat și hangare de corturi. Până la jumătatea anului 1915, Armee de l'Air a crescut la 119 escadrile de câte 10 avioane fiecare: 14 de avioane de vânătoare, 50 de bombardiere și restul unităților de recunoaștere, spotter și comunicații.  În timp ce escadrilele au funcționat inițial independent, în timpul bătăliei de la Verdun (1916), escadrilele chasseur (luptător) s-au format în formațiuni mai mari, pentru o coordonare mai ușoară.

În timpul celui de-al doilea război mondial, escadrilele franceze se aflau de obicei între 10 și 12 avioane. Prin urmare, ele au fost aproximativ echivalente cu un staffel german, gruppo italian sau eskadra poloneză (10 aeronave în 1939). Acest lucru a fost în contrast cu escadroanele  aeriene ale Commonwealth-ului britanic sau ale Statelor Unite, care aveau de obicei 12-18 aeronave, împărțite în două până la patru flights.

România
Escadrila de aviație este o subunitate tactică de aviație, care are în compunere un anumit număr de avioane militare, de regulă de același tip, precum și personalul navigant și tehnic care asigură pregătirea și ducerea acțiunilor de luptă. Escadrila de luptă se dispune pe un aerodrom al unității din care face parte în raport cu situația tactică sau cerințele de dispersare, fiind capabilă să îndeplinească misiuni de luptă independente.

Escadrilele de vânătoare au, de regulă 18-24 avioane, în timp ce escadrilele de bombardament, transport sau realimentare în aer sunt compuse dintr-un număr mai mic de avioane, de regulă 12 avioane. În Forțele Aeriene Române, escadrilele de vânătoare înzestrate cu aeronave Mig-21 LanceR sunt compuse din 16 avioane.

Referințe și note

Bibliografie
 Department of Defense, DOD Dictionary of Military and Associated Terms

Legături externe

Vezi și
 Forțele Aeriene Române

Aviație

redpajama_set_name: RedPajamaWikipedia