# Parameterized Complexity Classification for Interval Constraints††thanks:
The second and the fourth authors were supported by the Wallenberg AI,
Autonomous Systems and Software Program (WASP) funded by the Knut and Alice
Wallenberg Foundation. In addition, the second author was partially supported
by the Swedish Research Council (VR) under grant 2021-04371. The third author
acknowledges support from the Engineering and Physical Sciences Research
Council (EPSRC, project EP/V00252X/1). The research of the fifth author is a
part of a project that has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation
programme Grant Agreement 714704. In addition, the fifth author is also part
of BARC, supported by the VILLUM Foundation grant 16582.

Konrad K. Dabrowski School of Computing, Newcastle University, UK,
<EMAIL_ADDRESS>Peter Jonsson Department of Computer and
Information Science, Linköping University, Sweden<EMAIL_ADDRESS>Sebastian Ordyniak School of Computing, University of Leeds, UK,
<EMAIL_ADDRESS>George Osipov Department of Computer and Information
Science, Linköping University, Sweden<EMAIL_ADDRESS>Marcin Pilipczuk
Institute of Informatics, University of Warsaw, Poland and ITU Copenhagen,
Denmark<EMAIL_ADDRESS>Roohani Sharma Max Planck Institute for
Informatics, Saarland Informatics Campus, Saarbrücken, Germany, rsharma@mpi-
inf.mpg.de

Constraint satisfaction problems form a nicely behaved class of problems that
lends itself to complexity classification results. From the point of view of
parameterized complexity, a natural task is to classify the parameterized
complexity of MinCSP problems parameterized by the number of unsatisfied
constraints. In other words, we ask whether we can delete at most $k$
constraints, where $k$ is the parameter, to get a satisfiable instance. In
this work, we take a step towards classifying the parameterized complexity for
an important infinite-domain CSP: Allen’s interval algebra (IA). This CSP has
closed intervals with rational endpoints as domain values and employs a set
$\cal A$ of 13 basic comparison relations such as “precedes” or “during” for
relating intervals. IA is a highly influential and well-studied formalism
within AI and qualitative reasoning that has numerous applications in, for
instance, planning, natural language processing and molecular biology. We
provide an FPT vs. W[1]-hard dichotomy for MinCSP$(\Gamma)$ for all
$\Gamma\subseteq\cal A$. IA is sometimes extended with unions of the relations
in $\cal A$ or first-order definable relations over $\cal A$, but extending
our results to these cases would require first solving the parameterized
complexity of Directed Symmetric Multicut, which is a notorious open problem.
Already in this limited setting, we uncover connections to new variants of
graph cut and separation problems. This includes hardness proofs for
simultaneous cuts or feedback arc set problems in directed graphs, as well as
new tractable cases with algorithms based on the recently introduced _flow
augmentation_ technique. Given the intractability of MinCSP$(\cal A)$ in
general, we then consider (parameterized) approximation algorithms. We first
show that MinCSP$(\cal A)$ cannot be polynomial-time approximated within any
constant factor and continue by presenting a factor-$2$ fpt-approximation
algorithm. Once again, this algorithm has its roots in flow augmentation.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Parameterized Complexity
    2. 2.2 Constraint Satisfaction
    3. 2.3 Interval Relations
  3. 3 Classification Result
  4. 4 Bad Cycles
  5. 5 FPT Algorithms
    1. 5.1 Algorithm for MinCSP$({\sf m},{\sf p})$
    2. 5.2 Algorithm by Reduction to Bundled Cut
  6. 6 W[1]-hard Problems
    1. 6.1 Paired Problems
    2. 6.2 Simultaneous Problems
    3. 6.3 Intractable Fragments Containing ${\sf m}$
    4. 6.4 Intractable Fragments Containing ${\sf d}$, ${\sf o}$ or ${\sf p}$
  7. 7 Approximation
  8. 8 Discussion

##  1 Introduction

Background. The constraint satisfaction problem over a constraint language
$\Gamma$ (CSP$(\Gamma)$) is the problem of deciding whether there is a
variable assignment which satisfies a set of constraints, where each
constraint is constructed from a relation in $\Gamma$. CSPs over different
constraint languages is a nicely behaved class of problems that lends itself
to complexity classification results. Such results are an important testbed
for studying the power of algorithmic techniques and proving their
limitations— the inability to obtain a full classification indicates that new
algorithmic tools or new lower bound techniques are required. A prime example
is the dichotomy theorem for finite-domain CSPs that was conjectured by Feder
and Vardi [29] and independently proved by Bulatov [15] and Zhuk [57]. Here,
all hardness results were known since the work of Bulatov, Jeavons and Krokhin
[16] and the algorithms of [15] and [57] completed the proof of the
conjecture. In between, lots of work went into studying the problem from
various algorithmic and algebraic angles, and many ideas emerging from this
project have been re-used in different contexts (such as proving complexity
results for infinite-domain CSPs [9] or for analysing promise CSPs [44] and
other generalisations). Optimization versions of CSP such as the Valued CSP
(VCSP) have also been intensively studied. An instance of the VCSP consists of
a set of variables, a variable domain and a sum of functions, each function
depending on a subset of the variables. Each function can take finite values
specifying costs of assignments to its variables or the infinite value,
indicating an infeasible assignment. The goal is to find an assignment to the
variables that minimizes the sum. It is obvious that many other CSP
optimisation problems can be viewed as VCSPs; examples include the MaxCSP and
MinCSP problems where the instance is a CSP instance and the goal is to find
an assignment that maximises the number of satisfied constraints (MaxCSP) or
minimises the number of unsatisfied constraints (MinCSP). Such problems have
been the subject of various complexity classification projects and this has
generated a wide range of interesting results. Some notable results include
the proof of that every finite-domain VCSP is either polynomial-time solvable
or NP-complete [42], and the fine-grained result by Raghavendra [53] stating
that, under the Unique Games Conjecture, the semi-definite programming
relaxation of finite-domain MaxCSP achieves the best possible approximation
factor in polynomial time. One should note that even if the P/NP borderline
for finite-domain VCSPs is fully known, there are big gaps in our
understanding of the corresponding FPT/W[1] borderline (with parameter
solution weight). The situation is even worse if we consider infinite-domain
optimization versions of the CSPs, since we cannot expect to get a full
picture of the P/NP borderline even for the basic CSP problem [10]. Thus, one
must concentrate on subclasses that have sufficiently advantageous properties.

In the parameterized complexity world, MinCSP is a natural problem to study.
The parameterized complexity of MinCSP is far less well studied than its
classical computational complexity. Subproblems that have gained attraction
include Boolean constraint languages [14, 39, 54], Dechter et al.’s [26]
simple temporal problem (STP) [24], linear inequalities [6] and linear
equations [22, 25], to list a few. Highly interesting results have emerged
from studying the parameterized complexity of problems like these. For
instance, the recent dichotomy for MinCSPs over the Boolean domain by Kim et
al. [39] was obtained using a novel technique called _directed flow
augmentation_. The showcase application of this tool is a parameterized
algorithm for Chain SAT [38]. This notorious open problem appeared as the only
missing step in the study by Chitnis, Egri and Marx [19] towards classifying
the complexity of list $H$-colouring a graph by removing few vertices. Recent
work has indicated temporal CSPs as the next possible area of interest in this
context [28, 40]. Temporal CSPs are CSPs where the relations underlying the
constraints are first-order definable in $({\mathbb{Q}};<)$. The computational
complexity of temporal CSPs where we fix the set of allowed constraints
exhibits a dichotomy: every such problem is either polynomial-time solvable or
NP-complete [12]. The MinCSP problem for temporal CSPs is closely related to a
number of graph separation problems. For example, if we take the rationals as
the domain and allow constraints $\leq$ and $<$, the MinCSP problem is
equivalent to Directed Subset Feedback Arc Set [41], a problem known to be
fixed-parameter tractable for two different, but both quite involved reasons
[18, 41]. If we allow the relations $\leq$ and $\neq$, we obtain a problem
equivalent to Directed Symmetric Multicut, whose parameterized complexity is
identified as the main open problem in the area of directed graph separation
problems [28, 41]. Another related way forward is to analyse the MinCSP for
Allen’s interval algebra. Allen’s interval algebra is a highly influential
formalism within AI and qualitative reasoning that has numerous applications,
e.g. in planning [4, 51, 52], natural language processing [27, 55] and
molecular biology [33]. This CSP uses closed intervals with rational endpoints
as domain values and employs a set $\cal A$ of 13 basic comparison relations
such as “precedes” (one interval finishes before the other starts) or “during”
(one interval is a strict subset of the other); see Table 1. Formally
speaking, the CSP for the interval algebra is not a temporal CSP, since the
underlying domain is based on intervals instead of points. This difference is
important: complexity classifications for the interval algebra have been
harder to obtain than for temporal constraints. There are full classifications
for binary relations [43] and for first-order definable constraint languages
containing all basic relations [11]; a classification for all first-order
definable constraint languages appears remote.

Our contributions. The aim in this paper is to initiate a study of MinCSP in
the context of Allen’s interval algebra. Obtaining a full parameterized
complexity classification for Allen’s interval algebra would entail resolving
the status of Directed Symmetric Multicut and we do not aim at this very
ambitious task. Instead, we restrict ourselves to languages that are subsets
of $\cal A$ and do not consider more involved expressions (say, first-order
logic) built on top of $\cal A$. Even in this limited quest, we are able to
uncover new relations to graph separation problems, and new areas of both
tractability and intractability. One of the main ingredients for both our
tractability and intractability results is a characterization of unsatifiable
instances of CSP$(\cal A)$ in terms of minimal obstructions given by certain
arc-labelled mixed cycles of the instance. That is, for certain key subsets
$\Gamma\subseteq\cal A$, we provide a complete description of _bad_ cycles
such that an instance of CSP$(\Gamma)$ is satisfiable if and only if it does
not contain a bad cycle. This allows us show that MinCSP$(\Gamma)$ is
equivalent to the problem of finding a minimum set of arcs that hit every bad
cycle in an arc-labelled mixed graph. We prove that there are seven inclusion-
wise maximal subsets $\Gamma$ of $\cal A$ such that MinCSP$(\Gamma)$ is in
FPT, and that MinCSP$(\Gamma)$ is W[1]-hard in all other cases. We show that
$\textsc{MinCSP}(\cal A)$ is not approximable in polynomial time within any
constant under the UGC. In fact, we prove this to hold for MinCSP$({\sf r})$
whenever ${\sf r}\in\cal A\setminus\\{\equiv\\}$. As a response to this, we
suggest the use of fixed-parameter approximation algorithms. We show that
MinCSP$(\cal A)$ admits such an algorithm with approximation ratio $2$ and a
substantially faster algorithm with approximation ratio $4$. We describe the
results in greater detail below.

Intractability results. Our intractability results are based on novel
W[1]-hardness results for a variety of natural _paired_ and _simultaneous_ cut
and separation problems, which we believe to be of independent interest. Here,
the input consists of two (directed or undirected) graphs and the task is to
find a “generalized” cut that extends to both graphs. The two input graphs
share some arcs/edges that can be deleted simultaneously at unit cost, and the
goal is to compute a set of $k$ arcs/edges that is a cut in both graphs. Both
paired and simultaneous problems have recently received attention from the
parameterized complexity community [1, 2, 39]. In the FPT/W[1]-hardness
dichotomy for the Boolean domain [39], the fundamental difficult problem is
Paired Cut (proven to be W[1]-hard by Marx and Razgon [50]): given an integer
$k$ and a directed graph $G$ with two terminals $s,t\in V(G)$ and some arcs
grouped into _pairs_ , delete at most $k$ pairs to cut all paths from $s$ to
$t$. An intuitive reason why Paired Cut is difficult can be seen as follows.
Assume $G$ contains two long $st$-paths $P$ and $Q$ and the arcs of $P$ are
arbitrarily paired with the arcs of $Q$. Then, one cuts both paths with a cost
of only one pair, but the arbitrary pairing of the arcs allow us to encode an
arbitrary permutation — which is very powerful for encoding edge-choice
gadgets when reducing from Multicolored Clique. Our strategy for proving
W[1]-hardness of paired problems elaborates upon this idea. Our reductions of
simultaneous problems use a similar leverage. While the simultaneous setting
may not be as versatile at the first glance as the arbitrary pairing of Paired
Cut, the possibility of choosing common arcs/edges while deleting them at a
unit costs still leaves enough freedom to encode arbitrary permutations.

Altogether, we obtain novel W[1]-hardness results for Paired Cut Feedback Arc
Set, Simultaneous st-Separator, Simultaneous Directed st-Cut, and Simultaneous
Directed Feedback Arc Set. This allows us to identify six intractable
fragments subsets of basic interval relations: $\\{{\sf m},{\sf r}_{1}\\}$ for
${\sf r}_{1}\in\\{\equiv\nobreak,\allowbreak{\sf s},{\sf f}\\}$, $\\{{\sf
d},{\sf r}_{2}\\}$ for ${\sf r}_{2}\in\\{{\sf o},{\sf p}\\}$ and $\\{{\sf
p},{\sf o}\\}$. The hardness reduction for $\\{{\sf m},{\sf r}_{1}\\}$, is
based on the hardness of Paired Cut and Paired Cut Feedback Arc Set. The other
hardness results follow from reductions from Simultaneous Directed Feedback
Arc Set, whose W[1]-hardness is shown by a reduction from Simultaneous st-
Separator.

Tractability results. We identify seven maximal tractable sets of basic
interval relations: $\\{{\sf m},{\sf p}\\}$ and $\\{r_{1},r_{2},\equiv\\}$ for
$r_{1}\in\\{{\sf s},{\sf f}\\}$ and $r_{2}\in\\{{\sf p},{\sf d},{\sf o}\\}$.
All problems are handled by reductions to variants of Directed Feedback Arc
Set (DFAS). This classical problem asks, given a directed graph $G$ and a
budget $k$, whether one can make $G$ acyclic by deleting $k$ arcs. DFAS and
variations are extensively studied in parameterized complexity [7, 13, 17, 18,
31, 32, 47, 48]. One variant particularly relevant to our work is Subset DFAS
(Sub-DFAS). Here the input comes with a subset of red arcs, and the goal is to
delete $k$ arcs so that the resulting graph has no directed cycles containing
red arcs. Note that directed cycles of black (i.e. non-red) arcs are allowed
to stay. Sub-DFAS is equivalent to $\textsc{MinCSP}(<,\leq)$: regard the
constraints $u<v$ as red $(u,v)$-arcs and constraints $u\leq v$ as black
$(u,v)$-arcs, and observe that directed cycles of $\leq$-constraints are
satisfiable, while any directed cycle with a $<$-constraint is not. Sub-DFAS
is fixed-parameter tractable [18], and the weighted version of the problem
(where the input arcs have weights, and a separate weight budget is given in
the input) was recently [41] solved using flow augmentation [38]. To show that
MinCSP$({\sf m},{\sf p})$ is in FPT, we use a fairly straightforward reduction
to MinCSP$(<,=)$ which, in turn, reduces to MinCSP$(<,\leq)$.

For the remaining six tractable cases, we reduce them all to a new variant of
DFAS called Mixed Feedback Arc Set with Short and Long Arcs (LS-MFAS). The
input to this problem is a mixed graph, i.e. a graph with both arcs and
undirected edges; the arcs are either short or long. Forbidden cycles in this
graph are of two types: (1) cycles with at least one short arc, no long arcs,
and all short arcs in the same direction, and (2) cycles with at least one
long arc, all long arcs in the same direction, but the short arcs can be
traversed in arbitrary direction. One intuitive way to think about the problem
is to observe that a graph $G$ has no forbidden cycle if there exists a
placement of the vertices on the number line with certain distance constraints
represented by the edges and arcs. Vertices connected by edges (which
correspond to $\equiv$-constraints) should be placed at the same point. If
there is an arc $(u,v)$, we need to place $u$ before $v$. Moreover, if the arc
is long, then the distance from $u$ to $v$ should be big (say, greater than
twice the number of vertices), while is the arc is short, then the distance
from $u$ to $v$ should be small (say, at most $1$). In other words, the graph
$G$ after contracting all undirected edges is acyclic and we request a
topological ordering of this contracted graph where all (weak) connected
components of short arcs are grouped together and long arcs go only between
distinct connected components of short arcs. LS-MFAS generalizes
MinCSP$(<,=)$, which is a special case without long arcs.

Our algorithm for LS-MFAS builds upon the algorithm of [41] for Sub-DFAS. The
opening steps are standard for parameterized deletion problems. We start with
iterative compression, which reduces the problem to a special case when the
input comes together with a set of $k+1$ vertices intersecting all forbidden
cycles. We call these vertices _terminals_ and guess how they are positioned
relative to each other in the graph obtained by deleting the arcs of a
hypothetical optimal solution. Altogether, this requires $O^{*}(2^{O(k\log
k)})$ time. The aforementioned “placing on a line” way of phrasing the lack of
forbidden cycles is the main reason why this leads to a complete algorithm. In
the following step, we try to place all remaining vertices relative to the
terminals while breaking at most $k$ distance constraints. Note that the
number of ways in which a vertex can relate to a terminal is constant: it may
be placed in a short/long distance before/after the terminal, or in the same
position. Thus, we can define $O(k)$ types for each vertex, and the types
determine whether distance constraints are satisfied or not. The optimal type
assignment is then obtained by a reduction to Bundled Cut with pairwise linked
deletable arcs, a workhorse problem shown to be fixed-parameter tractable in
[39].

To see how MinCSP$({\sf r}_{1},{\sf r}_{2},\equiv)$ for ${\sf r}_{1}\in\\{{\sf
s},{\sf f}\\}$ and ${\sf r}_{2}\in\\{{\sf p},{\sf d},{\sf o}\\}$ relates to
LS-MFAS, consider the exemplary case of MinCSP$({\sf s},{\sf p},\equiv)$.
Represent variables as vertices, ${\sf s}$ relations as short arcs and ${\sf
p}$ relations as long arcs. Observe that in a satisfiable instance, the
resulting graph has no forbidden cycles for LS-MFAS: a cycle consisting of
undirected edges and short arcs oriented in the same direction corresponds to
a loop on ${\sf s}$ relations, while a cycle consisting of undirected edges,
short arcs in arbitrary directions, and long arcs in the same direction
corresponds to a cycle in the MinCSP instance with $\equiv$, ${\sf s}$ and
${\sf p}$ relations, where all ${\sf p}$ relations are in the same direction;
such a cycle imposes an unsafisfiable cyclic order on the starting points of
the corresponding intervals. Interestingly, one can prove an if-and-only-if
statement: the satisfiability of a MinCSP$({\sf s},{\sf p},\equiv)$ instance
is equivalent to the absence of forbidden cycles in the corresponding graph.
Hence, it suffices to solve LS-MFAS there.

Approximation results. As a response to the negative complexity results for
$\textsc{MinCSP}(\cal A)$, it is natural to consider approximation algorithms.
However, we show that $\textsc{MinCSP}(\cal A)$ is not approximable in
polynomial time within any constant under the UGC. In fact, we prove this to
hold for all $\textsc{MinCSP}({\sf r})$ with ${\sf r}\in\cal
A\setminus\\{\equiv\\}$.

An obvious next step is to use fixed-parameter approximation algorithms. This
is an approach combining parameterized complexity with approximability and it
has received rapidly increasing interest (see, for instance, the surveys by
Feldmann et al. [30] and Marx [49]). Let $c>1$ be a constant. A factor-$c$
fpt-approximation algorithm for MinCSP$(\cal A)$ takes an instance $(I,k)$ of
MinCSP$(\cal A)$ and either returns that there is no solution of size at most
$k$ or returns that there is a solution of size at most $c\cdot k$. The
running time of the algorithm is bounded by $f(k)\cdot\lVert I\rVert^{O(1)}$
where $f:\mathbb{N}\rightarrow\mathbb{N}$ is some computable function. Thus,
the algorithm is given more time to compute the solution (compared to a
polynomial-time approximation algorithm) and it may output a slightly
oversized solution (unlike an exact fpt algorithm for $\textsc{MinCSP}(\cal
A)$). This combination turns out to be successful. We show that
$\textsc{MinCSP}(\cal A)$ admits such an algorithm with $c=2$ and a
substantially faster algorithm with $c=4$. These results are (once again)
based on the Sub-DFAS problem. The idea is to look at two relaxations and
consider the left and the right endpoints of the intervals separately. The
problem for left/right endpoints is an instance of Sub-DFAS, which we can
solve in fpt time. If either of the relaxations is not solvable, then we
deduce that the original problem has no solution either. Otherwise, we have
two deletion sets, each of size at most $k$, that ensure consistency for the
left and the right endpoints, respectively. Combining them, we obtain a
deletion set for the initial problem of size at most $2k$. If we use a
factor-$2$ fpt approximation algorithm for Sub-DFAS instead of the slower
exact fpt algorithm when solving the relaxations, we obtain two solutions of
size at most $2k$, and combined they yield a solution of size at most $4k$. We
also show that there exists a factor-$2$ fpt approximation algorithm for the
weighted version of $\textsc{MinCSP}(\cal A)$. This harder problem can be
solved with directed flow augmentation [38], albeit at the price of increased
time complexity.

Roadmap. We begin by introducing some necessary preliminaries in Section 2.
Section 3 contains a bird’s eye view of our dichotomy theorem for the
parameterized complexity of $\textsc{MinCSP}(\Gamma)$ where
$\Gamma\subseteq\cal A$, and the technical details are collected in the
following sections. We describe the minimal obstructions to satisfiability for
certain subsets of $\cal A$ in Section 4. These results are essential for
connecting the MinCSP$(\cal A)$ problem with the graph-oriented problems that
we use in the paper. We complete our dichotomy result by presenting a number
of fixed-parameter algorithms in Section 5 and a collection of W[1]-hardness
results in Section 6. Our approximability results can be found in Section 7.
We conclude the paper with a brief discussion of our results and future
research directions in Section 8.

Basic relation |  | Example | Endpoint Relations
---|---|---|---
$I$ precedes $J$ | ${\sf p}$ | iii | $I^{+}<J^{-}$
$J$ preceded by $I$ | ${\sf pi}$ |  jjj |
$I$ meets $J$ | ${\sf m}$ | iiii | $I^{+}=J^{-}$
$J$ met-by $I$ | ${\sf mi}$ |  jjjj |
$I$ overlaps $J$ | ${\sf o}$ | iiii | $I^{-}<J^{-}<I^{+}<J^{+}$
$J$ overlapped-by $I$ | ${\sf oi}$ |  jjjj |
$I$ during $J$ | ${\sf d}$ |  iii |  $I^{-}>J^{-}$, $I^{+}<J^{+}$
$J$ includes $I$ | ${\sf di}$ | jjjjjjj |
$I$ starts $J$ | ${\sf s}$ | iii |  $I^{-}=J^{-}$, $I^{+}<J^{+}$
$J$ started by $I$ | ${\sf si}$ | jjjjjjj |
$I$ finishes $J$ | ${\sf f}$ |  iii |  $I^{+}=J^{+}$, $I^{-}>J^{-}$
$J$ finished by $I$ | ${\sf fi}$ | jjjjjjj |
$I$ equals $J$ | $\equiv$ | iiii |  $I^{-}=J^{-}$, $I^{+}=J^{+}$
|  | jjjj |
Table 1: The thirteen basic relations in Allen’s Interval Algebra. The
endpoint relations $I^{-}<I^{+}$ and $J^{-}<J^{+}$ that are valid for all
relations have been omitted.

##  2 Preliminaries

In this section we introduce the necessary prerequisites: we briefly present
the rudiments of parameterized complexity in Section 2.1, we define the CSP
and MinCSP problems in Section 2.2, and we provide some basics concerning
interval relations in Section 2.3. Before we begin, we need some terminology
and notation for graphs. Let $G$ be a (directed or undirected) graph; we allow
graphs to contain loops. We denote the set of vertices in $G$ by $V(G)$. If
$G$ is undirected, let $E(G)$ denote the set of edges in $G$. If $G$ is
directed, let $A(G)$ denote the set of arcs in $G$, and $E(G)$ denote the set
of edges in the underlying undirected graph of $G$. We use $uv$ to denote an
undirected edge with end-vertices $u$ and $v$. We use $(u,v)$ to denote a
directed arc from $u$ to $v$; the end-vertex $u$ is the _tail_ of the arc and
the end-vertex $v$ is the _head_. For every subset $X\subseteq E(G)$, we write
$G-X$ to denote the directed graph obtained by removing all edges/arcs
corresponding to $X$ from $G$ (formally, $V(G-X)=V(G)$ with
$E(G-X)=E(G)\setminus X)$ if $G$ is undirected and
$A(G-X)=A(G)\setminus\\{(u,v),(v,u)\mid\\{u,v\\}\in X\\})$ if $G$ is
directed). If $X\subseteq V(G)$ is a set of vertices, then we let
$G-X=G[V(G)\setminus X]$ be the subgraph induced in $G$ by $V(G)\setminus X$.
An $st$-cut in $G$ is a set of edges/arcs $X$ such that the vertices $s$ and
$t$ are separated in $G-X$. If $n\in\mathbb{N}$, then $[n]$ denotes the set
$\\{1,\ldots,n\\}$.

###  2.1 Parameterized Complexity

A parameterized problem is a subset of $\Sigma^{*}\times\mathbb{N}$, where
$\Sigma$ is the input alphabet. The parameterized complexity class FPT
contains the problems decidable in $f(k)\cdot n^{O(1)}$ time, where $f$ is a
computable function and $n$ is the instance size; this forms the set of the
computationally most tractable problems. Reductions between parameterized
problems need to take the parameter into account. To this end, we use
_parameterized reductions_ (or fpt-reductions). Consider two parameterized
problems $L_{1},L_{2}\subseteq\Sigma^{*}\times\mathbb{N}$. A mapping
$P:\Sigma^{*}\times\mathbb{N}\rightarrow\Sigma^{*}\times\mathbb{N}$ is a
parameterized reduction from $L_{1}$ to $L_{2}$ if

  1. (1)

$(x,k)\in L_{1}$ if and only if $P((x,k))\in L_{2}$,

  2. (2)

the mapping can be computed in $f(k)\cdot n^{O(1)}$ time for some computable
function $f$, and

  3. (3)

there is a computable function $g:\mathbb{N}\rightarrow\mathbb{N}$ such that
for all $(x,k)\in\Sigma^{*}\times\mathbb{N}$, if
$(x^{\prime},k^{\prime})=P((x,k))$, then $k^{\prime}\leq g(k)$.

We will sometimes prove that certain problems are not in FPT. The class
${{\mbox{{{W}}}}}[1]$ contains all problems that are fpt-reducible to
Independent Set parameterized by the solution size, i.e. the number of
vertices in the independent set. Showing ${{\mbox{{{W}}}}}[1]$-hardness (by an
fpt-reduction) for a problem rules out the existence of an fpt algorithm under
the standard assumption that ${\mbox{{{FPT}}}}\neq{{\mbox{{{W}}}}}[1]$.

###  2.2 Constraint Satisfaction

A constraint language $\Gamma$ is a set of relations over a domain $D$. Each
relation $R\in\Gamma$ has an associated _arity_ $r\in\mathbb{N}$ and
$R\subseteq D^{r}$. All relations considered in this paper are binary and all
constraint languages are finite. An instance $\mathcal{I}$ of
$\textsc{CSP}(\Gamma)$ consists of a set of variables $V(\mathcal{I})$ and a
set of constraints $C(\mathcal{I})$ of the form $R(x,y)$, where $R\in\Gamma$
and $x,y\in V(\mathcal{I})$. To simplify notation, we may write $R(x,y)$ as
$xRy$. An assignment $\varphi:V(\mathcal{I})\rightarrow D$ _satisfies_ a
constraint $R(x,y)$ if $(\varphi(x),\varphi(y))\in R$ and _violates_ $R(x,y)$
if $(\varphi(x),\varphi(y))\notin R$. The assignment $\varphi$ is a satisfying
assignment (or a solution) if it satisfies every constraint in
$C(\mathcal{I})$.

CSP$(\Gamma)$
Instance: An instance $\mathcal{I}$ of $\textsc{CSP}(\Gamma)$. Question: Does
$\mathcal{I}$ admit a satisfying assignment?

The value of an assignment $\varphi$ for $\mathcal{I}$ is the number of
constraints in $C(\mathcal{I})$ satisfied by $\varphi$. For any subset of
constraints $X\subseteq C(\mathcal{I})$, let $\mathcal{I}-X$ denote the
instance with $V(\mathcal{I}-X)=V(\mathcal{I})$ and
$C(\mathcal{I}-X)=C(\mathcal{I})\setminus X$. The (parameterized) _almost
constraint satisfaction problem_ ($\textsc{MinCSP}(\Gamma)$) is defined as
follows:

MinCSP$(\Gamma)$
Instance: An instance $\mathcal{I}$ of $\textsc{CSP}(\Gamma)$ and an integer
$k$. Parameter: $k$. Question: Is there a set $X\subseteq C(\mathcal{I})$ such
that $\lvert X\rvert\leq k$ and $\mathcal{I}-X$ is satisfiable?

Given an instance $\langle\mathcal{I},k\rangle$ of $\textsc{MinCSP}(\Gamma)$,
the set $X$ can be computed with $|C(\mathcal{I})|$ calls to an algorithm for
MinCSP$(\cal A)$. Hence, we can view MinCSP$(\Gamma)$ as a decision problem
without loss of generality. Additionally note that if MinCSP$(\Gamma)$ is in
FPT, then CSP$(\Gamma)$ must be polynomial-time solvable: an instance
$\mathcal{I}$ of CSP$(\Gamma)$ is satisfiable if and only if the instance
$\langle\mathcal{I},0\rangle$ of MinCSP$(\Gamma)$ is a yes-instance, and
instances of the form $\langle\mathcal{I},0\rangle$ are solvable in polynomial
time if MinCSP$(\Gamma)$ is in FPT.

###  2.3 Interval Relations

We begin by reviewing the basics of Allen’s interval algebra [3] (IA). Its
domain is the set ${\mathbb{I}}$ of all pairs $(x,y)\in{\mathbb{Q}}^{2}$ such
that $x<y$, i.e. ${\mathbb{I}}$ can be viewed as the set of all closed
intervals $[a,b]$ of rational numbers. If $I=[a,b]\in\mathbb{I}$, then we
write $I^{-}$ for $a$ and $I^{+}$ for $b$. Let $\cal A$ denote the set of 13
basic relations that are presented in Table 1, and let $2^{\cal A}$ denote the
8192 binary relations that can be formed by taking unions of relations in
$\cal A$. The complexity of CSP$(\Gamma)$ is known for every $\Gamma\subseteq
2^{\cal A}$ [43] and in each case CSP$(X)$ is either polynomial-time solvable
or NP-complete. In particular, CSP$(\cal A)$ is in P. When considering subsets
$\Gamma\subseteq\cal A$, note that any constraint $x{\sf ri}y$ is equivalent
to $y{\sf r}x$ for ${\sf r}\in\\{{\sf p},{\sf m},{\sf o},{\sf d},{\sf s},{\sf
f}\\}$, so we may assume that ${\sf r}\in\Gamma$ if and only if ${\sf
ri}\in\Gamma$. Furthermore, for the remainder of the paper, we may assume
$\cal A=\\{{\sf p},{\sf m},{\sf o},{\sf d},{\sf s},{\sf f},\equiv\\}$.

When studying the optimization problem MinCSP, it is convenient to allow
_crisp_ constraints, i.e. constraints that cannot be deleted. Formally, for a
language $\Gamma\subseteq\cal A$ and a relation ${\sf r}\in\Gamma$, we say
that _$\Gamma$ supports crisp ${\sf r}$-constraints_ if, for every value of
the parameter $k\in\mathbb{N}$, we can construct an instance $\mathcal{I}_{\sf
r}$ of MinCSP$(\Gamma)$ with primary variables $x,y\in V(\mathcal{I}_{\sf r})$
such that the constraint $x{\sf r}y$ is equivalent to $\mathcal{I}_{\sf r}-X$
for all $X\subseteq C(\mathcal{I})$ such that $|X|\leq k$. Then, if we want to
enforce a constraint $x{\sf r}y$ in an instance of MinCSP$(\Gamma)$, we can
use $\mathcal{I}_{\sf r}$ with fresh variables
$V(\mathcal{I})\setminus\\{x,y\\}$ in its place. We collect the tricks to make
constraints crisp in the following two lemmas. First, we show the result for
_idempotent_ binary relations over an infinite domain $D$, i.e. relations
${\sf r}$ that are transitive and dense: $a{\sf r}b$ and $b{\sf r}c$ implies
$a{\sf r}c$ for all $a,b,c\in D$, and, for every $a,c\in D$ such that $a{\sf
r}c$ holds, there exists $b\in D$ such that $a{\sf r}b$ and $b{\sf r}c$ hold.

######  Lemma 1.

Let ${\sf r}$ be an idempotent binary relation over an infinite domain $D$.
Then $\\{{\sf r}\\}$ supports crisp ${\sf r}$-constraints.

###### Proof.

The instance $\mathcal{I}_{\sf r}$ of $\textsc{MinCSP}({\sf r})$ can be
constructed as follows: introduce $k+1$ auxiliary variables
$u_{1},\dots,u_{k+1}$ and let $\mathcal{I}_{\sf r}$ contain constraints $x{\sf
r}u_{i}$, $u_{i}{\sf r}y$ for all $i\in[k+1]$. After deleting any $k$
constraints from $I$, there remains $i\in[k+1]$ such that $x{\sf r}u_{i}{\sf
r}y$ is still in the instance. Correctness follows by idempotence of ${\sf
r}$: if an assignment satisfies $x{\sf r}u_{i}{\sf r}y$, then it satisfies
$x{\sf r}y$ by transitivity of ${\sf r}$; conversely, if an assignment
satisfies $x{\sf r}y$, then it can be extended to the auxiliary variables
since $D$ is infinite and ${\sf r}$ is dense. ∎

We now show that all interval languages $\Gamma\subseteq\cal A$ support crisp
${\sf r}$-constraints for all relations ${\sf r}\in\Gamma$.

######  Lemma 2.

Let ${\sf r}\in\cal A$ be an interval relation. Then $\\{{\sf r}\\}$ supports
crisp ${\sf r}$-constraints.

###### Proof.

First, observe that $\equiv,{\sf p},{\sf d},{\sf s},{\sf f}\in\cal A$ are
idempotent, so Lemma 1 applies. There are two relations left, namely ${\sf m}$
and ${\sf o}$. To construct $\mathcal{I}_{\sf m}$, introduce $2(k+1)$
auxiliary variables $u_{i}$, $v_{i}$, and create constraints $x{\sf m}u_{i}$,
$v_{i}{\sf m}u_{i}$, $v_{i}{\sf m}y$ for all $i\in[k+1]$. For one direction,
observe that after deleting any $k$ constraints, three constraints with $x,y$
and $u_{i},v_{i}$ for some $i$ remain. By definition of the relation ${\sf
m}$, these four constraints imply that $x^{+}=u_{i}^{-}=v_{i}^{+}=y^{-}$,
hence they imply $x{\sf m}y$. For the converse, if an assignment satisfies
$x{\sf m}y$, then setting $u_{i}=y$ and $v_{i}=x$ satisfies $\mathcal{I}_{\sf
m}$.

To construct $\mathcal{I}_{\sf o}$, introduce $2(k+1)$ auxiliary variables
$u_{i},v_{i}$, and create constraints $x{\sf o}u_{i}$, $u_{i}{\sf o}y$,
$v_{i}{\sf o}x$, $v_{i}{\sf o}y$ for all $i\in[k+1]$. For one direction,
observe that constraints $x{\sf o}u_{i}$, $u_{i}{\sf o}y$ imply
$x^{-}<u_{i}^{-}<x^{+}<u_{i}^{+}$ and $u_{i}^{-}<y^{-}<u_{i}^{+}<y^{+}$, hence
$x^{-}<y^{-}$ and $x^{+}<y^{+}$. The constraints $v_{i}{\sf o}x$, $v_{i}{\sf
o}y$ imply $v_{i}^{-}<x^{-}<v_{i}^{+}<x^{+}$ and
$v_{i}^{-}<y^{-}<v_{i}^{+}<y^{+}$, hence $y^{-}<v_{i}^{+}<x^{+}$. We obtain
that $x^{-}<y^{-}<x^{+}<y^{+}$, i.e. $x{\sf o}y$ by definition. For the
converse, if an assignment satisfies $x{\sf o}y$, we can extend it to satisfy
$\mathcal{I}_{\sf o}$ by choosing any two intervals $u$ and $v$ such that
$v^{-}<x^{-}<u^{-}<y^{-}<v^{+}<x^{+}<u^{+}<y^{+}$ and setting $u_{i}=u$ and
$v_{i}=v$ for all $i\in[k+1]$. ∎

##  3 Classification Result

In this section we prove the dichotomy theorem for the parameterized
complexity of $\textsc{MinCSP}(\Gamma)$ for every subset $\Gamma\subseteq\cal
A$ of interval relations. We defer the proofs of the main technical details to
the following parts of the paper, while keeping this section relatively high-
level and focusing on the proof structure. Some observations reduce the number
of subsets of relations that we need to consider in the classification. For
the first one, we need a simplified definition of _implementations_. More
general definitions are used in e.g. [35] and [37].

######  Definition 3.

Let $\Gamma$ be a constraint language and ${\sf r}$ be a binary relation over
the same domain. A _(simple) implementation_ of a relation ${\sf r}$ in
$\Gamma$ is an instance $\mathcal{C}_{\sf r}$ of $\textsc{CSP}(\Gamma)$ with
primary variables $x_{1},x_{2}$ and, possibly, some auxiliary variables
$y_{1},\dots,y_{\ell}$ such that:

  * •

if an assignment $\varphi$ satisfies $\mathcal{C}_{\sf r}$, then it satisfies
the constraint $x_{1}{\sf r}x_{2}$;

  * •

if an assignment $\varphi$ does not satisfy $x_{1}{\sf r}x_{2}$, then it can
be extended to the auxiliary variables $y_{1},\dots,y_{\ell}$ so that all but
one constraint in $\mathcal{C}_{\sf r}$ are satisfied.

In this case we say that $\Gamma$ _implements_ ${\sf r}$.

Intuitively, we can replace every occurrence of a constraint $x{\sf r}y$ with
its implementation in $\Gamma$ while preserving the cost of making the
instance consistent. This intuition is made precise in the following lemma.

######  Lemma 4 (Proposition 5.2 in [37]).

Let $\Gamma$ be a constraint language that implements a relation ${\sf r}$. If
$\textsc{MinCSP}(\Gamma)$ is in FPT, then so is
$\textsc{MinCSP}(\Gamma\cup\\{{\sf r}\\})$. If
$\textsc{MinCSP}(\Gamma\cup\\{{\sf r}\\})$ is W[1]-hard, then so is
$\textsc{MinCSP}(\Gamma)$.

$x_{1}$$y$$x_{2}$

$x_{1}$$x_{2}$$y$

$x_{1}$$x_{2}$$y$

Figure 1: Implementations of the relations ${\sf p}$, ${\sf d}$ and ${\sf o}$
from Lemma 5.

######  Lemma 5 (Implementations).

Let $\Gamma\subseteq\cal A$ be a subset of interval relations.

  1. 1.

If $\Gamma$ contains ${\sf m}$, then $\Gamma$ implements ${\sf p}$.

  2. 2.

If $\Gamma$ contains ${\sf f}$ and ${\sf s}$, then $\Gamma$ implements ${\sf
d}$ and ${\sf o}$.

###### Proof.

Let $\mathcal{C}_{\sf p}=\\{x_{1}\\{{\sf m}\\}y,y\\{{\sf m}\\}x_{2}\\}$,
$\mathcal{C}_{\sf d}=\\{x_{1}\\{{\sf f}\\}y,y\\{{\sf s}\\}x_{2}\\}$ and
$\mathcal{C}_{\sf o}=\\{y\\{{\sf f}\\}x_{1},y\\{{\sf s}\\}x_{2}\\}$. See
Figure 1 for illustrations. One direction of the correctness proof is the same
for all three cases: any assignment to $x_{1}$ and $x_{2}$ can be extended to
$y$ so that it satisfies the constraint between $x_{1}$ and $y$ regardless of
the interval assigned to $x_{2}$. For the other direction, recall the
definitions of the interval relations. An assignment satisfying
$\mathcal{C}_{\sf p}$ satisfies $x_{1}^{+}=y^{-}<y^{+}=x_{2}^{-}$, i.e.
$x_{1}^{+}<x_{2}^{-}$ and so $x_{1}\\{{\sf p}\\}x_{2}$ holds. An assignment
satisfying $\mathcal{C}_{\sf d}$ satisfies $x_{1}^{-}>y^{-}=x_{2}^{-}$ and
$x_{1}^{+}=y^{+}<x_{2}^{+}$, i.e. $x_{1}^{-}>x_{2}^{-}\land
x_{1}^{+}<x_{2}^{+}$ and so $x_{1}\\{{\sf d}\\}x_{2}$ holds. Finally, an
assignment satisfying $\mathcal{C}_{\sf o}$ satisfies
$x_{1}^{-}<y^{-}=x_{2}^{-}$, $x_{2}^{-}=y^{-}<y^{+}=x_{1}^{+}$, and
$x_{1}^{+}=y^{+}<x_{2}^{+}$, i.e. $x_{1}^{-}<x_{2}^{-}<x_{1}^{+}<x_{2}^{+}$
and so $x_{1}\\{{\sf o}\\}x_{2}$ holds. ∎

Another observation utilizes the symmetry of interval relations. By switching
the left and the right endpoints of all intervals in an instance $\mathcal{I}$
of $\textsc{MinCSP}(\cal A)$ and then negating their values, we obtain a
_reversed instance_ $\mathcal{I}^{R}$. This way, in every constraint of
$\mathcal{I}$, all relations except ${\sf d}$, ${\sf s}$ and ${\sf f}$ are
mapped to their inverses, ${\sf d}$ stays unchanged, while ${\sf s}$ and ${\sf
f}$ are switched. Formally, instance $\mathcal{I}^{R}$ of $\textsc{CSP}(\cal
A)$ has the same set of variables as $\mathcal{I}$, and contains a constraint
$uf({\sf r})v$ for every $u{\sf r}v$ in $C(\mathcal{I})$, where $f:\cal
A\to\cal A$ is defined as $f({\sf r})={\sf ri}$ for ${\sf r}\in\\{{\sf m},{\sf
p},{\sf o}\\}$, $f(\equiv)=\equiv$, $f({\sf d})={\sf d}$, $f({\sf s})={\sf f}$
and $f({\sf f})={\sf s}$.

######  Lemma 6 (Lemma 4.2 of [43]).

An instance $\mathcal{I}$ of $\textsc{CSP}(\cal A)$ is satisfiable if and only
if the reversed instance $\mathcal{I}^{R}$ is satisfiable.

For example, this implies that obstructions for satisfiability of
$\textsc{CSP}({\sf s},{\sf p})$ are the same as those for $\textsc{CSP}({\sf
f},{\sf p})$ up to relabelling ${\sf s}$-arcs into ${\sf f}$-arcs, as shown in
Lemma 8.

To obtain our results, we use combinatorial tools and represent an instance
$\mathcal{I}$ of CSP$(\cal A)$ as an _arc-labelled mixed graph_
$G_{\mathcal{I}}$, i.e. a graph that contains edges for symmetric constraints
and labelled arcs for asymmetric ones. More precisely, the graph
$G_{\mathcal{I}}$ is obtained by introducing all variables of $\mathcal{I}$ as
vertices, adding directed arcs $(u,v)$ labelled with ${\sf r}\in\cal
A\setminus\\{\equiv\\}$ for every constraint $u{\sf r}v$ in $C(\mathcal{I})$,
and undirected edges $uv$ for every constraint $u\equiv v$ in $\mathcal{I}$.
Note that $G_{\mathcal{I}}$ may have parallel arcs with different labels and
may contain loops. The undirected graph underlying $G_{\mathcal{I}}$ is called
the _primal graph_ of $\mathcal{I}$; we allow the primal graph to contain
loops and parallel edges (in both cases, this will mean the primal graph
contains a cycle). The advantage of the graph representation is supported by
the following lemma:

######  Lemma 7 (Cycles).

Let $\mathcal{I}$ be an inclusion-wise minimal unsatisfiable instance of
CSP$(\cal A)$ (i.e. removing any constraint of $\mathcal{I}$ results in a
satisfiable instance). Then the primal graph of $\mathcal{I}$ is a cycle.

The proof of the lemma is deferred to Section 4. From the combinatorial point
of view, minimal unsatisfiable instances are _bad cycles_ in the labelled
graph. For example, in $\textsc{MinCSP}({\sf p})$, the bad cycles are all
directed cycles. For $\textsc{MinCSP}({\sf p},\equiv)$, the bad cycles contain
at least one ${\sf p}$-arc and all ${\sf p}$-arcs in the same direction. Thus,
$\textsc{MinCSP}(\Gamma)$ can now be cast as a certain feedback edge set
problem – our goal is to find a set of $k$ edges in the primal graph that
intersects all bad cycles. Understanding the complexity of
$\textsc{MinCSP}(\Gamma)$ for a particular subset of interval relations
$\Gamma\subseteq\cal A$ requires characterizing the bad cycles explicitly. We
present such a characterization for several cases below, and refer to Section
4 for the proof. As it turns out, these are sufficient for proving the
classification theorem.

######  Lemma 8 (Bad Cycles).

Let $\mathcal{I}$ be an instance of $\textsc{CSP}({\sf r}_{1},{\sf r}_{2})$
for some ${\sf r}_{1},{\sf r}_{2}\in\cal A$, and consider the arc-labelled
mixed graph $G_{\mathcal{I}}$. Then $\mathcal{I}$ is satisfiable if and only
if $G_{\mathcal{I}}$ does not contain any bad cycles described below.

  1. 1.

If ${\sf r}_{1}={\sf d}$ and ${\sf r}_{2}={\sf p}$, then the bad cycles are
cycles with ${\sf p}$-arcs in the same direction and no ${\sf d}$-arcs meeting
head-to-head.

  2. 2.

If ${\sf r}_{1}={\sf d}$ and ${\sf r}_{2}={\sf o}$, then the bad cycles are
cycles with all ${\sf d}$-arcs in the same direction and all ${\sf o}$-arcs in
the same direction (the direction of the ${\sf d}$-arcs may differ from that
of the ${\sf o}$-arcs).

  3. 3.

If ${\sf r}_{1}={\sf o}$ and ${\sf r}_{2}={\sf p}$, then the bad cycles are

     * •

directed cycles of ${\sf o}$-arcs and

     * •

cycles with all ${\sf p}$-arcs in the forward direction, with every
consecutive pair of ${\sf o}$-arcs in the reverse direction separated by a
${\sf p}$-arc (this case includes directed cycles of ${\sf p}$-arcs).

  4. 4.

If ${\sf r}_{1}\in\\{{\sf f},{\sf s}\\}$ and ${\sf r}_{2}\in\\{{\sf d},{\sf
o},{\sf p}\\}$, then the bad cycles are

     * •

directed cycles of ${\sf r}_{1}$-arcs and

     * •

cycles with at least one ${\sf r}_{2}$-arc and all ${\sf r}_{2}$-arcs in the
same direction (and ${\sf r}_{1}$-arcs directed arbitrarily).

Our first algorithmic result is based on a reduction to the Subset Directed
Feedback Arc Set (Sub-DFAS) problem. The formal definition of Sub-DFAS and the
proof can be found in Section 5.

######  Lemma 9.

$\textsc{MinCSP}({\sf m},{\sf p})$ is in FPT.

While Lemma 5 implies that we can replace a ${\sf p}$-constraint with an
implementation using ${\sf m}$ constraints in the above case, such an
implementation is not possible for our second algorithmic case. The latter
relies on the much more complicated characterization in Lemma 8, the symmetry
of ${\sf s}$ and ${\sf f}$ implied by Lemma 6, and a sophisticated
modification of the algorithm for Sub-DFAS from [41]. The algorithm is based
on the novel flow augmentation technique [38]. See Section 5 for the details.

######  Lemma 10.

$\textsc{MinCSP}({\sf r}_{1},{\sf r}_{2},\equiv)$ is in FPT for ${\sf
r}_{1}\in\\{{\sf s},{\sf f}\\}$ and ${\sf r}_{2}\in\\{{\sf p},{\sf o},{\sf
d}\\}$.

For the negative results, we start by proving W[1]-hardness for paired and
simultaneous graph cut problems in Sections 6.3 and 6.4, respectively. In
paired problems, the input consists of two graphs together with a pairing of
their edges. The goal is to compute cuts in both graphs using at most $k$
pairs. While the problems on individual graphs are solvable in polynomial
time, the pairing requirement leads to W[1]-hardness. For certain
$\Gamma\subseteq\cal A$, paired problems reduce to $\textsc{MinCSP}(\Gamma)$.
For intuition, consider a constraint $x\equiv y$. If we consider the left and
the right endpoints separately, then $\equiv$ implies two equalities:
$x^{-}=y^{-}$ and $x^{+}=y^{+}$. Together with another relation (e.g. ${\sf
m}$), this double-equality relation can be used to encode the pairing of the
edges of two graphs (namely, the left-endpoint graph and the right-endpoint
graph). We note that the double-equality relation is also the cornerstone of
all hardness results in the parameterized complexity classification of Boolean
MinCSP [39]. This intuition is crystallized in Section 6.3 in the proof of the
following lemma.

######  Lemma 11.

MinCSP$({\sf m},\equiv)$, MinCSP$({\sf m},{\sf s})$ and MinCSP$({\sf m},{\sf
f})$ are W[1]-hard.

In simultaneous cut problems, the input also consists of two graphs. Here, the
graphs share some arcs/edges that can be deleted simultaneously at unit cost.
The goal is to compute a set of $k$ arcs/edges that is a cut in both graphs.
As for the paired problems, computing cuts for individual graphs is feasible
in polynomial time. However, the possibility of choosing common arcs/edges
while deleting them at a unit cost correlates the choices in one graph with
the choices in the other, and leads to W[1]-hardness. Starting from this
problem, we prove the following lemma in Section 6.2.

######  Lemma 12.

MinCSP$({\sf d},{\sf o})$, MinCSP$({\sf p},{\sf o})$ and MinCSP$({\sf d},{\sf
p})$ are W[1]-hard.

| m | p | s | f | d | o
---|---|---|---|---|---|---
$\equiv$ |  W[1]-h | FPT | FPT | FPT | FPT | FPT
m |  | FPT |  W[1]-h |  W[1]-h |  W[1]-h |  W[1]-h
p |  |  | FPT | FPT |  W[1]-h |  W[1]-h
s |  |  |  |  W[1]-h | FPT | FPT
f |  |  |  |  | FPT | FPT
d |  |  |  |  |  |  W[1]-h
Table 2: Complexity of MinCSP with two interval relations. m p f/s $\equiv$ o
d Figure 2: Compatibility graph for interval relations. Two vertices $u$, $v$
are adjacent in this graph if $\textsc{MinCSP}(u,v)$ is in FPT. The ${\sf
f}/{\sf s}$ vertex represents either of these two relations.

Combining all results above, we are ready to present the full classification.

######  Theorem 13 (Full classification).

Let $\Gamma\subseteq\cal A$ be a subset of interval relations. Then
$\textsc{MinCSP}(\Gamma)$ is in FPT if $\Gamma\subseteq\\{{\sf m},{\sf p}\\}$
or $\Gamma\subseteq\\{{\sf r}_{1},{\sf r}_{2},\equiv\\}$ for any ${\sf
r}_{1}\in\\{{\sf s},{\sf f}\\}$ and ${\sf r}_{2}\in\\{{\sf p},{\sf o},{\sf
d}\\}$, and W[1]-hard otherwise.

###### Proof.

The tractable cases follow from Lemmas 9 and 10. For the full classification,
we consider subsets of relations $\Gamma\subseteq\cal A$ in order of
increasing cardinality. If $|\Gamma|=1$, then $\Gamma$ is contained in one of
the maximal tractable subsets. Now consider $|\Gamma|=2$. The classification
for this case is summarized in Table 2 . We consider the table row by row. We
only spell out W[1]-hardness arguments since tractability follows in all cases
by inclusion in one of the maximal tractable subsets.

  * •

$\textsc{MinCSP}(\equiv,{\sf m})$ is W[1]-hard by Lemma 11.
$\textsc{MinCSP}({\sf m},{\sf s})$ and $\textsc{MinCSP}({\sf m},{\sf f})$ are
W[1]-hard by Lemma 11; W[1]-hardness of $\textsc{MinCSP}({\sf m},{\sf o})$ and
$\textsc{MinCSP}({\sf m},{\sf d})$ follows from the hardness of
$\textsc{MinCSP}({\sf p},{\sf o})$ and $\textsc{MinCSP}({\sf p},{\sf d})$
(Lemma 12) by using Lemma 4 combined with the fact that ${\sf m}$ implements
${\sf p}$ (Lemma 5).

  * •

$\textsc{MinCSP}({\sf p},{\sf o})$ and $\textsc{MinCSP}({\sf p},{\sf d})$ are
W[1]-hard by Lemma 12.

  * •

W[1]-hardness of $\textsc{MinCSP}({\sf s},{\sf f})$ follows from the hardness
of $\textsc{MinCSP}({\sf d},{\sf o})$ (Lemma 12) by using Lemma 4 combined
with the fact that $\\{{\sf s},{\sf f}\\}$ implements ${\sf d}$ and ${\sf o}$
(Lemma 5).

  * •

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

We proceed to subsets $\Gamma$ of size $3$. It is useful to consider the
compatibility graph of relations, i.e. a graph with a vertex for every
relation in $\cal A$ and an edge for every pair of relations ${\sf r}_{1},{\sf
r}_{2}$ such that $\textsc{MinCSP}({\sf r}_{1},{\sf r}_{2})$ is in FPT. See
Figure 2for an illustration. Since $\textsc{MinCSP}({\sf s},{\sf f})$ is
W[1]-hard, ${\sf s}$ and ${\sf f}$ cannot both be included in a tractable
subset of relations. By symmetry (Lemma 6), we can identify ${\sf s}$ and
${\sf f}$, thus simplifying the drawing. Note that if $\Gamma$ contains a pair
${\sf r}_{1},{\sf r}_{2}$ that are not connected by an edge, then
$\textsc{MinCSP}(\Gamma)$ is W[1]-hard. Thus, candidates for tractable
constraint languages of size $3$ correspond to triangles in the graph. By
examining the graph, we find that there are exactly $3$ triangles, which
correspond to six constraint languages (recall that ${\sf s}$ and ${\sf f}$
are identified). MinCSP for all these languages is in FPT by Lemma 10. Since
the compatibility graph does not contain any cliques of size $4$, every
$\Gamma\subseteq\cal A$ with $|\Gamma|\geq 4$ contains an incompatible pair of
relations, therefore $\textsc{MinCSP}(\Gamma)$ is W[1]-hard if $|\Gamma|\geq
4$. This completes the proof. ∎

##  4 Bad Cycles

In this section, we prove Lemmas 7 and 8, i.e. we describe the minimal
obstructions to satisfiability for certain subsets of $\cal A$. To do this, we
will use the point algebra (PA) [56]. This a CSP with the rationals
${\mathbb{Q}}$ as the variable domain and the constraint language
$\\{<,=,\leq,\neq\\}$, where the relations are interpreted over ${\mathbb{Q}}$
in the obvious way. This CSP is polynomial-time solvable. For the subsets of
$\cal A$ we consider, we can encode our problem instances as instances of
point algebra that contain only $<$ and $=$ constraints (see also Table 1). It
is easy to verify that if an instance $\mathcal{I}$ of the point algebra
contains only $<$ and $=$ constraints, then it is satisfiable if and only if
its primal graph does not contain a cycle in which all $<$ relations are
directed in the same way. This allows us to show that the minimal
unsatisfiable instances of $\textsc{CSP}(\cal A)$ also have primal graphs that
are cycles (Lemma 7). We then completely describe these unsatisfiable cycles
for our chosen subsets of $\cal A$ in Lemma 8.

See 7

###### Proof.

Let $\mathcal{I}$ be an inclusion-wise minimal unsatisfiable instance of
CSP$(\cal A)$. We can write $\mathcal{I}$ as an instance
$\mathcal{I}^{\prime}$ of CSP$(<,=)$, a constraint satisfaction problem over
the point algebra. To do this, we set
$V(\mathcal{I}^{\prime})=\\{I^{-},I^{+}\;|\;I\in V(\mathcal{I})\\}$ and
$C(\mathcal{I}^{\prime})=\\{(I^{-}<I^{+})\;|\;I\in V(\mathcal{I})\\}$ and
then, for each constraint in $C(\mathcal{I})$, we add the corresponding $<$
and/or $=$ constraints to $C(\mathcal{I}^{\prime})$, as described in Table 1.
Since $\mathcal{I}$ is unsatisfiable, $\mathcal{I}^{\prime}$ must also be
unsatisfiable. This means that for some $\ell\geq 1$, there must be a sequence
of variables $v_{1},\ldots,v_{\ell}\in V(\mathcal{I}^{\prime})$ and a sequence
of constraints $v_{1}{\sf r}_{1}v_{2},v_{2}{\sf
r}_{2}v_{3},\ldots,v_{\ell-1}{\sf r}_{\ell-1}v_{\ell},v_{\ell}{\sf
r}_{\ell}v_{1}\in C(\mathcal{I}^{\prime})$, where ${\sf r}_{i}\in\\{<,=\\}$
for all $i$ and ${\sf r}_{i}$ is $<$ for at least one value of $i$. We may
assume the sequences are chosen such that (1) $\ell$ is minimum and (2) the
number of constraints in the sequence of the form $I^{-}<I^{+}$ is maximum for
this value of $\ell$.

Let $\mathcal{I}^{\prime\prime}$ be the sub-instance of $\mathcal{I}^{\prime}$
with $V(\mathcal{I}^{\prime\prime})=\\{v_{1},\ldots,v_{\ell}\\}$ and
$C(\mathcal{I}^{\prime\prime})=\\{v_{1}{\sf r}_{1}v_{2},v_{2}{\sf
r}_{2}v_{3},\ldots,v_{\ell-1}{\sf r}_{\ell-1}v_{\ell},v_{\ell}{\sf
r}_{\ell}v_{1}\\}$ and note that $\mathcal{I}^{\prime\prime}$ is
unsatisfiable. By minimality of $\ell$, the primal graph of
$\mathcal{I}^{\prime\prime}$ is a cycle and the $v_{i}$ variables are pairwise
distinct. Next, suppose for contradiction, that there is a variable
$I\in\mathcal{I}$ such that both $I^{-}\in V(\mathcal{I}^{\prime\prime})$ and
$I^{+}\in V(\mathcal{I}^{\prime\prime})$, but $(I^{-}<I^{+})\notin
C(\mathcal{I}^{\prime\prime})$. Without loss of generality, assume
$v_{1}=I^{-}$ and $v_{i}=I^{+}$. Replacing $v_{1}{\sf r}_{1}v_{2},v_{2}{\sf
r}_{2}v_{3},\ldots,v_{i-1}{\sf r}_{i-1}v_{i}$ by $(I^{-}<I^{+})$ in
$C(\mathcal{I}^{\prime\prime})$ yields another unsatisfiable instance, but
with either a smaller value of $\ell$ or more constraints of the form
$(I^{-}<I^{+})$. Since $(I^{-}<I^{+})$ is a constraint in
$\mathcal{I}^{\prime}$, this contradicts the choice of
$\mathcal{I}^{\prime\prime}$. Therefore if $I^{-}\in
V(\mathcal{I}^{\prime\prime})$ and $I^{+}\in V(\mathcal{I}^{\prime\prime})$,
then $(I^{-}<I^{+})\in C(\mathcal{I}^{\prime\prime})$.

We now construct an instance $\mathcal{I}^{\prime\prime\prime}$ of CSP$(\cal
A)$. We set
$V(I^{\prime\prime\prime})=\\{I\;|\;I^{-}\;\mathrm{or}\;I^{+}\in\\{v_{1},\ldots,v_{\ell}\\}\\}$.
Next, for each constraint in $\mathcal{I}^{\prime\prime}$ that is not of the
form $(I^{-}<I^{+})$, we add a constraint from $\mathcal{I}$ that implies this
constraint. Now if we translate the instance
$\mathcal{I}^{\prime\prime\prime}$ into the point algebra (like we did
translating $\mathcal{I}$ into $\mathcal{I}^{\prime}$), we obtain a
superinstance of $\mathcal{I}^{\prime\prime}$, so it follows that
$\mathcal{I}^{\prime\prime\prime}$ is unsatisfiable.

Furthermore, $\mathcal{I}^{\prime\prime\prime}$ is a sub-instance of
$\mathcal{I}$, so by minimality of $\mathcal{I}$, it follows that
$\mathcal{I}=\mathcal{I}^{\prime\prime\prime}$. If the primal graph of
$\mathcal{I}^{\prime\prime\prime}$ is a cycle of length $2$ or a loop, then we
are done. Otherwise, by construction, each variable in
$\mathcal{I}^{\prime\prime\prime}$ is contained in two constraints (which
either imply two consecutive constraints in the cycle in
$\mathcal{I}^{\prime\prime}$, or imply two constraints separated by an
$(I^{-}<I^{+})$ constraint in $\mathcal{I}^{\prime\prime}$) and the primal
graph f of $\mathcal{I}^{\prime\prime\prime}$ is connected. Therefore the
primal graph of $\mathcal{I}^{\prime\prime\prime}$ is a cycle. This completes
the proof. ∎

In the proof of the next lemma, we will use the following additional notation.
Suppose $\varphi$ is an assignment for an instance $\mathcal{I}$ of
$\textsc{CSP}(\cal A)$ and $c\in\mathbb{Q}$. For $v\in V(\mathcal{I})$, we let
$\varphi_{+c}(v)^{-}=\varphi(v)^{-}+c$ and
$\varphi_{+c}(v)^{-}=\varphi(v)^{-}+c$ (with $\varphi_{-c}$ defined
analogously). Observe that $\varphi_{+c}$ is a satisfying assignment for
$\mathcal{I}$ if and only if $\varphi$ is. Furthermore, let
$\varphi_{max}=\max\\{\varphi(v)^{+}\;|\;v\in V(\mathcal{I})\\}$ and
$\varphi_{min}=\min\\{\varphi(v)^{-}\;|\;v\in V(\mathcal{I})\\}$.

See 8

###### Proof.

By Lemma 7, we only need to consider instances $\mathcal{I}$ whose primal
graph is a minimal bad cycle. If $G_{\mathcal{I}}$ is a loop with a label
other than $\equiv$, then it is a bad cycle. If $G_{\mathcal{I}}$ contains two
parallel arcs with different labels or two anti-parallel arcs with labels in
$\\{{\sf d},{\sf f},{\sf m},{\sf o},{\sf p},{\sf s}\\}$, then it is a bad
cycle.

######  Claim 8.1.

If a cycle contains two ${\sf p}$-arcs in opposite directions, then it is
satisfiable.

###### Proof of claim.

Let $\mathcal{I}$ be such an instance and let $\mathcal{I}^{\prime}$ be the
instance obtained by removing a forward ${\sf p}$-arc and a reverse ${\sf
p}$-arc from $G_{\mathcal{I}}$. Note that $G_{\mathcal{I}^{\prime}}$ is
disconnected, and let $\mathcal{I}^{\prime\prime}$ and
$\mathcal{I}^{\prime\prime\prime}$ be the sub-instances of
$\mathcal{I}^{\prime}$ that correspond to the two components of
$G_{\mathcal{I}^{\prime}}$. Without loss of generality, we may assume that the
${\sf p}$-arcs we removed are each from variables in
$V(\mathcal{I}^{\prime\prime})$ to variables in
$V(\mathcal{I}^{\prime\prime\prime})$. Since $G_{\mathcal{I}^{\prime\prime}}$
and $G_{\mathcal{I}^{\prime\prime\prime}}$ are paths,
$\mathcal{I}^{\prime\prime}$ and $\mathcal{I}^{\prime\prime\prime}$ are
satisfiable by Lemma 7; let $\varphi^{\prime\prime}$ and
$\varphi^{\prime\prime\prime}$, respectively, be satisfying assignments for
these instances. We now define an assignment $\varphi$ for $\mathcal{I}$ by
setting
$\varphi(v)=\varphi_{-(\varphi_{max}^{\prime\prime}+1)}^{\prime\prime}(v)$ if
$v\in V(\mathcal{I}^{\prime\prime})$ and
$\varphi(v)=\varphi_{-(\varphi_{min}^{\prime\prime\prime}-1)}^{\prime\prime\prime}(v)$
if $v\in V(\mathcal{I}^{\prime\prime\prime})$. Note that $\varphi(v)^{-}$ and
$\varphi(v)^{+}$ are negative if $v\in V(\mathcal{I}^{\prime\prime})$ and
positive if $v\in V(\mathcal{I}^{\prime\prime\prime})$, so the two ${\sf p}$
constraints we removed from $\mathcal{I}$ are satisfied by $\varphi$.
Furthermore, all the other constraints in $\mathcal{I}$ appear in either
$\mathcal{I}^{\prime\prime}$ or $\mathcal{I}^{\prime\prime\prime}$ and
$\varphi$ satisfies these by construction. Therefore $\varphi$ is a satisfying
assignment for $\mathcal{I}$. ∎

######  Claim 8.2.

If a cycle contains two ${\sf d}$-arcs that meet head-to-head, then it is
satisfiable.

###### Proof of claim.

Let $\mathcal{I}$ be such an instance and let $x{\sf d}y$ and $z{\sf d}y$ be
the two constraints corresponding to these arcs. Let $\mathcal{I}^{\prime}$ be
the instance obtained from $\mathcal{I}$ by removing these two constraints,
along with the variable $y$. The primal graph of $\mathcal{I}^{\prime}$ is a
path, so $\mathcal{I}$ has a satisfying assignment $\varphi^{\prime}$. We set
$\varphi(y)^{-}=\varphi^{\prime}_{min}-1$,
$\varphi(y)^{+}=\varphi^{\prime}_{max}+1$ and $\varphi(v)=\varphi^{\prime}(v)$
otherwise. By construction, $\varphi$ satisfies the constraints $x{\sf d}y$
and $z{\sf d}y$, the constraint $\varphi(y)^{-}<\varphi(y)^{+}$ and all other
constraints in $\mathcal{I}$. Therefore $\varphi$ satisfies $\mathcal{I}$. ∎

We now consider the four cases stated in the lemma.

  1. 1.

If we have two ${\sf p}$-arcs in opposite directions, then the instance is
satisfiable by Claim 8.1. If we have two ${\sf d}$-arcs meeting head-to-head,
then the instance is satisfiable by Claim 8.2. We claim that otherwise the
instance $\mathcal{I}$ is unsatisfiable. Suppose, for contradiction, that the
instance is satisfiable. If there are no ${\sf p}$-arcs, then this would give
a cycle of ${\sf d}$-arcs all in the same direction, which is clearly not
satisfiable. We may therefore assume there is at least one ${\sf p}$-arc.
Observe the each non-empty set of consecutive ${\sf d}$-arcs consists of a
non-negative number of reverse $d$-arcs, followed by a non-negative number of
forward $d$-arcs i.e. we have a sequence of constraints

$x_{k+1}{\sf di}x_{k+2},\ldots,x_{k+i-1}{\sf di}x_{k+i},x_{k+i}{\sf
d}x_{k+i+1},\ldots,x_{k+j-1}{\sf d}x_{k+j},$

where $j\geq 1$. This implies the point algebra constraints

$x_{k+1}^{-}<\cdots<x_{k+i}^{-}>\cdots>x_{k+j}^{-}$

and

$x_{k+1}^{+}>\cdots>x_{k+i}^{+}<\cdots<x_{k+j}^{+}.$

Since $x_{k+i}^{-}<x_{k+i}^{+}$, this means that
$x_{k+i}^{*}=(x_{k+i}^{-}+x_{k+i}^{+})/2$ is contained in every interval in
$\\{x_{k+1},\ldots,x_{k+j}\\}$. Now if $u{\sf p}v$, then for every
$x\in[u^{-},u^{+}]$ and every $y\in[v^{-},v^{+}]$ we have $x<y$. We therefore
have a cyclic sequence of points in $\mathbb{Q}$, where if $u{\sf p}v$ is a
constraint in $\mathcal{I}$, then the point corresponding to $u$ is less than
that corresponding to $v$, and if $u{\sf d}v$ is a constraint in
$\mathcal{I}$, then the points corresponding to $u$ and $v$ are equal. We
therefore have a satisfied cycle of point algebra relations $<$ and $=$ with
at least one $<$ relation and all $<$ relations in the same direction, a
contradiction. Therefore $\mathcal{I}$ is indeed unsatisfiable.

  2. 2.

A constraint $u{\sf d}v$ implies that $u^{-}>v^{-}$ and $u^{+}<v^{+}$. A
constraint $u{\sf o}v$ implies that $u^{-}<v^{-}$ and $u^{+}<v^{+}$. Thus a
cycle of ${\sf d}$ and ${\sf o}$ constraints in which all of these constraints
correspond to arcs in the same direction yields an unsatisfiable set of point
algebra on $\\{v^{+}\;|\;v\in V(\mathcal{I})\\}$. Similarly, a cycle of ${\sf
d}$ and ${\sf o}$ constraints in which all of the ${\sf d}$ constraints are in
the forward direction, and all of the ${\sf o}$-arcs are in the reverse
direction yields unsatisfiable set of point algebra on $\\{v^{-}\;|\;v\in
V(\mathcal{I})\\}$. Therefore the described bad cycles really are indeed bad.

Suppose we have a cycle that is not of this form. Then the set of implied
constraints on pairs of variables in $\\{v^{-}\;|\;v\in V(\mathcal{I})\\}$ has
a satisfying assignment $\psi^{-}$. Similarly, the set of implied constraints
on pairs of variables in $\\{v^{+}\;|\;v\in V(\mathcal{I})\\}$ has a
satisfying assignment $\psi^{+}$. We may assume (by adding a fixed constant to
the values) that $\psi^{-}$ only takes negative values and $\psi^{+}$ only
takes positive values. Now for $v\in V(\mathcal{I})$, let
$\varphi(v)^{-}=\psi^{-}(v)$ and $\varphi(v)^{+}=\psi^{+}(v)$. Then $\varphi$
satisfies all of the ${\sf d}$ and ${\sf o}$ constraints in $\mathcal{I}$, by
construction. Furthermore, for all $v\in V(\mathcal{I})$,
$\varphi(v)^{-}<0<\varphi(v)^{+}$, so $\varphi$ is a satisfying assignment of
$\mathcal{I}$.

  3. 3.

Clearly, directed cycles of arcs of the same relation are bad. If the cycle
contains a forward ${\sf p}$-arc and a reverse ${\sf p}$-arc, then the
instance is satisfiable by Claim 8.1. We may therefore restrict ourselves to
looking at cycles in which all ${\sf p}$-arcs go in the forward direction and
there is at least one ${\sf o}$-arc. If the cycle contains only ${\sf
o}$-arcs, then we are done by Case 2, so we may assume there is at least one
${\sf p}$-arc. Now suppose that the cycle contains a forward ${\sf p}$-arc and
two reverse ${\sf o}$-arcs that do not have a ${\sf p}$-arc between then, but
may have a non-negative number of forward ${\sf o}$-arcs between them, say
$x{\sf oi}y_{1},y_{1}{\sf o}y_{2},\ldots,y_{k-1}{\sf o}y_{k},y_{k}{\sf oi}z$,
where $k\geq 1$. Let $\mathcal{I}^{\prime}$ be the instance obtained from
$\mathcal{I}$ by deleting these constraints and the variables $y_{i}$ and
adding the constraint $x{\sf pi}z$. Then $\mathcal{I}^{\prime}$ contains a
forward and a reverse ${\sf p}$-arc, so it has a satisfying assignment
$\varphi^{\prime}$ and note that
$\varphi^{\prime}(x)^{-}>\varphi^{\prime}(z)^{+}$. We let

$\varphi(y_{i})^{-}=\frac{i\cdot\varphi^{\prime}(z)^{-}+(k+1-i)\cdot\varphi^{\prime}(z)^{+}}{k+1},$
$\varphi(y_{i})^{+}=\frac{i\cdot\varphi^{\prime}(x)^{-}+(k+1-i)\cdot\varphi^{\prime}(x)^{+}}{k+1},$

and let $\varphi(w)=\varphi^{\prime}(w)$ otherwise. Now
$\varphi(y_{i})^{-}<\varphi(y_{i+1})^{-}<\varphi(y_{i})^{+}<\varphi(y_{i+1})^{+}$
for all $i\in[k-1]$. Furthermore,
$\varphi(y_{1})^{-}<\varphi(x)^{-}<\varphi(y_{1})^{+}<\varphi(x)^{+}$ and
$\varphi(z)^{-}<\varphi(y_{k})^{-}<\varphi(z)^{+}<\varphi(y_{k})^{+}$.
Therefore $\varphi$ satisfies $x{\sf oi}y_{1},y_{1}{\sf
o}y_{2},\ldots,y_{k-1}{\sf o}y_{k},y_{k}{\sf oi}z$ and all the other
constraints in $\mathcal{I}$. Therefore every bad cycle is of the form stated
in the lemma.

Now suppose there is a cycle of the form stated in the lemma and assume, for
contradiction, that it is satisfiable; note that the cycle must contain at
least one ${\sf p}$-arc. If there is a consecutive run of a non-negative
number of forward ${\sf o}$-arcs, say $y_{1}{\sf o}y_{2},\ldots,y_{k-1}{\sf
o}y_{k}$ for some $k\geq 1$, then $y_{1}^{-}\leq y_{k}^{-}$ and $y_{1}^{+}\leq
y_{k}^{+}$. If there is a reverse ${\sf o}$-arc, say $x{\sf oi}y$, then
$x^{-}<y^{+}$. Therefore, if there is a consecutive run of ${\sf o}$-arcs, at
most one of which is a reverse arc, from the variable $x$ to the variable $y$,
then $x^{-}<y^{+}$. If there is a consecutive run of forward ${\sf p}$-arcs
from the variable $x$ to the variable $z$, say $x{\sf p}y_{1},y_{1}{\sf
p}y_{2},\ldots,y_{k-1}{\sf p}y_{k},y_{k}{\sf p}z$ for some $k\geq 0$, then
$x^{+}<y^{-}$. Therefore encoding $\mathcal{I}$ in the point algebra yields an
unsatisfiable instance, a contradiction. This completes the proof for this
case.

  4. 4.

By Lemma 6, we may assume that ${\sf r}_{1}={\sf s}$ and we may replace ${\sf
d}$ by ${\sf di}$ in the statement of the lemma. We first show that the cycles
described in the lemma are indeed bad. Clearly, a directed cycle of ${\sf
s}$-arcs is not satisfiable. Now suppose that the ${\sf r}_{2}$-arcs are all
directed in the same direction. We encode the instance $\mathcal{I}$ as an
instance $\mathcal{I}^{\prime}$ of the point algebra and we claim that
$\mathcal{I}^{\prime}$ is not satisfiable. Indeed, each $u{\sf s}v$ constraint
in $\mathcal{I}$ yields a $u^{-}=v^{-}$ constraint in $\mathcal{I}^{\prime}$.
If $u{\sf di}v$ or $u{\sf o}v$ is a constraint in $\mathcal{I}$, then
$u^{-}<v^{-}$ is a constraint in $\mathcal{I}^{\prime}$. If $u{\sf p}v$ is a
constraint in $\mathcal{I}$, then $u^{+}<v^{-}$ is a constraint in
$\mathcal{I}^{\prime}$; since $u^{-}<u^{+}$ is also a constraint in
$\mathcal{I}^{\prime}$, this implies that $(u^{-}<v^{-})$ must be satisfied by
any satisfying assignment for $\mathcal{I}^{\prime}$. We conclude that in each
case, if the cycle is as described in the lemma, then the instance
$\mathcal{I}^{\prime}$ is unsatisfiable.

Next, we show that if a cycle is not of the form written in the lemma, then it
is satisfiable. If ${\sf r}_{2}={\sf p}$, this means that there must be two
${\sf p}$-arcs in opposite directions, so the instance is satisfiable by Claim
8.1.

It remains to consider ${\sf r}_{2}\in\\{{\sf o},{\sf di}\\}$. Let
$\mathcal{I}^{\prime\prime}$ be the instance obtained from $\mathcal{I}$ by
replacing each $u{\sf s}v$ constraint by a $u\equiv v$ constraint. Observe
that a cycle containing an $\equiv$-edge is satisfiable if and only if the
cycle obtained by contracting this edge away is satisfiable. Now
$\mathcal{I}^{\prime\prime}$ is satisfiable by Case 2, as its primal graph
does not contain a cycle in which all ${\sf r}_{2}$ relations are in the same
direction. Let $\varphi^{\prime\prime}$ be a satisfying assignment for
$\mathcal{I}^{\prime\prime}$. Observe that we may assume all values taken by
this assignment are pairs of integers (if not, then multiply all values by a
common multiple of their divisors). Let $n$ be the number of variables in
$\mathcal{I}$. Let $u_{1}{\sf t}_{1}u_{2},u_{2}{\sf
t}_{2}u_{3},\ldots,u_{n-1}{\sf t}_{n-1}u_{n},u_{n}{\sf t}_{n}u_{1}$ be the
cycle that forms the instance $\mathcal{I}$ and assume without loss of
generality that ${\sf t}_{n}\in\\{{\sf r}_{2},{\sf r}_{2}\sf i\\}$ (where
${\sf r}_{2}\sf i={\sf oi}$ or ${\sf d}$ if ${\sf r}_{2}={\sf o}$ or ${\sf
di}$, respectively). We construct a satisfying assignment $\varphi$ for
$\mathcal{I}$ as follows. For all $v\in V(\mathcal{I})$, let
$\varphi^{-}(v)=\varphi^{\prime\prime-}(v)$. We let
$\varphi(u_{1})^{+}=\varphi^{\prime\prime}(u_{1})^{+}$. Next, for each
$i\in\\{1,\ldots,n-1\\}$ in turn, we let
$\varphi(u_{i+1})^{+}=\varphi^{\prime\prime}(u_{i+1})^{+}$ if ${\sf
t}_{i}\in\\{{\sf r}_{2},{\sf r}_{2}\sf i\\}$,
$\varphi(u_{i+1})^{+}=\varphi(u_{i})^{+}+\frac{1}{2n}$ if ${\sf t}_{i}={\sf
s}$ and $\varphi(u_{i+1})^{+}=\varphi(u_{i})^{+}-\frac{1}{2n}$ if ${\sf
t}_{i}={\sf si}$. This changes the value of the each $u^{+}$ variables by less
than $\frac{1}{2}$, but keeps all $u^{-}$ variables unchanged. Therefore all
$u^{-}<u^{+}$ relations remain satisfied, all ${\sf r}_{2}$ relations remain
satisfied and the $u^{-}=v^{-}$ parts of the $u{\sf s}v$ relations also remain
satisfied. By construction, the $u^{+}<v^{+}$ parts of the $u{\sf s}v$ also
become satisfied. Therefore $\varphi$ is a satisfying assignment for
$\mathcal{I}$.

∎

##  5 FPT Algorithms

We prove Lemmas 9 and 10 in this section. This amounts to proving that
MinCSP$(\Gamma)$ is in FPT for seven subsets $\Gamma\subseteq\cal A$ of
interval relations: these are $\Gamma=\\{{\sf m},{\sf p}\\}$ and
$\Gamma=\\{{\sf r}_{1},{\sf r}_{2},\equiv\\}$ for ${\sf r}_{1}\in\\{{\sf
s},{\sf f}\\}$ and ${\sf r}_{2}\in\\{{\sf p},{\sf d},{\sf o}\\}$. We begin in
Section 5.1 by presenting the algorithm for $\\{{\sf m},{\sf p}\\}$, which
works by first reducing the problem to MinCSP$(<,=)$ and then to Sub-DFAS. In
Section 5.2 we treat the remaining six cases by reducing all of them to a
fairly natural generalization of Directed Feedback Arc Set problem, and
showing that this problem is fixed-parameter tractable.

###  5.1 Algorithm for MinCSP$({\sf m},{\sf p})$

We show that MinCSP$({\sf m},{\sf p})$ is in FPT. The algorithm works by
reducing the problem to MinCSP$(<,=)$ and then to Subset Directed Feedback Arc
Set defined as follows.

Subset Directed Feedback Arc Set (Sub-DFAS)
Instance: A directed graph $G$, a subset of red arcs $R\subseteq A(G)$, and an
integer $k$. Parameter: $k$. Question: Is there a subset $Z\subseteq A(G)$ of
size at most $k$ such that $G-Z$ contains no cycles with at least one red arc?

We refer to arcs in $A(G)\setminus R$ as black.

######  Theorem 14 ([18]).

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

First, we show that MinCSP$(<,=)$, i.e. MinCSP over an infinite ordered domain
(say $\mathbb{Q}$) with binary relations ‘less-than’ $<$ and ‘equals’ $=$,
reduces to Sub-DFAS.

######  Lemma 15.

There is an algorithm that takes an instance $(\mathcal{I},k)$ of
${\textsc{MinCSP}(<,=)}$ as input and produces in polynomial time an instance
$(G,R,k)$ of Sub-DFAS such that $(\mathcal{I},k)$ is a yes-instance if and
only if $(G,R,k)$ is a yes-instance.

###### Proof.

Let $(\mathcal{I},k)$ be an instance of $\textsc{MinCSP}(<,=)$. Construct a
directed graph $G$ with the variables in $V(\mathcal{I})$ as vertices. If
$\mathcal{I}$ contains a constraint $x=y$, add black arcs $(x,y)$ and $(y,x)$
to $A(G)$. If $\mathcal{I}$ contains a constraint $x<y$, add a red arc $(x,y)$
to $A(G)$ and $R$. This completes the construction. The colours of the arcs
are added only to make the proof easier to read.

For an intuition, one can think of the black arcs in $G$ as $\leq$ relations,
and the red arcs as $<$ relations. Then two black arcs $(x,y)$ and $(y,x)$
enforce equality $x=y$. A directed cycle in $G$ consisting solely of black
arcs (i.e. $\leq$ relations) corresponds to a satisfiable subset of
constraints – indeed, we can assign the same value to all variables and
satisfy all these constrains. On the other hand, if a directed cycle contains
a red arc (i.e. $<$ relation), then it corresponds to an inconsistent instance
since it implies $x<y$ and $x\geq y$ for a pair of variables.

To formally prove correctness, we first assume $X$ to be a set of constraints
such that $\mathcal{I}-X$ is consistent. Create a set of arcs $Z$ as follows:
if $X$ contains the constraint $x=y$, then add one black arc $(x,y)$ to $Z$;
if $X$ contains the constraint $x<y$, then add the red arc $(x,y)$ to $Z$.
Clearly, $|X|=|Z|$. We claim that $Z$ intersects every cycle that contains an
arc from $S\setminus Z$. Assume to the contrary that $G-Z$ contains a cycle
with a red arc, i.e. a directed $(x,y)$-path $P$ and a red arc $(y,x)\in
S\setminus Z$. The constraints along $P$ imply $x\leq y$, while the red arc
$(y,x)$ corresponds to a constraint $x>y$, contradicting that $\mathcal{I}-X$
is satisfiable.

For the opposite direction, suppose that $Z^{\prime}$ is a set of arcs such
that $G-Z^{\prime}$ does not contain any cycle with at least one red arc.
Construct a set of constraints $X^{\prime}$ as follows: if $Z^{\prime}$
contains a black arc $(x,y)$, then add $x=y$ to $X^{\prime}$, and if
$Z^{\prime}$ contains a red arc $(x,y)$, then add $x<y$ to $X^{\prime}$. This
construction implies that $|X^{\prime}|\leq|Z^{\prime}|$. We show that
$\mathcal{I}-X^{\prime}$ is consistent by defining an explicit assignment
$\varphi:V(\mathcal{I})\rightarrow\mathbb{Q}$. To this end, construct a graph
$H$ from $G-Z^{\prime}$ by identifying every pair of vertices $u$ and $v$ that
are strongly connected by black arcs. We know that there is no cycle of black
arcs in $H$. Moreover, there is no cycle with a red arc because it would
correspond to a cycle with a red arc in $G-Z^{\prime}$. Hence, $H$ is acyclic.
Let $\varphi$ be a linear ordering of $H$, i.e. an assignment that satisfies
the following property: if we have $\varphi(v)>\varphi(u)$, then there is no
$(u,v)$-path in $H$. We claim that $\varphi$ satisfies
$\mathcal{I}-X^{\prime}$. If there is a constraint $x=y$ in
$\mathcal{I}-X^{\prime}$, then $G-Z^{\prime}$ contains two arcs $(x,y)$ and
$(y,x)$, making $x$ and $y$ strongly connected by black arcs. Then $x$ and $y$
are identified in $H$ and $\varphi(x)=\varphi(y)$. If $\mathcal{I}-X^{\prime}$
contains a constraint $x<y$, then $x$ and $y$ are not identified since there
is no $(y,x)$-path in $G-Z^{\prime}$. Moreover, arc $(x,y)$ is present in
$G-Z^{\prime}$ and $H$, and, since $\varphi$ is a linear ordering of $H$, we
have $\varphi(x)<\varphi(y)$, and the constraint $x<y$ is satisfied. This
concludes the proof. ∎

Now we are ready to prove that $\textsc{MinCSP}({\sf m},{\sf p})$ is in FPT.

###### Proof of Lemma 9.

Lemma 5 implies that we can replace a ${\sf p}$-constraint with an
implementation using two ${\sf m}$ constraints. This observation, together
with Lemma 4, implies that ${\textsc{MinCSP}({\sf m},{\sf p})}$ is in FPT if
$\textsc{MinCSP}({\sf m})$ is in FPT. We show how to reduce the latter problem
to ${\textsc{MinCSP}(<,=)}$.

Let $(\mathcal{I},k)$ be an instance of $\textsc{MinCSP}({\sf m})$. Construct
an instance $(\mathcal{I}^{\prime},k)$ of ${\textsc{MinCSP}(<,=)}$ by
introducing two variables $x^{-}$ and $x^{+}$ in $V(\mathcal{I}^{\prime})$ for
every $x\in V(\mathcal{I})$. Add crisp constraints $x^{-}<x^{+}$ to
$\mathcal{I}^{\prime}$ for all $x\in V(\mathcal{I})$, and soft constraints
$x^{+}=y^{-}$ to $\mathcal{I}^{\prime}$ for every constraint $x\\{{\sf m}\\}y$
in $\mathcal{I}$. This completes the reduction and it can clearly be performed
in polynomial time.

To prove correctness, we show that $\mathcal{I}$ and $\mathcal{I}^{\prime}$
have the same cost. To show that
$\operatorname{cost}(\mathcal{I})\leq\operatorname{cost}(\mathcal{I}^{\prime})$,
let $\varphi$ be an arbitrary assignment of non-empty intervals to the
variables in $V(\mathcal{I})$. We construct an assignment $\varphi^{\prime}$
to $\mathcal{I}^{\prime}$ with the same cost. In fact, one can view $\varphi$
as an assignment of rationals to the endpoints, i.e.
$\varphi^{\prime}:V(\mathcal{I}^{\prime})\to\mathbb{Q}$ such that
$\varphi(x)=[\varphi^{\prime}(x^{-}),\varphi^{\prime}(x^{+})]$. Clearly, we
have $\varphi(v^{-})<\varphi(v^{+})$ for all $v\in V(\mathcal{I})$ since the
intervals are non-empty. Furthermore, a constraint $x\\{{\sf m}\\}y$ holds if
and only if $\varphi(x^{+})=\varphi(y^{-})$. Hence, $\varphi$ and
$\varphi^{\prime}$ violate the same number of constraints in $\mathcal{I}$ and
$\mathcal{I}^{\prime}$, respectively.

To show that
$\operatorname{cost}(\mathcal{I}^{\prime})\leq\operatorname{cost}(\mathcal{I})$,
assume $\psi^{\prime}$ is an assignment of rational values to
$V(\mathcal{I}^{\prime})$ that satisfies all crisp constraints. Define an
interval assignment $\psi$ as $\psi(v)=[\psi(v^{-}),\psi(v^{+})]$ for all
$v\in V(\mathcal{I})$. The intervals are non-empty because
$\psi(v^{-})<\psi(v^{+})$ is enforced by the crisp constraints. Moreover,
$\psi^{\prime}$ satisfies $x^{+}=y^{-}$ if and only if $\psi$ satisfies
$x\\{{\sf m}\\}y$. Hence, $\psi$ and $\psi^{\prime}$ violate the same number
of constraints in $\mathcal{I}$ and $\mathcal{I}^{\prime}$, respectively. We
conclude that
$\operatorname{cost}(\mathcal{I})=\operatorname{cost}(\mathcal{I}^{\prime})$.
∎

###  5.2 Algorithm by Reduction to Bundled Cut

In this section we prove fixed-parameter tractability of $\textsc{MinCSP}({\sf
r}_{1},{\sf r}_{2},\equiv)$, where ${\sf r}_{1}\in\\{{\sf s},{\sf f}\\}$ and
${\sf r}_{2}\in\\{{\sf p},{\sf o},{\sf d}\\}$. Lemma 8.4 suggests that all six
fragments allow uniform treatment. Indeed, to check whether an instance of
$\textsc{CSP}({\sf r}_{1},{\sf r}_{2},\equiv)$ is consistent, one can identify
all variables constrained to be equal. This corresponds exactly to contracting
all edges in the graph $G_{\mathcal{I}}$. Then $\mathcal{I}$ becomes an
instance of $\textsc{CSP}({\sf r}_{1},{\sf r}_{2})$, and the criterion of
Lemma 8.4 applies. This observation allows us to formulate
$\textsc{MinCSP}({\sf r}_{1},{\sf r}_{2},\equiv)$ as a variant of feedback arc
set on mixed graphs.

######  Definition 16.

Consider a mixed graph $G$ with arcs of two types – short and long – and a
walk $W$ in $G$ from $u$ to $v$ that may ignore direction of the arcs. The
walk $W$ in $G$ is _undirected_ if it only contains edges. The walk $W$ is
_short_ if it contains a short arc but no long arcs. The walk $W$ is _long_ if
it contains a long arc. The walk $W$ is _directed_ if it is either short and
all short arcs are directed from $u$ to $v$ or if it is long and all long arcs
are directed from $u$ to $v$. If $W$ is short or long, but not directed, it is
_mixed_.

Note that short arcs on a directed long walk may be directed arbitrarily.

Mixed Feedback Arc Set with Short and Long Arcs (LS-MFAS)
Instance: A mixed graph $G$ with the arc set $A(G)$ partitioned into _short_
$A_{s}$ and _long_ $A_{\ell}$, and an integer $k$. Parameter: $k$. Question:
Is there a set $Z\subseteq E(G)\cup A(G)$ such that $G-Z$ contains neither
short directed cycles nor long directed cycles?

The main result of this section is the following theorem.

######  Theorem 17.

LS-MFAS can be solved in time $O^{*}(2^{O(k^{8}\log k)})$.

Lemma 10 positing that $\textsc{MinCSP}({\sf r}_{1},{\sf r}_{2},\equiv)$ is in
FPT whenever ${\sf r}_{1}\in\\{{\sf s},{\sf f}\\}$ and ${\sf r}_{2}\in\\{{\sf
p},{\sf o},{\sf d}\\}$ is an immediate consequence of Lemma 8.4 and Theorem
17.

It is informative to understand the structure of mixed graphs without bad
cycles in the sense of LS-MFAS. One way of characterizing LS-MFAS (with a
pronounced connection to interval constraints) is as a problem of placing
vertices of the input graph $G$ on the number line under certain distance
constraints represented by the edges and arcs. An edge $uv$ requires $u$ and
$v$ to be placed at the same point. An arc $(u,v)$ requires that $u$ is placed
before $v$. If the arc is long, then the distance from $u$ to $v$ should be
big (say, $2|V(G)|$ units of length), while if the arc is short, the distance
should be small (say, at most a unit of length). We make the intuition precise
in the following lemma.

######  Lemma 18.

Let $G$ be a mixed graph with long and short arcs. Then $G$ contains no
directed long cycles nor directed short cycles if and only if there exists a
pair of mappings $\sigma_{1},\sigma_{2}:V(G)\to\mathbb{N}$ such that

  1. 1.

for every $u,v\in V(G)$, $u$ and $v$ are connected by an undirected walk if
and only if $(\sigma_{1},\sigma_{2})(u)=(\sigma_{1},\sigma_{2})(v)$;

  2. 2.

for every $u,v\in V(G)$, there exists a short $(u,v)$-walk in $G$ if and only
if $\sigma_{1}(u)=\sigma_{1}(v)$;

  3. 3.

for every $u,v\in V(G)$, if there exists a directed short $(u,v)$-walk in $G$,
then $\sigma_{2}(u)<\sigma_{2}(v)$;

  4. 4.

for every $u,v\in V(G)$, if there exists a directed long $(u,v)$-walk in $G$,
then $\sigma_{1}(u)<\sigma_{1}(v)$.

###### Proof.

Forward direction. Consider a graph $G_{1}$ constructed from $G$ as follows:
we replace every short arc with an undirect edge, and then contract all
undirect edges. While performing the contraction, we do not delete long arcs,
even if they become loops or multiple arcs. In other words, the vertex set of
$G_{1}$ is the set of (weak) connected components of the subgraph of $G$
consisting of undirected edges and short arcs, and every long arc $(u,v)$ of
$G$ yields an arc in $G_{1}$ from the component containing $u$ to the
component containing $v$. Then, the assumption that $G$ has no directed long
cycles implies that $G_{1}$ is acyclic: any cycle $C_{1}$ in $G_{1}$ can be
lifted to a directed long cycle $C$ in $G$ by padding with contracted
undirected edges and short arcs. Fix a topological ordering of $G_{1}$ and
define $\sigma_{1}(v)$ for $v\in V(G)$ as the index of the image of $v$ in
$G_{1}$ in the said topological ordering. This gives the second and the fourth
property.

Now, consider a graph $G_{2}$ defined as the graph $G$ with first all long
arcs deleted and then all undirected edges contracted. (Similarly as for
$G_{1}$, we do not delete short arcs while doing the contractions, keeping all
arising loops and multiple arcs.) Note that the connected components of
$G_{2}$ are in one-to-one correspondence with the vertices of $G_{1}$.
Furthermore, similarly as in the case of $G_{1}$, the assumption that $G$ has
no directed short cycles implies that $G_{2}$ is acyclic. For every connected
component $C$ of $G_{2}$, fix a topological ordering of $C$ and for $v\in C$
define $\sigma_{2}(v)$ as the index of the image of $v$ in this topological
ordering. This gives the first and the third properties.

Backward direction. Let $\sigma_{1},\sigma_{2}$ be two mappings as in the
statement of the lemma. Assume first that $G$ contains a directed short cycle
$C$. By the second property, $\sigma_{1}$ is constant on the vertices of $C$.
By the third property, for every short arc $(u,v)$ on $C$ we have
$\sigma_{2}(u)<\sigma_{2}(v)$ while by the first property, for every
undirected edge $uv$ on $C$ we have $\sigma_{2}(u)=\sigma_{2}(v)$. This is a
contradiction with the fact that $C$ contains at least one short arc and no
long arcs.

Assume now that $G$ contains a directed long cycle $C$. By the second
property, for every undirected edge $uv$ or short arc $(u,v)$ on $C$, we have
$\sigma_{1}(u)=\sigma_{1}(v)$. By the fourth property, for every long arc
$(u,v)$ on $C$ we have $\sigma_{1}(u)<\sigma_{1}(v)$. This is a contradiction
with the fact that $C$ contains at least one long arc. ∎

Now we introduce the technical machinery used in our algorithm for LS-MFAS. We
start by iterative compression, a standard method in parameterized algorithms
(see e.g. Chapter 4 in [23]). The idea is to solve the problem starting from
an empty graph and iteratively build up the graph by add edges and arcs,
maintaining a solution of size $k$ in the process. We clearly have a solution
while the size of the graph is at most $k$. Now consider an iteration where we
have a graph $G$ together with a solution $Z$, and a new edge/arc $e$ is
added. Observe that $Z\cup\\{e\\}$ is a solution to $(V(G),E(G)\cup\\{e\\})$,
thus we may assume access to an approximate solution of size $k+1$ at each
iteration.

The problem resulting from iterative compression reduces to Bundled Cut with
pairwise linked deletable edges, defined in [39] and solved using the flow-
augmentation technique of [38]. To describe the problem, let $G$ be a directed
graph with two distinguished vertices $s,t\in V(G)$. Let $\mathcal{B}$ be a
family of pairwise disjoint subsets of $E(G)$, which we call _bundles_. The
edges of $\bigcup\mathcal{B}$ are called _soft_ and the edges of
$E(G)\setminus\bigcup\mathcal{B}$ are _crisp_. A set
$Z\subseteq\bigcup\mathcal{B}$ _violates_ a bundle $B\in\mathcal{B}$ if $Z\cap
B\neq\emptyset$ and _satisfies_ $B$ otherwise.

Bundled Cut
Instance: A directed graph $G$, two distinguished vertices $s,t\in V(G)$, a
family $\mathcal{B}$ of pairwise disjoint subsets of $E(G)$, and an integer
$k$. Parameter: $k$. Question: Is there an $st$-cut
$Z\subseteq\bigcup\mathcal{B}$ that violates at most $k$ bundles?

In general, Bundled Cut is W[1]-hard even if all bundles are of size $2$.
However, there is a special case of Bundled Cut that is tractable. Let
$(G,s,t,\mathcal{B},k)$ be a Bundled Cut instance. A soft arc $e$ is
_deletable_ if there is no crisp copy of $e$ in $G$. An instance
$(G,s,t,\mathcal{B},k)$ has _pairwise linked deletable arcs_ if for every
$B\in\mathcal{B}$ and every two deletable arcs $e_{1},e_{2}\in B$, there
exists in $G$ a path from an endpoint of one of the arcs $e_{1},e_{2}$ to an
endpoint of the second of those arcs that does not use any arcs of
$\mathcal{B}\setminus\\{B\\}$.

The assumption of pairwise linked deletable arcs makes Bundled Cut tractable.

######  Theorem 19 (Theorem 4.1 of [40]).

Bundled Cut instances with pairwise linked deletable arcs can be solved in
time $O^{*}(2^{O(k^{4}d^{4}\log(kd))})$ where $d$ is the maximum number of
deletable arcs in a single bundle.

Armed with Lemma 18 and Theorem 19, we are ready to prove the main result.

###### Proof of Theorem 17.

Let $(G,A_{s},A_{\ell},k)$ be an instance of LS-MFAS. By iterative
compression, we can assume that we have access to a set $X\subseteq E(G)\cup
A(G)$ of size at most $k+1$ that intersects all bad cycles. Subdivide every
edge and arc in $X$, i.e. for every edge $uv\in X$ (arc $(u,v)\in X$,
respectively), replace it by edges $uy_{uv}$ and $y_{uv}v$ (arcs $(u,y_{uv})$
and $(y_{uv},v)$, respectively), where $y_{uv}$ is a fresh variable. Let
$Y=\\{y_{uv}:uv\in X\text{ or }(u,v)\in X\\}$. Note that $Y\subseteq V(G)$
intersects all bad cycles in $G$. Moreover, the resulting graph has a set of
$k$ edges intersecting all bad cycles if and only if the original graph has
one. We will refer to the vertices of $Y$ as _terminals_.

Fix a hypothetical solution $Z\subseteq A(G)\cup E(G)$. Guess which pairs of
terminals are connected by undirected paths in $G-Z$ and identify them. Define
_ordering_ $\sigma:Y\to\mathbb{N}\times\mathbb{N}$ that maps terminals to

$\\{(1,1),\dots,(1,q_{1}),\cdots,(i,1),\dots,(i,q_{i}),\cdots,(p,1),\dots,(p,q_{p})\\}$

such that the following hold. For every pair of terminals $y,y^{\prime}\in Y$,
let $\sigma(y)=(i,j)$ and $\sigma(y^{\prime})=(i^{\prime},j^{\prime})$.

  * •

If $y$ and $y^{\prime}$ are connected by a short path in $G-Z$, then
$i=i^{\prime}$.

  * •

If $y$ reaches $y^{\prime}$ by a directed short path in $G-Z$, then
$j<j^{\prime}$.

  * •

If $y$ reaches $y^{\prime}$ by a directed long path in $G-Z$, then
$i<i^{\prime}$.

Note that $\sigma$ exists by Lemma 18. If an ordering satisfies the conditions
above, we say that it is _compatible with_ $G-Z$. In the sequel we write
$(i,j)<(i^{\prime},j^{\prime})$ to denote that $(i,j)$ lexicographically
precedes $(i^{\prime},j^{\prime})$, i.e. either $i=i^{\prime}$ and
$j<j^{\prime}$ or $i<i^{\prime}$.

$r$$s$$t$$1,1$$1,2$$2,1$$\sigma$$\sigma$$\sigma$$(1,1)$$(2,1)$$(2,2)$$(2,3)$$(2,4)$$(2,5)$$(3,1)$$(4,1)$$(4,2)$$(4,3)$$(5,1)$

$x_{1,1}$$x_{2,1}$$x_{2,2}$$x_{2,3}$$x_{2,4}$$x_{2,5}$$x_{3,1}$$x_{4,1}$$x_{4,2}$$x_{4,3}$$x_{5,1}$$x$$y_{1,1}$$y_{2,1}$$y_{2,2}$$y_{2,3}$$y_{2,4}$$y_{2,5}$$y_{3,1}$$y_{4,1}$$y_{4,2}$$y_{4,3}$$y_{5,1}$$y$short

$x_{1,1}$$x_{2,1}$$x_{2,2}$$x_{2,3}$$x_{2,4}$$x_{2,5}$$x_{3,1}$$x_{4,1}$$x_{4,2}$$x_{4,3}$$x_{5,1}$$x$$y_{1,1}$$y_{2,1}$$y_{2,2}$$y_{2,3}$$y_{2,4}$$y_{2,5}$$y_{3,1}$$y_{4,1}$$y_{4,2}$$y_{4,3}$$y_{5,1}$$y$long

Figure 3: An example with three terminals $r,s,t$ where $\sigma(r)=(1,1)$, $\sigma(s)=(1,2)$, $\sigma(t)=(2,1)$. |  $i$ odd |  $i$ even, $j$ odd |  $i$ even, $j$ even
---|---|---|---
Edge $uv$ | $(i,j)\to(i,j)$ | $(i,j)\to(i,j)$ | $(i,j)\to(i,j)$
$(i,j)\leftarrow(i,j)$ | $(i,j)\leftarrow(i,j)$ | $(i,j)\leftarrow(i,j)$
Short $(u,v)$ | $(i,j)\to(i,j)$ | $(i,j)\to(i,j)$ | $(i,j)\to(i,j+1)$
$(i,1)\leftarrow(i,j)$ | $(i,1)\leftarrow(i,j)$ | $(i,1)\leftarrow(i,j)$
Long $(u,v)$ | $(i,1)\to(i,1)$ | $(i,j)\to(i+1,1)$ | $(i,j)\to(i+1,1)$
Table 3: Correspondence between edges, short arcs and long arcs of the LS-MFAS
instance and the arcs introduced in the reduction to Bundled Cut in Theorem
17.

For the algorithm, proceed by guessing an ordering $\sigma$, creating
$2^{O(k\log k)}$ branches in total. For each $\sigma$, create an instance
$(H:=H(G,\sigma),\mathcal{B}:=\mathcal{B}(G,\sigma),k)$ of Bundled Cut as
follows. Introduce two distinguished vertices $s$ and $t$ in $H$. For every
vertex $v\in V(G)$, create vertices $v^{i}_{1}$ in $H$ for all odd
$i\in[2p+1]$ and vertices $v^{i}_{j}$ in $H$ for all even $i\in[2p+1]$ and all
$j\in[2q_{i}+1]$. Connect vertices created above by _downward_ arcs
$(v^{i}_{j},v^{i^{\prime}}_{j^{\prime}})$ for all
$(i,j)>(i^{\prime},j^{\prime})$. For every terminal $y$, let
$\sigma(y)=(i,j)$, and add arcs $(s,y^{2i}_{2j})$ and $(y^{2i}_{2j+1},t)$ in
$H$. Using the rules below, create a bundle $B_{e}$ in $\mathcal{B}$ for every
$e\in E(G)\cup A(G)$, add the newly created arcs to $H$.

  * •

For an edge $e=uv$, let $B_{e}$ consist of arcs $(u^{i}_{j},v^{i}_{j})$ and
$(v^{i}_{j},u^{i}_{j})$ for all $(i,j)$.

  * •

For short arcs $e=(u,v)$, let $B_{e}$ consist of arcs $(u^{i}_{j},v^{i}_{j})$
for all $i,j$ such that $i$ or $j$ is odd, arcs $(u^{i}_{j},v^{i}_{j+1})$ for
all even $i,j$, and arcs $(v^{i}_{j},u^{i}_{1})$ for all $i,j$.

  * •

For long arcs $e=(u,v)$, let $B_{e}$ consist of arcs $(u^{i}_{1},v^{i}_{1})$
for all odd $i$, and arcs arcs $(u^{i}_{j},v^{i+1}_{1})$ for all even $i$ and
all $j$.

This completes the construction. Bundle construction rules are summarized in
Table 3, and Figure 3 contains an illustrated example.

Observe that the downward arcs ensure that $(H,\mathcal{B},k)$ has the
pairwise-linked deletable arc property. Moreover, the bundle size is $O(k)$,
so we can solve $(H,\mathcal{B},k)$ in $O^{*}(2^{O(k^{8}\log{k})})$ time. It
remains to show that the reduction is correct.

Forward direction. Suppose $Z$ is a solution to $(G,A_{s},A_{\ell},k)$, and
$\sigma$ is an ordering of terminals $Y$ compatible with $G-Z$. Consider the
instance $(H:=H(G,\sigma),\mathcal{B}:=\mathcal{B}(G,\sigma),k)$. Let
$Z^{\prime}=\bigcup_{e\in Z}B_{e}$. Clearly, $Z^{\prime}$ intersects at most
$|Z|\leq k$ bundles. We claim that $Z^{\prime}$ is an $(s,t)$-cut in $H$.

Suppose for the sake of contradiction that there is an $(s,t)$-path $P$ in
$H-Z^{\prime}$. By construction, the out-neighbour of $s$ on $P$ is
$x^{2i}_{2j}$, and the in-neighbour of $t$ is
$y^{2i^{\prime}}_{2j^{\prime}+1}$, where $x$ and $y$ are terminals such that
$\sigma(x)=(i,j)$ and $\sigma(y)=(i^{\prime},j^{\prime})$. Let $W_{P}$ be the
$(x,y)$-walk in $G-Z$ formed by the arcs $\\{e:P\cap B_{e}\neq\emptyset\\}$
traversed in the same order as $P$ does. We consider two cases, and in each
case deduce that either $\sigma$ is incompatible with $G-Z$, or that $G-Z$
contains a short or a directed long cycle.

Suppose $i=i^{\prime}$. If $W_{P}$ contains a long arc, then, by construction
of $H$, all long arcs are in the same direction. Since $G-Z$ has no directed
long cycles, $x$ reaches $y$ by a directed long path. However, we have
$i\nless i^{\prime}$, which implies that $\sigma$ is incompatible with $G-Z$.
Now assume $W_{P}$ has no long arcs. Then $W_{P}$ is a directed short walk:
indeed, if $W_{P}$ uses a short arc against its direction, then $P$ contains a
vertex with lower index $1$, and the lower index of all subsequent vertices is
also $1$ by construction of $H$; however, $P$ reaches $y^{2i}_{2j^{\prime}+1}$
and $2j^{\prime}+1>1$. If $x=y$, then $W_{P}$ is a closed directed short walk,
and it contains a directed short cycle. If $x\neq y$, then $x$ reaches $y$ in
$G-Z$ by a directed short walk, hence $j<j^{\prime}$ by the definition of
$\sigma$. However, indices of the vertices on the path $P$ cannot exceed
$(2i,2j+1)$ by construction of $H$, hence
$(2i^{\prime},2j^{\prime}+1)\leq(2i,2j+1)$ and $j^{\prime}\leq j$.

Suppose $i\neq i^{\prime}$. By construction of $H$, since $x^{2i}_{2j}$
appears on $P$, the index of every other variable on $P$ is at most
$(2i+1,1)$. Hence, $(2i+1,1)\geq(2i^{\prime},2j^{\prime}+1)$ and $i\geq
i^{\prime}$. Together with $i\neq i^{\prime}$, this implies $i>i^{\prime}$.
Clearly, $x\neq y$ in this case, and the walk $W_{P}$ contains a long arc. By
construction of $H$, all long arcs on $W_{P}$ are in the same direction, i.e.
from $x$ to $y$. However, this implies that $\sigma$ is incompatible with
$G-Z$ since there is a directed long $(x,y)$-path in this graph,
$\sigma(x)=(i,j)$, $\sigma(y)=(i^{\prime},j^{\prime})$, but $i>i^{\prime}$.

Backward direction. Now suppose $W$ is a solution to
$(H:=H(G,\sigma),\mathcal{B}:=\mathcal{B}(G,\sigma),k)$ for some ordering
$\sigma$. Define $W^{\prime}\subseteq E(G)\cup A(G)$ as the set of all edges
and arcs $e$ such that $B_{e}\cap W\neq\emptyset$. We claim that $W^{\prime}$
is a solution to $(G,A_{s},A_{\ell},k)$. Clearly, $|W^{\prime}|\leq|W|\leq k$
since $W$ intersects at most $k$ bundles in $\mathcal{B}$. Now suppose
$G-W^{\prime}$ contains a bad cycle $C$. Observe that $C$ contains at least
one terminal. We let $x$ and $y$ be two (not necessarily distinct) terminals
on $C$. We have two cases to consider, depending on whether $C$ is long or
short. In each case, we deduce that $H-W$ contains an $(s,t)$-path.

In case $C$ is directed short, assume by symmetry that $C$ consists of a
directed short $(x,y)$-path and a $(y,x)$-path that is either undirected or
directed short. Let $\sigma(x)=(i,j)$ and $\sigma(y)=(i^{\prime},j^{\prime})$.
Since $x$ reaches $y$ by a directed short path, $H-W$ contains a path

$s\to x_{2i,2j}\to\dots\to y_{2i,2j+1}.$

If $y_{2i,2j+1}$ reaches $t$ in $H-W$, then we are done. If not, then $x\neq
y$. Since $y$ reaches $x$ by either an undirected or a directed short path in
$G-W^{\prime}$, we have a path

$s\to\dots\to y_{2i,2j+1}\to\dots\to x_{2i,2j+1}\to t$

in $H-W$.

In case $C$ is directed long, assume by symmetry that $C$ consists of a
directed long $(x,y)$-path and a $(y,x)$-path that is either short or directed
long. Let $\sigma(x)=(i,j)$ and $\sigma(y)=(i^{\prime},j^{\prime})$. Since
$G-W^{\prime}$ contains a directed long $(x,y)$-path, $H-W$ contains a path

$s\to x_{2i,2j}\to\dots\to y_{2i+1,1}.$

If $y_{2i+1,1}$ reaches $t$, then we are done. Otherwise, $x\neq y$. Since $y$
reaches $x$ in $G-W^{\prime}$ without using long arcs against their direction,
$H-W$ contains a path

$s\to\dots\to y_{2i+1,1}\to\dots\to
x_{a,b}\xrightarrow{\text{down}}x_{2i,2j+1}\to t$

where $(a,b)\geq(2i+1,1)>(2i,2j+1)$. ∎

##  6 W[1]-hard Problems

Here, we show Lemmas 11 and 12. Our W[1]-hardness results for various
MinCSP$(\Gamma)$ problems are based on reductions from graph problems. These
graph problems fall into two categories: paired and simultaneous cut problems.
In paired cut problems, the input consists of two graphs together with a
pairing of their edges, and the goal is to compute cuts in both graphs using
at most $k$ pairs. While the problems on individual graphs are solvable in
polynomial time, the pairing requirement leads to W[1]-hardness. In
simultaneous cut problems, the two input graphs share some arcs/edges that can
be deleted simultaneously at unit cost, and the goal is to compute a set of
$k$ arcs/edges that is a cut in both graphs. As for the paired problems,
computing cuts for individual graphs is feasible in polynomial time. However,
the possibility of choosing common arcs/edges while deleting them at a unit
cost correlates the choices in one graph and the other, and leads to
W[1]-hardness. The hardness results for paired and simultaneous cut problems
can be found in Sections 6.1 and 6.2, respectively. We use paired cut problems
for proving hardness of $\textsc{MinCSP}({\sf m},\equiv)$ and
$\textsc{MinCSP}({\sf m},{\sf s})$ in Section 6.3, and we use simultaneous cut
problems for proving hardness of $\textsc{MinCSP}({\sf d},{\sf p})$,
$\textsc{MinCSP}({\sf d},{\sf o})$, and $\textsc{MinCSP}({\sf p},{\sf o})$, in
Section 6.4. Our reductions will make use of the following well-known problem,
whose W[1]-hardness follows by a simple reduction from Multicolored Clique
(see e.g. Exercise 13.3 in [23]).

Multicolored Biclique (MC-BiClique)
Instance: An undirected graph $G$ with a partition
$V(G)=A_{1}\uplus\ldots\uplus A_{k}\uplus B_{1}\uplus\ldots\uplus B_{k}$,
where $|A_{i}|=|B_{i}|=n$ for each $i\in[k]$ and both $\uplus_{i\in[k]}A_{i}$
and $\uplus_{i\in[k]}B_{i}$ form independent sets in $G$. Parameter: $k$.
Question: Does $G$ contain $K_{k,k}$ as a subgraph, a.k.a. a _multicolored
biclique_?

######  Proposition 20.

MC-BiClique is W[1]-hard.

###  6.1 Paired Problems

We consider the problems Paired Cut and Paired Cut Feedback Arc Set (PCFAS) in
the sequel.

Paired Cut
Instance: Undirected graphs $G_{1}$ and $G_{2}$, vertices $s_{i},t_{i}\in
V(G_{i})$, a set of disjoint edge pairs $\mathcal{B}\subseteq E(G_{1})\times
E(G_{2})$, and an integer $k$. Parameter: $k$. Question: Is there a subset
$X\subseteq\mathcal{B}$ such that $|X|\leq k$ and
$X_{i}=\\{e_{i}\;|\;\\{e_{1},e_{2}\\}\in X\\}$ is an $\\{s_{i},t_{i}\\}$-cut
in $G_{i}$ for both $i\in\\{1,2\\}$?

Paired Cut FAS (PCFAS)
Instance: An undirected graph $G_{1}$ and a digraph $G_{2}$, vertices $s,t\in
V(G_{1})$, a set of disjoint edge pairs $\mathcal{B}\subseteq E(G_{1})\times
E(G_{2})$, and an integer $k$. Parameter: $k$. Question: Is there a subset
$X\subseteq\mathcal{B}$ such that $|X|\leq k$, $X_{1}$ is an $\\{s,t\\}$-cut
in $G_{1}$ and $G_{2}-X_{2}$ is acyclic, where
$X_{i}=\\{e_{i}\;|\;\\{e_{1},e_{2}\\}\in X\\}$ for both $i\in\\{1,2\\}$?

We show W[1]-hardness of both problems. Since both reductions are from MC-
BiClique and quite similar, we start to decribe the common part of both
reductions. Let $I=(G,A_{1},\dotsc,A_{k},B_{1},\dotsc,B_{k},k)$ be an instance
of MC-BiClique. We define two directed graphs $G_{A}$ and $G_{B}$ as follows.
$G_{A}$ contains the vertices $s_{A}$ and $t_{A}$. Moreover, for every
$i\in[k]$, $G_{A}$ contains the vertices in
$P_{i}^{A}=\\{v_{i,1},\dotsc,v_{i,n-1}\\}$. For convinence, we use that
$v_{i,0}=s_{A}$ and $v_{i,n}=t_{A}$ for every $i\in[k]$. Moreover, for every
vertex $a_{i,j}$ and every $i^{\prime}\in[k]$, $G_{A}$ contains the directed
path $P^{A}_{i,j,i^{\prime}}$ from $v_{i,j-1}$ to $v_{i,j}$ that has one edge
(using fresh auxiliary vertices) for every edge between $a_{i,j}$ and a vertex
in $B_{i^{\prime}}$. Therefore, we can assume in the following that there is a
bijection between the edges of $P_{i,j,i^{\prime}}^{A}$ and the edges between
$a_{i,j}$ and a vertex in $B_{i^{\prime}}$. This concludes the description of
$G_{A}$. $G_{B}$ is defined very similarily to $G_{A}$ with the roles of the
sets $A_{1},\dotsc,A_{k}$ and $B_{1},\dotsc,B_{k}$ being reversed. In
particular, $G_{B}$ contains the vertices $s_{B}$ and $t_{B}$ and for every
$i\in[k]$, $G_{B}$ contains the vertices in
$P_{i}^{B}=\\{u_{i,1},\dotsc,u_{i,n-1}\\}$. For convinence, we will assume
that $u_{i,0}=s_{B}$ and $u_{i,n}=t_{B}$ for every $i\in[k]$. Moreover, for
every vertex $b_{i,j}$ and every $i^{\prime}\in[k]$, $G_{B}$ contains the
directed path $P_{i,j,i^{\prime}}^{B}$ from $u_{i,j-1}$ to $u_{i,j}$ that has
one edge (using novel auxiliary vertices) for every edge between $b_{i,j}$ and
a vertex in $A_{i^{\prime}}$. Therefore, we can assume in the following that
there is a bijection between the edges of $P_{i,j,i^{\prime}}^{B}$ and the
edges between $b_{i,j}$ and a vertex in $A_{i^{\prime}}$.

Finally, define a set $\mathcal{B}\subseteq E(G_{A})\times E(G_{B})$ of
bundles as follows. For every edge
$e=\\{a_{i,j},b_{i^{\prime},j^{\prime}}\\}\in E(G)$, $\mathcal{B}$ contains
the pair $(e^{A},e^{B})$, where $e^{A}$ is the edge corresponding to $e$ on
the path $P_{i,j,i^{\prime}}^{A}$ and $e^{B}$ is the edge corresponding to $e$
on the path $P_{i^{\prime},j^{\prime},i}^{B}$. This concludes the construction
and the following lemma shows its main property.

######  Lemma 21.

$I=(G,A_{1},\dotsc,A_{k},B_{1},\dotsc,B_{k},k)$ is a yes-instance of MC-
BiClique if and only if there is a set $X\subseteq\mathcal{B}$ with
$|X|=k^{2}$ and $X_{A}=\\{e\mid(e,e^{\prime})\in X\\}$
($X_{B}=\\{e^{\prime}\mid(e,e^{\prime})\in X\\}$) is an $(s_{A},t_{A})$-cut
($(s_{B},t_{B})$-cut) in $G_{A}$ ($G_{B}$).

###### Proof.

Forward direction. Let $K$ be a biclique in $G$ with vertices

$a_{1,j_{1}},\dotsc,a_{k,j_{k}},b_{1,\ell_{1}},\dotsc,b_{k,\ell_{k}}.$

Let $X\subseteq\mathcal{B}$ be the set of bundles containing the pair
$(e^{A},e^{B})$ for every edge $e$ of $K$. Then, $|X|=k^{2}$ and we claim that
$X_{A}$ ($X_{B}$) is an $(s_{A},t_{A})$-cut ($(s_{B},t_{B})$-cut) in $G_{A}$
($G_{B}$). This holds because:

  * •

For every $a_{i,j_{i}}$ and $i^{\prime}\in[k]$, $X_{A}$ contains an edge from
the path $P_{i,j_{i},i^{\prime}}^{A}$ and therefore there is no path from
$a_{i,j_{i}-1}$ to $a_{i,j_{i}}$ in $G_{A}-X_{A}$.

  * •

For every $b_{i,\ell_{i}}$ and $i^{\prime}\in[k]$, $X_{B}$ contains an edge
from the path $P_{i,\ell_{i},i^{\prime}}^{B}$ and therefore there is no path
from $b_{i,\ell_{i}-1}$ to $b_{i,\ell_{i}}$ in $G_{B}-X_{B}$.

Backward direction. Let $X\subseteq\mathcal{B}$ with $|X|=k^{2}$ such that
$X_{A}=\\{e\mid(e,e^{\prime})\in X\\}$
($X_{B}=\\{e^{\prime}\mid(e,e^{\prime})\in X\\}$) is an $(s,t)$-cut in $G_{A}$
($G_{B}$). Then, for every $i\in[k]$ there must exist a $j\in[k]$ such that
for every $i^{\prime}\in[k]$, $X_{A}$ contains an edge from the path
$P_{i,j,i^{\prime}}^{A}$. Similarily, for every $i\in[k]$ there must exist a
$j\in[k]$ such that for every $i^{\prime}\in[k]$, $X_{B}$ contains an edge
from the path $P_{i,j,i^{\prime}}^{B}$. Because $|X|=k^{2}$, $X_{A}$ and
$X_{B}$ cannot contain any other edges. Therefore, for every $i\in[k]$ there
is a unique vertex $a_{i,j_{i}}$ in $A_{i}$ such that all paths between
$a_{i,j_{i}-1}$ and $a_{i,j_{i}}$ are cut in $G_{A}-X_{A}$. Similarily, for
every $i\in[k]$ there is a unique vertex $b_{i,\ell_{i}}$ in $B_{i^{\prime}}$
such that all paths between $b_{i,\ell_{i}-1}$ and $b_{i,\ell_{i}}$ are cut in
$G_{B}-X_{B}$. But due to the definition of $\mathcal{B}$, this is only
possible if there is an edge in $G$ between every vertex $a_{i,j_{i}}$ and
every vertex $b_{i,\ell_{i}}$ so
$\\{a_{1,j_{1}},\dotsc,a_{k,j_{k}},b_{1,j_{1}},\dotsc,b_{k,j_{k}}\\}$ is
indeed a biclique in $G$. ∎

The lemma above makes it relatively straightforward to show W[1]-hardness for
Paired Cut and PCFAS.

######  Lemma 22.

Paired Cut is W[1]-hard.

###### Proof.

Let $I=(G,A_{1},\dotsc,A_{k},B_{1},\dotsc,B_{k},k)$ be an instance of MC-
BiClique and let $G_{A}$, $G_{B}$, and $\mathcal{B}$ be the corresponding
gadgets defined in Lemma 21. First note that Lemma 21 still holds if we
consider the underlying undirected graphs $G_{A}^{\prime}$ and
$G_{B}^{\prime}$ of $G_{A}$ and $G_{B}$, respectively. Therefore, using the
same lemma, we obtain that $I$ is equivalent to the instance
$(G_{A}^{\prime},G_{B}^{\prime},s_{A},t_{A},s_{B},t_{B},\mathcal{B},k)$ of
Paired Cut, as required. ∎

######  Lemma 23.

PCFAS is W[1]-hard.

###### Proof.

Let $I=(G,A_{1},\dotsc,A_{k},B_{1},\dotsc,B_{k},k)$ be an instance of MC-
BiClique and let $G_{A}$, $G_{B}$, and $\mathcal{B}$ be the corresponding
gadgets defined in Lemma 21. First note that Lemma 21 still holds if we
consider the underlying undirected graphs $G_{A}^{\prime}$ of $G_{A}$. Let
$G_{B}^{\prime}$ be the directed graph obtained from $G_{B}$ after adding the
edge from $t_{A}$ to $s_{A}$. Because $G_{B}$ is acyclic, it holds that a set
$X_{B}$ of edges of $G_{B}$ is an $(s_{B},t_{B})$-cut if and only if $X_{B}$
is a FAS for $G_{B}^{\prime}$. Therefore, using Lemma 21, we obtain that $I$
is equivalent to the instance
$(G_{A},G_{B}^{\prime},s_{A},t_{A},\mathcal{B},k)$ of PCFAS, as required. ∎

###  6.2 Simultaneous Problems

In this section we prove W[1]-hardness of several simultaneous cut problems.
Our basis is the following problem.

Simultaneous Separator (Sim-Separator)
Instance: Two directed graphs $D_{1}$ and $D_{2}$ with $V=V(D_{1})=V(D_{2})$,
vertices $s,t\in V$, and an integer $k$. Parameter: $k$. Question: Is there a
subset $X\subseteq V\setminus\\{s,t\\}$ of size at most $k$ such that neither
$D_{1}-X$ nor $D_{2}-X$ contain a path from $s$ to $t$?

We begin by proving that this problem is W[1]-hard in Theorem 24. We will then
prove that simultaneous variants of Directed st-Cut and Directed Feedback Arc
Set are W[1]-hard via reductions from Sim-Separator; these results can be
found in Theorems 25 and 26, respectively. It will be convenient to use the
term $st$-separator when working with directed graphs: given a directed graph
$G=(V,E)$ and two vertices $s,t\in V$, we say that $X\subseteq
V\setminus\\{s,t\\}$ is an $st$-separator if the graph $G-X$ contains no
directed path from $s$ to $t$ and no directed path from $t$ to $s$.

######  Theorem 24.

Sim-Separator is W[1]-hard even if both input digraphs are acyclic.

###### Proof.

Given an instance $(G,k)$ of MC-BiClique we construct an instance
$(D_{1},D_{2},\texttt{s},\texttt{t},k^{\prime})$ of Sim-Separator in
polynomial time such that $k^{\prime}=O(k^{2})$ and $(G,k)$ is a Yes-instance
of MC-BiClique if and only if $(D_{1},D_{2},\texttt{s},\texttt{t},k^{\prime})$
is a Yes-instance of Sim-Separator. Moreover, the digraphs $D_{1}$ and $D_{2}$
are both acyclic.

#### Construction.

Recall that $V(G)=A_{1}\uplus\cdots\uplus A_{k}\uplus B_{1}\uplus\cdots\uplus
B_{k}$. Let $A_{i}=\\{a^{i}_{1},\ldots,a^{i}_{n}\\}$ and
$B_{i}=\\{b^{i}_{1},\ldots,b^{i}_{n}\\}$. The digraphs $D_{1},D_{2}$ (as per
the problem definition) should be defined on the same vertex set. For
convenience we define the vertex set of $D_{1}$ and $D_{2}$ separately, state
which of the vertices are common to both, and for the others we provide a one-
to-one-map between those in $D_{1}$ and those in $D_{2}$. The vertex set of
the digraphs $D_{1},D_{2}$ are described in the following five steps.

(V-1) Corresponding to each $A_{i}$, $i\in[k]$, there are two vertex sets in
$D_{1}$ and $D_{2}$: $\textsf{\bf
A}^{i}=\\{\alpha^{i}_{1},\ldots,\alpha^{i}_{n}\\}$ and a set of dummy vertices

$\textsf{\bf
D}^{i,A}=\\{d^{i,A}_{1,\texttt{in}},d^{i,A}_{1,\texttt{out}},\ldots,d^{i,A}_{n,\texttt{in}},d^{i,A}_{n,\texttt{out}}\\}.$

(The vertex sets $\textsf{\bf A}^{i}$ and $\textsf{\bf D}^{i,A}$ are common in
$D_{1}$ and $D_{2}$.)

(V-2) Corresponding to each $B_{i}$, $i\in[k]$, there are two vertex sets in
$D_{1}$ and $D_{2}$: $\textsf{\bf
B}^{i}=\\{\beta^{i}_{1},\ldots,\beta^{i}_{n}\\}$ and a set of dummy vertices

$\textsf{\bf
D}^{i,B}=\\{d^{i,B}_{1,\texttt{in}},d^{i,B}_{1,\texttt{out}},\ldots,d^{i,B}_{n,\texttt{in}},d^{i,B}_{n,\texttt{out}}\\}.$

(The vertex sets $\textsf{\bf B}^{i}$ and $\textsf{\bf D}^{i,B}$ are common in
$D_{1}$ and $D_{2}$.)

(V-3) For each ordered pair $i,j\in[k]\times[k]$, there is a set of dummy
vertices in $D_{1}$ and $D_{2}$: $\textsf{\bf
D}^{i,j}=\\{d^{i,j}_{1,\texttt{in}},d^{i,j}_{1,\texttt{out}},\ldots,\allowbreak
d^{i,j}_{n,\texttt{in}},\allowbreak d^{i,j}_{n,\texttt{out}}\\}$. (The sets
$\textsf{\bf D}^{i,j}$ are common in $D_{1}$ and $D_{2}$.)

(V-4) For each ordered pair $i,j\in[k]\times[k]$, there is a set of vertices
$\textsf{\bf P}^{i,j}_{A}=\\{p^{i,j}_{1,1},\ldots,p^{i,j}_{1,n},\allowbreak
p^{i,j}_{2,1},\ldots p^{i,j}_{2,n},\ldots,\allowbreak
p^{i,j}_{n,1},\ldots,p^{i,j}_{n,n}\\}$ in $D_{1}$ and a set of vertices
$\textsf{\bf
P}^{i,j}_{B}=\\{\hat{p}^{i,j}_{1,1},\ldots,\hat{p}^{i,j}_{1,n},\allowbreak\hat{p}^{i,j}_{2,1},\ldots\hat{p}^{i,j}_{2,n},\ldots,\allowbreak\hat{p}^{i,j}_{n,1},\ldots,\hat{p}^{i,j}_{n,n}\\}$
in $D_{2}$. Since in the construction we desire the vertex set of $D_{1}$ to
be the same as the vertex set of $D_{2}$, we map the vertices of $\textsf{\bf
P}^{i,j}_{A}$ with $\textsf{\bf P}^{i,j}_{B}$ such that the mapped vertices
corresponds to the same vertex (which is just called by different names in the
two digraphs). The desired map, maps the vertex $p^{i,j}_{q,r}$ to the vertex
$\hat{p}^{i,j}_{r,q}$.

(V-5) In addition to the above vertices, there is a source vertex s and a sink
vertex t in both digraphs $D_{1}$ and $D_{2}$.

The arc set of $D_{1}$ is constructed as follows. See Figure 4 for an
illustration.

(A1-1) For each $i\in[k]$, there is a directed path on the vertex set
$\textsf{\bf A}^{i}\cup\textsf{\bf D}^{i,A}$ defined as
$\rho^{A}_{i}=(d^{i,A}_{1,\texttt{in}},\alpha^{i}_{1},d^{i,A}_{1,\texttt{out}},\allowbreak
d^{i,A}_{2,\texttt{in}},\alpha^{i}_{2},d^{i,A}_{2,\texttt{out}},\allowbreak\ldots,\allowbreak
d^{i,A}_{n,\texttt{in}},\allowbreak\alpha^{i}_{n},\allowbreak
d^{i,A}_{n,\texttt{out}})$ of length $3n$ (here length is the number of
vertices on the path).

(A1-2) For each ordered pair $i,j\in[k]\times[k]$, there is a directed path
$\rho_{i,j}$ (of length $n^{2}+2n$) on the vertex set $\textsf{\bf
P}^{i,j}_{A}\cup\textsf{\bf D}^{i,j}$ defined as

$(d^{i,j}_{1,\texttt{in}},p^{i,j}_{1,1},\allowbreak\ldots,\allowbreak
p^{i,j}_{1,n},d^{i,j}_{1,\texttt{out}}\allowbreak
d^{i,j}_{2,\texttt{in}},p^{i,j}_{2,1},\ldots
p^{i,j}_{2,n},d^{i,j}_{2,\texttt{out}},\ldots,\allowbreak
d^{i,j}_{n,\texttt{in}},p^{i,j}_{n,1},\ldots,p^{i,j}_{n,n},d^{i,j}_{n,\texttt{out}}).$

(A1-3) The vertex s is a source and has as out-neighbours the first vertices
of each of the paths $\rho^{A}_{i}$ and $\rho_{i,j}$. The vertex t is a sink
and has as in-neighbours the last vertices of each of the paths $\rho^{A}_{i}$
and $\rho_{i,j}$.

(A1-4) For each $i,j\in[k]\times[k]$ and $q\in[n]$,
$(d^{i,j}_{q,\texttt{in}},d^{i,A}_{q,\texttt{in}})$ and
$(d^{i,j}_{q,\texttt{out}},d^{i,A}_{q,\texttt{out}})$ are arcs in $D_{1}$.
These are the block arcs.

(A1-5) For each $i,j\in[k]\times[k]$ and $q,r\in[n]$,
$(p^{i,j}_{q,r},\alpha^{i}_{q})\in A(D_{1})$ if and only if
$(a^{i}_{q},b^{j}_{r})\in E(G)$. These edges are called adjacency-encoders in
$D_{1}$.

Observe that for each $i\in[k]$, the vertices of $\textsf{\bf
B}_{i}\cup\textsf{\bf D}^{i,B}$ are isolated vertices in $D_{1}$. We continue
by constructing the arc set of $D_{2}$.

(A2-1) For each $i\in[k]$, there is a directed path on the vertex set
$\textsf{\bf B}^{i}\cup\textsf{\bf D}^{i,B}$ defined as
$\rho^{B}_{i}=(d^{i,B}_{1,\texttt{in}},\beta^{i}_{1},d^{i,B}_{1,\texttt{out}},\allowbreak
d^{i,B}_{2,\texttt{in}},\beta^{i}_{2},d^{i,B}_{2,\texttt{out}},\allowbreak\ldots,\allowbreak
d^{i,B}_{n,\texttt{in}},\allowbreak\beta^{i}_{n},\allowbreak
d^{i,B}_{n,\texttt{out}})$ of length $3n$.

(A2-2) For each ordered pair $i,j\in[k]\times[k]$, there is a directed path
$\hat{\rho}_{i,j}$ (of length $n^{2}+2n$) on the vertex set $\textsf{\bf
P}^{i,j}_{B}\cup\textsf{\bf D}^{i,B}$ defined as

$(d^{i,j}_{1,\texttt{in}},\hat{p}^{i,j}_{1,1},\ldots,\hat{p}^{i,j}_{1,n},d^{i,j}_{1,\texttt{out}}\allowbreak
d^{i,j}_{2,\texttt{in}},\hat{p}^{i,j}_{2,1},\ldots\hat{p}^{i,j}_{2,n},d^{i,j}_{2,\texttt{out}},\ldots,\allowbreak
d^{i,j}_{n,\texttt{in}},\hat{p}^{i,j}_{n,1},\ldots,\hat{p}^{i,j}_{n,n},d^{i,j}_{n,\texttt{out}}).$

(A2-3) The vertex s is a source and has as out-neighbours the first vertices
of each of the paths $\rho^{B}_{i}$ and $\hat{\rho}_{i,j}$. The vertex t is a
sink and has as in-neighbours the last vertices of each of the paths
$\rho^{B}_{i}$ and $\hat{\rho}_{i,j}$.

(A2-4) For each $i,j\in[k]\times[k]$ and $q\in[n]$,
$(d^{i,j}_{q,\texttt{in}},d^{i,B}_{q,\texttt{in}})$ and
$(d^{i,j}_{q,\texttt{out}},d^{i,B}_{q,\texttt{out}})$ are arcs in $D_{2}$.

(A2-5) For each $i,j\in[k]\times[k]$ and $q,r\in[n]$,
$(\hat{p}^{i,j}_{q,r},\beta^{j}_{q})\in A(D_{1})$ if and only if
$(b^{j}_{q},a^{i}_{r})\in E(G)$. Also observe that, for each $i\in[k]$, the
vertices of $\textsf{\bf A}_{i}\cup\textsf{\bf D}^{i,A}$ are isolated in
$D_{2}$. We refer to the arcs introduced in (A2-4) and (A2-5) as block arcs
and adjacency-encoders, respectively, just as we did in $D_{1}$. All the
vertices that are not incident to the adjacency-encoder edges should be
undeletable. This can be obtained by adding $k^{\prime}+1$ copies of these
vertices which have the same neighbourhood as the original vertex (that is
they form a set of pairwise false twins). It is straightforward to verify
(with the aid of Figure 4) that the digraphs $D_{1}$ and $D_{2}$ are indeed
acyclic. Finally, we set $k^{\prime}=2k+k^{2}$ and note the that resulting
instance of Sim-Separator can be computed in polynomial time.

We continue by proving the correctness of the reduction. Observe from the
adjacency of the vertices s and t that any st-separator in $D_{1}$ picks at
least one vertex from each path $\rho^{A}_{i}$, $i\in[k]$, and from each path
$\rho_{i,j}$, $i,j\in[k]$. Similarly, any st-separator in $D_{2}$ picks at
least one vertex from each path $\rho^{B}_{i}$ and from each path
$\hat{\rho}_{i,j}$. Further, since the vertices of $\rho^{A}_{i}$ and
$\rho^{B}_{i}$ are distinct, and $k^{\prime}=2k+k^{2}$, the solution for Sim-
Separator picks exactly one vertex from each $\rho^{A}_{i}$, one vertex from
each $\rho^{B}_{i}$, one vertex from $\rho_{i,j}$ and one vertex from
$\hat{\rho}_{i,j}$. Further, for each $i,j\in[k]\times[k]$, if the solution
picks $p^{i,j}_{q,r}$ from $\rho_{i,j}$ then it is picking
$\hat{p}^{i,j}_{r,q}$ from $\hat{\rho}_{i,j}$. We show that $G$ has a
multicolored biclique if and only if there is a set $X\subseteq V(D_{1})$
($=V(D_{2})$) such that $|X|\leq k^{\prime}$ and $D_{1}-X,D_{2}-X$ contain no
st-paths.

Forward direction. If $G$ has a multicolored biclique consisting of vertices
$\\{a^{i}_{f(i)}:i\in[k],f(i)\in[n]\\}$ and
$\\{b^{i}_{g(i)}:i\in[k],g(i)\in[n]\\}$, then construct $X\subseteq
V(D_{1})(=V(D_{2}))$ as follows:

  1. 1.

$X$ contains the vertex set
$\\{\alpha^{i}_{f(i)}:i\in[k]\\}\cup\\{\beta^{j}_{g(j)}:j\in[k]\\}$, and

  2. 2.

for each $i,j\in[k]\times[k]$, $X$ contains $p^{i,j}_{f(i),q(j)}$.

Recall that $p^{i,j}_{f(i),g(j)}=\hat{p}^{i,j}_{g(j),f(i)}$, none of the
vertices of $X$ are undeletable, and $|X|=2k+k^{2}=k^{\prime}$. We will now
show that $X$ is an st-separator in $D_{1}$ and in $D_{2}$.

For the sake of contradiction, we assume that $D_{1}-X$ contains an st-path.
We know that $X$ picks a vertex from each of the paths
$\rho^{A}_{i},\rho^{B}_{i},\rho_{i,j}$ and $\hat{\rho}_{i,j}$. We also know
that there are no direct connections (edges) between the paths $\rho^{A}_{i}$
and $\rho^{A}_{j}$, and between the paths $\rho_{i,j}$ and $\rho_{k,\ell}$.
Hence, if there is an $st$-path in $D_{1}-X$, then such a path intersects
$\rho^{A}_{i}$ and $\rho_{i,j}$ for some $i,j\in[k]$. In fact, such a path
intersects only $\rho^{A}_{i}$ and $\rho_{i,j}$ for some $i,j\in[k]$. Since
there is no arc from a vertex before $\alpha^{i}_{f(i)}$ in $\rho^{A}_{i}$ to
a vertex after $p^{i,j}_{f(i),g(j)}$, and
$\alpha^{i}_{f(i)},p^{i,j}_{f(i),g(i)}\in X$, we conclude that there is no st-
path in $D_{1}-X$.

Using symmetric arguments, it is immediate that there is no st-path in
$D_{2}-X$ either.

Backward direction. Let $X\subseteq V(D_{1})(=V(D_{2}))$ such that $|X|\leq
k^{\prime}$ and, $D_{1}-X,D_{2}-X$ have no st-paths. Recall that since
$|X|\leq k^{\prime}$, $X$ intersects each of the paths
$\rho^{A}_{i},\rho^{B}_{i},\rho_{i,j},\hat{\rho}_{i,j}$ in exactly one vertex.
In fact, the bijection between the vertices of the paths $\rho_{i,j}$ and
$\hat{\rho_{i,j}}$ implies that if $p^{i,j}_{q,r}\in X$, then
$\hat{p}^{i,j}_{r,q}\in X$, too.

We first claim that if $p^{i,j}_{q,r}\in X$, then $\alpha^{i}_{q}\in X$.
Assume to the contrary that this is not true. Then consider the following st-
path in $D_{1}-X$. The path starts from s, traverses the path $\rho_{i,j}$
until $d^{i,j}_{q,\texttt{in}}$, uses the block edge
$(d^{i,j}_{q,\texttt{in}},d^{i,A}_{q,\texttt{in}})$, traverses the
$(d^{i,A}_{q,\texttt{in}},d^{i,A}_{q,\texttt{out}})$-subpath of $\rho^{A}_{i}$
which exists because $d^{i,A}_{q,\texttt{in}},d^{i,A}_{q,\texttt{out}}$ are
undeletable and $\alpha^{i}_{q}\not\in X$ by assumption, traverses the block
edge $(d^{i,A}_{q,\texttt{out}},d^{i,j}_{q,\texttt{out}})$, and then traverses
the $(d^{i,j}_{q,\texttt{out}},d^{i,j}_{n,\texttt{out}})$-subpath of
$\rho_{i,j}$, and finally reaches t from $d^{i,j}_{n,\texttt{out}}$.

Using symmetric arguments, one can show that if $\hat{p}^{i,j}_{r,q}\in X$,
then $\beta^{j}_{r}\in X$. Using these claims, say $p^{i,j}_{q,r}\in X$ then
$\alpha^{i}_{q}\in X$. Since $p^{i,j}_{q,r}=\hat{p}^{i,j}_{r,q}$, then
$\beta^{j}_{r}\in X$. Also $(a^{i}_{q},b^{j}_{r})\in E(G)$ since
$p^{i,j}_{q,r},\alpha^{i}_{q},\beta^{j}_{r}$ are not undeletable and hence
they are incident to adjacency-encoder arcs. Thus, the set
$\\{a^{i}_{q}:\alpha^{i}_{q}\in X\\}\cup\\{b^{j}_{r}:\beta^{j}_{r}\in X\\}$
induces a multicolored biclique $K_{k,k}$ in $G$.

Since MC-BiClique is W[1]-hard parameterized by the solution size (Proposition
20), the above reduction shows that the Sim-Separator is W[1]-hard
parameterized by the solution size even when the input digraphs are acyclic. ∎

$a^{i}_{1}$$a^{i}_{2}$$a^{i}_{3}$$b^{j}_{1}$$b^{j}_{2}$$b^{j}_{3}$

$\alpha^{i}_{1}$$\alpha^{i}_{2}$$\alpha^{i}_{3}$$d^{i,A}_{1,\texttt{in}}$$d^{i,A}_{1,\texttt{out}}$$d^{i,A}_{2,\texttt{in}}$$d^{i,A}_{2,\texttt{out}}$$d^{i,A}_{3,\texttt{in}}$$d^{i,A}_{3,\texttt{out}}$$d^{i,j}_{1,\texttt{in}}$$d^{i,j}_{1,\texttt{out}}$$d^{i,j}_{2,\texttt{in}}$$d^{i,j}_{2,\texttt{out}}$$d^{i,j}_{3,\texttt{in}}$$d^{i,j}_{3,\texttt{out}}$$p^{i,j}_{1,1}$$p^{i,j}_{1,2}$$p^{i,j}_{1,3}$$p^{i,j}_{2,1}$$p^{i,j}_{2,2}$$p^{i,j}_{2,3}$$p^{i,j}_{3,1}$$p^{i,j}_{3,2}$$p^{i,j}_{3,3}$st$\beta^{j}_{1}$$\beta^{j}_{2}$$\beta^{j}_{3}$$d^{j,B}_{1,\texttt{in}}$$d^{j,B}_{1,\texttt{out}}$$d^{j,B}_{2,\texttt{in}}$$d^{j,B}_{2,\texttt{out}}$$d^{j,B}_{3,\texttt{in}}$$d^{j,B}_{3,\texttt{out}}$$d^{i,j}_{1,\texttt{in}}$$d^{i,j}_{1,\texttt{out}}$$d^{i,j}_{2,\texttt{in}}$$d^{i,j}_{2,\texttt{out}}$$d^{i,j}_{3,\texttt{in}}$$d^{i,j}_{3,\texttt{out}}$$\hat{p}^{i,j}_{1,1}$$\hat{p}^{i,j}_{1,2}$$\hat{p}^{i,j}_{1,3}$$\hat{p}^{i,j}_{2,1}$$\hat{p}^{i,j}_{2,2}$$\hat{p}^{i,j}_{2,3}$$\hat{p}^{i,j}_{3,1}$$\hat{p}^{i,j}_{3,2}$$\hat{p}^{i,j}_{3,3}$st

Figure 4: An illustration of the construction for $n=3$. The left figure is a
snippet of the adjacency between the set $A_{i}$ and the set $B_{j}$ in $G$
corresponding to which the next sets of paths have been constructed in $D_{1}$
and $D_{2}$ respectively. The first set of two paths are $\rho^{A}_{i}$ and
$\rho_{i,j}$ respectively in $D_{1}$. The next set of two paths are
$\rho^{B}_{j}$ and $\hat{\rho}_{i,j}$ in $D_{2}$. The brown vertices are the
dummy vertices. The vertices marked with red circles are in the solution.

We continue by using the W[1]-hardness of Sim-Separator for proving
W[1]-hardness of the following two problems.

Simultaneous Directed st-Cut (Sim-Cut)
Instance: Two directed graphs $D_{1}$ and $D_{2}$ with $V=V(D_{1})=V(D_{2})$,
vertices $s,t\in V$, and an integer $k$. Parameter: $k$. Question: Is there a
subset $X\subseteq E(D_{1})\cup E(D_{2})$ of size at most $k$ such that
neither $D_{1}-X$ nor $D_{2}-X$ contain a path from $s$ to $t$?

Simultaneous Directed Feedback Arc Set (Sim-DFAS)
Instance: Directed graphs $D_{1}$, $D_{2}$ with $V=V(D_{1})=V(D_{2})$, and an
integer $k$. Parameter: $k$. Question: Is there a subset $X\subseteq
E(D_{1})\cup E(D_{2})$ of size at most $k$ such that both $D_{1}-X$ and
$D_{2}-X$ are acyclic?

######  Theorem 25.

Sim-Cut is W[1]-hard even if both input digraphs are acyclic.

###### Proof.

We use the W[1]-hardness of Sim-Separator (Theorem 24) and the construction in
the proof as our basis. Hence, assume that we have started with an instance
$(G,k)$ of MC-BiClique and used the construction for computing two acyclic
directed graphs $D_{1}$ and $D_{2}$. We perform the following operations on
$D_{1}$ and $D_{2}$.

  1. 1.

Split each vertex $v$ in the graph into two vertices $v^{-}$ and $v^{+}$.

  2. 2.

Add an arc $(v^{-},v^{+})$, which we refer to as the splitting arc.

  3. 3.

Let all in-neighbours of $v$ be in-neighbours of $v^{-}$ and all out-
neighbours of $v$ be out-neighbours of $v^{+}$.

  4. 4.

Make all arcs in the graph, except the splitting arcs, undeletable. This can
be achieved by making $k^{\prime}+1$ copies of each of these arcs and
subdividing them once.

Let $D^{\prime}_{1},D^{\prime}_{2}$ denote the resulting graphs and note that
they are acyclic. It is now easy to see that
$(D^{\prime}_{1},D^{\prime}_{2},k)$ is a yes-instance of Sim-Cut if and only
if $(G,k)$ is a yes-instance of MC-BiClique. We conclude that Sim-Cut is
W[1]-hard. ∎

######  Theorem 26.

Sim-DFAS is W[1]-hard.

###### Proof.

Recall the proof of Theorem 25. The graphs $D_{1},D_{2}$ that are constructed
in the proof are both acyclic. To each of these graphs, add the arc
$(\texttt{t},\texttt{s})$ and make it undeletable. Then all directed cycles in
$D_{1}$ and $D_{2}$ must use this undeletable arc $(\texttt{t},\texttt{s})$.
Thus, a set of arcs hits all cycles in $D_{1}$ and $D_{2}$ if and only if it
hits all st-paths in $D_{1}$ and $D_{2}$. ∎

###  6.3 Intractable Fragments Containing ${\sf m}$

We will now show that the problems $\textsc{MinCSP}({\sf m},\equiv)$ and
$\textsc{MinCSP}({\sf m},{\sf s})$ are W[1]-hard. We introduce two binary
relations: let $\equiv^{-}$ denote the _left-equals_ relation and $\equiv^{+}$
denote the _right-equals_ relation, which hold for any pair of intervals with
matching left endpoints and right endpoints, respectively. Both relations can
be implemented using only ${\sf m}$ as follows: $\\{z{\sf m}x,z{\sf m}y\\}$
implements $x\equiv^{-}y$ where $z$ is a fresh variable; similarly, $\\{x{\sf
m}z,y{\sf m}z\\}$ implements $x\equiv^{+}y$. Thus, we may assume that
relations $\equiv^{-}$ and $\equiv^{+}$ are available whenever we have access
to the ${\sf m}$ relation. We are now ready to present the reduction for
$\textsc{MinCSP}({\sf m},\equiv)$, which will be from the Paired Cut problem
that was shown to be W[1]-hard in Lemma 22. The reduction uses a gadget that
is also used in the proof of Theorem 6.2 in [25] (see also Figure 5).

$u_{1}$$v_{1}$$u_{2}$$v_{2}$$x_{p}$$y_{p}$$\equiv^{-}$$\equiv^{+}$$\equiv$$\equiv^{-}$$\equiv^{+}$
Figure 5: Gadget from Theorem 27.

######  Theorem 27.

MinCSP$({\sf m},\equiv)$ is W[1]-hard.

###### Proof.

Let $(G_{1},G_{2},s_{1},t_{1},s_{2},t_{2},\mathcal{B},k)$ be an arbitrary
instance of Paired Cut. We construct an instance $(\mathcal{I},k)$ of
$\textsc{MinCSP}({\sf m},\equiv)$ with the same parameter. Start by
introducing a variable for every vertex of $V(G_{1})\cup V(G_{2})$ and adding
a crisp constraint

$u\equiv v$ (1)

for every edge $uv\in E(G_{1})\cup E(G_{2})$ with
$uv\notin\bigcup\mathcal{B}$, i.e. edges that are not included in any bundle
pair and are thus undeletable. We also add the following crisp constraints:

$s_{1}{\sf m}t_{1},t_{1}{\sf m}s_{2},s_{2}{\sf m}t_{2}.$ (2)

For every pair $p\in\mathcal{B}$ with edges $(u_{i},v_{i})$ for
$i\in\\{1,2\\}$, introduce two new variables $x_{p}$ and $y_{p}$, and add the
following constraints as illustrated in Figure 5:

  * •

crisp constraints $u_{1}\equiv^{-}x_{p}$ and $u_{2}\equiv^{+}x_{p}$,

  * •

crisp constraints $v_{1}\equiv^{-}y_{p}$ and $v_{2}\equiv^{+}y_{p}$,

  * •

soft constraint $x_{p}\equiv y_{p}$.

This completes the reduction. Clearly, it can be implemented in polynomial
time. The equivalence of the instances
$(G_{1},G_{2},s_{1},t_{1},s_{2},t_{2},\mathcal{B},k)$ and $(\mathcal{I},k)$
now follows relatively straightforwardly after the observation that removing a
soft constraint $x_{p}\equiv y_{p}$ corresponds to removing any (or both)
edge(s) in bundle $p$. We claim that
$(G_{1},G_{2},s_{1},t_{1},s_{2},t_{2},\mathcal{B},k)$ is a yes-instance of
Paired Cut if and only if $(\mathcal{I},k)$ is a yes-instance of MinCSP$({\sf
m},\equiv)$.

Forward direction. Suppose $X\subseteq\mathcal{B}$ is a subset of $k$ pairs
such that $X_{i}=\\{e_{i}:(e_{1},e_{2})\in X\\}$ is an $\\{s_{i},t_{i}\\}$-cut
in $G_{i}$ for $i\in\\{1,2\\}$. Let $X^{\prime}$ be the set of constraints
that contains $x_{p}\equiv y_{p}$ for all $p\in X$. We claim that
$I-X^{\prime}$ is satisfied by assignment $\alpha$ constructed as follows.
First, set

$\displaystyle\alpha(s_{1})=[0,1],$ $\displaystyle\alpha(t_{1})=[1,2],$
$\displaystyle\alpha(s_{2})=[2,3],$ $\displaystyle\alpha(t_{2})=[3,4].$

For every vertex $u_{i}\in V(G_{i})$, set

$\alpha(u_{i})=\begin{cases}\alpha(s_{i})&\text{there is an
}s_{i}u_{i}\text{-path in }G_{i}-X,\\\
\alpha(t_{i})&\text{otherwise}.\end{cases}$

For every pair $p\in\mathcal{B}$ consisting of two edges $u_{i}v_{i}$ for
$i\in\\{1,2\\}$, assign

$\displaystyle\alpha(x_{p})=[\alpha(u_{1})^{-},\alpha(u_{2})^{+}],$
$\displaystyle\alpha(y_{p})=[\alpha(v_{1})^{-},\alpha(v_{2})^{+}].$

Observe that $\alpha(u_{1})^{-},\alpha(v_{1})^{-}\leq 1$ and
$\alpha(u_{2})^{+},\alpha(v_{2})^{+}\geq 2$, so $\alpha$ assigns non-empty
intervals to all variables. By definition, $\alpha$ satisfies all crisp
constraints in $I$. All soft constraints are of the form $x_{p}\equiv y_{p}$
for some pair $p\in\mathcal{B}$. If such a constraint is not in $X^{\prime}$,
then the edges $u_{1}v_{1}$ and $u_{2}v_{2}$ are present in $G-X$. Then
$\alpha(u_{i})=\alpha(v_{i})$ for $i\in\\{1,2\\}$ so
$\alpha(x_{p})=\alpha(y_{p})$. This implies that $\alpha$ can leave at most
$|X|\leq k$ constraints unsatisfied.

Backward direction. Suppose $Y$ is a set of at most $k$ soft constraints such
that $I-Y$ is consistent. Let $Y^{\prime}\subseteq\mathcal{B}$ contain all
pairs of edges $p$ such that the constraint $x_{p}\equiv y_{p}$ is in $Y$. We
claim that $Y^{\prime}$ is an $st$-cut in $G_{1}$ and $G_{2}$. For the sake of
contradiction, assume there is a path in $G_{1}-Y^{\prime}$ from $s_{1}$ to
$t_{1}$. This path corresponds to a chain of constraints in $I$ linking
$s_{1}$ and $t_{1}$ by $\equiv$-constraints and $\equiv^{-}$-constraints. This
implies that the left endpoints of $s_{1}$ and $t_{1}$ match and this
contradicts the crisp constraint $s_{1}{\sf m}t_{1}$. The case with $G_{2}$,
$s_{2}$, $t_{2}$ is similar. ∎

We continue by showing that $\textsc{MinCSP}({\sf m},{\sf s})$ is W[1]-hard.
First note even though we no longer have access to $\equiv$, we can add
constraints $x\equiv^{-}y$ and $x\equiv^{+}y$ which imply $x\equiv y$. As
previously, relations $\equiv^{-}$ and $\equiv^{+}$ can be implemented using
only ${\sf m}$. We remark that $\\{x\equiv^{-}y,x\equiv^{+}y\\}$ is _not_ an
implementation of $\equiv$, so we can only use $\equiv$ in crisp constraints.
Our reduction is based on the PCFAS problem, which was shown to be W[1]-hard
in Lemma 23. While the reduction is quite similar to the reduction for
$\textsc{MinCSP}({\sf m},\equiv)$, it is non-trivial to replace the role of
$\equiv$ with ${\sf s}$. We therefore provide the reduction here in its
entirety.

######  Theorem 28.

MinCSP$({\sf m},{\sf s})$ is W[1]-hard.

###### Proof.

Let $(G_{1},G_{2},s,t,\mathcal{B},k)$ be an arbitrary instance of PCFAS and