let $\mathcal{B}_{i}=\\{e_{i}\mid(e_{1},e_{2})\in\mathcal{B}\\}$ for every
$i\in\\{1,2\\}$. We construct an instance $(\mathcal{I},k)$ of
$\textsc{MinCSP}({\sf m},{\sf s})$ with the same parameter.

We start by introducing a variable for every vertex of $V(G_{1})\cup V(G_{2})$
and add the following crisp constraints:

  * •

$u\equiv v$ for every $uv\in E(G_{1})\setminus\mathcal{B}_{1}$,

  * •

$u{\sf s}v$ for every $(u,v)\in E(G_{2})\setminus\mathcal{B}_{2}$,

  * •

$s{\sf m}t$,

  * •

$t{\sf m}v$ for every $v\in V(G_{2})$.

Moreover, for every bundle $b=(xy,(u,v))\in\mathcal{B}$, we introduce two
fresh variables $z_{b}$ and $z_{b}^{\prime}$ and the following constraints:

  * •

crisp constraints $x{\sf s}z_{b}$ and $y{\sf s}z_{b}^{\prime}$,

  * •

crisp constraints $z_{b}\equiv^{+}u$ and $z_{b}^{\prime}\equiv^{+}v$ and

  * •

the soft constraint $z_{b}{\sf s}z_{b}^{\prime}$.

This completes the reduction. Clearly, it can be implemented in polynomial
time. We claim that $(G_{1},G_{2},s,t,\mathcal{B},k)$ is a yes-instance of
PCFAS if and only if $(\mathcal{I},k)$ is a yes-instance of MinCSP$({\sf
m},{\sf s})$.

Forward direction. Suppose $X\subseteq\mathcal{B}$ is a subset of $k$ pairs
such that $X_{1}$ is an $st$-cut in $G_{1}$ and $X_{2}$ is a FAS for $G_{2}$,
where $X_{i}=\\{e_{i}\mid(e_{1},e_{2})\in X\\}$. Let $X^{\prime}$ be the set
of constraints that contains $z_{b}{\sf s}z_{b}^{\prime}$ for all $b\in X$. We
claim that $I-X^{\prime}$ is satisfied by assignment $\alpha$ constructed as
follows. First, set

$\displaystyle\alpha(s)=[0,1],$ $\displaystyle\alpha(t)=[1,2],$

For every vertex $u\in V(G_{1})$, set

$\alpha(u)=\begin{cases}\alpha(s)&\text{there is an }su\text{-path in
}G_{1}-X_{1},\\\ \alpha(t)&\text{otherwise}.\end{cases}$

We know that $G_{2}-X_{2}$ is acyclic. Hence, there is an ordering
$u_{1},\dotsc,u_{\ell}$ of the vertices in $G_{2}$ such that there is no arc
in $G_{2}-X_{2}$ from $u_{i}$ to $u_{j}$ for any $j<i$. Then, we set
$\alpha(u_{i})=[2,2+i]$ for every $i$ with $1\leq i\leq\ell$. For every pair
$b=(xy,uv)\in\mathcal{B}$, assign

$\displaystyle\alpha(z_{b})=[\alpha(x)^{-},\alpha(u)^{+}],$
$\displaystyle\alpha(z_{b}^{\prime})=[\alpha(y)^{-},\alpha(v)^{+}].$

By definition, $\alpha$ satisfies all crisp constraints in $I$. All soft
constraints are of the form $z_{b}{\sf s}z_{b}^{\prime}$ for some pair
$b=(xy,(u,v)\in\mathcal{B}$. If such a constraint is not in $X^{\prime}$, then
the edge $xy$ is present in $G_{1}-X_{1}$. Therefore, $\alpha(x)=\alpha(y)$
and $\alpha(z_{b})^{-}=\alpha(z_{b}^{\prime})^{-}$. Similarily, the arc
$(u,v)$ is present in $G_{2}-X_{2}$, which implies that
$\alpha(u)^{+}<\alpha(v)^{+}$ and therefore
$\alpha(z_{b})^{+}<\alpha(z_{b}^{\prime})^{+}$. Therefore, the assignment
$\alpha$ satisfies the soft constraint $z_{b}{\sf s}z_{b}^{\prime}$.

Backward direction. Suppose $Y$ is a set of at most $k$ soft constraints such
that $\mathcal{I}-Y$ is consistent. Let $Y^{\prime}\subseteq\mathcal{B}$
contain all pairs of edges $b=(xy,(u,v)\\})$ such that constraint $z_{b}{\sf
s}z_{b}^{\prime}$ is in $Y$. Let
$Y_{i}^{\prime}=\\{e_{i}\mid(e_{1},e_{2})\\}$. We start by showing that
$Y_{1}^{\prime}$ is an $st$-cut in $G_{1}$. For the sake of contradiction,
assume there is a path in $G_{1}-Y_{1}^{\prime}$ from $s$ to $t$. This path
corresponds to a chain of constraints in $I$ linking $s$ and $t$ by
$\equiv$-constraints and ${\sf s}$-constraints. This implies that the left
endpoints of $s$ and $t$ match and this contradicts the crisp constraint
$s{\sf m}t$.

We finish by showing that $Y_{2}^{\prime}$ is a FAS for $G_{2}$. Suppose to
the contrary that this is not the case and let $C$ be a directed cycle in
$G_{2}-Y_{2}^{\prime}$. The cycle $C$ corresponds to a cycle of constraints in
$I$ linked by ${\sf s}$-constraints and $\equiv^{+}$-constraints. The
constraints implied on the right endpoints of the intervals on $C$ are not
satisfiable since there is at least one ${\sf s}$-constraint on the cycle,
hence $C$ is inconsistent. ∎

###  6.4 Intractable Fragments Containing ${\sf d}$, ${\sf o}$ or ${\sf p}$

The following three theorems, which show W[1]-hardness of
$\textsc{MinCSP}({\sf d},{\sf p})$, $\textsc{MinCSP}({\sf d},{\sf o})$, and
$\textsc{MinCSP}({\sf p},{\sf o})$, are all based on fairly similar
parameterized reductions from Sim-DFAS (which is a W[1]-hard problem by
Theorem 26). In all three cases, we reduce an instance
$\mathcal{I}=(D_{1},D_{2},k)$ with $V=V(D_{1})=V(D_{2})$ of Sim-DFAS to an
instance of the respective fragment of MinCSP. Our reductions preserve the
parameter $k$ exactly and they introduce one variable $v$ for every vertex in
$V$ together with additional variables and constraints for every arc $(u,v)\in
A_{1}\cup A_{2}$.

######  Theorem 29.

$\textsc{MinCSP}({\sf d},{\sf p})$ is W[1]-hard.

###### Proof.

$u$$h_{u,v}$$v$${\sf p}$${\sf d}$$(u,v)\in A_{1}\setminus
A_{2}$$u$$h_{u,v}$$v$${\sf p}$${\sf d}$$(u,v)\in A_{2}\setminus
A_{1}$$u$$v$${\sf d}$$(u,v)\in A_{2}\cap A_{1}$ Figure 6: The variables and
constraints introduced in the construction of the proof of Theorem 29 for
every arc $(u,v)$ of the Sim-DFAS instance.

Let $\mathcal{I}=(D_{1},D_{2},k)$ with $V=V(D_{1})=V(D_{2})$ be an instance of
Sim-DFAS. We construct an instance $\mathcal{I}^{\prime}$ of
$\textsc{MinCSP}({\sf d},{\sf p})$ with the same parameter $k$ and where we
have one variable $v$ for every vertex in $V$. Additionally, we introduce the
following variables and constraints. For every arc $(u,v)\in(A_{1}\cup
A_{2})\setminus(A_{1}\cap A_{2})$, we add a fresh variable $h_{u,v}$.
Moreover, for every arc $(u,v)\in A_{1}\cup A_{2}$, we distinguish the
following cases, which are illustrated in Figure 6:

  * •

If $(u,v)\in A_{1}\setminus A_{2}$, then we add the constraints $u{\sf
p}h_{u,v}$ and $h_{u,v}{\sf d}v$.

  * •

If $(u,v)\in A_{2}\setminus A_{1}$, then we add the constraints: $h_{u,v}{\sf
p}u$ and $h_{u,v}{\sf d}v$.

  * •

If $(u,v)\in A_{1}\cap A_{2}$, then we add the constraint $u{\sf d}v$.

This completes the construction of $\mathcal{I}^{\prime}$, which is clearly a
polynomial-time reduction. It remains to show that $\mathcal{I}$ and
$\mathcal{I}^{\prime}$ are equivalent. Bad cycles in this case are cycles with
${\sf p}$-arcs in the same direction and no ${\sf d}$-arcs meeting head-to-
head by Lemma 8.

Forward direction. Let $X\subseteq A_{1}\cup A_{2}$ be a solution for
$\mathcal{I}$. We claim that any set $X^{\prime}$ that for every arc in
$X^{\prime}$ contains an arbitrary constraint introduced for the arc is a
solution for $\mathcal{I}^{\prime}$. Suppose for a contradiction that this is
not the case and let $C^{\prime}$ be a bad cycle of
$\mathcal{I}^{\prime}-X^{\prime}$ witnessing this. Let $C$ be the sequence of
arcs corresponding to $C^{\prime}$ in $(V,A_{1}\cup A_{2})$. If $C$ is not a
directed cycle, then it contains 2 consecutive arcs that are head-to-head and
therefore also $C^{\prime}$ contains 2 consequitive $d$-arcs that are head-to
head, contradicting our assumption that $C^{\prime}$ is a bad cycle.
Therefore, $C$ is directed and contains an arc in $A_{1}\setminus A_{2}$ and
an arc in $A_{2}\setminus A_{1}$. However, then $C^{\prime}$ is not a bad
cycle because it contains two $p$-arcs in opposite directions. Therefore, $C$
is a directed cycle in $D_{1}$ or in $D_{2}$ and this contradicts our
assumption that $X$ is a solution for $\mathcal{I}$.

Backward direction. Let $X^{\prime}$ be a solution for $\mathcal{I}^{\prime}$
and let $X\subseteq A_{1}\cup A_{2}$ be the set obtained from $X^{\prime}$ by
taking every arc such that $X^{\prime}$ contains a corresponding constraint.
We claim that $X$ is a solution for $\mathcal{I}$. Suppose for a contradiction
that this is not the case and let $C$ be a cycle in $D_{i}-X$ witnessing this.
Then, the corresponding cycle $C^{\prime}$ in $\mathcal{I}^{\prime}$ must be a
bad cycle and this contradicts our assumption that $X^{\prime}$ is a solution
for $\mathcal{I}$. ∎

######  Theorem 30.

$\textsc{MinCSP}({\sf d},{\sf o})$ is W[1]-hard.

###### Proof.

$u$$h_{u,v}$$v$${\sf d}$${\sf o}$$(u,v)\in A_{1}\setminus
A_{2}$$u$$h_{u,v}$$v$${\sf d}$${\sf o}$$(u,v)\in A_{2}\setminus
A_{1}$$u$$v$${\sf d}$$(u,v)\in A_{2}\cap A_{1}$ Figure 7: The variables and
constraints introduced in the construction of the proof of Theorem 30 for
every arc $(u,v)$ of the Sim-DFAS instance.

Let $\mathcal{I}=(D_{1},D_{2},k)$ with $V=V(D_{1})=V(D_{2})$ be an instance of
Sim-DFAS. We construct an instance $\mathcal{I}^{\prime}$ of
$\textsc{MinCSP}({\sf d},{\sf o})$ with the same parameter $k$ and where we
have one variable $v$ for every vertex in $V$. Additionally, we introduce the
following variables and constraints. For every arc $(u,v)\in(A_{1}\cup
A_{2})\setminus(A_{1}\cap A_{2})$, we add the variable $h_{u,v}$. Moreover,
for every arc $(u,v)\in A_{1}\cup A_{2}$, we distinguish the following cases,
which are illustrated in Figure 7:

  * •

If $(u,v)\in A_{1}\setminus A_{2}$, we add the constraints $u{\sf d}h_{u,v}$
and $v{\sf o}h_{u,v}$.

  * •

If $(u,v)\in A_{2}\setminus A_{1}$, we add the constraints $u{\sf d}h_{u,v}$
and $h_{u,v}{\sf o}v$.

  * •

If $(u,v)\in A_{1}\cap A_{2}$, we add the constraint $u{\sf d}v$.

This completes the construction of $\mathcal{I}^{\prime}$, which is clearly a
polynomial-time reduction. It remains to show that $\mathcal{I}$ and
$\mathcal{I}^{\prime}$ are equivalent. Bad cycles here are cycles with all
${\sf d}$-arcs in the same direction and all ${\sf o}$-arcs in the same
direction (the directions of a ${\sf d}$-arc and an ${\sf o}$-arc may differ)
by Lemma 8.

Forward direction. Let $X\subseteq A_{1}\cup A_{2}$ be a solution for
$\mathcal{I}$. We claim that any set $X^{\prime}$ that for every arc in $X$
contains an arbitrary constraint introduced for the arc is a solution for
$\mathcal{I}^{\prime}$. Suppose for a contradiction that this is not the case
and let $C^{\prime}$ be a bad cycle of $\mathcal{I}^{\prime}-X^{\prime}$
witnessing this. Let $C$ be the sequence of arcs corresponding to $C^{\prime}$
in $(V,A_{1}\cup A_{2})$. If $C$ is not a directed cycle, then it contains 2
arcs in opposite directions, which implies that $C^{\prime}$ contains 2 ${\sf
d}$-arcs in opposite directions and therefore contradicts our assumption that
$C^{\prime}$ is a bad cycle. Therefore, $C$ is directed. Suppose now that $C$
contains an arc in $A_{1}\setminus A_{2}$ and an arc in $A_{2}\setminus
A_{1}$. However, then $C^{\prime}$ is not a bad cycle because it contains two
${\sf o}$-arcs in opposite directions. Therefore, $C$ is a directed cycle in
$D_{1}$ or in $D_{2}$, contradicting our assumption that $X$ is a solution for
$\mathcal{I}$.

Backward direction. Let $X^{\prime}$ be a solution for $\mathcal{I}^{\prime}$
and let $X\subseteq A_{1}\cup A_{2}$ be the set obtained from $X^{\prime}$ by
taking every arc such that $X^{\prime}$ contains a corresponding constraint.
We claim that $X$ is a solution for $\mathcal{I}$. Suppose for a contradiction
that this is not the case and let $C$ be a cycle in $D_{i}-X$ witnessing this.
Then, the corresponding cycle $C^{\prime}$ in $\mathcal{I}^{\prime}$ must be a
bad cycle, a contradiction to our assumption that $X^{\prime}$ is a solution
for $\mathcal{I}$. ∎

######  Theorem 31.

$\textsc{MinCSP}({\sf p},{\sf o})$ is W[1]-hard.

###### Proof.

$u$$h_{u,v}^{1}$$h_{u,v}^{2}$$v$${\sf o}$${\sf p}$${\sf o}$$(u,v)\in
A_{1}\setminus A_{2}$$u$$h_{u,v}^{1}$$h_{u,v}^{2}$$v$${\sf o}$${\sf p}$${\sf
o}$$(u,v)\in A_{2}\setminus A_{1}$$u$$h_{u,v}^{1}$$v$${\sf o}$${\sf
o}$$(u,v)\in A_{2}\cap A_{1}$ Figure 8: The variables and constraints
introduced in the construction of the proof of Theorem 31 for every arc
$(u,v)$ of the Sim-DFAS instance.

Let $\mathcal{I}=(D_{1},D_{2},k)$ with $V=V(D_{1})=V(D_{2})$ be an instance of
Sim-DFAS. We construct an instance $\mathcal{I}^{\prime}$ of
$\textsc{MinCSP}({\sf p},{\sf o})$ with the same parameter $k$ and where we
have one variable $v$ for every vertex in $V$. Additionally, we introduce the
following variables and constraints. For every arc $(u,v)\in(A_{1}\cup
A_{2})\setminus(A_{1}\cap A_{2})$, we add two variables $h_{u,v}^{1}$ and
$h_{u,v}^{2}$. Finally, for every arc $(u,v)\in A_{1}\cup A_{2}$, we
distinguish the following cases, which are illustrated in Figure 8:

  * •

If $(u,v)\in A_{1}\setminus A_{2}$, we add the constraints $u{\sf
o}h_{u,v}^{1}$, $h_{u,v}^{1}{\sf p}h_{u,v}^{2}$, and $v{\sf o}h_{u,v}^{2}$.

  * •

If $(u,v)\in A_{2}\setminus A_{1}$, we add the constraints $h_{u,v}^{1}{\sf
o}u$, $h_{u,v}^{1}{\sf p}h_{u,v}^{2}$, and $h_{u,v}^{2}{\sf o}v$.

  * •

If $(u,v)\in A_{1}\cap A_{2}$, we add one fresh variable $h_{u,v}$ and the
constraints $u{\sf o}h_{u,v}$ and $h_{u,v}{\sf o}v$.

This completes the construction of $\mathcal{I}^{\prime}$ and this is clearly
a polynomial-time reduction. It remains to show that $\mathcal{I}$ and
$\mathcal{I}^{\prime}$ are equivalent. Before the proof, we recall the
definition of bad cycles for the case of $\textsc{MinCSP}({\sf p},{\sf o})$
from Lemma 8: bad cycles are (1) directed cycles of ${\sf o}$-arcs and (2)
cycles with all ${\sf p}$-arcs in the same (forward) direction with every
consecutive pair of ${\sf o}$-arcs in the reverse direction separated by a
${\sf p}$-arc. Note that (2) implies that directed cycles of ${\sf p}$-arcs
are bad.

Forward direction. Let $X\subseteq A_{1}\cup A_{2}$ be a solution for
$\mathcal{I}$. We claim that every set $X^{\prime}$ that for every arc $a$ in
$X$ contains any of the constraints introduced for $a$ is a solution for
$\mathcal{I}^{\prime}$. Suppose to the contrary that this is not the case and
let $C^{\prime}$ be a bad cycle in $\mathcal{I}^{\prime}-X^{\prime}$
witnessing this. Let $C$ be the sequence of arcs corresponding to $C^{\prime}$
in $(V,A_{1}\cup A_{2})$. We first show that $C$ is a directed cycle.
Otherwise, $C$ contains 2 arcs $a$ and $a^{\prime}$ that are pointing in
opposite directions. If $a\in A_{1}\setminus A_{2}$ and $a^{\prime}\in
A_{2}\setminus A_{1}$ (or vice versa), then $C^{\prime}$ contains two $p$-arcs
in opposite directions, contradicting our assumption that $C^{\prime}$ is a
bad cycle. Otherwise, $a\in A_{1}\cap A_{2}$ and $a^{\prime}\in A_{1}\cup
A_{2}$, but then $C^{\prime}$ contains two consecutive $o$-arcs in reverse
direction; this contradicts once again our assumption that $C^{\prime}$ is
bad. This shows that $C$ is a directed cycle. Therefore, if $C$ is also in
$D_{1}$ or in $D_{2}$, we obtain a contradiction to our assumption that $X$ is
a solution for $\mathcal{I}$. Otherwise, $C$ uses at least one arc from
$A_{1}\setminus A_{2}$ and at least one arc from $A_{2}\setminus A_{1}$.
Hence, $C$ contains an arc $(u_{1},v_{1})\in A_{1}\setminus A_{2}$ and an arc
$(u_{2},v_{2})\in A_{2}\setminus A_{1}$ such that $C$ contains only arcs from
$A_{1}\cap A_{2}$ in the path from $a_{1}$ to $a_{2}$ in $C$. But then,
$C^{\prime}$ contains the constraints $v_{1}{\sf o}h_{u_{1},v_{1}}^{2}$ and
$h_{u_{2},v_{2}}^{1}{\sf o}u_{2}$. Moreover, between these two constraints,
$C^{\prime}$ contains only forward $o$ constraints, which contradicts our
assumption that $C^{\prime}$ is a bad cycle in $\mathcal{I}^{\prime}$.

Backward direction. Let $X^{\prime}$ be a solution for $\mathcal{I}^{\prime}$
and let $X\subseteq A_{1}\cup A_{2}$ be the set obtained from $X^{\prime}$ by
taking every arc such that $X^{\prime}$ contains a corresponding constraint.
We claim that $X$ is a solution for $\mathcal{I}$. Suppose for a contradiction
that this is not the case and let $C$ be a cycle in $D_{i}-X$ witnessing this.
Then, the corresponding cycle $C^{\prime}$ in $\mathcal{I}^{\prime}$ is a bad
cycle contradicting our assumption that $X^{\prime}$ is a solution for
$\mathcal{I}^{\prime}$. ∎

##  7 Approximation

Our previous results imply that MinCSP$(\cal A)$ is W[1]-hard. We will now
take a brief look on the approximability of this problem, and show that
MinCSP$({\sf r})$ is not approximable in polynomial time within any constant
when ${\sf r}\in\cal A\setminus\\{\equiv\\}$, but approximable in fpt time
within a factor of $2$. We refer the reader to the textbook by Ausiello et.
al. [5] for more information about polynomial-time approximability, and to the
surveys by Marx [49] and Feldmann et al. [30] for an introduction to
parameterized approximability. We will exclusively consider minimisation
problems in the sequel. Formally speaking, a minimisation problem is a 3-tuple
$(X,sol,cost)$ where

  1. 1.

$X$ is the set of instances.

  2. 2.

For an instance $x\in X$, $sol(x)$ is the set of feasible solutions for $x$,
the length of each $y\in sol(x)$ is polynomially bounded in $\lVert x\rVert$,
and it is decidable in polynomial time (in $\lVert x\rVert$) whether $y\in
sol(x)$ holds for given $x$ and $y$.

  3. 3.

For an instance $x\in X$ with feasible solution $y$, $cost(x,y)$ is a
polynomial-time computable positive integer.

The objective of the minimisation problem $(X,sol,cost)$ is to find an
solution $z$ of minimum cost for a given instance $x\in X$ i.e. a solution $z$
with $cost(x,z)=opt(x)$ where $opt(x)=\min\\{cost(x,y)\mid y\in sol(x)\\}$. If
$y$ is a solution for the instance $x$, then the performance ratio of $y$ is
defined as $cost(x,y)/opt(x)$. For $c\geq 1$, we say that an algorithm is a
factor-$c$ approximation algorithm if it always computes a solution with
performance ratio at most $c$ i.e. the cost of solutions returned by the
algorithm is at most $c$ times greater than the minimum cost. One often
replaces the constant $c$ with a function of instance $x$ but this is not
needed in this paper.

The starting point of the polynomial-time hardness-of-approximation results is
the following consequence of the Unique Games Conjecture (UGC) of Khot [36].

######  Theorem 32 (Corollary 1.2 in [34]).

Assuming UGC, it is NP-hard to $c$-approximate Directed Feedback Arc Set for
any $c>1$.

By Lemma 8, an instance $I$ of $\textsc{CSP}({\sf r})$ for ${\sf r}\in\cal
A\setminus\\{\equiv,{\sf m}\\}$ is consistent if and only if the arc-labelled
graph $G_{I}$ has no directed cycles. Hence, $\textsc{MinCSP}({\sf r})$ is
equivalent to DFAS in these cases. By Lemma 4, the relation ${\sf m}$
implements ${\sf p}$ so there is a polynomial-time reduction from
$\textsc{MinCSP}({\sf p})$ to $\textsc{MinCSP}({\sf m})$ that preserves
approximation factors. Thus, we conclude the following.

######  Observation 33.

Let $\Gamma\subseteq\cal A$ be interval constraint language. If
$\Gamma\neq\\{\equiv\\}$, then, assuming UGC, it is NP-hard to $c$-approximate
MinCSP$(\Gamma)$ for any $c>1$.

We continue with fpt-approximability of minimization problems. For a
minimization problem $(X,sol,cost)$ parameterized by the solution size $k$, a
factor-$c$ fpt-approximation algorithm is an algorithm that

  1. 1.

takes a tuple $(x,k)$ as input where $x\in X$ is an instance and
$k\in\mathbb{N}$,

  2. 2.

either returns that there is no solution of size at most $k$ or returns a
solution of size at most $c\cdot k$, and

  3. 3.

runs in time $f(k)\cdot\lVert x\rVert^{O(1)}$ where
$f:\mathbb{N}\rightarrow\mathbb{N}$ is some computable function.

######  Theorem 34 ([46]).

Sub-DFAS is $2$-approximable in $O^{*}(2^{O(k)})$ time.

######  Theorem 35.

MinCSP$(\cal A)$ is $2$-approximable in $O^{*}(2^{O(k^{3})})$ time and
$4$-approximable in $O^{*}(2^{O(k)})$ time.

###### Proof.

Let $(\mathcal{I},k)$ be an instance of MinCSP$(\cal A)$. Replace every
constraint $x\\{{\sf o}\\}y$ by its implementation in $\\{{\sf s},{\sf f}\\}$
according to Lemma 5. By Lemma 4, this does not change the cost of the
instance. Using Table 1, we can rewrite all constraints of
$\mathcal{I}^{\prime}$ as conjunctions of two atomic constraints of the form
$x<y$ and $x=y$. Let $S$ be the set of all atomic constraints. Note that we
can view $S$ as an instance of $\textsc{MinCSP}(<,=)$. The algorithm is then
to check whether $(S,2k)$ is a yes-instance of $\textsc{MinCSP}(<,=)$ by
casting it as an instance of Sub-DFAS according to Lemma 15. For correctness,
observe that deleting $k$ constraints in $\mathcal{I}^{\prime}$ corresponds to
deleting at most $2k$ constraints in $S$, hence if $(\mathcal{I}^{\prime},k)$
is a yes-instance, then so is $(S,2k)$. On the other hand, if deleting any
subset of $2k$ constraints from $S$ does not make it consistent, then deleting
any subset of $k$ constraints from $\mathcal{I}^{\prime}$ cannot make it
consistent either.

The parameter $k$ is unchanged so the time complexity follows from Theorems 14
and 34, respectively. ∎

Weighted MinCSP is a generalization of MinCSP where every constraint in the
instance $(\mathcal{I},k)$ is assigned a positive integer weight, and we also
have a weight budget $W$. The goal is now to find a set $X$ of at most $k$
constraints with total weight at most $W$ such that $I-X$ is consistent. The
parameter is still $k$ – the size of deletion set. This strictly generalizes
MinCSP by assigning unit weights to all constraints and setting the weight
budget $W=k$. Weighted Subset Directed Feedback Arc Set has been shown to be
in FPT [41] using recently introduced directed flow augmentation technique.
While the running time is not explicitly stated in the corresponding theorem
of [41], it is analysed in Section 5 of [41].

######  Theorem 36 ([41]).

Weighted Subset Directed Feedback Arc Set can be solved in time
$O^{*}(2^{O(k^{8}\log k)})$.

The reduction in Lemma 15 readily implies that Weighted MinCSP$(<,=)$ is in
FPT and we obtain the following.

######  Observation 37.

Weighted MinCSP$(\cal A)$ is $2$-approximable in time $O^{*}(2^{O(k^{8}\log
k)})$.

##  8 Discussion

We have initiated a study of the parameterized complexity of MinCSP for
Allen’s interval algebra. We prove that MinCSP restricted to the relations in
$\cal A$ exhibits a dichotomy: MinCSP$(\Gamma)$ is either fixed-parameter
tractable or W[1]-hard when $\Gamma\subseteq\cal A$. Even though the
restriction to the relations in $\cal A$ may seem severe, one should keep in
mind that a CSP instance over $\cal A$ is sufficient for representing definite
information about the relative positions of intervals. In other words, such an
instance can be viewed as a data set of interval information and the MinCSP
problem can be viewed as a way of filtering out erroneous information (that
may be the result of contradictory sources of information, noise in the
measurements, human mistakes etc.) Various ways of “repairing” inconsistent
data sets of qualitative information have been thoroughly discussed by many
authors; see, for instance, [8, 20, 21] and the references therein.

Proving a full parameterized complexity classification for Allen’s interval
algebra is hindered by a barrier: such a classification would settle the
parameterized complexity of Directed Symmetric Multicut, and this problem is
considered to be one of the main open problems in the area of directed graph
separation problems [28, 41]. This barrier comes into play even in very
restricted cases: as an example, it is not difficult to see that MinCSP for
the two Allen relations $({\sf f}\>\cup\>{\sf fi})$ and $({\sf
f}\>\cup\>\equiv)$ is equivalent to the MinCSP problem for the two PA
relations $\neq$ and $\leq$ and thus equivalent to Directed Symmetric
Multicut.

One way of continuing this work without necessarily settling the parameterized
complexity of Directed Symmetric Multicut is to consider fpt approximability:
it is known that Directed Symmetric Multicut is $2$-approximable in fpt time
[28]. Thus, a possible research direction is to analyse the fpt
approximability for MinCSP$(\Gamma)$ when $\Gamma$ is a subset of $2^{\cal A}$
or, more ambitiously, when $\Gamma$ is first-order definable in $\cal A$. A
classification that separates the cases that are constant-factor fpt
approximable from those that are not may very well be easier to obtain than
mapping the FPT/W[1] borderline. There is at least one technical reason for
optimism here, and we introduce some definitions to outline this idea. An
$n$-ary relation $R$ is said to have a primitive positive definition (pp-
definition) in a structure $\Gamma$ if

$R(x_{1},\ldots,x_{n})\equiv\exists x_{n+1},\ldots,x_{n+n^{\prime}}\colon
R_{1}(\mathbf{x}_{1})\wedge\ldots\wedge R_{m}({\mathbf{x}_{m}}),$

where each $R_{i}\in\Gamma\cup\\{=\\}$ and each $\mathbf{x}_{i}$ is a tuple of
variables over $x_{1},\ldots,x_{n}$, $x_{n+1},\ldots,x_{n+n^{\prime}}$ with
the same length as the arity of $R_{i}$. If, in addition, each
$R_{i}\in\Gamma$ then we say that $R$ has an equality-free primitive positive
definition (efpp-definition) in $\Gamma$. Bonnet et al. [14, Lemma 10] have
shown that constant-factor fpt approximability is preserved by efpp-
definitions [14], i.e. if $R$ is efpp-definable in $\Gamma$ and
MinCSP$(\Gamma)$ is constant-factor fpt approximable, then
MinCSP$(\Gamma\cup\\{R\\})$ is also constant-factor fpt approximable. Bonnet
et al. focus on Boolean domains, but it is clear that their Lemma 10 works for
problems with arbitrarily large domains. Lagerkvist [45, Lemma 5] has shown
that in most cases one can use pp-definitions instead of efpp-definitions.
This implies that the standard algebraic approach via polymorphisms (that for
instance underlies the full complexity classification of finite-domain CSPs
[15, 57]) often becomes applicable when analysing constant-factor fpt
approximability. One should note that, on the other, the exact complexity of
MinCSP is only preserved by much more limited constructions such as
proportional implementations (see Section 5.2. in [37]). We know from the
literature that this may be an important difference: it took several years
after Bonnet et al.’s classification of approximability before the full
classification of exact parameterized complexity was obtained using a much
more complex framework [39]. It is also worth noting that parameterized
approximation results for MinCSP may have very interesting consequences, e.g.
[14] resolved the parameterized complexity of Even Set, which was a long-
standing open problem.

## References

  * [1] Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh.  Simultaneous feedback vertex set: A parameterized perspective.  ACM Transactions on Computation Theory, 10(4):1–25, 2018.
  * [2] Akanksha Agrawal, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Simultaneous feedback edge set: a parameterized perspective.  Algorithmica, 83(2):753–774, 2021.
  * [3] James F. Allen.  Maintaining knowledge about temporal intervals.  Communications of the ACM, 26(11):832–843, 1983.
  * [4] James F. Allen and Johannes A. G. M. Koomen.  Planning using a temporal world model.  In Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI-1983), pages 741–747, 1983.
  * [5] Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, and Marco Protasi.  Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties.  Springer Science & Business Media, 2012.
  * [6] Kristóf Bérczi, Alexander Göke, Lydia Mirabel Mendoza Cadena, and Matthias Mnich.  Resolving infeasibility of linear systems: A parameterized approach.  CoRR, abs/2209.02017, 2022.
  * [7] Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan.  Towards a polynomial kernel for directed feedback vertex set.  Algorithmica, 83(5):1201–1221, 2021.
  * [8] Leopoldo Bertossi and Jan Chomicki.  Query answering in inconsistent databases.  In Logics for Emerging Applications of Databases, pages 43–83. Springer, 2004.
  * [9] Manuel Bodirsky.  Complexity of Infinite-Domain Constraint Satisfaction.  Cambridge University Press, 2021.
  * [10] Manuel Bodirsky and Martin Grohe.  Non-dichotomies in constraint satisfaction complexity.  In Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP-2008), pages 184–196, 2008.
  * [11] Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet, and Zaneta Semanisinová.  Complexity classification transfer for CSPs via algebraic products.  CoRR, abs/2211.03340, 2022.
  * [12] Manuel Bodirsky and Jan Kára.  The complexity of temporal constraint satisfaction problems.  Journal of the ACM, 57(2):9:1–9:41, 2010.
  * [13] Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała, and Marcin Wrochna.  On directed feedback vertex set parameterized by treewidth.  In Proc. 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG-2018), volume 11159, pages 65–78, 2018.
  * [14] Édouard Bonnet, László Egri, and Dániel Marx.  Fixed-parameter approximability of Boolean MinCSPs.  In Proc. 24th Annual European Symposium on Algorithms (ESA-2016), pages 18:1–18:18, 2016.
  * [15] Andrei A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In Proc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS-2017), pages 319–330, 2017.
  * [16] Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin.  Classifying the complexity of constraints using finite algebras.  SIAM Journal on Computing, 34(3):720–742, 2005.
  * [17] Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon.  A fixed-parameter algorithm for the directed feedback vertex set problem.  In Proc. 40th Annual ACM Symposium on Theory of Computing (STOC-2008), pages 177–186, 2008.
  * [18] Rajesh Chitnis, Marek Cygan, Mohammataghi Hajiaghayi, and Dániel Marx.  Directed subset feedback vertex set is fixed-parameter tractable.  ACM Transactions on Algorithms, 11(4):1–28, 2015.
  * [19] Rajesh Chitnis, László Egri, and Dániel Marx.  List H-coloring a graph by removing few vertices.  Algorithmica, 78(1):110–146, 2017.
  * [20] Jan Chomicki and Jerzy Marcinkowski.  Minimal-change integrity maintenance using tuple deletions.  Information and Computation, 197(1-2):90–121, 2005.
  * [21] Jean-François Condotta, Issam Nouaouri, and Michael Sioutis.  A SAT approach for maximizing satisfiability in qualitative spatial and temporal constraint networks.  In Proc. 15th International Conference on the Principles of Knowledge Representation and Reasoning (KR-2016), 2016.
  * [22] Robert Crowston, Gregory Gutin, Mark Jones, and Anders Yeo.  Parameterized complexity of satisfying almost all linear equations over $\mathbb{F}_{2}$.  Theory of Computing Systems, 52(4):719–728, 2013.
  * [23] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized algorithms.  Springer, 2015.
  * [24] Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, and George Osipov.  Resolving inconsistencies in simple temporal problems: A parameterized approach.  In Proc. 36th AAAI Conference on Artificial Intelligence, (AAAI-2022), pages 3724–3732, 2022.
  * [25] Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström.  Almost consistent systems of linear equations.  In Proc. 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2023), pages 3179–3217, 2023.
  * [26] Rina Dechter, Itay Meiri, and Judea Pearl.  Temporal constraint networks.  Artificial Intelligence, 49(1-3):61–95, 1991.
  * [27] Pascal Denis and Philippe Muller.  Predicting globally-coherent temporal structures from texts via endpoint inference and graph decomposition.  In Proc. 22nd International Joint Conference on Artificial Intelligence (IJCAI-2011), pages 1788–1793, 2011.
  * [28] Eduard Eiben, Clément Rambaud, and Magnus Wahlström.  On the parameterized complexity of symmetric directed multicut.  In Proc. 17th International Symposium on Parameterized and Exact Computation (IPEC-2022), volume 249, pages 11:1–11:17, 2022.
  * [29] Tomás Feder and Moshe Y. Vardi.  The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory.  SIAM Journal on Computing, 28(1):57–104, 1998.
  * [30] Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi.  A survey on approximation in parameterized complexity: Hardness and algorithms.  Algorithms, 13(6):146, 2020.
  * [31] Alexander Göke, Dániel Marx, and Matthias Mnich.  Hitting long directed cycles is fixed-parameter tractable.  In Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP-2020), volume 168, pages 59:1–59:18, 2020.
  * [32] Alexander Göke, Dániel Marx, and Matthias Mnich.  Parameterized algorithms for generalizations of directed feedback vertex set.  Discrete Optimization, 46:100740, 2022.
  * [33] Martin Charles Golumbic and Ron Shamir.  Complexity and algorithms for reasoning about time: A graph-theoretic approach.  Journal of the ACM, 40(5):1108–1133, 1993.
  * [34] Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar.  Beating the random ordering is hard: Every ordering CSP is approximation resistant.  SIAM Journal on Computing, 40(3):878–914, 2011.
  * [35] Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson.  The approximability of constraint satisfaction problems.  SIAM J. Comput., 30(6):1863–1920, 2000.
  * [36] Subhash Khot.  On the power of unique 2-prover 1-round games.  In Proc. 24th Annual ACM Symposium on Theory of Computing (STOC-2002), pages 767–775, 2002.
  * [37] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Solving hard cut problems via flow-augmentation.  In Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA-2021), pages 149–168, 2021.
  * [38] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Directed flow-augmentation.  In Proc. 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC-2022), pages 938–947, 2022.
  * [39] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Flow-augmentation III: complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints.  In Proc. 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2023), pages 3218–3228, 2023.
  * [40] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Flow-augmentation I: directed graphs.  arXiv preprint arXiv:2111.03450, 2023.
  * [41] Eun Jung Kim, Tomáš Masařík, Marcin Pilipczuk, Roohani Sharma, and Magnus Wahlström.  On weighted graph separation problems and flow-augmentation.  arXiv preprint arXiv:2208.14841, 2022.
  * [42] Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolínek.  The complexity of general-valued CSPs.  SIAM Journal on Computing, 46(3):1087–1110, 2017.
  * [43] Andrei A. Krokhin, Peter Jeavons, and Peter Jonsson.  Reasoning about temporal relations: The tractable subalgebras of Allen’s interval algebra.  Journal of the ACM, 50(5):591–640, 2003.
  * [44] Andrei A. Krokhin and Jakub Oprsal.  An invitation to the promise constraint satisfaction problem.  ACM SIGLOG News, 9(3):30–59, 2022.
  * [45] Victor Lagerkvist.  A new characterization of restriction-closed hyperclones.  In Proc. 50th IEEE International Symposium on Multiple-Valued Logic (ISMVL-2020), pages 303–308, 2020.
  * [46] Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi.  Fpt-approximation for fpt problems.  In Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA-2021), pages 199–218, 2021.
  * [47] Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh.  Linear time parameterized algorithms for subset feedback vertex set.  ACM Transactions on Algorithms, 14(1):7:1–7:37, 2018.
  * [48] Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh.  When recursion is better than iteration: A linear-time algorithm for acyclicity with few error vertices.  In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2018), pages 1916–1933, 2018.
  * [49] Dániel Marx.  Parameterized complexity and approximation algorithms.  The Computer Journal, 51(1):60–78, 2008.
  * [50] Dániel Marx and Igor Razgon.  Constant ratio fixed-parameter approximation of the edge multicut problem.  Inf. Process. Lett., 109(20):1161–1166, 2009.
  * [51] Lenka Mudrová and Nick Hawes.  Task scheduling for mobile robots using interval algebra.  In Proc. 2015 IEEE International Conference on Robotics and Automation (ICRA-2015), pages 383–388, 2015.
  * [52] Richard N. Pelavin and James F. Allen.  A model for concurrent actions having temporal extent.  In Proc. 6th National Conference on Artificial Intelligence (AAAI-1987), pages 246–250, 1987.
  * [53] Prasad Raghavendra.  Optimal algorithms and inapproximability results for every CSP?  In Proc. 40th Annual ACM Symposium on Theory of Computing (STOC-2008), pages 245–254, 2008.
  * [54] Igor Razgon and Barry O’Sullivan.  Almost 2-SAT is fixed-parameter tractable.  Journal of Computer and System Sciences, 75(8):435–450, 2009.
  * [55] Fei Song and Robin Cohen.  The interpretation of temporal relations in narrative.  In Proc. 7th National Conference on Artificial Intelligence (AAAI-1988), pages 745–750, 1988.
  * [56] Marc B. Vilain and Henry A. Kautz.  Constraint propagation algorithms for temporal reasoning.  In Proc. 5th National Conference on Artificial Intelligence (AAAI-1986), pages 377–382, 1986.
  * [57] Dmitriy Zhuk.  A proof of the CSP dichotomy conjecture.  Journal of the ACM, 67(5):30:1–30:78, 2020.


# Intrinsic mono-chromatic emission of X and gamma-rays in symmetric electron-
photon beam collisions

L. Serafini
INFN-Section of Milan
Via G. Celoria 16
Milano, Italy, 20133
& V. Petrillo
INFN-Section of Milan
Via G. Celoria 16
Milano, Italy, 20133
& A. Bacci
INFN-Section of Milan
Via G. Celoria 16
Milano, Italy, 20133
& C. Curatolo
INFN-Section of Milan
Via G. Celoria 16
Milano, Italy, 20133
& I. Drebot
INFN-Section of Milan
Via G. Celoria 16
Milano, Italy, 20133
& M. Rossetti Conti
INFN-Section of Milan
Via G. Celoria 16
Milano, Italy, 20133
& A. R. Rossi
INFN-Section of Milan
Via G. Celoria 16
Milano, Italy, 20133

###### Abstract

This paper explores the transition between Compton Scattering and Inverse
Compton Scattering (ICS), which is characterized by an equal exchange of
energy and momentum between the colliding particles (electrons and photons).
This regime has been called Symmetric Compton Scattering (SCS) and has the
unique property of cancelling the energy-angle correlation of scattered
photons, and, when the electron recoil is large, transferring mono-
chromaticity from one colliding beam to the other, resulting in back-scattered
photon beams that are intrinsically monochromatic. The paper suggests that
large-recoil SCS or quasi-SCS can be used to design compact intrinsic
monochromatic gamma-ray sources based on compact linacs, thus avoiding the use
of GeV-class electron beams together with powerful laser/optical systems as
those typically required for ICS sources.

##  1 Introduction

The spectral red-shift observed when a X-ray pulse interacts with a carbon
target was observed by Arthur Compton in 1922 [1] and interpreted as an effect
of the collision between the photons of the X-rays and the electrons of the
solid, both assumed as point-like particles. The scattering of energetic
photons by electrons at rest in the laboratory was called Compton effect after
him.

Much later, the Inverse Compton Scattering (ICS) effect was studied [2] and
experimentally demonstrated at particle accelerators [3], using highly
relativistic electrons colliding with laser beams, within an inverse
kinematics set-up where the electron looses energy and momentum in favor of
the incident photon, that is back-scattered and up-shifted to much larger
energies.

While the Compton effect cannot be explained classically, the low recoil
regime of ICS, in which the electron energy/momentum loss is negligible, has
been described in the framework of the classical electro-dynamics and it is
known as Thomson effect [4].In this paper we analyze the transition between
Compton effect and ICS, occurring when the colliding particles exchange an
equal amount of energy and momentum, and we call this regime Symmetric Compton
Scattering (SCS). In this particular condition, the properties of the
scattered photons are unique: unlike in all other radiations emitted with a
Lorentz boost, SCS scattered photon energy indeed no longer depends on the
scattering angle, so that the back-scattered radiation beam becomes
intrinsically monochromatic. Extending the analyses on large electron recoil
ICS carried out in Ref. [5] to this particular regime, we find that SCS is
characterized by the transfer of mono-chromaticity from one colliding beam to
the other, so that when a large bandwidth photon beam collides under SCS
conditions with a mono-energetic electron beam, the back-scattered photon beam
results to be mono-chromatized.

SCS or quasi-SCS at large recoil could allow to design compact sources of
intrinsic mono-chromatic gamma-rays alimented by low energy MeV electron
bunches, thus avoiding the use of GeV-class accelerators and powerful
laser/optical systems, actually needed by ICS sources.

##  2 Compton interaction regimes

Considering the Compton interaction between photon pulses and counter-
propagating electron beams, we can derive the well-known equation for the
photon energy ($E_{\mathrm{ph}}^{\prime}=\hbar\omega^{\prime}$, with
$\omega^{\prime}$ being the photon associated angular frequency and $\hbar$
the reduced Planck constant) scattered at an angle $\theta$. Following the
notation of eq. 3 in Ref. [6], we can write:

$E_{\mathrm{ph}}^{\prime}(\theta)=\frac{(1+\beta)\gamma^{2}}{\gamma^{2}(1-\beta\cos\theta)+\frac{X}{4}(1+\cos\theta)}E_{\mathrm{ph}},$
(1)

where the incident photon energy is $E_{\mathrm{ph}}=\hbar\omega$,
$\beta=v_{e}/c$ is the ratio between electron velocity $v_{e}$ and light speed
$c$, $\gamma=1/\sqrt{1-\beta^{2}}$ is electron Lorentz factor and $X$ is the
electron recoil factor that introduces an important contribution at high
energy of both incident photons and electrons. $X$ has been defined in [5]
(eq. 4) as:

$X=\frac{4E_{e}E_{\mathrm{ph}}}{(m_{0}c^{2})^{2}}=\frac{4\gamma
E_{\mathrm{ph}}}{m_{0}c^{2}}=4\gamma^{2}\frac{E_{\mathrm{ph}}}{E_{e}},$ (2)

with $m_{0}$ the electron rest mass ans $E_{e}=\gamma m_{0}c^{2}$.

We can distinguish the following different interaction regimes: Direct,
Inverse and Symmetric Compton Scattering.

###  2.1 Direct Compton

The collision between high energy photons and electrons at rest
($E_{\mathrm{ph}}\gg T_{e}$, where $T_{e}=\left(\gamma-1\right)m_{0}c^{2}$) is
usually called Direct Compton (DC) scattering. In this process, the photon
loses energy, being red-shifted, while the collided electron gains energy,
being recoiled.

The interaction studied in Arthur Compton’s original experiment exploited
X-rays incident on fixed target ($\beta=0$, $\gamma=1$). eq. 1 reduces
therefore to:

$E_{\mathrm{ph}}^{\prime}(\theta)=\frac{E_{\mathrm{ph}}}{1+\frac{X_{DC}}{4}(1+\cos\theta)}.$
(3)

In such a case, the electron recoil factor can be rewritten as a function of
the well-known electron Compton wavelength $\lambda_{C}=h/(m_{0}c)$ and the
colliding photon wavelength $\lambda$:

$X_{DC}=\frac{4E_{\mathrm{ph}}}{m_{0}c^{2}}=\frac{4\lambda_{C}}{\lambda}.$ (4)

where $\lambda=hc/E_{\mathrm{ph}}$ , leading directly to Compton’s
relationship for the scattered photon wavelength $\lambda^{\prime}$:

$\lambda^{\prime}-\lambda=\lambda_{C}(1+\cos{\theta}).$ (5)

Here we start seeing a clear signature of radiation emission in collisions:
the angular dependence of the scattered photon energy. Also, this is the
fundamental expression for the photon wavelength red-shift that allowed Arthur
Compton to invoke the quantum nature of the photon-electron collision in order
to explain the experimental data.

###  2.2 Inverse Compton Scattering

The Inverse Compton Scattering (ICS) regime is instead characterized by
collisions of highly energetic electrons and low energy photons (usually
delivered by a laser) with $E_{\mathrm{ph}}\ll T_{e}$. In the interaction the
photon receives energy from the electron. ICS sources are characterized by
high electron beam energy (from tens to hundreds MeV) i.e. $\beta\rightarrow
1$ and $\gamma\gg 1$. In this conditions, and in low recoil regime, the
angular aperture of the cone containing half of the emitted radiation scales
as $\gamma^{-1}$. The boost effect contracts the angular coordinate of the
photons, compressing such a cone. For $\theta$ small, $cos(\theta)\approx
1-\theta^{2}/2$ and eq. 1 can be approximated with:

$E_{\mathrm{ph}}^{\prime}(\theta)=\frac{4E_{\mathrm{ph}}\gamma^{2}}{1+X+\gamma^{2}\theta^{2}}.$
(6)

Equations 1 and 6 show the intrinsic dependence of the scattered photon energy
on the scattering angle through the term $\theta\gamma$ in the denominator.

In the DC regime, $\gamma\simeq 1$ and the angular dependence appears without
any boost effect.

The maximum photon energy is achieved by fully back-scattered photons at
$\theta=0$:
$E_{\mathrm{ph}}^{\prime}(\theta=0)={4E_{\mathrm{ph}}\gamma^{2}}/(1+X).$ In
case of negligible recoil, that is in Thomson regime, the maximum photon
energy just reduces to
$E_{\mathrm{ph}}^{\prime}(\theta=0)=4E_{\mathrm{ph}}\gamma^{2}$.

###  2.3 Symmetric Compton Scattering

In the transition between the two regimes previously discussed, the
energy/momentum transfer between photons and electrons is balanced. We call
Symmetric Compton Scattering (SCS) this regime of transition between DC and
ICS. SCS is uniquely characterized by the disappearance of the energy-angle
correlation of the scattered radiation that becomes monochromatic. Regarding
the angular distribution, the radiation fills the whole solid angle with a
different probability set by the angular dependence of the cross-section.
Referring to equation 1, the condition for eliminating the $\theta$ dependence
in $E_{\mathrm{ph}}^{\prime}$ is

$\frac{X}{4}=\beta\gamma^{2},$ (7)

a condition achieved when photon and electron energies satisfy the relation
$E_{\mathrm{ph}}=\beta E_{e}$, which is equivalent to a photon and an electron
with equal momenta and opposite directions $\vv{p}_{e}=-\vv{p}_{\mathrm{ph}}$.

Moreover, we introduce here an asymmetry factor

$A=\beta\gamma^{2}-\frac{X}{4}$ (8)

that vanishes ($A=0$) in SCS regime and assumes large positive values
($A\rightarrow\gamma^{2}$) in ICS regime. It is worth noting that the
condition $A=0$ actually deletes the angular dependence shown in eq. 1.

In the SCS regime, the center of mass of the collisions is at rest in the
laboratory reference frame (see next chapter), therefore the produced
radiation is not Lorentz transformed and its frequency is no more boosted. As
a result, the energy of the scattered photons is:

$E^{\prime}_{\mathrm{ph}}=E_{\mathrm{ph}}\ \forall\theta.$ (9)

For convenience we call $E_{0}^{\prime}$ the value that eq. 1 assumes for
$\theta=0$:

$E_{0}^{\prime}=E_{\mathrm{ph}}^{\prime}(\theta=0)=\frac{2\gamma^{2}\left(1+\beta\right)}{2\gamma^{2}\left(1-\beta\right)+X}E_{\mathrm{ph}}.$
(10)

Expressing eq. 1 in Taylor Expansion of $\theta$ around $\theta=0$ we find the
following first two terms:

$E_{\mathrm{ph}}^{\prime}(\theta)=E_{0}^{\prime}-\frac{E_{0}^{\prime}}{\gamma^{2}}\frac{A\gamma^{2}\theta^{2}}{2\gamma^{2}\left(1-\beta\right)+X}+A\
O(\gamma^{4}\theta^{4}),$ (11)

where the higher order terms confirm that the symmetry condition ($A=0$)
cancels the angular correlation.

Note that the asymmetry factor A is negative in DC regime, where $\beta=0$ and
$\gamma=1$, and $A=-\lambda_{C}/\lambda$. On the other side, in ICS regime the
asymmetry factor A is positive and scales like $\gamma^{2}$. Equation 11 is
actually a generalization of a well known formula in ICS, that reads
$dE^{\prime}_{\mathrm{ph}}/E^{\prime}_{0}=\gamma^{2}\theta^{2}/(1+X)$. Figures
1 and 2 show the dependence of $E^{\prime}_{0}$ vs. $T_{e}$ and of the recoil
factor $X$ in different regimes (DC, SCS, ICS), that are associated to the
sign of the asymmetry factor A.

Figure 1: Evolution of the recoil factor X value and of the scattered photon
energy in SCS regime as a function of the electron kinetic energy $T_{e}$.
Colored areas identify the possible Compton Scattering regimes and the
relative asymmetry factor A sign, DC in yellow ($A<0$), ICS in blue ($A>0$)
and in green the SCS divide line ($A=0$). Figure 2: 3D representation of the
value of the recoil factor X as a function of the interacting electron kinetic
energy ($T_{e}$) and of the incident photon energy. The line shows the recoil
value in SCS conditions

##  3 A Four-vector description

The four-momentum of a particle is defined as
$\textbf{p}=\left(\frac{E}{c},p_{x},p_{y},p_{z}\right)$, where $E$ is the
total energy of the particle, $c$ is the speed of light in vacuum, and
$p_{x},p_{y},p_{z}$ are the components of the particle’s momentum along the
$x$, $y$, $z$ axes respectively.

Let us consider the case of an head-on collision between a photon and a
counter-propagating electron along the z-axis. Before the collision, the
electron and the photon have the following four-momenta:

$\begin{array}[]{@{}r@{\;}c@{\;}l@{}}\mathbf{p_{e}}&=&\left(\gamma
m_{0}c,0,0,\beta\gamma m_{0}c\right),\\\
\mathbf{p_{\mathrm{ph}}}&=&\left(\frac{E_{\mathrm{ph}}}{c},0,0,-\frac{E_{\mathrm{ph}}}{c}\right).\end{array}$
(12)

and the total four-momentum is:

$\mathbf{p_{tot}}=\left(\gamma
m_{0}c+\frac{E_{\mathrm{ph}}}{c},0,0,\beta\gamma
m_{0}c-\frac{E_{\mathrm{ph}}}{c}\right).$ (13)

The energy available in the center of mass $E_{cm}$, in terms of the recoil
factor introduced in eq. 2, is:

$E_{cm}=c\sqrt{\mathbf{p_{tot}}\cdot\mathbf{p_{tot}}}=m_{0}c^{2}\sqrt{(1+\beta)\frac{X}{2}+1}=m_{0}c^{2}\sqrt{(1+\beta)\frac{2E_{e}E_{\mathrm{ph}}}{(m_{0}c^{2})^{2}}+1}.$
(14)

The different regimes of Compton scattering can be analyzed in terms of their
center of mass energy $E_{cm}$.

For the DC regime ($\beta=0$, $\gamma=1$):

$E_{cm-DC}=m_{0}c^{2}\sqrt{\frac{2E_{\mathrm{ph}}}{m_{0}c^{2}}+1}.$ (15)

On the opposite side, in the ICS regime ($\beta\simeq 1$), we obtain:

$E_{cm-ICS}=m_{0}c^{2}\sqrt{X+1}=m_{0}c^{2}\sqrt{\frac{4\gamma
E_{\mathrm{ph}}}{m_{0}c^{2}}+1}.$ (16)

Finally, for the SCS regime ($E_{\mathrm{ph}}=\beta E_{e}=\beta\gamma
m_{0}c^{2}$):

$E_{cm-SCS}=(1+\beta)\gamma m_{0}c^{2}.$ (17)

In this peculiar situation $E_{cm}\propto\gamma$ like in a collider. Being
$\gamma_{cm}\equiv E_{lab}/E_{cm}$ the Lorentz boost factor associated to the
center of mass reference frame, in SCS we have $\gamma_{cm}=1$ (because
$E_{lab-SCS}=E_{cm-SCS}$), meaning that the center of mass of the system is at
rest in the laboratory system, and the radiation produced here has the same
angular and spectral distribution seen by a detector at rest in the lab. On
the other hand, DC and ICS exhibit a dependence of the available energy
$E_{cm}$ typical of a fixed target collision, where $E_{cm}$ scales like
$E_{cm}\propto\sqrt{T_{p}}$, where $T_{p}$ is the projectile kinetic energy.
ICS regime is characterized by $\gamma_{cm}\gg 1$ since the center of mass
reference frame is almost traveling with the electron (as shown in ref. [5]
$\gamma_{cm}=\gamma/(1+X)$).

##  4 Effects of deep recoil in Compton scattering

The energy spread of the scattered photon beam
($dE^{\prime}_{\mathrm{ph}}/E^{\prime}_{\mathrm{ph}}$, that is typically
referred as relative bandwidth) has a vanishing dependence on the energy
spread of incident photon beam ($dE_{\mathrm{ph}}/E_{\mathrm{ph}}$) whenever
the recoil factor is very large. This effect is clearly illustrated in ref
[6], eq. 9 for the Compton scattering interaction:

$\frac{dE^{\prime}_{ph}}{E^{\prime}_{ph}}=\frac{2+X}{1+X}\frac{d\gamma}{\gamma}+\frac{1}{1+X}\frac{dE_{ph}}{E_{ph}}$
(18)

In this equation, the impact of high recoil factor values of X can be seen in
the form of damping of the dependence of energy spread for the scattered
photon beam ($\frac{dE^{\prime}_{ph}}{E^{\prime}_{ph}}$) on the energy spread
of the incident photon beam ($\frac{dE_{ph}}{E_{ph}}$) and a resulting that’s
equal to the energy spread of the incident electrons
($\frac{d\gamma}{\gamma}$).

Figure 3: Simulations of SCS are shown through 9 plots arranged in three rows
representing the energy and angular distributions of the particles involved in
the interaction. The rows depict the incident photons, outgoing photons, and
outgoing electrons, respectively. In the first column, the energy
distributions of the three particle species are displayed. In the second
column, the angular distributions of the outgoing particles are shown. In the
third column, the energy of the particles are shown as a function of their
propagation angle.

We derive the dependence of the outgoing photon energy spread on the incident
photon energy spread to study the effect of deep recoil:

$\frac{dE_{0}^{\prime}}{E_{0}^{\prime}}=\frac{\frac{2}{1+\beta}}{2(1-\beta)\gamma^{2}+X}\frac{dE_{0}}{E_{0}}=\frac{1}{1+\frac{1+\beta}{2}X}\frac{dE_{0}}{E_{0}}$
(19)

for $\beta\rightarrow 1$ this result reproduces the second term of the right
hand side of eq. 18.

We also derive the dependence of the outgoing photon energy spread on the
energy spread of the incoming electron beam under the approximation of
$\gamma\gg 1$, $\beta\simeq 1-1/2\gamma^{2}$

$\frac{dE_{0}^{\prime}}{E_{0}^{\prime}}=\frac{1}{1+\frac{1}{4\gamma^{2}}}\frac{2X+X^{2}+X/\gamma}{X\left(1+X\right)}\frac{d\gamma}{\gamma}$
(20)

This result reproduces the first term of the right hand side of eq. 18 at the
limit $\gamma\gg 1$ .

##  5 Symmetric Compton Scattering simulation

This chapter is focused on the simulations of the Symmetric Compton Scattering
using two different codes to quantify the phenomenon. Our simulation approach
investigates energy transfer, scattering angles and bandwidth variation of the
particles that interacted.

###  5.1 WHIZARD

We used the WHIZARD code [7], a universal parton-level Monte Carlo event
generator, to perform simulations of SCS.

An almost monochromatic (with an rms energy spread of the order of $10^{-4}$)
10 MeV electron beam ($\beta\rightarrow 1$) collided head-on with an incoming
photon beam characterized by large bandwidth (20 percent rms spread). The
recoil in this interaction is large, the computed value being $X=1533$. The
results of the interaction, shown in fig. 3, confirmed the theoretical
predictions: the outgoing photons showed no correlation between energy and
emission angle and featured a significant narrowing of the bandwidth ($2\cdot
10^{-4}$ rms spread, i.e. a reduction of the energy spread by about 3 orders
of magnitude from incident photon beam to the scattered photon beam). On the
other hand, the electron beam emerging from the interaction inherited an high
energy spread (of the order of $10^{-1}$) from the original interacting photon
beam, displaying an entropy exchange.

WHIZARD was also used to perform an analysis of the SCS effect in presence of
angular divergence of the incident photon beam, shown in fig. 4, by mixing
several runs with different scattering angle. The result confirms the SCS
mono-chromatization also in interactions characterized by small incidence
angles.

Figure 4: Simulations of SCS with an incoming photon beam displaying a
correlation between angle of propagation and photon energy. The results are
shown through 9 plots arranged in three rows as in fig. 3. The angular
correlation of the incoming photon beam is removed in the interaction thanks
to the high recoil factor ($X\sim 1500$).

###  5.2 Monte Carlo code

A home made multitasking Monte Carlo code has been developed, validated for
different type of collisions and applied to the Compton scattering process
[8]. As an additional internal feature, the code allows to consider the energy
and angular (polar and azimuth) spread of both incident beams. To confirm the
occurrence of the effect, we conducted the same simulation of the deep-recoil
SCS interaction (at $X=1533$). Our findings confirm the exchange of entropy,
resulting in a reduction of the bandwidth of the emitted radiation and an
enlargement of the electron’s bandwidth (as summarized in fig. 5).

Figure 5: This figure illustrates the simulations of the SCS regime for a
recoil factor of $X=1533$. The plot consists of six subplots organized into
two rows, with the first row showing the photon behavior and the second row
showing the electron behavior. In each row, the leftmost column displays the
bandwidth of the incoming bunch, the central column shows the resulting
particles after the interaction, and the rightmost column displays the angular
distribution of the particles. This arrangement allows for a detailed analysis
of the behavior of photons and electrons during the SCS regime.

Furthermore, we examined the transition from the SCS regime to the ICS regime,
with particular focus on the angular distribution of the scattered radiation.
To explore the transition regime, we started with the deep-recoil SCS
interaction ($X=1533$) and slightly increased the energy of the incident
electron bunch while reducing the energy of the photon bunch. We investigated
three cases, specifically with electron-photon energies of ($E_{e}\simeq
E_{ph}=10$ MeV), ($E_{e}=11$ MeV, $E_{ph}=9.08$ MeV), and ($E_{e}=12$ MeV,
$E_{ph}=8.33$ MeV). The results, depicted in fig. 7, show the distribution
shifting from an uncorrelated energy-angle pattern to a more correlated one,
resembling the typical "mustache" shaped curve observed in ICS experiments.

Figure 6: This figure demonstrates the regime transitions between SCS and ICS
for three different sets of photons and electrons energy. The upper row
displays the produced photon energy distribution for each set, while the
bottom row shows the angular distribution of the particles (i.e., energy as a
function of emission angle) for each set. This arrangement allows for a
comprehensive comparison of the behavior of the particles during the
transition between SCS and ICS regimes.

Finally we investigated the SCS regime with low recoil factor ($A=0$,
$X=3.13$). In this peculiar situation (see fig. 6), a milder mono-
chromatization of the incident photons occurs, compared with what happens in
deep recoil regime represented in. 5.

Figure 7: This figure shows the simulations of the SCS regime for a small
recoil factor of $X\sim 3$. The plot consists of six subplots organized into
two rows, with the first row showing the photon behavior and the second row
showing the electron behavior. In each row, the leftmost column displays the
bandwidth of the incoming bunch, the central column shows the resulting
particles after the interaction, and the rightmost column displays the angular
distribution of the particles. This arrangement allows to underline the
incomplete exchange of energy spread due to the reduced recoil factor.

##  6 Conclusions

We explore the transition between Compton Scattering and Inverse Compton
Scattering (ICS), a regime characterized by an equal exchange of energy and
momentum between the colliding particles. This regime has been called
Symmetric Compton Scattering (SCS) and has the unique property of transferring
mono-chromaticity from one beam to the other, resulting in back-scattered
photons that are intrinsically monochromatic. The paper suggests that large-
recoil SCS or quasi-SCS can be used to design compact intrinsic monochromatic
gamma-ray sources, thus avoiding the use of GeV-class electron beams and
powerful laser/optical systems typically required for ICS sources.

Indeed the capability of SCS regime to vanish the photon energy-angle
correlation, married to the large recoil beneficial effects on the scattered
photon energy spread, as shown in previous chapters, makes possible to
conceive a mono-chromatic gamma ray beam source based on the collision between
a bremsstrahlung radiation beam (or a coherent bremsstrahlung beam from a
channeling source, [9]) and a mono-energetic electron beam of similar energy,
say in the 2-10 MeV range, so to employ a compact source that is much more
sustainable than typical ICS sources for nuclear physics/photonics like ELI-
NP-GBS [10], that all envisage the use of GeV-class linear accelerators.

An Energy Recovery Linac with 10-20 MeV electron beam energy would allow to
sustain a much larger average current (in the range of tens of mA) than a room
temperature Linac like in ELI-NP-GBS, to the collision point with the broad-
band bremsstrahlung photon beam, compensating the decrease of total cross
section $\sigma$ with the recoil factor $X$ typical of Klein-Nishina formula,
as shown here below (see ref. [5])

$\left\\{\begin{aligned} \lim\limits_{X\to 0}\sigma&=\frac{8\pi
r_{e}^{2}}{3}(1-X)=\sigma_{T}(1-X)\\\
\lim\limits_{X\to\infty}\sigma&=\frac{2\pi r_{e}^{2}}{X}\left(\log
X+\frac{1}{2}\right)\end{aligned}\right.$ (21)

A detailed study of a SCS $\gamma$-ray source will be the subject of a future
work, that will have to take into account the compensation of the cross
section decrease for large recoils with the positive effects of reducing the
photon bandwidth by large recoils, as shown by equations 18, 19 and 20
(assuming the capability to bring to collision a good quality electron beam
with small energy spread $\frac{\Delta_{\gamma}}{\gamma}$ below $10^{-3}$
[11]). The guidelines of such a design study should be oriented to optimize
the SCS $\gamma$-ray source in terms of maximum Spectral Density $S_{d}$, as
illustrated in [11] and typically requested by nuclear photonics and photo-
nuclear physics applications. $S_{d}$ is actually defined as $S_{d}\equiv
N_{\mathrm{ph}}(\Delta E^{\prime}_{ph}/E^{\prime}_{ph})^{-1}$, where
$N_{\mathrm{ph}}$ is the number of gamma ray photons generated per second
within the relative bandwidth $\Delta E^{\prime}_{ph}/E^{\prime}_{ph}$ around
the nominal average energy $E^{\prime}_{ph}$. Since $N_{\mathrm{ph}}$ scales
with the product $L\sigma$, where $L$ is the collision luminosity and $\sigma$
is given in eq. 21, we see that for large recoil collisions $S_{d}$ scales
like $L\log{X}/X$. On the other side $\Delta E^{\prime}_{ph}$ becomes very
small in case of SCS at large recoil, as stated by equations 11, 19 and 20,
and well illustrated in figures 3, 4 and 5, showing the potentiality of SCS to
attain photon beams with relative bandwidths smaller than $10^{-3}$.

## References

  * [1] Arthur H. Compton.  A quantum theory of the scattering of x-rays by light elements.  Phys. Rev., 21:483–502, May 1923.
  * [2] O.F Kulikov, Y.Y Telnov, E.I Filippov, and M.N Yakimenko.  Compton effect on moving electrons.  Physics Letters, 13(4):344–346, 1964.
  * [3] L. Federici, G. Giordano, G. Matone, G. Pasquariello, P. G. Picozza, et al.  Backward compton scattering of laser light against high-energy electrons: the ladon photon beam at frascati.  Il Nuovo Cimento B (1971-1996), 59(2):247–256, 1980.
  * [4] P. Tomassini, A. Bacci, J. Cary, M. Ferrario, A. Giulietti, et al.  Linear and nonlinear thomson scattering for advanced x-ray sources in plasmonx.  IEEE Transactions on Plasma Science, 36(4):1782, 2008.
  * [5] C. Curatolo, I. Drebot, V. Petrillo, and L. Serafini.  Analytical description of photon beam phase spaces in inverse compton scattering sources.  Phys. Rev. Accel. Beams, 20:080701, Aug 2017.
  * [6] N. Ranjan, B. Terzić, G. A. Krafft, V. Petrillo, I. Drebot, and L. Serafini.  Simulation of inverse compton scattering and its implications on the scattered linewidth.  Phys. Rev. Accel. Beams, 21:030701, Mar 2018.
  * [7] Wolfgang Kilian, Thorsten Ohl, and Jürgen Reuter.  WHIZARD—simulating multi-particle processes at LHC and ILC.  European Physical Journal C, 71(9):1742, 2011.
  * [8] Camilla Curatolo.  High brilliance photon pulses interacting with relativistic electron and proton beams.  PhD thesis, University of Milan, www.doi.org/10.13130/curatolo-camilla_phd2016-01-22, 2022.
  * [9] S. B. Dabagov and N. K. Zhevago.  On radiation by relativistic electrons and positrons channeled in crystals.  La Rivista del Nuovo Cimento, 9:491–530, September 2008.
  * [10] O. Adriani, S. Albergo, D. Alesini, M. Anania, D. Angal-Kalinin, et al.  Technical design report eurogammas proposal for the eli-np gamma beam system, 2014.
  * [11] A. Bacci, D. Alesini, P. Antici, M. Bellaveglia, R. Boni, et al.  Electron linac design to drive bright compton back-scattering gamma-ray sources.  Journal of Applied Physics, 113(19):194508, 2013.