text:
FOREX-Sterling slides after BoE buys bonds, dollar hits 20-year high
(Updates to U.S. trading hours, adds commentary; adds NEW YORK dateline)
By Sinéad Carew and Alun John
NEW YORK/LONDON, Sept 28 (Reuters) - Sterling tumbled against the dollar on Wednesday before paring some losses after the Bank of England (BOE) said it would step in to prop up the gilt market, and the dollar index touched a fresh 20-year high trading was volatile.
The BOE said it would buy as many long-dated government bonds as needed between now and Oct. 14 to stabilise financial markets, and added that it would postpone next week's start of its gilt sale programme.
As markets tried to digest what this meant for the pound, the currency whipsawed, jumping as high as $1.084 and falling as low as $1.0539. It was last down 0.4% at $1.0695.
"They're really trying to help the structure of the gilt market, more than anything else... The fact that they're effectively doing (quantitative easing) again, while also hiking rates confuses the monetary policy outlook," said Brad Bechtel, global head of FX at Jefferies in New York.
"It also forces the pound to be the outlet valve for the additional expenditures proposed by the government."
Investors were also eyeing the safety of the dollar against a backdrop of political uncertainty after leaks on Nord Stream pipelines between Russia and Europe spewed gas into the Baltic Sea. NATO Secretary-General Jens Stoltenberg attributed the leaks to acts of sabotage.
"Some of it is safety related, given what we saw yesterday with the NordStream and the Russia Ukraine situation," said Bechtel, also referring to the Federal Reserve's aggressive interest rate hiking cycle aimed at taming inflation
"It is the Fed, outperforming in terms of being aggressive and continuing to hike aggressively. The world is realizing that the U.S. is in a better position to handle higher rates whereas other economies are more vulnerable."
The dollar index, which measures the greenback against a group of major currencies, after earlier hitting a fresh 20-year high of 114.78 was last at 114.100.
While initially the dollar's gains were broad-based, the greenback eased in the U.S. trading morning with the euro last up 0.02% at $0.9595 after falling as low as $0.95355.
The dollar was last down 0.22% against Japan's yen at 144.510 after touching a high of 144.860.
The Australian dollar, which is particularly sensitive to swings in investors sentiment was last up 0.420%.
Elsewhere in Asia, the offshore yuan hit a record low, pressured by expectations of further U.S. rate hikes.
(Reporting by Sinéad Carew in New York, Rae Wee in Singapore and Alun John in London ; editing by Richard Pullin, Kim Coghill, Shri Navaratnam, Gareth Jones and Jonathan Oatis)


text:
\section{Introduction}

Three of the most natural types of subgraph-restricted matchings\cite{lopl,gohehela} are
the induced matchings\cite{stva},
the uniquely restricted matchings\cite{gohile}, and
the acyclic matchings \cite{gohehela}.
If $M$ is a matching in a graph $G$, and $G(M)$ is the subgraph of $G$ induced by the vertices of $G$ incident with some edge in $M$, then
$M$ is {\it induced} if $G(M)$ is $1$-regular,
$M$ is {\it uniquely restricted} if $M$ is the only perfect matching of $G(M)$, and
$M$ is {\it acyclic} if $G(M)$ is a forest.
Clearly, induced matchings are also acyclic.
Furthermore, since $M$ is uniquely restricted if and only if there is no $M$-alternating cycle \cite{gohile},
that is, a cycle whose every second edges belongs to $M$,
acyclic matchings are also uniquely restricted.
Therefore,
if $\nu_s(G)$, $\nu_{ac}(G)$, and $\nu_{ur}(G)$ are the largest sizes of an induced, acyclic, and uniquely restricted matching in $G$, respectively,
then
$$\nu_s(G)\leq \nu_{ac}(G)\leq \nu_{ur}(G)\leq \nu(G)$$
for every graph $G$,
where $\nu(G)$ is the classical matching number \cite{lopl},
that is, the largest size of an unrestricted matching.

Unlike the classical matching number, which is one of the most important tractable graph parameter,
the three parameters $\nu_s(G)$, $\nu_{ac}(G)$, and $\nu_{ur}(G)$ are all computationally hard.
For the induced matching number $\nu_s(G)$, this has first been shown by Stockmeyer and Vazirani \cite{stva},
and strong inapproximability results are known \cite{dadelo,dumazi}.
For the uniquely restricted matching number $\nu_{ur}(G)$, the hardness was established by Golumbic, Hirst, and Lewenstein \cite{gohile},
and also for this parameter inapproximability results are known \cite{mi}.
The hardness of the acylic matching number $\nu_{ur}(G)$ was shown by Goddard, Hedetniemi, Hedetniemi, and Laskar \cite{gohehela}
by exploiting the well-known hardness of the maximum induced forest problem,
and Panda and Pradhan \cite{papr} provided further hardness results.

In view of these hardness results, it is quite surprising that
\begin{itemize}
\item the graphs $G$ for which $\nu_s(G)=\nu(G)$ \cite{koro,cawa,dujoperaso,jora}, and also
\item the graphs $G$ for which $\nu_{ur}(G)=\nu(G)$ \cite{peraso}
\end{itemize}
can both be recognized efficiently.

As our first main result in this paper, we show that something similar does not hold for the acyclic matching number.
More precisely, we show that deciding $\nu_{ac}(G)=\nu(G)$ for a given graph $G$ is hard even under strong restrictions imposed on $G$.

Next to the hardness results mentioned above,
some efficiently tractable cases have been studied
for the induced matching number \cite{brmo,ca1,ca2,lo,koro,lomo},
the uniquely restricted matching number \cite{gohile,frja}, and
the acyclic matching number \cite{bara, papr}.
We contribute to this line of research by showing that maximum weight acyclic matchings
can be found efficiently for $P_4$-free graphs and for $2P_3$-free graphs.
Finally, we characterize the graphs for which every maximum matching is acyclic.

The next section contains all our results and in a third section we discuss some open problems.

\medskip

\noindent Before we proceed to our results, we collect some terminology and notation.
We consider finite, simple, and undirected graphs.
Let $G$ be a graph.
The vertex set of $G$ is denoted $V(G)$ and the edge set of $G$ is denoted $E(G)$.
The neighborhood $N_G(u)$ of a vertex $u$ in $G$ is the set $\{ v\in V(G):uv\in E(G)\}$,
and the degree $d_G(u)$ of $u$ in $G$ is $|N_G(u)|$.
For a set $U$ of vertices of $G$, let $N_G(U)$ be $\bigcup_{u\in U}N_G(u)$.
A matching $M$ in a graph $G$ is a set of pairwise disjoint edges.
The set of vertices of $G$ incident with an edge in $M$ is $V(M)$,
and the subgraph of $G$ induced by $V(M)$ is $G(M)$.
For an integer $k$, let $[k]$ be the set of all positive integers at most $k$.

\section{Results}

We begin with our first main result showing that deciding the equality of the acyclic matching number and the matching number is hard
even for quite restricted instances.

\begin{theorem}\label{theorem1}
For a given bipartite graph $G$ of maximum degree at most $4$, partite sets $A$ and $B$ with $|A|\leq |B|$, and matching number $|A|$, it is NP-complete to decide whether $\nu_{ac}(G)=\nu(G)$.
\end{theorem}
{\it Proof:} The proof relies on a restricted version of {\sc Satisfiability}.
It is known (cf.~[LO1] in \cite{gajo}) that {\sc Satisfiability} remains NP-complete when restricted to instances where every clause contains at most three literals, and for every variable $x$, at most three clauses contain the variable $x$ or its negation $\bar{x}$.
Note
that variables that appear only positively or only negatively can be eliminated,
that clauses of size one allow to eliminate a variable,
and that clauses containing a variable and its negation can be removed.
Therefore, {\sc Satisfiability} remains NP-complete when restricted to instances
where every clause contains two or three literals, and,
for every variable $x$,
at most two clauses contain the variable $x$,
at most two clauses contain its negation $\bar{x}$, and
no clause contains both $x$ and $\bar{x}$.

Let $f$ be such an instance of {\sc Satisfiability} consisting of the clauses $c_1,\ldots,c_m$ over the
boolean variables $x_1,\ldots,x_n$.
We construct a graph $G$ as in the statement of the theorem such that the order of $G$ is polynomially bounded in terms of $n$ and $m$, and $f$ is satisfiable if and only if $\nu_{ac}(G)=\nu(G)$.

Starting with $G$ being the empty graph,
\begin{itemize}
\item for every $i$ in $[n]$, we add to $G$ a subgraph $G_i$ as shown in Figure \ref{fig1}, and
\item for every $r$ in $[m]$, and every literal $\ell$ in the clause $c_r$,
we add to $G$ a complete subgraph with the two vertices $\ell(r,1)$ and $\ell(r,2)$.
\end{itemize}
\begin{figure}[H]
\centering\tiny
\begin{tikzpicture}[scale = 0.9]
	    \node (A) at (7,0) {$y(i,8)$};
	    \node (B) at (7,1.5) {$z(i,8)$};
	    \node (C) at (3,3) {$y(i,2)$};
	    \node (D) at (7,3) {$y(i,6)$};
	    \node (E) at (11,3) {$y(i,4)$};
	    \node (F) at (3,4) {$z(i,2)$};
	    \node (G) at (7,4) {$z(i,6)$};
	    \node (H) at (11,4) {$z(i,4)$};
	    \node (I) at (0,5) {$f(i,1)$};
	    \node (J) at (2,5) {$t(i,1)$};
	    \node (K) at (4,5) {$f(i,2)$};
	    \node (L) at (6,5) {$t(i,2)$};
	    \node (M) at (8,5) {$f(i,3)$};
	    \node (N) at (10,5) {$t(i,3)$};
	    \node (O) at (12,5) {$f(i,4)$};
	    \node (P) at (14,5) {$t(i,4)$};
	    \node (Q) at (3,6) {$y(i,1)$};
	    \node (R) at (7,6) {$y(i,5)$};
	    \node (S) at (11,6) {$y(i,3)$};
	    \node (T) at (3,7) {$z(i,1)$};
	    \node (U) at (7,7.5) {$z(i,5)$};
	    \node (V) at (11,7) {$z(i,3)$};
	    \node (W) at (1,8) {$u(i,1)$};
	    \node (X) at (5,8) {$u(i,2)$};
	    \node (Y) at (9,8) {$u(i,3)$};
	    \node (Z) at (13,8) {$u(i,4)$};
	    \node (a) at (3,9) {$w(i,1)$};
	    \node (b) at (7,9.3) {$y(i,7)$};
	    \node (c) at (11,9) {$w(i,2)$};
	    \node (d) at (3,10.5) {$x(i,1)$};
	    \node (e) at (7,10.8) {$z(i,7)$};
	    \node (f) at (11,10.5) {$x(i,2)$};

	    \draw[-] (A) to (B);
	    \draw (7.4,0) arc(-88:-21.5 :7.3);
	    \draw (6.6,0) arc(-90:-159:7.1);
	    \draw[-] (C) to (F);
	    \draw[-] (C) to (I);
	    \draw[-] (C) to (L);
	    \draw[-] (D) to (G);
	    \draw[-] (D) to (K);
	    \draw[-] (D) to (N);
	    \draw[-] (E) to (H);
	    \draw[-] (E) to (M);
	    \draw[-] (E) to (P);
	    \draw[-] (I) to (W);
	    \draw[-] (J) to (W);
	    \draw[-] (J) to (Q);
	    \draw (2,5.4) arc(180:81.3:4);
	    \draw[-] (K) to (Q);
	    \draw[-] (K) to (X);
	    \draw[-] (L) to (X);
	    \draw[-] (L) to (R);
	    \draw[-] (M) to (R);
	    \draw[-] (M) to (Y);
	    \draw[-] (N) to (Y);
	    \draw[-] (N) to (S);
	    \draw[-] (O) to (S);
	    \draw (12,5.43) arc(0:98.7:4);
	    \draw[-] (O) to (Z);
	    \draw[-] (P) to (Z);
	    \draw[-] (W) to (a);
	    \draw[-] (Q) to (T);
	    \draw[-] (X) to (a);
	    \draw[-] (R) to (U);
	    \draw[-] (S) to (V);
	    \draw[-] (Y) to (c);
	    \draw[-] (Z) to (c);
	    \draw[-] (a) to (d);
	    \draw[-] (b) to (e);
	    \draw[-] (c) to (f);
    \end{tikzpicture}
\caption{The gadget $G_i$ corresponding to the boolean variable $x_i$.} \label{fig1}
\end{figure}
\noindent Note that the clause $c_r$ of the form $x_i\vee \bar{x}_j$ leads to a subgraph with
four vertices $x_i(r,1)$, $x_i(r,2)$, $\bar{x}_j(r,1)$, and $\bar{x}_j(r,2)$, and
two edges $x_i(r,1)x_i(r,2)$ and $\bar{x}_j(r,1)\bar{x}_j(r,2)$.
Similarly, a clause containing three literals leads to a subgraph with six vertices and three edges.
Therefore, the graph constructed so far has order at most $32n+6m$.

In order to complete the construction of $G$,
for every $i$ in $[n]$,
we add to $G$ some further edges between the subgraph $G_i$ and the subgraphs corresponding to the clauses containing $x_i$ or $\bar{x}_i$.
Therefore, let $i\in [n]$.
Let $c_r$ and $c_s$ be the clauses that contain $x_i$, where $r\leq s$,
that is, if $x_i$ is contained in just one clause, then let $r=s$.
First, suppose that $c_r$ contains only two literals $x_i$ and $\ell$.
Let $j\in [n]\setminus \{ i\}$ be such that $\ell$ is in $\{ x_j,\bar{x}_j\}$.
If $i<j$, then add to $G$ the two edges $x_i(r,1) f(i,1)$ and $\ell(r,1)f(i,2)$, and,
if $i>j$, then add to $G$ the two edges $x_i(r,1) f(i,2)$ and $\ell(r,1)f(i,1)$.
Next, suppose that $c_r$ contains three literals $x_i$, $\ell$, and $\ell'$.
Let $j,k\in [n]\setminus \{ i\}$ be such that $\ell$ is in $\{ x_j,\bar{x}_j\}$
and $\ell'$ is in $\{ x_k,\bar{x}_k\}$, where we may assume that $j<k$.
In this case, add to $G$ the two edges $\ell(r,1) f(i,1)$ and $\ell'(r,1)f(i,2)$.
If $r<s$, that is, $x_i$ is contained in two different clauses,
then proceed similarly for the clause $c_s$
using the vertices $f(i,3)$ and $f(i,4)$ instead of the vertices $f(i,1)$ and $f(i,2)$.
Furthermore, proceed similarly for the one or two clauses that contain $\bar{x}_i$
using the vertices $t(i,1)$, $t(i,2)$, $t(i,3)$, and $t(i,4)$
instead of the vertices $f(i,1)$, $f(i,2)$, $f(i,3)$, and $f(i,4)$.

This completes the construction of $G$, and we continue with a series of claims.

The next claim establishes some structural properties of $G$.

\begin{claim}\label{claim1}
$G$ is bipartite, has maximum degree $4$,
partite sets $A$ and $B$ with $|A|\leq |B|$,
and matching number $|A|$.
\end{claim}
{\it Proof of Claim \ref{claim1}:}
It follows immediate from the construction that $G$ has maximum degree of $4$.

For the two sets
$$
A=
\bigcup\limits_{i\in [n]}
\Big(\{ u(i,j):j\in [4]\}\cup \{ x(i,j):j\in [2]\}\cup \{ y(i,j):j\in [8]\}\Big)
\cup\bigcup_{j\in[m]}\,\,\,\,\bigcup_{\ell\,\,is\,\,a\,\,literal\,\,in\,\,c_j}\ell(j,1)
$$
and $B=V(G)\setminus A$,
it is easy to verify that $G$ is bipartite with partite sets $A$ and $B$.
The matching $M$ that contains all edges incident with endvertices
as well as,
for every $i$ in $[n]$,
the four edges $u(i,j)t(i,j)$ with $j\in [4]$,
satisfies $A\subseteq V(M)$,
which completes the proof of the claim. $\Box$

\medskip

\noindent The next claim restricts the structure of maximum matchings in $G$
that are acyclic.

\begin{claim}\label{claim2}
Every maximum matching $M$ in $G$ that is acyclic
contains all edges incident with endvertices,
and, for every $i$ in $[n]$, the set $V(M)\cap V(G_i)$ is
either
$V(G_i)\setminus \{ t(i,j):j\in [4]\}$
or
$V(G_i)\setminus \{ f(i,j):j\in [4]\}$.
\end{claim}
{\it Proof of Claim \ref{claim2}:}
By Claim \ref{claim1}, we have $A\subseteq V(M)$.
Let $i$ be in $[n]$.
Since $x(i,j)\in A$ for $j\in [2]$,
the matching $M$ contains the two edges incident with the endvertices $x(i,1)$ and $x(i,2)$.

If $u(i,1)t(i,1),u(i,2)f(i,2)\in M$,
then $G(M)$ contains the cycle
$$u(i,1)t(i,1)y(i,1)f(i,2)u(i,2)w(i,1),$$
which is a contradiction.
Hence, by symmetry, the matching $M$ contains
\begin{itemize}
\item either $u(i,j)t(i,j)\in M$ for $j\in [2]$ or $u(i,j)f(i,j)\in M$ for $j\in [2]$, and
\item either $u(i,j)t(i,j)\in M$ for $j\in [4]\setminus [2]$ or $u(i,j)f(i,j)\in M$ for $j\in [4]\setminus [2]$.
\end{itemize}
If $u(i,j)t(i,j)\in M$ for $j\in [2]$ and $u(i,j)f(i,j)\in M$ for $j\in [4]\setminus [2]$,
then $G(M)$ contains the cycle
$$u(i,2)t(i,2)y(i,5)f(i,3)u(i,3)w(i,2)u(i,4)f(i,4)y(i,7)t(i,1)u(i,1)w(i,1)u(i,2),$$
which is a contradiction.
Hence, either $u(i,j)t(i,j)\in M$ for $j\in [4]$ or $u(i,j)f(i,j)\in M$ for $j\in [4]$.

If $f(i,1)\in V(M)$ and $u(i,j)t(i,j)\in M$ for $j\in [4]$,
then $G(M)$ contains the cycle
$$f(i,1)y(i,2)t(i,2)u(i,2)w(i,1)u(i,1)f(i,1),$$
which is a contradiction.
Hence, by symmetry, it follows that the set $V(M)\cap V(G_i)$ is
either
$V(G_i)\setminus \{ t(i,j):j\in [4]\}$
or
$V(G_i)\setminus \{ f(i,j):j\in [4]\}$.
This implies that $y(i,j)z(i,j)\in M$ for $j\in [8]$,
and that $\ell(j,1)\ell(j,2)\in M$ for every $j\in [m]$ and every literal $\ell$ in the clause $c_j$,
which completes the proof of the claim.
$\Box$

\medskip

\noindent By construction, for every $i$ in $[n]$, the only vertices within $V(G_i)$
that can have neighbors outside of $V(G_i)$
are the eight vertices $t(i,j)$ and $f(i,j)$ for $j\in [4]$.
By Claim \ref{claim2}, if $M$ is a maximum matching in $G$ that is acyclic, then
$G[V(M)\cap V(G_i)]$ is a forest.
Furthermore,
if $V(M)\cap V(G_i)=V(G_i)\setminus \{ t(i,j):j\in [4]\}$,
then the vertices $f(i,1)$ and $f(i,2)$ lie in one component of $G[V(M)\cap V(G_i)]$,
and the vertices $f(i,3)$ and $f(i,4)$ lie in another component of $G[V(M)\cap V(G_i)]$,
and,
if $V(M)\cap V(G_i)=V(G_i)\setminus \{ f(i,j):j\in [4]\}$,
then the vertices $t(i,1)$ and $t(i,2)$ lie in one component of $G[V(M)\cap V(G_i)]$,
and the vertices $t(i,3)$ and $t(i,4)$ lie in another component of $G[V(M)\cap V(G_i)]$.

\begin{claim}\label{claim3}
$\nu_{ac}(G)=\nu(G)$ if and only if $f$ is satisfiable.
\end{claim}
{\it Proof of Claim \ref{claim3}:}
First, suppose that $\nu_{ac}(G)=\nu(G)$.
Let $M$ be a maximum matching in $G$ that is acyclic.
For every $i$ in $[n]$, set the variable $x_i$ to \texttt{true}
if and only if $t(i,1)\in V(M)$.
Now, let $r$ be in $[m]$.
First, suppose that $c_r$ contains two literals
$\ell\in \{ x_i,\bar{x}_i\}$ and
$\ell'\in \{ x_j,\bar{x}_j\}$ for some $i$ and $j$ in $[n]$.
If both literals in $c_r$ are not \texttt{true},
then $G(M)$ contains
a path between $\ell(r,1)$ and $\ell'(r,1)$ through $G_i$
and also through $G_j$,
which contradicts the assumption that $M$ is acyclic.
Next, suppose that $c_r$ contains three literals
$\ell\in \{ x_i,\bar{x}_i\}$,
$\ell'\in \{ x_j,\bar{x}_j\}$, and
$\ell''\in \{ x_k,\bar{x}_k\}$ for some $i$, $j$, and $k$ in $[n]$.
If all three literals in $c_r$ are not \texttt{true},
then $G(M)$ contains
a path between $\ell(r,1)$ and $\ell'(r,1)$ through $G_k$,
a path between $\ell'(r,1)$ and $\ell''(r,1)$ through $G_i$, and
a path between $\ell(r,1)$ and $\ell''(r,1)$ through $G_j$,
which contradicts the assumption that $M$ is acyclic.
Hence, the considered truth assignment satisfies every clause of $f$.

Next, suppose that $f$ is satisfiable, and consider a satisfying truth assignment.
Let $M$ be the maximum matching in $G$ that contains all edges incident with endvertices,
and satisfies
$V(M)\cap V(G_i)=V(G_i)\setminus \{ f(i,j):j\in [4]\}$
if and only if $x_i$ is \texttt{true} for every $i$ in $[n]$.
The existence of such a matching follows easily from the construction.
Note that, if $x_i$ is not \texttt{true},
then $V(M)\cap V(G_i)=V(G_i)\setminus \{ t(i,j):j\in [4]\}$.

Suppose for a contradiction, that $G(M)$ contains a cycle $C$.
It is easy to see that $C$ contains a vertex $\ell(r,1)$
for some $r$ in $[m]$ and some literal $\ell$ in the clause $c_r$.
If the clause $c_r$ contains only one further literal $\ell'$,
and $i$ and $j$ in $[n]$ are such that
$\ell\in \{ x_i,\bar{x}_i\}$ and
$\ell'\in \{ x_j,\bar{x}_j\}$,
then the two neighbors of $\ell(r,1)$ in $G_i$ and $G_j$ are both in $V(M)$.
By the construction of $G$ and the definition of $M$,
this implies that both literals $\ell$ and $\ell'$ are not \texttt{true},
which is a contradiction.
Hence, we may assume that the clause $c_r$
contains two further literals $\ell'$ and $\ell''$.
Let $i$, $j$, and $k$ in $[n]$ be such that
$\ell\in \{ x_i,\bar{x}_i\}$,
$\ell'\in \{ x_j,\bar{x}_j\}$, and
$\ell''\in \{ x_k,\bar{x}_k\}$.
Since $\ell(r,1)$ lies on $C$,
the two neighbors of $\ell(r,1)$ in $G_j$ and $G_k$ are both in $V(M)$.
In view of the intersection of $V(M)$ with $V(G_j)$ and $V(G_k)$,
it follows easily that $C$ contains the vertices $\ell'(r,1)$ and $\ell''(r,1)$.
This implies that
the two neighbors of $\ell'(r,1)$ in $G_i$ and $G_k$ are both in $V(M)$,
and that also
the two neighbors of $\ell''(r,1)$ in $G_i$ and $G_j$ are both in $V(M)$.
By the definition of $M$,
this implies that all three literals $\ell$, $\ell'$, and $\ell''$ are not \texttt{true},
which is a contradiction, and completes the proof of the claim.
$\Box$

\medskip

\noindent The above three claims clearly imply the desired statement,
which completes the proof.
$\Box$

\medskip

\noindent Subdividing each non-pendant edge in the graph $G$
constucted within the proof of Theorem \ref{theorem1}
an even number of times,
and attaching endvertices to the vertices created by these subdivisions
easily implies that the conclusion of Theorem \ref{theorem1} still holds
when we additionally require a large girth.
Furthermore, since $\nu(G)=\nu_{ur}(G)$ for the graph $G$
constucted within the proof of Theorem \ref{theorem1},
the proof of this result also implies the hardness of deciding
whether $\nu_{ur}(G)$ equals $\nu_{ac}(G)$
for a given graph $G$ as in Theorem \ref{theorem1}.

The following three results concern tractable cases for the maximum weight acyclic matching problem.

\begin{theorem}\label{theorem2}
For a given edge-weighted $P_4$-free graph,
a maximum weight acyclic matching can be determined in polynomial time.
\end{theorem}
{\it Proof:} Is it well-known that every $P_4$-free graph $G$ of order at least $2$
is either disconnected
or the join of two disjoint $P_4$-free graphs.
Clearly, a maximum weight acyclic matching of a disconnected graph is the union of maximum weight acyclic matchings of its components.
Furthermore, if $G$ is the join of $G_1$ and $G_2$,
and $M$ is an acyclic matching in $G$, then
either $M\subseteq E(G_1)$,
or $M\subseteq E(G_2)$,
or $M$ consists of exactly one edge between a vertex of $G_1$ and a vertex of $G_2$.
These observations lead to a simple polynomial time reduction algorithm
that determines a maximum weight acyclic matching
in a given edge-weighted $P_4$-free graph.
$\Box$

\medskip

\noindent Our next lemma shows that for $2P_3$-free graphs,
induced matchings and acyclic matching are similar.

\begin{figure}[H]
\begin{minipage}[t]{0.48\textwidth}
\centering\tiny
\begin{tikzpicture}[scale = 0.9]
	    \node (A) at (0,0) {};
	    \node (B) at (1,0) {};
	    \node (C) at (2,0) {};
	    \node (D) at (3,0) {};

	    \draw[-] (A) to (B);
	    \draw[-] (B) to (C);
	    \draw[-] (C) to (D);
\end{tikzpicture}
\end{minipage} \hfill
\begin{minipage}[t]{0.49\textwidth}
\centering\tiny
\begin{tikzpicture}[scale = 0.9]
	    \node (A) at (0,0) {};
	    \node (B) at (1,0) {};
	    \node (C) at (2,0.5) {};
	    \node (D) at (3,0.5) {};
	    \node (E) at (2,-0.5) {};
	    \node (F) at (3,-0.5) {};

	    \draw[-] (A) to (B) to (C) to (D);
	    \draw[-] (B) to (E) to (F);
	    \draw[dotted] (2.5,-0.25) to (2.5,0.25);
\end{tikzpicture}
\end{minipage} \\[10pt]
\begin{minipage}[t]{0.48\textwidth}
\centering\tiny
\begin{tikzpicture}[scale = 0.9]
	    \node (A) at (0,0.5) {};
	    \node (B) at (1,0.5) {};
	    \node (C) at (2,1) {};
	    \node (D) at (3,1) {};
	    \node (E) at (2,0) {};
	    \node (F) at (3,0) {};
	    \node (G) at (-1,1) {};
	    \node (H) at (-2,1) {};
	    \node (I) at (-1,0) {};
	    \node (J) at (-2,0) {};

	    \draw[-] (A) to (B) to (C) to (D);
	    \draw[-] (B) to (E) to (F);
	    \draw[-] (A) to (G) to (H);
	    \draw[-] (A) to (I) to (J);
	    \draw[dotted] (2.5,0.25) to (2.5,0.75);
	    \draw[dotted] (-1.5,0.25) to (-1.5,0.75);
\end{tikzpicture}
\end{minipage} \hfill
\begin{minipage}[t]{0.49\textwidth}
\centering\tiny
 \begin{tikzpicture}[scale = 0.9]
	    \node (A) at (0,0.5) {};
	    \node (B) at (1,0.5) {};
	    \node (C) at (2,1) {};
	    \node (D) at (3,1) {};
	    \node (E) at (2,0) {};
	    \node (F) at (3,0) {};
	    \node (G) at (-1,1) {};
	    \node (H) at (-2,1) {};
	    \node (I) at (-1,0) {};
	    \node (J) at (-2,0) {};
	    \node (K) at (0,1.5) {};
	    \node (L) at (1,1.5) {};

	    \draw[-] (A) to (B) to (C) to (D);
	    \draw[-] (B) to (E) to (F);
	    \draw[-] (A) to (G) to (H);
	    \draw[-] (A) to (I) to (J);
	    \draw[-] (A) to (K);
	    \draw[-] (B) to (L);
	    \draw[dotted] (2.5,0.25) to (2.5,0.75);
	    \draw[dotted] (-1.5,0.25) to (-1.5,0.75);
 \end{tikzpicture}
\end{minipage}
\caption{An illustration of Lemma \ref{lemma1} $(i)-(iv)$.} \label{fig2}
\end{figure}

\begin{lemma}\label{lemma1}
If $M$ is an acyclic matching in a $2P_3$-free graph $G$,
then $G(M)$ has at most one component that is not a $K_2$,
and such a component $T$ satisfies
\begin{enumerate}[(i)]
\item either $T$ is a $P_4$,
\item or
\begin{eqnarray*}
V(T) &=& \{ x,x'\}\cup \{ y_i:i\in [k]\}\cup \{ y'_i:i\in [k]\}\mbox{ and}\\
E(T)&=& \{ xx'\}\cup \{ y_iy_i':i\in [k]\}\cup \{ xy_i:i\in [k]\}
\end{eqnarray*}
for some integer $k$ at least $2$,
\item or
\begin{eqnarray*}
V(T) &=& \{ x,x'\}\cup \{ y_i:i\in [k]\}\cup \{ y'_i:i\in [k]\}\cup \{ z_i:i\in [\ell]\}\cup \{ z'_i:i\in [\ell]\}\mbox{ and}\\
E(T)&=& \{ xx'\}\cup \{ y_iy_i':i\in [k]\}\cup \{ xy_i:i\in [k]\}\cup \{ z_iz_i':i\in [\ell]\}\cup \{ x'z_i:i\in [\ell]\}
\end{eqnarray*}
for some positive integers $k$ and $\ell$,
\item or
\begin{eqnarray*}
V(T) &=& \{ x,x',y,y'\}\cup \{ w_i:i\in [k]\}\cup \{ w'_i:i\in [k]\}\cup \{ z_i:i\in [\ell]\}\cup \{ z'_i:i\in [\ell]\}\mbox{ and}\\
E(T)&=& \{ xx',yy',xy\}\cup \{ w_iw_i':i\in [k]\}\cup \{ xw_i:i\in [k]\}\cup \{ z_iz_i':i\in [\ell]\}\cup \{ yz_i:i\in [\ell]\}
\end{eqnarray*}
for some positive integers $k$ and $\ell$.
\end{enumerate}
\end{lemma}
{\it Proof:} Let $F=G(M)$.
Since $M$ is acyclic, $F$ is a forest with a perfect matching.
Since every component of $F$ that is not a $K_2$, contains a $P_3$,
the $2P_3$-freeness of $G$ implies that at most one component of $F$ is not a $K_2$.
Let $T$ be such a component.
Let $P:u_1\ldots u_n$ be a longest path in $T$.
Since $F$ has a perfect matching, we obtain $n\geq 4$, and,
since $G$ is $2P_3$-free, we obtain $n\leq 6$.
Note that $d_F(u_1)=d_F(u_n)=1$,
which implies that $M$ contains the two edges $u_1u_2$ and $u_{n-1}u_n$.
By the choice of $P$, we obtain furthermore that $N_F(u_2)=\{ u_1,u_3\}$ and $N_F(u_{n-1})=\{ u_{n-2},u_n\}$.
If $n=4$, this already implies that $T$ is a $P_4$.
For $n=5$, the matching $M$ contains an edge $u_3u_3'$ for some $u_3\in V(T)\setminus V(P)$.
By symmetry and the choice of $P$,
it follows that all vertices in $N_{T-(E(T)\cap M)}(u_3)=N_T(u_3)\setminus \{ u_3'\}$ have degree $2$ in $T$,
and that their neighbors distinct from $u_3$ are endvertices of $T$.
Altogether, it follows that $T$ is as in (ii).
Now, let $n=6$.
Since $M$ contains a perfect matching of $T$,
it follows that either $u_3u_4\in M$
or $M$ contains two edges $u_3u_3'$ and $u_4u_4'$ for some distinct vertices $u_3'$ and $u_4'$ in $V(T)\setminus V(P)$.
As before it follows that all vertices in
$\left(N_{T-(E(T)\cap M)}(u_3)\cup N_{T-(E(T)\cap M)}(u_4)\right)\setminus \{ u_3,u_4\}$ have degree $2$ in $T$,
and that their neighbors distinct from $u_3$ and $u_4$ are endvertices of $T$.
Hence, if $u_3u_4\in M$, then $T$ is as in (iii), and, otherwise, $T$ is as in (iv).
$\Box$

\begin{theorem}\label{theorem3}
For a given edge-weighted $2P_3$-free graph,
a maximum weight acyclic matching can be determined in polynomial time.
\end{theorem}
{\it Proof:} Let $G$ be an edge-weighted $2P_3$-free graph of order $n$.
Using Lemma \ref{lemma1}, we will reduce the problem to determine a maximum weight acyclic matching in $G$
to polynomially many instances of the maximum weight induced matching problem in smaller $2P_3$-free graphs.
As shown by Lozin and Mosca \cite{lomo}
a maximum weight induced matching can be determined in polynomial time for a given $2P_3$-free graph.

By Lemma \ref{lemma1}, a maximum weight acyclic matching $M$ in $G$ is a matching of largest weight of one of the following five types:
\begin{enumerate}[(1)]
\item An induced matching.
\item An acyclic matching $M$ for which $G(M)$ contains a component $T$ that is a $P_4$.
\item An acyclic matching $M$ for which $G(M)$ contains a component $T$ as in (ii) of Lemma \ref{lemma1}.
\item An acyclic matching $M$ for which $G(M)$ contains a component $T$ as in (iii) of Lemma \ref{lemma1}.
\item An acyclic matching $M$ for which $G(M)$ contains a component $T$ as in (iv) of Lemma \ref{lemma1}.
\end{enumerate}
We already observed that a maximum weight matching of type (1)
can be determined efficiently \cite{lomo}.
A maximum weight matching $M$ of type (2)
can be determined by considering all $O(n^4)$ choices for the $P_4$ component $T$,
adding to $M$ the two edges of a perfect matching of $T$
as well as a maximum weight induced matching of the graph $G-N_G[V(T)]$.

A maximum weight matching $M$ of type (3)
can be determined by
\begin{itemize}
\item considering all $O(n^6)$ choices for the six vertices
$x$, $x'$, $y_1$, $y_1'$, $y_2$, and $y_2'$ of $T$,
\item adding to $M$ the three edges $xx'$, $y_1y_1'$, and $y_2y_2'$,
as well as
\item a maximum weight induced matching $M'$ of the graph $G'=G-N_G[\{ x',y_1,y_1',y_2,y_2'\}]$,
where the weight of the edges of $G'$ that are between vertices in $N_G(x)$ is changed to $-1$.
\end{itemize}
By the construction of $G'$ and the change of the weight function, every edge in $M'$ contains at most one neighbor of $x$.
Note that the edges in $M'$ containing a neighbor of $x$,
correspond to the edges
$y_3y_3',\ldots,y_ky_k'$ as in Lemma \ref{lemma1}(ii).

In the remaining cases, we proceed similarly.

A maximum weight matching $M$ of type (4)
can be determined by
considering all $O(n^6)$ choices for the six vertices $x$, $x'$, $y_1$, $y_1'$, $z_1$, and $z_1'$ of $T$,
adding to $M$ the three edges $xx'$, $y_1y_1'$, and $z_1z_1'$,
as well as a maximum weight induced matching $M'$ of the graph $G'=G-\left(N_G[\{ y_1,y_1',z_1,z_1'\}]\cup \left(N_G(x)\cap N_G(x')\right)\right)$,
where the weight of the edges of $G'$ that are between vertices in $N_G(x)\cup N_G(x')$ is changed to $-1$.
Note that
$N_G(u)\cap \{ x,x',y_1,y_1',z_1,z_1'\}$
is either $\emptyset$, or $\{ x\}$, or $\{ x'\}$
for every vertex $u$ in $V(G')$,
and that every edge in $M'$ contains at most one vertex with a neighbor in $\{ x,x'\}$,
which implies that the structure of $G(M)$ is as desired.

Finally,
a maximum weight matching $M$ of type (5) can be determined
by considering all $O(n^8)$ choices for the eight vertices $x$, $x'$, $y$, $y'$, $w_1$, $w_1'$, $z_1$, and $z_1'$ of $T$,
adding to $M$ the four edges $xx'$, $yy'$, $w_1w_1'$, and $z_1z_1'$,
as well as a maximum weight induced matching of the graph $G'=G-\left(N_G[\{ x',y',w_1,w_1',z_1,z_1'\}]\cup \left(N_G(x)\cap N_G(y)\right)\right)$,
where the weight of the edges of $G'$ that are between vertices in $N_G(x)\cup N_G(y)$ is changed to $-1$.

Altogether, we need to solve $O(n^8)$ instances of the maximum weight induced matching problem in edge-weighted $2P_3$-free graphs that are induced subgraphs of $G$ such that the encoding lengths of the weight functions are polynomially bounded in terms of the encoding length of the original weight function, which, by \cite{lomo}, completes the proof. $\Box$

\medskip

\noindent Our final result concerns the graphs for which every maximum matching is acyclic.

\begin{theorem}\label{theorem4}
Let $G$ be a graph.

Every maximum matching in $G$ is acyclic
if and only if
every component of $G$ is a tree or an odd cycle.
\end{theorem}
{\it Proof:} Clearly, if every component of $G$ is a tree or an odd cycle,
then every maximum matching in $G$ is acyclic.
Now, let $G$ be such that every maximum matching in $G$ is acyclic.
Let $C$ be a cycle in $G$.
In order to complete the proof,
it suffices to show that $C$ is a component of $G$ of odd order.
Let $M$ be a maximum matching in $G$ maximizing $|V(M)\cap V(C)|$.
Since $M$ is acyclic, not all vertices of $C$ are covered by $M$.

Suppose that $M$ contains an edge between a vertex on $C$ and a vertex not on $C$.
If $u_0\ldots u_k$ is a shortest path within $C$ between a vertex $u_0$ not covered by $M$
and a vertex $u_k$ such that $u_kv\in M$ for some vertex $v$ not on $C$,
then $k$ is odd, and $u_{2i-1}u_{2i}\in M$ for every $i\in [(k-1)/2]$.
Now,
$$M'=\left(M\setminus \left(\{ u_kv\}\cup \left\{ u_{2i-1}u_{2i}:i\in [(k-1)/2]\right\}\right)\right)\cup \left\{ u_{2i-2}u_{2i-1}:i\in [(k+1)/2]\right\}$$
is a maximum matching in $G$ with $|V(M')\cap V(C)|>|V(M)\cap V(C)|$,
contradicting the choice of $M$.
Hence, $M$ contains no edge between a vertex on $C$ and a vertex not on $C$.
Since $M$ is a maximum matching,
this easily implies that $M$ covers all but exactly one vertex of $C$,
which implies that $C$ has odd order.

Suppose that $C$ is not a component of $G$.
This implies that some vertex $u$ on $C$ has a neighbor $v$ that is not on $C$.
Removing from $M$ all edges that belong to $C$ as well as any edge incident with $v$,
and adding to the resulting matching
the edge $uv$
as well as a matching in $C$ covering all vertices of $C$ except for $u$,
results in a maximum matching in $G$ that is not acyclic,
which is a contradiction.
Hence, $C$ is a component of $G$, which completes the proof. $\Box$

\begin{corollary}\label{corollary1}
Let $G$ be a graph.

Every maximum matching in $G$ is induced
if and only if
every component of $G$ is a star or a triangle.
\end{corollary}
{\it Proof:} Clearly, if every component of $G$ is a star or a triangle,
then every maximum matching is induced.
Now, let $G$ be such that every maximum matching in $G$ is induced.
Since this implies that every maximum matching in $G$ is acyclic,
the graph $G$ is as in Theorem \ref{theorem4}.
Since odd cycles of length at least $5$
have non-induced maximum matchings,
every component of $G$ that is not a tree, is a triangle.
Now, suppose that $T$ is a component of $G$ that is a tree but not a star.
Let $M$ be a maximum matching of $G$ that contains a pendant edge $uv$ of $T$,
where $u$ is an endvertex.
Since $T$ is not a star, the vertex $v$ has a neighbor $w$ that is not an endvertex.
Since $M$ is a maximum matching that is induced, the vertex $w$ is not covered by $M$
but every vertex in $N_T(w)$ is covered by $M$.
Removing an edge from $M$ incident with a neighbor $x$ of $w$ that is distinct from $v$, and adding $wx$ to the resulting matching,
yields a non-induced maximum matching, which is a contradiction. $\Box$

\section{Conclusion}

Two obvious open problems motivated by our results concern
\begin{itemize}
\item the complexity of deciding whether $\nu_{ac}(G)=\nu(G)$
for a given bipartite graph $G$ of maximum degree $3$, and
\item the complexity of the maximum acyclic matching problem for $P_5$-free graphs.
\end{itemize}
We believe that the first of these two problems can be solved efficiently,
and add some comments concerning the second problem.
Kobler and Rotics \cite{koro} describe efficient algorithms for the maximum induced matching problem restricted to some subclasses of $P_5$-free graphs.
Their key insight is that the square of the line graph $L^2(G)$ of a $P_5$-free graph $G$ is still $P_5$-free, and that induced matchings in $G$
correspond to independent sets in $L^2(G)$.
In view of \cite{lovavi}, it actually follows that the maximum induced matching problem can be solved efficiently for all $P_5$-free graphs.
If $M$ is an acyclic matching in a $P_5$-free graph $G$, then $G(M)$ is the disjoint union of $P_4$s and $K_2$s, and, may, in particular, contain many $P_4$s. Therefore, for the maximum acyclic matching problem in $P_5$-free graphs, an approach as in the proof of Theorem \ref{theorem3} does not seem to work. Nevertheless, considering $M$ as a vertex subset of $L^2(G)$, there might be a connection with the dissociation set problem.

Note that if $M$ is a maximum matching in a graph $G$ that is acyclic,
then $V(G)\setminus V(M)$ is a so-called independent feedback vertex set.
The algorithmic problems in connection with (minimum) independent feedback vertex sets
have attracted considerable attention recently \cite{aggusash,bodafejopa,miphrasa,taitzh}.
Maybe some of the techniques from this context
lead to interesting cases,
where deciding the equality of the acyclic matching number and the matching number is tractable.

redpajama_set_name: RedPajamaArXiv


text:
Private Kitchen
Homewood Suites by Hilton Sarasota
Sarasota Florida
Check out 12:00 PM
With a stay at Homewood Suites by Hilton Sarasota in Sarasota, you'll be within a 10-minute drive of St. Armands Circle and Marina Jack. This aparthotel is 7.3 mi (11.8 km) from Lido Beach and 9.2 mi (14.8 km) from Siesta Key Beach.
Make yourself at home in one of the 100 guestrooms, featuring kitchens with refrigerators and stovetops. Your bed comes with premium bedding, and all rooms are furnished with double sofa beds. Cable programming and video-game consoles are provided for your entertainment, while complimentary wired Internet access keeps you connected. Conveniences include safes and complimentary newspapers, and housekeeping is provided daily.
Take advantage of recreational opportunities offered, including an outdoor pool, a spa tub, and a fitness center. Additional amenities at this aparthotel include complimentary wireless Internet access, a television in a common area, and barbecue grills.
Barbecue grill(s)
Coffee/tea in common areas
Free reception
Number of coffee shops/cafes - 1
Free grocery shopping service
Check-in is from 3:00 PM until anytime. Guests must be at least 21 to check-in.
Front desk staff will greet guests on arrival. Due to COVID-19, this property's food and beverage options may be limited pursuant to local regulations.
This property accepts credit cards, debit cards, and cash
Enjoy a meal at the restaurant or snacks in the aparthotel's coffee shop/café. Quench your thirst with your favorite drink at the bar/lounge. For your convenience, a complimentary breakfast is served daily.
Featured amenities include a business center, express check-out, and complimentary newspapers in the lobby. Free self parking is available onsite.
Sarasota Commons Shopping Center - 0.9 km / 0.6 mi
Bobby Jones Golf Complex - 1.6 km / 1 mi
Ed Smith Stadium - 3 km / 1.9 mi
Stardust Event Center - 3.1 km / 1.9 mi
Payne Park - 3.1 km / 1.9 mi
Sarasota Childrens Garden - 4.5 km / 2.8 mi
Sarasota Opera House - 4.6 km / 2.8 mi
Westcoast Black Theatre Troupe - 4.6 km / 2.9 mi
Florida Studio Theatre - 4.7 km / 2.9 mi
Island Park - 4.9 km / 3 mi
Marie Selby Botanical Gardens - 4.9 km / 3.1 mi
Marina Jack - 5.4 km / 3.4 mi
Players Theatre - 5.6 km / 3.5 mi
Sarasota Memorial Hospital - 5.7 km / 3.5 mi
Rolling Green Golf Club - 5.8 km / 3.6 mi
Sarasota-Bradenton Intl. Airport (SRQ) - 11.2 km / 7 mi
St. Petersburg, FL (SPG-Albert Whitted) - 71.6 km / 44.5 mi
The preferred airport for Homewood Suites by Hilton Sarasota is Sarasota-Bradenton Intl. Airport (SRQ).
Pool access available from 9 AM to 10 PM.
Personal protective equipment, including masks, will be available to guests.
Social distancing measures are in place; staff at the property wear personal protective equipment; a shield is in place between staff and guests in main contact areas; guests are provided with hand sanitizer; masks are required in public areas.
Individually-wrapped food options are available for breakfast and dinner.
This property affirms that it follows the cleaning and disinfection practices of CleanStay (Hilton).
This property welcomes guests of all sexual orientations and gender identities (LGBTQ friendly).
Property follows a brand or regulatory agency's sanitization guidelines CleanStay (Hilton)
Individually-wrapped food options are available
Individually-wrapped food options are available for breakfast
Individually-wrapped food options are available for dinner
Contactless check-out is available
Masks are compulsory at the property
3470 Fruitville Rd, Sarasota, Florida 34237, United States

redpajama_set_name: RedPajamaCommonCrawl


text:
package io.fabric8.gateway.handlers.detecting.protocol.openwire.support.blob;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.net.HttpURLConnection;
import java.net.MalformedURLException;
import java.net.URL;

import io.fabric8.gateway.handlers.detecting.protocol.openwire.command.ActiveMQBlobMessage;
import io.fabric8.gateway.handlers.detecting.protocol.openwire.support.OpenwireException;

/**
 * A default implementation of {@link BlobUploadStrategy} which uses the URL
 * class to upload files or streams to a remote URL
 */
public class DefaultBlobUploadStrategy implements BlobUploadStrategy {
    private BlobTransferPolicy transferPolicy;

    public DefaultBlobUploadStrategy(BlobTransferPolicy transferPolicy) {
        this.transferPolicy = transferPolicy;
    }

    public URL uploadFile(ActiveMQBlobMessage message, File file) throws OpenwireException, IOException {
        return uploadStream(message, new FileInputStream(file));
    }

    public URL uploadStream(ActiveMQBlobMessage message, InputStream fis) throws OpenwireException, IOException {
        URL url = createUploadURL(message);

        HttpURLConnection connection = (HttpURLConnection)url.openConnection();
        connection.setRequestMethod("PUT");
        connection.setDoOutput(true);

        // use chunked mode or otherwise URLConnection loads everything into
        // memory
        // (chunked mode not supported before JRE 1.5)
        connection.setChunkedStreamingMode(transferPolicy.getBufferSize());

        OutputStream os = connection.getOutputStream();

        byte[] buf = new byte[transferPolicy.getBufferSize()];
        for (int c = fis.read(buf); c != -1; c = fis.read(buf)) {
            os.write(buf, 0, c);
            os.flush();
        }
        os.close();
        fis.close();

        if (!isSuccessfulCode(connection.getResponseCode())) {
            throw new IOException("PUT was not successful: " + connection.getResponseCode() + " "
                                  + connection.getResponseMessage());
        }

        return url;
    }

    public void deleteFile(ActiveMQBlobMessage message) throws IOException, OpenwireException {
        URL url = createUploadURL(message);

        HttpURLConnection connection = (HttpURLConnection)url.openConnection();
        connection.setRequestMethod("DELETE");
        connection.connect();
        connection.disconnect();

        if (!isSuccessfulCode(connection.getResponseCode())) {
            throw new IOException("DELETE was not successful: " + connection.getResponseCode() + " "
                                  + connection.getResponseMessage());
        }
    }

    private boolean isSuccessfulCode(int responseCode) {
        return responseCode >= 200 && responseCode < 300; // 2xx => successful
    }

    protected URL createUploadURL(ActiveMQBlobMessage message) throws OpenwireException, MalformedURLException {
        return new URL(transferPolicy.getUploadUrl() + message.getMessageId().toString());
    }
}

redpajama_set_name: RedPajamaGithub


Many people who enter the job market are faced with a number of choices in terms of type of job, industry and location. If you are looking for a new job, either because you have just graduated from college or because you have decided to change focus mid-career, a nonprofit career is a great way to combine your passion for social or human issues with your day-to-day life.
What is a nonprofit job?
A nonprofit job is a position of any type within and organization that is designated a not-for-profit.
This means that the organization was created for charitable or religious purposes like the American Red Cross, the Salvation Army or National Humane Society.
Not-for-profit organizations can either delivery programs, like the American Red Cross' disaster relief, make donations to other organizations, or create awareness about a particular topic or issue.
Because of the broad range of activities that nonprofit organizations carry out, the types of nonprofit job types that exist are equally varied. For that reason, there is not one reason to work for a nonprofit, but many reasons that are different and personal for each individual.
What are the benefits of a nonprofit job?
For most people in nonprofit careers, the biggest benefit of a nonprofit job is the ability to work with a cause for which you are extremely passionate. People find ways to apply their specialized skills – be it finance, technology, counseling or anything else – to nonprofit organizations in order to be a part of the work that they do. Work at not-for-profit organizations can be rewarding in ways that jobs in the corporate world may not be.
It is because of these benefits that many people switch into the nonprofit workforce mid-career, however it is becoming more common for idealistic young recent college grads to begin working for small nonprofit organizations so that they can do good work, and learn more about how an organization works in a very hands-on way.
With all of these rewards, why doesn't everyone work for a nonprofit organization? Quite simply, salaries and other compensation are on average much lower in not-for-profit organizations than they are for corporations and other for-profit companies. This does not mean that all non-profit organizations are struggling financially, and that all salaries are low (which is a common misconception) but that compensation is drastically lower in the nonprofit sector, and that most people are not "in it for the money." There are many large nonprofits that are able to pay higher salaries and provide the same robust benefits (comprehensive health care, tuition assistance, paid vacation) as for-profit companies.
So why work for a nonprofit? The truth is, it is a very personal choice. When you are considering taking a job with a nonprofit organization, you should ask the same questions that you would for any other job: Is this a good fit for my skills? Do I care about the work? Is this an acceptable salary? Is there upward mobility?
But most of all, ask yourself if the job will make you happy. If the answer is yes, then you can feel confident about accepting your nonprofit job.


text:
BIOHAZARD SOUND CHRONICLE II
Suleputer
The BIOHAZARD SOUND CHRONICLE II, is a limited-edition release of music from the Resident Evil game series, currently known as BIOHAZARD in Japan. It includes music from Resident Evil: The Umbrella Chronicles (2007), The Darkside Chronicles (2009), 5 (2009) and The Mercenaries (2011). The six-CD set includes a lot of previously unreleased music but also lacks some tracks that are included in individual releases.
1 Tracklist
1.1 Disk 1
Disk 1 was taken from BIOHAZARD THE UMBRELLA CHRONICLES ORIGINAL SOUND TRACK.
1. "Briefing" 1:42
2. "The Theme Of Umbrella Chronicles" 1:59
3. "Begin Here" 2:16
4. "Preparations" 2:12
5. "The Ecliptic Express" 2:01
6. "Convulsions" 1:10
7. "Trauma" 0:35
8. "Endogenous Opioid" 0:57
9. "July 1998" 1:44
10. "White Out" 2:06
11. "Mimesis" 0:57
12. "The Zombie Who Came In From The Cold" 1:02
13. "Outbreak" 1:51
14. "Salute" 1:01
15. "Endtroduction" 0:47
16. "The Mansion Incident" 0:45
17. "Swoon" 1:15
18. "July 24, 1998" 1:50
19. "Exposure" 1:19
20. "Initial R" 1:42
21. "Suicidal Explosion" 1:39
22. "Virus Syndicate" 2:29
23. "Escape Death" 0:51
24. "Blacken Sabbath" 1:39
25. "Slight Injury" 0:49
26. "Raccoon's Destruction" 1:43
27. "Fight Or Flight" 1:15
28. "Sterilization" 1:30
29. "Beasties" 1:50
30. "September 1998" 1:40
31. "Tetrodotoxin" 1:27
32. "Oriental Woman" 2:11
33. "Sympathy For The Zombie" 2:19
34. "Extinction" 0:38
35. "No Word For It" 1:43
36. "Hazmat" 0:41
37. "Live Evil" 2:24
38. "Umbrella Ribs" 0:31
39. "Unlikely Allies" 1:41
40. "To The End" 1:08
41. "Escapee" 2:20
42. "2003, Somewhere Over Russia" 0:48
43. "Corporal" 2:04
44. "No Data" 0:49
45. "Palma" 0:52
46. "You Only Live Twice" 2:05
47. "Accumulation" 1:02
48. "Nothing Is Impossible" 2:34
49. "Umbrella Lives On" 3:21
Disks 2 and free contain tracks from Biohazard: The Darkside Chronicles Original Soundtrack
1. "Memories" Shūsaku Uchiyama 2:29
2. "Overture (long ver.)" 1:46
3. "South Land" Shūsaku Uchiyama 1:42
4. "Sleeping Beauty" Shūsaku Uchiyama 2:18
5. "Dead Running" 1:45
6. "Hydra" 3:11
7. "Encounter" 0:48
8. "Raccoon City" Shūsaku Uchiyama 1:44
9. "Dark Alley" 2:21
10. "Tea Time" 1:00
11. "Horror" 1:27
12. "The Front Hall" Shūsaku Uchiyama 1:18
13. "Licker" 1:11
14. "In Pursuit of Sherry" Shūsaku Uchiyama 1:48
15. ""T"-A" Shūsaku Uchiyama 2:28
16. "G Adult Body" 3:26
17. "The First Mutation of "G"" 1:37
18. "Paths Cross" 1:03
19. "Drainage" 1:39
20. "Death Match" 1:36
21. "Escape From The Laboratory" 2:15
22. "The Third Mutation of "G"" 2:57
23. "The Forth Mutation of "G"" 4:02
24. ""T"-B" 1:53
25. "The Final Mutation of "G"" 2:57
26. "Survivors" Shūsaku Uchiyama 1:42
27. "Floating Memories" 1:44
28. "Dark Pressure" 1:54
29. "Water Devil" 2:27
30. "Death Siege" Takeshi Miura 1:46
31. "Alexia's Lullaby" 0:34
32. "Insanity's Palace" 1:48
33. "Infants" 1:05
34. "Mad" Takeshi Miura 1:16
35. "Alfred" Takeshi Miura 2:03
36. "Game of Oblivion" Takeshi Miura 4:20
37. "Father and Son" 0:56
38. "Gulp Worm" Takeshi Miura 2:22
1. "The Suspended Doll" 3:17
2. "Alexia?" 3:44
3. "Carousel" 1:01
4. "A State of Emergency" Takeshi Miura 3:06
5. "Tyrant (Mass Produced Type)" 4:33
6. "The Theme of Tyrant 3: Ver. B" Takeshi Miura 2:17
7. "Blanc" 2:09
8. "The Theme of Nosferatu" 2:00
9. "Reunion" 1:32
10. "Metamorphosis" Takeshi Miura 0:46
11. "Sorrow" Takeshi Miura 5:59
12. "Last Words" 1:18
13. "Queen" Takeshi Miura 1:05
14. "The Theme of Alexia Type I" Takeshi Miura 5:12
15. "Atonement" Takeshi Miura 1:06
16. "The Theme of Alexia Type II" Takeshi Miura 4:38
17. "Old Foe" Takeshi Miura 1:00
18. "Memento" Takeshi Miura 1:24
19. "Jabberwock" Shūsaku Uchiyama 3:16
20. "Conviction" 1:15
21. "Blood Relation" 3:14
22. "Veronica Complex" Shūsaku Uchiyama 3:11
23. "Desperation" Shūsaku Uchiyama 1:30
24. "Blood Judgment" Shūsaku Uchiyama 3:41
25. "End of The Road" Shūsaku Uchiyama 1:50
26. "The Return" 1:32
27. "Darkness Falls" Shūsaku Uchiyama 5:00
28. "Ending & Sleeping Beauty" Shūsaku Uchiyama 4:24
Disk 4 represents BIOHAZARD 5 Best Track Collection 01.
1. "Title Movie" Hideki Okukawa 0:17
2. "Opening -Chris's Arrival- (Digital Ver.)" Kōta Suzuki 3:40
3. "Item Box" Kōta Suzuki 1:35
4. "New Fear" Hideki Okukawa 1:56
5. "The Town" Hideki Okukawa 1:46
6. "First Encounter" Kōta Suzuki 1:06
7. "Majini Ⅰ" Kōta Suzuki 1:53
8. "Majini Ⅱ" Kōta Suzuki 2:14
9. "Game Over" Akihiko Narita 0:13
10. "Majini Ⅲ" Hideki Okukawa 2:52
11. "An Emergency (Digital Ver.)" Kōta Suzuki 2:38
12. "Result" Kōta Suzuki 1:06
13. "Executioner" Akihiko Narita 1:58
14. "Voice of The Darkness" Hideki Okukawa 1:53
15. "Flying Nightmare" Hideki Okukawa 1:46
16. "Pursuer and The Pursued" Hideki Okukawa 1:49
17. "Burning with Anger" Akihiko Narita 2:46
18. "Shadows of the Past" Kōta Suzuki 2:52
19. "Eerie Stillness" Hideki Okukawa 1:31
20. "Majini Ⅳ" Hideki Okukawa 1:23
21. "Majini V" Hideki Okukawa 2:27
22. "Get out!" Kōta Suzuki 2:31
23. "Majini's Trap Ⅰ" Kōta Suzuki 1:56
24. "The Patrol Boat" Akihiko Narita 2:44
25. "Evil Mutation" Akihiko Narita 3:38
26. "Ancient Noise" Kōta Suzuki 2:08
27. "Majini VI" Hideki Okukawa 2:26
28. "Majini's Trap Ⅱ" Kōta Suzuki 1:15
29. "Underground Garden" Hideki Okukawa 1:27
30. "The Claw" Kōta Suzuki 2:15
31. "Gigantic Attack" Akihiko Narita 3:12
32. "Majini Ⅶ" Kōta Suzuki 2:36
33. "Haze of Horror" Akihiko Narita 2:05
34. "The Mask" Kōta Suzuki 2:20
35. "Two on Two" Kōta Suzuki 3:05
1. "Old Friends, New Enemies" Akihiko Narita 1:49
2. "Sad but true" Akihiko Narita 3:30
3. "Trust" Akihiko Narita 1:59
4. "Majini Ⅷ" Akihiko Narita 2:50
5. "Shot or Death" Kōta Suzuki 2:16
6. "Fragment of Fears" Kōta Suzuki 1:28
7. "The Sign" Kōta Suzuki 2:36
8. "A Big Despair (Digital Ver.)" Kōta Suzuki 2:54
9. "Message" Hideki Okukawa 1:29
10. "Majini Ⅸ -in flames-" Akihiko Narita 3:35
11. "Rematch" Kōta Suzuki 1:58
12. "Wind of Madness (Digital Ver.)" 4:10
13. "The Vulnerability" 1:35
14. "Sky-high Skirmish" 3:06
15. "The Final Curtain" 1:16
16. "Deep Ambition (Digital Ver.)" 3:25
17. "Striker" Akihiko Narita 1:05
18. "Homeward Bound!" Kōta Suzuki 1:01
19. "Pray -Theme Song- (Digital Ver.)" Kōta Suzuki 3:00
20. "Plan of Uroboros (Digital Ver.)" Kōta Suzuki 3:22
21. "Menu" Kōta Suzuki 2:04
22. "Viewer" Kōta Suzuki 2:00
23. "Colors" Kōta Suzuki 1:38
24. "Assault Fire" Hideki Okukawa 3:17
25. "Dreamy Loops" Kōta Suzuki 0:54
26. "On the Bass" Kōta Suzuki 1:06
27. "Rust in summer 2008" Akihiko Narita 3:53
28. "KILLERS" Kōta Suzuki 2:57
29. "Do you challenge Again?" Kōta Suzuki 1:00
Disk 6 consists of tracks from Resident Evil 5: Gold Edition and Resident Evil: The Mercenaries 3D. The first sixteen are from the former, with tracks 1-7 representing Lost in Nightmares, 8-13, Desperate Escape, and 14-16 being from The Mercenaries Reunion.
1. "Lost in Nightmares" 1:34
2. "Spencer's Mansion" 2:50
3. "Needles of Ceiling" 0:51
4. "Oubliette" 2:40
5. "Nest of Insanity" 2:12
6. "Frenzied Guardian" 1:19
7. "Save Theme -in Memories-" 1:00
8. "Desperate Escape" 1:09
9. "Jill & Josh 1" 1:25
10. "Jill & Josh 2" 1:27
12. "When the Chopper Comes" 2:17
13. "Proof of the Trust" 1:16
14. "Colors -Reunion Mix-" 1:20
15. "The Mercenaries Reunion" 1:57
16. "Dreamy Loops -Reunion Mix-" 0:57
17. "Soldiers's Dance (Digital ver.)" 1:17
18. "M3D Title (Digital ver.)" 0:55
19. "M3D Main Menu" 1:30
20. "Calling" 1:09
21. "The Path for Fight" 1:41
22. "Secret Lines" 1:50
23. "Subspecies" 2:01
24. "Breaking Limit" 1:36
25. "Voices" 1:00
26. "Contamination" 1:31
27. "Power of Flames" 1:38
28. "Crying From Far away" 1:40
29. "Shotting in Desert!" 1:37
30. "Upsurge of Sentiment" 1:37
31. "M3D Game Over" 0:11
32. "A BraveMan" 1:26
33. "Reckless Driving of LMO" 1:39
34. "Ghost on the Blue" 1:31
35. "A Warrior filled with Hope" 1:39
36. "Hurry Up!!" 1:38
37. "Impending Threat" 2:05
38. "M3D End Roll (Digital ver.)" 3:01
39. "Soldiers's Dance (Orchestra ver.)" 1:20
40. "M3D Title (Orchestra ver.)" 0:57
41. "M3D End Roll (Orchestra ver.)" 3:04
Go back to: Franchise navigation
Dedicated game soundtracks
1 (original) (Original Remix • Symphony, Op. 91) • 2 (original) (Original • Complete • Remix) • 3: Nemesis • CODE:Veronica (Original • Complete) • 1 (remake) (Remaster HD) • 4 (Original • Soundtrack book) • 5 • Revelations (Original • Digital) • 6 (Original • Digital) • Revelations 2 (Official • Special • Episode 1 • Episode 2 • Episode 3 • Episode 4) • 7: Biohazard • 2 (remake) (Digital • Original) • 3 (remake)
Outbreak • Umbrella Chronicles • Darkside Chronicles • The Mercenaries 3D • Operation Raccoon City • Umbrella Corps • Resistance
Score: Apocalypse • Extinction • Afterlife • Retribution • The Final Chapter • Degeneration • Damnation • Vendetta
Generic: Resident Evil • Apocalypse • Extinction
Promotional soundtracks
ReMIX sample • biohazard 4 e-CAPCOM ORIGINAL Preview Sound Clips • Biohazard 5 Selection Track • DARKSIDE SYMPHONY • LAW'S -Biohazard The Darkside Chronicles Edition • Revelations TGS 2011 Limited Edition • Revelations Special Arrange Track • Resident Evil 0 Special Medley • Laced Records (2 • 3: Nemesis • CODE:Veronica • 1 (remake) • 0 • 4 • 5 • 6)
Pachi-slot
Biohazard • Revelations • 5 • 6
Compilation & other
Biohazard Orchestra Album • Ten Years of Resident Evil • Sound Chronicle I • Sound Chronicle II
Retrieved from "https://residentevil.fandom.com/wiki/BIOHAZARD_SOUND_CHRONICLE_II?oldid=751250"