# On weighted graph separation problems and flow-augmentation††thanks: This
research is a part of a project that have received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme Grant Agreement 714704 (M. Pilipczuk). Eun Jung Kim is
supported by the grant from French National Research Agency under JCJC program
(ASSK: ANR-18-CE40-0025-01).

Eun Jung Kim  Université Paris-Dauphine, PSL Research University, CNRS, UMR
7243, LAMSADE, 75016, Paris, France.  Tomáš Masařík  University of Warsaw,
Warsaw, Poland  Marcin Pilipczuk  University of Warsaw, Warsaw, Poland
Roohani Sharma  Max Planck Institute for Informatics, Saarland Informatics
Campus, Saarbrücken, Germany.  Magnus Wahlström  Royal Holloway, University of
London, TW20 0EX, UK

###### Abstract

One of the first application of the recently introduced technique of _flow-
augmentation_ [Kim et al., STOC 2022] is a fixed-parameter algorithm for the
weighted version of Directed Feedback Vertex Set, a landmark problem in
parameterized complexity. In this note we explore applicability of flow-
augmentation to other weighted graph separation problems parameterized by the
size of the cutset. We show the following.

  * •

In weighted undirected graphs Multicut is FPT, both in the edge- and vertex-
deletion version.

  * •

The weighted version of Group Feedback Vertex Set is FPT, even with an oracle
access to group operations.

  * •

The weighted version of Directed Subset Feedback Vertex Set is FPT.

Our study reveals Directed Symmetric Multicut as the next important graph
separation problem whose parameterized complexity remains unknown, even in the
unweighted setting.

20(0, 13.0)  20(0, 13.9)

##  1 Introduction

The family of graph separation problems includes a wide range of combinatorial
problems where the goal is to remove a small part of the input graph to obtain
some separation properties. For example, in the Multicut problem, the input
graph $G$ is equipped with a set of terminal pairs $\mathcal{T}\subseteq
V(G)\times V(G)$ and the separation objective is to destroy, for every
$(s,t)\in\mathcal{T}$, all paths from $s$ to $t$. In the Subset Feedback
Edge/Vertex Set problems, the input graph $G$ is equipped with a set
$R\subseteq E(G)$ of _red edges_ and the goal is to destroy all cycles that
contain at least one red edge.111In the literature, sometimes one considers
red vertices instead of red edges. Since there are simple reductions between
the variants (cf. [11]), we prefer to work with red edges. We remark that in
directed graphs, one can equivalently require to destroy all closed walks
containing at least one red edge.

Both these problems (and many others) can be considered in multiple variants:
graphs can be undirected or directed, we are allowed to delete edges or
vertices, weights can be present, etc. In this paper we consider both edge-
and vertex-deletion variants and both cardinality and weight budget for the
solution. That is, the input graph $G$ is equipped with a weight function
$\omega$ that assigns positive integral weights to deletable objects (i.e.,
edges or vertices), and we are given two integers: $k$, the maximum number of
deleted objects, and $W$, the maximum total weight of the deleted objects in
the sought solution.

The study of parameterized complexity of graph separation problems has been a
vivid line for the past two decades, and resulted in many tractability results
and a wide range of algorithmic techniques: important separators and shadow
removal [3, 6, 7, 11, 26, 22, 31, 33], branching guilded by an LP relaxation
[10, 14, 16], matroid-based techniques [23, 24], treewidth reduction [27],
randomized contractions [4, 8], and, most recent, flow-augmentation [19, 20].
However, the vast majority of these works considered only the unweighted
versions of the problems, for a very simple reason: we did not know how to
handle their weighted counterparts. In particular, one of the most fundamental
notion — important separators, introduced by Marx in 2004 [26] — relies on a
greedy argument that breaks down in the presence of weights. The quest to
understand the weighted counterparts of studied graph separation problems,
with a specific goal to resolve the parameterized complexity of the weighted
version of Directed Feedback Vertex Set — the landmark problem in
parameterized complexity [6] — was raised by Saurabh in 2017 [35] (see also
[25]).

This question has been resolved recently by Kim et al. [20] with a new
algorithmic technique called _flow-augmentation_. Apart from proving fixed-
parameter tractability of the weighted version of Directed Feedback Vertex
Set, they also showed fixed-parameter tractability of Chain SAT, resolving
another long-standing open problem [5]. Both the aforementioned results are in
fact the same relatively simple algorithm for a more general problem Weighted
Bundled Cut with Order, and solve also the weighted version of Chain SAT.

Very recently, Galby et al. [13] used the flow-augmentation technique to
design an FPT algorithm for weighted Multicut on trees. Our results thus
extend theirs, by generalizing the input graphs from trees to arbitrary
undirected graphs.

#### Our results.

The goal of this note is to explore for which other graph separation problems
the flow-augmentation technique helps in getting fixed-parameter algorithms
for weighted graph separation problems. (All algorithms below are randomized;
all randomization comes from the flow-augmentation technique.)

We start with the Multicut problem in undirected graphs, whose parameterized
complexity — in the unweighted setting — had been a long-standing open problem
until being settled in the affirmative by two independent groups of
researchers in 2011 [2, 31].

######  Theorem 1.1.

Weighted Multicut, parameterized by the cardinality of the cutset, is
randomized FPT, both in the edge- and vertex-deletion variants.

Theorem 1.1 follows from a combination of two arguments. First, we revisit the
reduction of Marx and Razgon from Multicut to a _bipedal variant_ , presented
in the conference version of their paper [29] and show how to replace one
greedy step based on important separators with a different, weights-resilient
step. Then, a folklore reduction to a graph separation problem called Coupled
Min-Cut, spelled out in [18], does the job: the fixed-parameter tractability
of a wide generalization of Coupled Min-Cut, including its weighted variant,
is one of the main applications of flow-augmentation [19, 20, 21].

Multiway Cut is a special case of Multicut where the input graph $G$ is
equipped with a set $T\subseteq V(G)$ of terminals and
$\mathcal{T}=\\{(s,t)~{}|~{}s,t\in T,s\neq t\\}$, that is, we are to destroy
all paths between distinct terminals. Thus, Theorem 1.1 implies the following.

######  Corollary 1.2.

Weighted Multiway Cut, parameterized by the cardinality of the cutset, is
randomized FPT, both in the edge- and vertex-deletion variants.

We remark that in directed graphs the parameterized complexity of Multicut is
fully understood: without weights, it is W[1]-hard for 4 terminal pairs [32]
and FPT for 3 terminal pairs [15], but with weights it is already W[1]-hard
for 2 terminal pairs [15], while for 1 terminal pair it is known under the
name of Bi-Objective $st$-cut and its fixed-parameter tractability follows
easily via flow-augmentation [20]. Furthermore, while Multiway Cut on directed
graphs is FPT in the unweighted setting [7], on directed graphs Multicut with
2 terminal pairs reduces to Multiway Cut with two terminals [7], hence
Multiway Cut with weights is W[1]-hard and without weights is FPT on directed
graphs.

Then we turn our attention to Group Feedback Edge/Vertex Set. Here, the input
graph $G$ is equipped with a group $\Gamma$, not necessarily Abelian, and an
assignment $\psi$, called the group labels, that assigns to every $e\in E(G)$
and $v\in e$ an element $\psi(e,v)\in\Gamma$ such that for $e=uv$ we have
$\psi(e,u)+\psi(e,v)=0$.222Thorough this paper, we use $+$ for the group
operation, $0$ for the neutral element in the group, and $-$ for the group
inverse, to conform with the standard terminology of _null cycles_ in GFVS. We
note that this is in tension with the convention that a group operation
written as $+$ tends to imply an Abelian group. With a walk
$C=(v_{1},e_{1},v_{2},e_{2},\ldots,v_{\ell},e_{\ell},v_{\ell+1})$ we associate
a sum $\psi(C)=\sum_{i=1}^{\ell}\psi(e_{i},v_{i})$; a walk $C$ is a _null
walk_ in $(G,\psi)$ if $\psi(C)=0$ and _non-null_ otherwise. This is well-
defined even for non-Abelian groups, i.e., a cycle being null or non-null does
not depend on the direction of traversal or the choice of starting vertex
$v_{1}$ [9]. The separation goal is to destroy all non-null cycles
(equivalently, all non-null closed walks) by edge or vertex deletions.

######  Theorem 1.3.

Weighted Group Feedback Edge Set and Weighted Group Feedback Vertex Set,
parameterized by the cardinality of the cutset, are randomized FPT.

Since Weighted Subset Feedback Edge/Vertex Set can be modeled as Weigted Group
Feedback Edge/Vertex Set with group $\Gamma=\mathbb{Z}_{2}^{R}$ (cf. [9]), we
immediately have the following corollary.

######  Corollary 1.4.

Weighted Subset Feedback Edge Set and Weighted Subset Feedback Vertex Set,
parameterized by the cardinality of the cutset, are randomized FPT.

The currently fastest FPT algorithm for (unweighted) Group Feedback Vertex Set
is due to Iwata, Wahlström, and Yoshida [16] and uses sophisticated branching
guided by an LP relaxation. To prove Theorem 1.3, we revisit an older (and
less efficient) FPT algorithm due to Cygan et al. [9] that performs some
branching steps to reduce the problem to multiple instances of Multiway Cut.
We observe that the branching easily adapts to the weighted setting, and the
algorithm for Weighted Multiway Cut is provided by Corollary 1.2.

We now move to directed graphs. As already mentioned, the parameterized
complexity of both weighted and unweighted Directed Multicut (and Directed
Multiway Cut) is already fully understood [15, 32]. Our main result here is
fixed-parameter tractability of Weighted Directed Subset Feedback Edge/Vertex
Set.

######  Theorem 1.5.

Weighted Directed Subset Feedback Edge Set and Weighted Directed Subset
Feedback Vertex Set, parameterized by the cardinality of the cutset, are
randomized FPT.

Theorem 1.5 follows from a surprisingly delicate reduction to Weighted Bundled
Cut with Order, known to be FPT via flow-augmentation [20].

Skew Multicut is a special case of Directed Multicut where the set
$\mathcal{T}$ has the form $\\{(s_{i},t_{j})~{}|~{}1\leq i\leq j\leq\ell\\}$
for some terminals $s_{1},\ldots,s_{\ell},t_{1},\ldots,t_{\ell}\in V(G)$. Skew
Multicut naturally arises in the context of Directed Feedback Vertex Set if
one applies the iterative compression technique. In the unweighted setting,
Skew Multicut is long known to be FPT parameterized by the size of the cutset
[3]. With weights, [20] showed that Skew Multicut is FPT when parameterized by
$k+\ell$. We observe a simple reduction to Weighted Directed Subset Feedback
Vertex Set, yielding fixed-parameter tractability when parameterizing by $k$
only.

######  Corollary 1.6.

Weighted Skew Multicut, parameterized by the cardinality of the cutset, is
randomized FPT, both in the edge- and vertex-deletion variants.

###### Proof.

Let $(G,(s_{i},t_{i})_{i=1}^{\ell},\omega,k,W)$ be a Weighted Skew Multicut
instance (in the edge- or vertex-deletion setting) where $\omega$ is the
weight function (on the edges or vertices respectively) and $W$ is the weight
budget of the solution. Construct a graph $G^{\prime}$ and a set of red edges
$R$ as follows: start with $G^{\prime}=G$, $R=\emptyset$ and, for every $1\leq
i\leq j\leq\ell$, introduce a red edge $(t_{j},s_{i})$ and add it to
$G^{\prime}$ (in the edge-deletion setting, the new edge has weight $W+1$,
that is, it is effectively undeletable). It is easy to see that the resulting
Weighted Directed Subset Feedback Edge/Vertex Set instance
$(G^{\prime},R,\omega,k,W)$ is equivalent to the input Weighted Skew Multicut
instance: any closed walk in $G^{\prime}$ involving a red edge contains a
subpath from $s_{i}$ to $t_{j}$ for some $1\leq i\leq j\leq\ell$ without any
red edge, and any path in $G$ from $s_{i}$ to $t_{j}$ for $1\leq i\leq
j\leq\ell$ closes up to a cycle with a red edge $(t_{j},s_{i})$ in
$G^{\prime}$. ∎

The running time bounds of all our algorithms are of the form
$2^{\mathrm{poly}(k)}\mathrm{poly}(|V(G)|)$, where both polynomial
dependencies have unspecified large degree coming from the use of involved
flow-augmentation-based algorithms of [20, 21].

#### Organization.

We introduce the necessary tools, in particular the used corollaries of the
flow-augmentation technique, in Section 2. Theorem 1.1 is proven in Section 3,
Theorem 1.3 is proven in Section 4, and Theorem 1.5 is proven in Section 5.
Section 6 concludes the paper and identifies Directed Symmetric Multicut as a
next problem whose parameterized complexity remains open.

##  2 Preliminaries

###  2.1 Edge- and vertex-deletion variants

In directed graphs, there is a simple reduction from the vertex-deletion
setting to the edge-deletion one: replace every vertex $v$ with two vertices
$v^{+}$ and $v^{-}$ and an edge $(v^{-},v^{+})$; every previous arc $(u,v)$
becomes an arc $(u^{+},v^{-})$. Now, the deletion of the vertex $v$
corresponds to the deletion of the arc $(v^{-},v^{+})$. Hence, in Section 5 we
will consider only the edge-deletion variant, that is, Directed Subset
Feedback Edge Set.

No such simple reduction is available in undirected graphs and, in fact, in
some cases the vertex-deletion variant turns out to be significantly more
difficult (cf. the $k$-Way Cut problem [4, 17, 26]). In the presence of
weights, there is a simple reduction from the edge-deletion variant to the
vertex-deletion variant: subdivide every edge with a new vertex that inherits
the weight of the edge it is placed on, and set the weight of the original
vertices to $+\infty$, making them undeletable. (For clarity, we allow the
weight function $\omega$ to attain the value $+\infty$, which is equivalent to
any weight larger than $W$ and models an undeletable edge or vertex.) Thus,
both in Section 3 and in Section 4 we consider the vertex-deletion variants.

###  2.2 Iterative Compression

All problems considered in this paper are monotone in the sense that deletion
of an edge or a vertex from the input graph cannot turn a Yes-instance into a
No-instance. This allows to use the standard technique of _iterative
compression_ [34]: We enumerate $V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$ for
$n=|V(G)|$, denote $G_{i}=G[\\{v_{1},\ldots,v_{i}\\}]$ for $0\leq i\leq n$ and
iteratively solve the problem on graphs $G_{0}$, $G_{1}$, …, $G_{n}=G$. If the
instance for $G_{i}$ turns out to be a No-instance, we deduce that the input
instance is a No-instance, too. Otherwise, the computed solution for $G_{i}$
allows us to infer a set $X^{\prime}\subseteq V(G_{i})$ of size at most $k$
such that in $G_{i}-X^{\prime}$ already has the desired separation (i.e.,
induces a Yes-instance with parameter $k=0$). We set
$X=X^{\prime}\cup\\{v_{i+1}\\}$ and observe that $G_{i+1}-X=G_{i}-X^{\prime}$
and $|X|\leq k+1$.

Furthermore, in all considered problems, using self-reducibility it is
immediate to turn an algorithm that only gives a yes/no answer into an
algorithm that, in case of a positive answer, returns a cutset that is a
solution.

Hence, in all our algorithmic results, we can solve a compression version of
the problem. That is, we can assume that our algorithm is additionally given
on input a set $X\subseteq V(G)$ of size at most $k+1$ such that $G-X$ already
satisfies the desired separation (i.e., has no cycle with a red edge in case
of Subset Feedback Edge Set etc.).

Furthermore, in the problems that involve vertex deletions (i.e., Sections 3
and 4), we can additionally branch on the set $X$ into $2^{|X|}$ options,
guessing a set $Y\subseteq X$ of vertices that are included in the sought
solution. In each branch, we delete $Y$ from the graph and the set $X$,
decrease $k$ by $|Y|$ and decrease $W$ by the weight of $Y$. Furthemore, we
set the weight of the remaining vertices of $X\setminus Y$ to $+\infty$, so
they become undeletable. In other words, in Sections 3 and 4 we solve a
disjoint compression variant of the problem, where the sought solution is
supposed to be disjoint with the set $X$.

###  2.3 Generalized Digraph Pair Cut

We will not need flow-augmentation in its raw form, but only one algorithmic
corollary of this technique.

An instance of Generalized Digraph Pair Cut (GDPC for short) consists of:

  * •

a directed multigraph $G$ with two distinguished vertices $s,t\in V(G)$;

  * •

a multiset $\mathcal{C}$ of (unordered) pairs of vertices of $G$, called
_clauses_ ;

  * •

a family $\mathcal{B}$ of pairwise disjoint subsets of $E(G)\cup\mathcal{C}$
called _bundles_ such that no bundle contains two copies of the same arc or
two copies of the same pair;

  * •

a weight function $\omega:\mathcal{B}\to\mathbb{Z}_{+}$;

  * •

two integers $k$ and $W$.

A set $Z\subseteq E(G)$ is a _cut_ in a GDPC instance
$\mathcal{I}=(G,s,t,\mathcal{C},\mathcal{B},\omega,k,W)$ if $Z\subseteq
E(G)\cap\bigcup_{B\in\mathcal{B}}B$ (i.e., $Z$ contains only edges of bundles)
and there is no path from $s$ to $t$ in $G-Z$. A cut $Z$ _violates_ an edge
$e\in E(G)$ if $e\in Z$ and _violates_ a clause $uv\in\mathcal{C}$ if both $u$
and $v$ are reachable from $s$ in $G-Z$. A bundle is _violated_ by $Z$ if it
contains an edge or a clause violated by $Z$. An edge, a clause, or a bundle
not violated by $Z$ is _satisfied_ by $Z$. A cut $Z$ is a _solution_ if every
clause violated by $Z$ is part of a bundle, $Z$ violates at most $k$ bundles,
and the total weight of violated bundles is at most $W$. (Recall that a cut is
required to contain only edges of bundles, that is, it satisfies all edges
outside bundles.) The GDPC problem asks for an existence of a solution.

GDPC, parameterized by $k$, is W[1]-hard even in the unweighted setting and
without clauses: it suffices to have bundles consisting of two edges for the
hardness [28]. However, flow-augmentation yields fixed-parameter tractability
of some specific useful restrictions of GDPC.

For a bundle $B\in\mathcal{B}$, let $V(B)$ be the set of vertices that are
involved in an arc or a clause of $B$ and let $G_{B}$ be an undirected graph
with $V(G_{B})=V(B)\setminus\\{s,t\\}$ and $uv\in E(G_{B})$ if $B$ contains an
arc $(u,v)$, an arc $(v,u)$, or a clause $uv$. A bundle $B$ is $2K_{2}$-free
if $G_{B}$ is $2K_{2}$-free, that is, it does not contain $2K_{2}$ (the four-
vertex graph consisting of two independent edges) as an induced subgraph. An
instance $\mathcal{I}$ of GDPC is $2K_{2}$-free if every bundle of
$\mathcal{I}$ is $2K_{2}$-free. Finally, an instance $\mathcal{I}$ is
$b$-bounded if for every $B\in\mathcal{B}$ we have $|V(B)|\leq b$.

One of the main algorithmic corollaries of the flow-augmentation technique is
the tractability of $2K_{2}$-free $b$-bounded instances of GDPC.

######  Theorem 2.1 ([21], Theorem 3.3).

There exists a randomized polynomial-time algorithm for Generalized Digraph
Pair Cut restricted to $2K_{2}$-free $b$-bounded instances that never accepts
a No-instance and accepts a Yes-instance with probability
$2^{-\mathrm{poly}(k,b)}$.

For Directed Subset Feedback Edge Set it will be more convenient to look at a
different restriction of GDPC. Let
$\mathcal{I}=(G,s,t,\emptyset,\mathcal{B},\omega,k,W)$ be a GDPC instance
without clauses. An arc $e\in E(G)$ is _crisp_ if it is not contained in any
bundle, and _soft_ otherwise. An arc $e\in E(G)$ is _deletable_ if it is soft
and there is no copy of $e$ in $G$ that is crisp. Note that a cut needs to
contain soft arcs only and in fact we can restrict our attention to cuts
containing only deletable arcs. A bundle $B\in\mathcal{B}$ has _pairwise
linked deletable edges_ if for every two deletable arcs $e_{1},e_{2}\in B$
that are not incident with either $s$ or $t$, there is a path from an endpoint
of one of the edges to an endpoint of the other that does not use an edge of
another bundle (i.e., uses only edges of $B$ and crisp edges).

In [20], a notion of Bundled Cut with Order has been introduced as one variant
of GDPC without clauses that is tractable. In [21], it was observed that the
notion of _pairwise linked deletable edges_ is slightly more general than the
“with order” assumption and is more handy.

######  Theorem 2.2 ([21], Theorem 3.21).

There exists a randomized polynomial-time algorithm that, given a GDPC
instance $\mathcal{I}=(G,s,t,\emptyset,\mathcal{B},\omega,k,W)$ with no
clauses and whose every bundle has pairwise linked deletable edges, never
accepts a No-instance and accepts a Yes-instance with probability
$2^{-\mathcal{O}(k^{4}d^{4}\log(kd))}$ where $d$ is the maximum number of
deletable arcs in a single bundle.

Note that if $\mathcal{I}$ is $b$-bounded, then $d\leq b^{2}$.

##  3 Multicut

This section is devoted to the proof of Theorem 1.1.

As discussed in Section 2, we can restrict ourselves to the vertex-deletion
variant. Let $\mathcal{I}=(G,\mathcal{T},\omega,k,W)$ be an instance of
Weighted Multicut. Let $T=\bigcup_{(s,t)\in\mathcal{T}}\\{s,t\\}$ be the set
of all terminals. By a simple reduction, we can assume that all terminals have
weight $+\infty$ and form an independent set: for every $(s,t)\in\mathcal{T}$,
add a new vertex $s^{\prime}$ adjacent to $s$, add a new vertex $t^{\prime}$
adjacent to $t$, set $\omega(s^{\prime})=\omega(t^{\prime})=+\infty$ and
replace $(s,t)$ with $(s^{\prime},t^{\prime})$ in $\mathcal{T}$.

We also use iterative compression, but in the ordering $v_{1},\ldots,v_{n}$ of
$V(G)$ we start with terminals. Note that the subgraph of $G$ induced by the
terminals is edgeless and thus admits a solution being the emptyset. As a
result, using standard iterative compression step discussed in Section 2 we
can assume that the algorithm is given access to a set $X\subseteq
V(G)\setminus T$ of size $|X|\leq k+1$ such that for every
$(s,t)\in\mathcal{T}$ there is no path from $s$ to $t$ in $G-X$ and we are to
check if there is a solution disjoint with $X$. We can set $\omega(x)=+\infty$
for every $x\in X$.

We closely follow the steps in Section 5 of [30], reengineering only one
branching step that originally uses important separators.

Fix a hypothetical solution $Z$. We first guess how the vertices of $X$ are
partitioned between connected components of $G-Z$. This results in
$2^{\mathcal{O}(k\log k)}$ subcases. If two vertices of $X$ are guessed to be
in the same connected component of $G-Z$, we can merge them into a single
vertex (recall that the solution $Z$ is disjoint with $X$). After this step,
we can assume that every connected component of $G-Z$ contains at most one
vertex of $X$ and $X$ is an independent set. For brevity, we say that
$Y\subseteq V(G)\setminus(X\cup T)$ is a _multiway cut_ if every connected
component of $G-Y$ contains at most one vertex of $X$. Thus, it suffices to
develop a randomized FPT algorithm that (a) accepts with constant probability
an instance that admits a solution that is a multiway cut; (b) never accepts a
No-instance.

An instance is _bipedal_ if $X$ is an independent set and for every connected
component $C$ of $G-X$, we have $|N_{G}(C)|\leq 2$, that is, $C$ is adjacent
to at most two vertices of $X$. In Section 3.2 we show how to reduce a bipedal
instance to a GDPC instance handled by Theorem 2.1. We emphasize that we do
not claim authorship of this reduction: while there is no citeable source of
this reduction, it has been floating around in the community in the last
years. The reduction, in the edge-deletion setting (and leading to an
undirected analog of GDPC) has been spelled out in [18]. We include it here
for completeness of the argument.

Section 3.1 describes a branching algorithm, closely following the arguments
of [30], whose goal is to break connected components $C$ of $G-X$ with
$|N_{G}(C)|>2$. In the leaves of the branching process we obtain bipedal
instances that are passed to the algorithm of Section 3.2.

###  3.1 Branching on a multilegged component

The algorithm is a recursive branching routine on an instance
$(G,\mathcal{T},\omega,k,W,X)$ where $X$ is an independent set and a multicut
for $\mathcal{T}$, and the hypothetical solution is also a multiway cut for
$X$. In the beginning $|X|\leq k+1$ as discussed earlier. During the branching
algorithm one may delete vertices, merge vertices or grow the set $X$ while
maintaining that the hypothetical solution is also a multiway cut for (the
new) $X$.

In a recursive call, we start with a few cleaning steps. At every moment,
apply the first applicable reduction step.

  1. 1.

If $\emptyset$ is a solution, return Yes.

  2. 2.

If $k\leq 0$, $W\leq 0$, or $X$ is not an independent set, return No.

  3. 3.

If the number of connected components $C$ of $G-X$ with $|N_{G}(C)|>1$ is more
than $k$, return No. (Note that every such component needs to contain at least
one vertex of every multiway cut.)

  4. 4.

If there exists $x\in X$ such that the cardinality of the minimum-cardinality
vertex cut between $x$ and $X\setminus x$ is of size larger than $k$, return
No. (Recall that the solution is also a multiway cut for $X$.)

  5. 5.

If there exists a vertex $v$ that admits a family $\mathcal{P}$ of $k+2$ paths
that start in $v$, end in distinct vertices of $X$, and are vertex-disjoint
except for $v$, delete $v$, decrease $k$ by one, decrease $W$ by $\omega(v)$,
and recurse. (Note that every such vertex $v$ needs to be included in any
multiway cut of size at most $k$.)

  6. 6.

If there exists a connected component $C$ of $G$ that do not contain both
vertices of any terminal pair $(s,t)\in\mathcal{T}$ and contains at most one
vertex of $X$, delete it and all terminal pairs involving a vertex of $C$.
(Recall that for every $(s,t)\in\mathcal{T}$, the terminals $s$ and $t$ lie in
different connected components of $G-X$. Hence, this rule applies to any
component $C$ that contains no vertex of $X$ and to any isolated vertex of
$X$.)

  7. 7.

If $|X|>k(k+1)$, return No. (Since the previous reduction rule is
inapplicable, for every multiway cut $Z$, every $z\in Z$ is adjacent to at
most $k+1$ connected components of $G-Z$ that contain a vertex of $X$. Also,
since $Z$ is a multiway cut for $X$, every vertex of $X$ is in a distinct
connected component of $G-Z$. Further, since the previous rule is not
applicable, there does not exist a connected component of $G-Z$ that has no
neighbour in $Z$. Indeed, as such an isolated component will have at most one
vertex from each terminal pair in $\mathcal{T}$ because $Z$ is a solution and
at most one vertex of $X$ since $Z$ is a multiway cut of $Z$. Therefore, $|X|$
is at most the number of connected components of $G-Z$ that intersect $X$,
which is upper bounded by $|Z|(k+1)\leq k(k+1)$.)

  8. 8.

If the current instance is bipedal, pass it to the algorithm of Section 3.2.

A component $C$ of $G-X$ is _nontrivial_ if $|N_{G}(C)|>1$. If neither of the
reduction steps is applicable, we have at most $k$ nontrivial connected
components and the size of the neighbourhood of each component of $G-X$ is at
most $|X|\leq k(k+1)$.

At every branching step, we will ensure that one of the following progresses
happen in any recursive call:

  * •

the instance will be resolved immediately by reduction rules 1-4 or 7, or

  * •

the parameter $k$ decreases, or

  * •

the parameter $k$ stays the same, but the number of nontrivial connected
components plus the number vertices of $X$ adjacent to a nontrivial component
increases.

We observe that the reduction rules do not reverse the above progress. That
is, Rule 5 can decrease the number of nontrivial connected components or the
number of vertices of $X$ incident with a nontrivial connected component, but
at the same time decreases $k$ by one, while Rule 6 cannot delete a nontrivial
connected component.

After the application of the described reduction rules, the number of non-
trivial components is at most $k$ and the size of $X$ is at most $k(k+1)$.
Thus, the depth of the recursion is bounded by $\mathcal{O}(k^{3})$.

Let $C$ be a component of $G-X$ with $|N_{G}(C)|>2$. (It exists as the
instance is not bipedal.) For a subset $B\subseteq C$ and a function $f:B\to
N_{G}(C)$, we construct an instance $\mathcal{I}_{f}$ as follows: for every
$v\in B$, we merge $v$ onto the vertex $f(v)$ (we use $f(v)$ as the name of
the resulting vertex and the resulting vertex still belongs to $X$). We say
that $B$ is a _shattering set_ if for every $f:B\to N_{G}(C)$, the instance
$\mathcal{I}_{f}$ either contains strictly more nontrivial components than the
current instance, or recursing on $\mathcal{I}_{f}$ will result in returning
an immediate answer by one of the first four reduction rules.

The main technical contribution of Section 5 of [30] is the following
statement.

######  Lemma 3.1.

Given an instance $(G,\mathcal{T},\omega,k,W)$ together with a set $X\subseteq
V(G)\setminus T$ such that in $G-X$ there is no path from $s$ to $t$ for any
$(s,t)\in\mathcal{T}$, and a component $C$ of $G-X$ with $|N_{G}(C)|>2$, one
can find a shattering set $B\subseteq C$ of size at most $3k$ in polynomial
time.

We apply Lemma 3.1 to $C$, obtaining a set $B$ of size at most $3k$. We
branch, guessing the first of the following options that happens with regards
to a hypothetical solution $Z$:

  1. 1.

There is a vertex $v\in B\cap Z$. We guess $v$, delete $v$ from the graph,
decrease $k$ by one, decrease $W$ by $\omega(v)$, and recurse. This gives
$|B|\leq 3k$ subcases and in each subcase $k$ drops.

  2. 2.

For every $v\in B$, the connected component of $G-Z$ that contains $v$ also
contains a vertex of $X$. For every $v\in B$, we guess a vertex $f(v)\in
N_{G}(C)$ that is in the same connected component of $G-Z$ as $v$. As
$|N_{G}(C)|\leq|X|\leq k(k+1)$ and $|B|\leq 3k$, there are
$2^{\mathcal{O}(k\log k)}$ options for $f:B\to N_{G}(C)$. We recurse on
$\mathcal{I}_{f}$. To see that we obtain progress, observe that:

     * •

the parameter $k$ stays the same;

     * •

if $X$ is not an independent set, the recursive call returns No immediately;

     * •

otherwise, the fact that $B$ is a shattering set implies that in each instance
$\mathcal{I}_{f}$ the number of non-trivial components increases, while the
connectivity of $C$ implies that every vertex of $N_{G}(C)$ remains adjacent
to a nontrivial connected component, so the set of vertices of $X$ adjacent to
a nontrivial connected component does not change.

  3. 3.

There exists $v\in B$ such that the connected component of $G-Z$ that contains
$v$ is disjoint with $X$. Here, [30] branches on an important separator
separating $v$ from $X$. This does not work in the presence of weights, so we
need to proceed differently. We insert $v$ into $X$, set its weight to
$+\infty$, and recurse. Clearly, the hypothetical solution $Z$ remains a
solution and, if the guess is correct, $Z$ remains a multiway cut (with
regards to the enlarged set $X$). To see that we obtain progress, observe
that:

     * •

the parameter $k$ stays the same;

     * •

if $X$ is not an independent set, the recursive call returns No immediately;

     * •

otherwise, first observe that in the right guess $v$ has no neighbors in the
set $X$; therefore, for every $y\in N_{G}(C)$, there exists a connected
component $C_{y}$ of $C-\\{v\\}$ with $y\in N_{G}(C_{y})$ and as $v\in
N_{G}(C_{y})$ due to connectivity of $C$, $C_{y}$ is a new nontrivial
component; hence the number of vertices of $X$ that are incident with a
nontrivial connected component increases as both $v$ and the whole $N_{G}(C)$
are now adjacent to nontrivial connected components; furthermore, the number
of nontrivial connected components does not decrease as at least one new
nontrivial component is created in the place of $C$ since
$N_{G}(C)\neq\emptyset$.

Hence, the recursive step invokes $2^{\mathcal{O}(k\log k)}$ recursive
subcalls, in each obtaining the promised progress. Every single recursive call
takes polynomial time. Consequently, the branching algorithm takes
$2^{\mathcal{O}(k^{4}\log k)}n^{\mathcal{O}(1)}$ time and results in
$2^{\mathcal{O}(k^{4}\log k)}$ leaves of the recursion trees that give either
an immediate answer or a bipedal instance, which is passed to Section 3.2.

###  3.2 Solving a bipedal instance

We now show how to reduce a bipedal instance to a GDPC instance where every
bundle consists of at most two arcs and a single clause containing the heads
of these two arcs. These bundles are $2K_{2}$-free and $4$-bounded and hence
can be solved by Theorem 2.1 in randomized FPT time
$2^{k^{\mathcal{O}(1)}}n^{\mathcal{O}(1)}$. This is essentially repeating the
arguments of Lemma 7.1 of [18], adjusted for the vertex-deletion setting and
GDPC.

We start with a graph $H$ consisting of vertices $s$ and $t$. For every
component $C$ of $G-X$, proceed as follows. Recall that
$|N_{G}(C)|\in\\{1,2\\}$. Denote one of the elements of $N_{G}(C)$ as $s_{C}$
and the other as $t_{C}$, if present. For every $v\in V(G)$, create four
vertices $v_{s}^{+}$, $v_{s}^{-}$, $v_{t}^{+}$, $v_{t}^{-}$, arcs
$(v_{s}^{-},v_{s}^{+})$, $(v_{t}^{-},v_{t}^{+})$, and a clause
$v_{s}^{+}v_{t}^{+}$. The two constructed arcs and the constructed clause form
a bundle $B_{v}$ of weight $\omega(v)$. These are all the bundles that we will
construct; all subsequent arcs and clauses will not be in any bundle and thus
will be undeletable. For every connected component $C$ of $G-X$ and $uv\in
E(G[C])$, add arcs $(u_{s}^{+},v_{s}^{-})$, $(v_{s}^{+},u_{s}^{-})$
$(u_{t}^{+},v_{t}^{-})$, and $(v_{t}^{+},u_{t}^{-})$. For every $vs_{C}\in
E(G)$ with $v\in C$, add arcs $(s,v_{s}^{-})$ and $(v_{t}^{+},t)$. For every
$vt_{C}\in E(G)$ with $v\in C$, add arcs $(s,v_{t}^{-})$ and $(v_{s}^{+},t)$.

Finally, for every $(u,v)\in\mathcal{T}$ we proceed as follows. Note that $u$
and $v$ are in distinct connected components of $G-X$, say $C_{u}$ and
$C_{v}$. For every $x\in N_{G}(C_{u})\cap N_{G}(C_{v})$ we proceed as follows.
Say $x=\alpha_{C_{u}}$ and $x=\beta_{C_{v}}$ for $\alpha,\beta\in\\{s,t\\}$.
Add a clause $u^{-}_{\alpha}v^{-}_{\beta}$. This finishes the description of
the GDPC instance
$\mathcal{I}^{\prime}=(H,s,t,\mathcal{C},\mathcal{B},\omega,k,W)$. It is
immediate that the instance satisfies the prerequisities of Theorem 2.1 with
$b=4$.

It remains to check the equivalence of the instance $\mathcal{I}^{\prime}$ of
GDPC with the input instance $\mathcal{I}=(G,\mathcal{T},\omega,k,W)$ together
with the set $X$. We do it in the next two lemmata, completing the proof of
Theorem 1.1. Recall $T$ is the set of all terminal vertices.

######  Lemma 3.2.

If $Z\subseteq V(G)\setminus(X\cup T)$ is a solution that is also a multiway
cut for $X$, then $Z^{\prime}=\bigcup_{v\in Z}B_{v}\cap E(H)$ is a cut in
$\mathcal{I}^{\prime}$ that satisfies all clauses outside $B_{v}$ for $v\in
Z$.

###### Proof.

Assume first that $H-Z^{\prime}$ contains a path $P^{\prime}$ from $s$ to $t$.
Observe that there exists a component $C$ of $G-X$ and $\alpha\in\\{s,t\\}$
such that all internal vertices of $P^{\prime}$ are of the form
$v_{\alpha}^{+}$ or $v_{\alpha}^{-}$ for $v\in C$. Then, the path $P^{\prime}$
induces a path from $s_{C}$ to $t_{C}$ via $C$ in $G-Z$, a contradiction to
the assumption that $Z$ is a multiway cut for $X$.

Assume now that $Z^{\prime}$ violates a clause $v_{s}^{+}v_{t}^{+}$ in
$B_{v}$. Then first observe that $v\in C$, for a component $C$ of $G-X$. Let
$P_{s}^{\prime}$ be a path from $s$ to $v_{s}^{+}$ in $H-Z^{\prime}$ and let
$P_{t}^{\prime}$ be a path from $s$ to $v_{t}^{+}$ in $H-Z^{\prime}$. In
$G-Z$, the path $P_{s}^{\prime}$ yields a path $P_{s}$ from $s_{C}$ to $v$ and
the path $P_{t}^{\prime}$ (reversed) yields a path $P_{t}$ from $v$ to
$t_{C}$. Together, $P_{s}$ and $P_{t}$ yield a path from $s_{C}$ to $t_{C}$ in
$G-Z$, a contradiction to the assumption that $Z$ is a multiway cut.

Finally, assume that $Z^{\prime}$ violates a clause
$u^{-}_{\alpha}v^{-}_{\beta}$ for some $(u,v)\in\mathcal{T}$, where $C_{u}$
and $C_{v}$ are the components of $G-X$ containing $u$ and $v$, respectively,
$x\in N_{G}(C_{u})\cap N_{G}(C_{v})$, and $x=\alpha_{C_{u}}$,
$x=\beta_{C_{v}}$ for $\alpha,\beta\in\\{s,t\\}$. Let $P_{u}^{\prime}$ be a
path from $s$ to $u^{-}_{\alpha}$ in $H-Z^{\prime}$ and let $P_{v}^{\prime}$
be a path from $s$ to $v^{-}_{\beta}$ in $H-Z^{\prime}$. In $G-Z$,
$P_{u}^{\prime}$ yields a path $P_{u}$ from $u$ to $x=\alpha_{C_{u}}$ and
$P_{v}^{\prime}$ yields a path $P_{v}$ from $v$ to $x=\beta_{C_{v}}$.
Together, $P_{u}$ and $P_{v}$ yield a path from $u$ to $v$ in $G-Z$, a
contradiction to the assumption that $Z$ is a solution. ∎

######  Lemma 3.3.

If $Z^{\prime}$ is a cut in $\mathcal{I}^{\prime}$ that satisfies all clauses
that are not in bundles and $Z$ consists of those $v$ such that $Z^{\prime}$
violates $B_{v}$, then $Z$ is a solution to $\mathcal{I}$ that is also a
multiway cut for $X$.

###### Proof.

We first show that $Z$ is a multiway cut for $X$. By contradiction, assume
that there exists a component $C$ of $G-X$ and a path $P$ from $s_{C}$ to
$t_{C}$ via $C$ that avoids $Z$. Let $v$ be an arbitrary vertex of $P$ in $C$.
Then, the prefix of $P$ from $s_{C}$ to $v$ lifts to a path $P_{s}^{\prime}$
in $H-Z^{\prime}$ from $s$ to $v_{s}^{+}$. Similarly, the suffix of $P$ from
$v$ to $t_{C}$, reversed, lifts to a path $P_{t}^{\prime}$ in $H-Z^{\prime}$
from $s$ to $v_{t}^{+}$. Hence, $Z^{\prime}$ violates the clause
$v_{s}^{+}v_{t}^{+}$ and hence the bundle $B_{v}$, which is a contradiction.

Consider now $(u,v)\in\mathcal{T}$ and assume there is a path $P$ from $u$ to
$v$ in $G-Z$. Since $Z$ is a multiway cut for $X$, $P$ contains at most one
vertex of $X$. Since $u$ and $v$ are in distinct connected components of $G-X$
(say, $C_{u}$ and $C_{v}$, respectively), $P$ contains at least one vertex of
$X$. That is, $P$ starts in $u$, continues via $C_{u}$ to a vertex $x\in
N_{G}(C_{u})\cap N_{G}(C_{v})$, and then continues via $C_{v}$ to $v$. The
prefix of $P$ from $u$ to $x$ (reversed) lifts to a path $P_{u}^{\prime}$ in
$H-Z^{\prime}$ from $s$ to $u_{\alpha}^{-}$ where $x=\alpha_{C_{u}}$,
$\alpha\in\\{s,t\\}$. The suffix of $P$ from $x$ to $v$ lifts to a path
$P_{v}^{\prime}$ in $H-Z^{\prime}$ from $s$ to $v_{\beta}^{-}$ where
$x=\beta_{C_{v}}$, $\beta\in\\{s,t\\}$. Hence, the clause
$u_{\alpha}^{-}v_{\beta}^{-}$ is violated by $Z^{\prime}$, a contradiction.
This finishes the proof of Lemma 3.3. ∎

With the discussion above, Lemmata 3.2 and 3.3 conclude the proof of Theorem
1.1.

##  4 Group Feedback Edge/Vertex Set

This section is devoted to the proof of Theorem 1.3. In fact, we just closely
follow the arguments of [9] and verify that they work also in the weighted
setting. The algorithm reduces the problem to multiple instances of Multiway
Cut. Here, in the presence of weights, we apply the algorithm of Theorem 1.1
to solve Weighted Multiway Cut (in particular, we use Corollary 1.2).

As discussed in Section 2, we can focus on the vertex-deletion variant Group
Feedback Vertex Set Using iterative compression (Section 2) we assume that,
apart from the input instance $(G,\psi,\omega,k,W)$, we are given a set
$X\subseteq V(G)$ of size at most $k+1$ such that $G-X$ has no non-null cycles
and the goal is to find a solution disjoint from $X$. We set
$\omega(x)=+\infty$ for every $x\in X$. Recall that in this problem the input
graph $G$ is equipped with a group $\Gamma$.

For a graph $H$ with group labels $\psi$, a _consistent labeling_ is a
function $\phi:V(H)\to\Gamma$ such that $\phi(v)=\phi(u)+\psi(e,u)$ for every
$e=uv\in E(H)$. It is easy to see that $(H,\psi)$ has no non-null cycle if and
only it admits a consistent labeling.

#### Untangling.

By standard relabelling process, we can assume that $\psi(e,v)=0$ for every
$e\in E(G-X)$ and $v\in e$; we call such an instance _untangled_. Since $G-X$
has no non-null cycles, there exists $\phi:V(G)\setminus X\to\Gamma$ such that
for every $e=uv\in E(G-X)$ we have $\phi(v)=\phi(u)+\psi(e,u)$. For every
$e=uv\in E(G-X)$ we relabel $\psi(e,u):=\phi(u)+\psi(e,u)-\phi(v)$ and
$\psi(e,v):=\phi(v)+\psi(e,v)-\phi(u)$. Furthermore, for every $e=uv\in E(G)$
with $u\in X$ but $v\notin X$, we relabel $\psi(e,u):=\psi(e,u)-\phi(v)$ and
$\psi(e,v)=\phi(v)+\psi(e,v)$. It is easy to check that, after the above
relabeling, for every closed walk $C$ it does not change whether $\psi(C)=0$
or not, while $\psi(e,v)=0$ for every $e\in E(G-X)$ and $v\in e$.

#### Extending a labeling of $X$.

We now observe that, given a labeling $\phi_{0}:X\to\Gamma$, finding a set
$Z\subseteq V(G)\setminus X$ such that $\phi_{0}$ extends to a consistent
labeling of $G-Z$ reduces to Multiway Cut.

######  Lemma 4.1.

There exists a randomized FPT algorithm with running time bound
$2^{k^{\mathcal{O}(1)}}n^{\mathcal{O}(1)}$ that, given an untangled instance
$(G,\psi,\omega,k,W,X)$ and a function $\phi_{0}:X\to\Gamma$, checks if there
is a set $Z\subseteq V(G)\setminus X$ of cardinality at most $k$ and weight at
most $W$ such that $G-Z$ admits a consistent labeling extending $\phi_{0}$.

###### Proof.

First, we check if for every $e=uv\in E(G[X])$ we indeed have
$\phi_{0}(v)=\phi_{0}(u)+\psi(e,u)$, as otherwise the answer is No. We
construct a Multiway Cut instance as follows. Let $T$ be the set of those
elements $g\in\Gamma$ such that there exists $uv\in E(G)$, $u\in X$, $v\notin
X$, and $g=\phi_{0}(u)+\psi(uv,u)$ (i.e., in a consistent labeling extending
$\phi_{0}$, we would need to assign $g$ to $v$). Note that $|T|\leq|E(G)|$.
Let $H$ be the graph consisting of a copy of $G-X$ (with weights inherited),
the set $T$ as additional vertices, and for every $uv\in E(G)$, $u\in X$,
$v\notin X$, an edge from $\phi_{0}(u)+\psi(uv,u)\in T$ to $v$. A direct check
shows that it suffices to solve the obtained Multiway Cut instance
$(G,T,\omega,k,W)$ and return the answer (the proof of the equivalence is
spelled out in the proof of Lemma 7 in [9]). ∎

#### Enumerating reasonable labelings of $X$.

Since $\Gamma$ can be large, we cannot enumerate all labelings
$\phi_{0}:X\to\Gamma$. In [9], a procedure is presented that enumerates a
family of $2^{\mathcal{O}(k\log k)}$ labelings such that, for every solution
$Z$, there is a consistent labeling of $G-Z$ that extends one of the
enumerated labelings.

The main trick lies in the following reduction step. For $v\in V(G)\setminus
X$ and $x\in X$, we define a flow graph $F(v,x)$ as follows. Let $\Gamma_{x}$
be the set of those $g\in\Gamma$ such that there exists $xu\in E(G)$, $u\notin
X$ and $\psi(xu,u)=g$. Note that $|\Gamma_{x}|\leq|E(G)|$. The graph $F(v,x)$
consists of a copy of $G-X$, the set $\Gamma_{x}$ as additional vertices and,
for every $xu\in E(G)$ with $u\notin X$, an edge $u\psi(xu,u)$.

We have the following statement.

######  Lemma 4.2 (Lemma 8 of [9]).

If there are $k+2$ paths in $F(v,x)$ from $v$ to distinct elements of
$\Gamma_{x}$ that are vertex-disjoint except for $v$, then $v$ is contained in
every solution of cardinality at most $k$.

The condition of Lemma 4.2 can be checked in polynomial time. If such a vertex
$v$ is discovered, we can delete it, decrease $k$ by one, decrease $W$ by
$\omega(v)$, and repeat the analysis.

Fix $x,y\in X$, $x\neq y$. An _external path_ from $x$ to $y$ is a path with
endpoints $x$ and $y$ and all internal vertices in $G-X$; note that an edge
$xy$ is also an external path. Let $\Gamma(x,y)$ be the set of all elements
$g\in\Gamma$ such that there exists an external path $P$ from $x$ to $y$ with
$\psi(P)=g$. We have also the following statement.

######  Lemma 4.3 (Lemma 9 of [9]).

If there is no vertex $v$ as in Lemma 4.2, but for some $x,y\in X$, $x\neq y$
we have $|\Gamma(x,y)|\geq k^{3}(k+1)^{2}+2$, then there is no solution of
cardinality at most $k$.

The condition of Lemma 4.3 can be again checked in polynomial time and, if we
find that $\Gamma(x,y)$ is too large for some $x,y\in X$, $x\neq y$, we return
No.

Otherwise, we enumerate resonable labelings $\phi_{0}:X\to\Gamma$ as follows.
First, we guess how $X$ is partitioned into connected components of $G-Z$ for
a hypothetical solution $Z$; in every connected component, we can set
$\phi_{0}$ independently. Let $Y\subseteq X$ be a set of vertices guessed to
be in the same connected component of $G-Z$; note that necessarily $Y$ needs
to live in the same connected component of $G$, so $\Gamma(x,y)\neq\emptyset$
for every distinct $x,y\in Y$. Fix $y\in Y$ and set $\phi_{0}(y)=0$. Note that
in a consistent labeling of $G-Z$ that assigns the value of $y$ to $0$, for
$x\in Y\setminus\\{y\\}$ the value assigned to $x$ needs to be in
$\Gamma(y,x)$ as a path $P$ from $y$ to $x$ in $G-Z$ has
$\psi(P)\in\Gamma(y,x)$. By Lemma 4.3, there are only $\mathcal{O}(k^{5})$
options for $\phi_{0}(x)$. Overall, this gives $2^{\mathcal{O}(k\log k)}$
options for $\phi_{0}$, as desired.

This finishes the proof of Theorem 1.3.

##  5 Directed Subset Feedback Edge/Vertex Set

This section is devoted to the proof of Theorem 1.5. As discussed in Section
2, we can restrict ourselves to the edge-deletion version, that is, to the
Directed Subset Feedback Edge Set problem. Furthermore, we can assume that red
edges are undeletable (of weight $+\infty$): for every $e=(u,v)\in R$, we
subdivide $e$, replacing it with a path $u\to x_{e}\to v$; the edge
$(u,x_{e})$ becomes red and of weight $+\infty$, and $(x_{e},v)$ is not red
and inherits the weight of $e$.

Let $\mathcal{I}=(G,R,\omega,k,W)$ be the input instance. Using iterative
compression, we can assume we are given access to a set $X\subseteq V(G)$ of
size at most $k+1$ such that $G-X$ has no cycle involving a red edge.

Let $Z\subseteq E(G)\setminus R$. Observe that $G-Z$ has no cycle containing a
red edge if and only if for every $(u,v)\in R$, there is no path from $v$ to
$u$ in $G-Z$. The latter condition is equivalent to $u$ and $v$ being in
different strong connected components of $G-Z$. We will use the above
reformulations of the desired separation property interchangably.

Let $Z$ be a sought solution. We start with some branching steps. First, we
guess how the vertices of $X$ are partitioned between strong connected
components of $G-Z$. We identify vertices of $X$ that are guessed to be in the
same connected components of $G-Z$; note that in the branch where the guess is
correct, this does not change whether two vertices of $G-Z$ are in the same
strong connected component or not. Henceforth, by somewhat abusing the
notation, we can assume that the vertices of $X$ lie in distinct strong
connected components of $G-Z$. We guess the order of $X$ in a topological
ordering of the strong connected components of $G-Z$; that is, we guess an
enumeration of $X$ as $x_{1},x_{2},\ldots,x_{|X|}$ such that in $G-Z$ there is
no path from $x_{j}$ to $x_{i}$ for $1\leq i<j\leq|X|$. Since initially
$|X|\leq k+1$, there are $2^{\mathcal{O}(k\log k)}$ branches up to this point
and we retain the property $|X|\leq k+1$.

We now construct a GDPC instance $\mathcal{I}^{\prime}$. We first construct a
graph $H$ as follows. We start from $2|X|+1$ copies of the graph $G$, denoted
$G^{a}$ for $1\leq a\leq 2|X|+1$. For $u\in V(G)$, let $u^{a}$ be the copy of
$u$ in the graph $G^{a}$. For every $1\leq a<b\leq 2|X|+1$ and every $u\in
V(G)$ we add an arc $(u^{b},u^{a})$. For every red arc $(u,v)\in R$ and every
$1\leq a\leq|X|$, we add an arc $(u^{2a},v^{2a+1})$ Finally, we introduce two
new vertices $s$ and $t$ and, for every $1\leq a\leq X$ and $1\leq b\leq
2|X|+1$ an arc $(s,x_{a}^{b})$ if $2a\geq b$ and an arc $(x_{a}^{b},t)$ if
$2a<b$.

For every $e=(u,v)\in E(G)\setminus R$, we make a bundle $B_{e}$ consisting of
all $2|X|+1$ copies of the arc $e$. We set $\omega(B_{e})=\omega(e)$. This
finishes the description of a GDPC instance
$\mathcal{I}^{\prime}=(H,s,t,\emptyset,\mathcal{B},\omega,k,W)$ with no
clauses. See Figure 1.

Figure 1: Illustration of the reduction of Section 5. All copies of an edge
$e$ of $G$ form a bundle $B_{e}$: here blue edges form one bundle for an edge
$(u,v)$ and magenta edges form another bundle for an edge $(v,w)$.
Furthermore, if $(v,w)$ is red, then there is an extra arc $(v^{2a},w^{2a+1})$
for every $1\leq a\leq|X|$, depicted in red. Intutively, this arc, together
with arcs $(s,x_{a}^{2a})$ and $(x_{a}^{2a+1},t)$ asks to destroy all closed
walks that pass both through $(v,w)$ and $x_{a}$.

We observe that the obtained instance has pairwise linked deletable edges, due
to the existence of crisp arcs $(u^{b},u^{a})$ for every $u\in V(G)$ and
$1\leq a<b\leq 2|X|+1$. Furthermore, every bundle contains at most $2|X|+1\leq
2k+3$ deletable edges. Thus, by Theorem 2.2, we can resolve it in randomized
FPT time $2^{\mathcal{O}(k^{8}\log k)}n^{\mathcal{O}(1)}$.

It remains to show that the answer to $\mathcal{I}^{\prime}$ is actually
meaningful. This is done in the next two lemmata that complete the proof of
Theorem 1.5.

######  Lemma 5.1.

Let $Z\subseteq E(G)\setminus R$ be such that $G-Z$ has no cycle containing a
red edge, and, additionally, all vertices of $X$ lie in distinct strong
connected components of $G-Z$ and there is no path from $x_{j}$ to $x_{i}$ in
$G-Z$ for every $1\leq i<j\leq|X|$. Then $Z^{\prime}=\bigcup_{e\in Z}B_{e}$ is
a solution to $\mathcal{I}^{\prime}$.

###### Proof.

By contradiction, assume that $G-Z^{\prime}$ contains a path $P^{\prime}$ from
$s$ to $t$. Pick such a path $P^{\prime}$ that minimizes the number of indices
$a$ such that $P^{\prime}$ contains a vertex of $G^{a}$. Let
$a\in\\{1,\ldots,2|X|+1\\}$ be the minimum index such that $P^{\prime}$
contains a vertex of $G^{a}$ and let $u^{a}\in V(P^{\prime})$ be the last
vertex of $P^{\prime}$ in $G^{a}$. Observe that if $(s,x_{i}^{b})$ is the
first edge of $P^{\prime}$, then $H$ also contains crisp edges
$(s,x_{i}^{b^{\prime}})$ for every $1\leq b^{\prime}\leq b$. Hence, by the
minimality of $a$, we can modify $P^{\prime}$ so that the entire prefix from
$s$ to $u^{a}$ is contained in $G^{a}$: whenever $P^{\prime}$ traverses a
vertex $v^{a^{\prime}}$, we instead traverse the vertex $v^{a}$.

Symmetrically, by choosing $a$ to be maximum such that $P^{\prime}$ contains a
vertex of $G^{a}$ and $u^{a}\in V(P^{\prime})$ to be the first vertex of
$P^{\prime}$ in $G^{a}$, we observe that we can replace the suffix of
$P^{\prime}$ from $u^{a}$ to $t$ so that it is completely contained in
$G^{a}$.

Observe that the only edges of $H$ that lead from $G^{a}$ to $G^{b}$ for $a<b$
are edges of the form $(u^{2a},v^{2a+1})$ for $1\leq a\leq|X|$ and red arcs
$(u,v)$. Hence, we can assume that the path $P^{\prime}$ is of one of the
following two types:

  1. 1.

All internal vertices of $P^{\prime}$ lie in the same graph $G^{a}$.

  2. 2.

For some $1\leq a\leq|X|$, the path $P^{\prime}$ first goes from $s$ via
$G^{2a}$, then uses one edge $(u^{2a},v^{2a+1})$ for some $(u,v)\in R$, and
then continues via $G^{2a+1}$ to $t$.

In the first case, let $(s,x_{j}^{a})$ be the first edge of $P^{\prime}$ and
let $(x_{i}^{a},t)$ be the last edge of $P^{\prime}$. By construction of $H$,
we have $2j\geq a>2i$, so $j>i$. Thus, $P^{\prime}$ without the first and the
last edge gives a path in $G-Z$ from $x_{j}$ to $x_{i}$ for some $j>i$, a
contradiction.

In the second case, let $(s,x_{j}^{2a})$ be the first edge of $P^{\prime}$ and
let $(x_{i}^{2a+1},t)$ be the last edge of $P^{\prime}$. By construction of
$H$, we have $2j\geq 2a$ and $2a+1>2i$, so $j\geq i$. If $j>i$, $P^{\prime}$
without the first and the last edge gives a path from $x_{j}$ to $x_{i}$,
again a contradiction as in the first case. If $j=i$, then the subpath of
$P^{\prime}$ from $v^{2a+1}$ to $x_{i}^{2a+1}$ gives a path from $v$ to
$x_{i}$ in $G-Z$ and the subpath of $P^{\prime}$ from $x_{j}^{2a}$ to $u^{2a}$
gives a path from $x_{j}$ to $u$ in $G-Z$. As $j=i$, this gives a path from
$v$ to $u$ in $G-Z$, a contradiction as $(u,v)$ is a red edge. ∎

######  Lemma 5.2.

Let $Z^{\prime}$ be a cut in $\mathcal{I}^{\prime}$ and let $Z=\\{e\in
E(G)\setminus R~{}|~{}B_{e}\cap Z^{\prime}\neq\emptyset\\}$. Then $G-Z$
contains no cycle containing a red edge.

###### Proof.

By contradiction, assume $G-Z$ contains a path $P$ from $v$ to $u$ for some
$(u,v)\in R$. Since $G-X$ contains no such path, $P$ contains a vertex of $X$.
Let $x_{i}\in V(P)$. Let $P_{v}$ be the prefix of $P$ from $v$ to $x_{i}$ and
let $P_{u}$ be the suffix of $P$ from $x_{i}$ to $u$. Consider the copy
$P_{v}^{2i+1}$ of $P_{v}$ in $G^{2i+1}$ and the copy $P_{u}^{2i}$ of $P_{u}$
in $G^{2i}$. Then, since $Z^{\prime}$ contains no edge of $B_{e}$ for any
$e\in E(P)$, $P_{v}^{2i+1}$ and $P_{u}^{2i}$ are disjoint with $Z^{\prime}$.
This is a contradiction, as a concatenation of $(s,x_{i}^{2i})$, $P_{u}^{2i}$,
$(u^{2i},v^{2i+1})$, $P_{v}^{2i+1}$, and $(x_{i}^{2i+1},t)$ is a path from $s$
to $t$ in $H-Z^{\prime}$. ∎

##  6 Conclusions

We showed fixed-parameter tractability of a number of weighted graph
separation problems. Our first result extends a recent result of Galby et al.
[13], who considered the special case of weighted Multicut in trees. For all
our algorithms, we revisited an old combinatorial approach to the problem,
adjusted it to weights, and provided a reduction to GDPC in one of its
tractable variants. The application of the technique of flow-augmentation is
hidden in the algorithms for GDPC (Theorems 2.1 and 2.2).

We would like to highlight here one graph separation problem that resisted our
attempts: Directed Symmetric Multicut. Here, the input consists of a directed
graph $G$, weights $\omega:E(G)\to\mathbb{Z}_{+}$ (that is, we consider an
edge-deletion variant, but, as we are working with directed graphs, it is
straightforward to reduce between edge- and vertex-deletion variants),
integers $k$ and $W$, and a set $\mathcal{T}\subseteq\binom{V(G)}{2}$ of
unordered pairs of vertices of $G$. The problem asks for an existence of a set
$Z\subseteq E(G)$ of size at most $k$ and total weight at most $W$ such that
for every $uv\in\mathcal{T}$, the vertices $u$ and $v$ are not in the same
strong connected component of $G-Z$ (i.e., $Z$ cuts all paths from $u$ to $v$
or cuts all paths from $v$ to $u$). Eiben et al. [12] considered the
parameterized complexity of Directed Symmetric Multicut and gave partial
results, but the main problem of the parameterized complexity of Directed
Symmetric Multicut parameterized by $k$ remains open, even in the unweighted
setting.

To motivate the Directed Symmetric Multicut problem further, we point out that
it has a very natural reformulation in the context of _temporal CSPs_ , that
is, constraint satisfiaction problems with domain $\mathbb{Q}$ and access to
the order on $\mathbb{Q}$. More formally, a _temporal CSP relation_ is an FO
formula with a number of free variables that can be accessed via comparison
predicates $x=y$, $x\neq y$, $x<y$, and $x\leq y$. A _temporal CSP language_
is a set of temporal CSP predicates. For a temporal CSP language $\Lambda$, an
instance of CSP($\Lambda$) consists of a set of variables $X$ and a set
$\mathcal{C}$ of constraints; each constraint is an application of a formula
from $\Lambda$ to a tuple of variables from $X$. The goal is to find an
assignment $\alpha:X\to\mathbb{Q}$ that satisfies all constraints. In the Max
SAT($\Lambda$) problem, we are additionally given an integer $k$ and the goal
is satisfy all but $k$ constraints (i.e., delete at most $k$ constraints to
get a satisfiable instance).

In various CSP contexts, the Max SAT($\Lambda$) problem is usually hard, yet
the parameterized complexity landscape with $k$ as a parameter is often rich;
see e.g. the recent dichotomy for the Boolean domain [21] and references
therein. The P vs NP dichotomy for temporal CSP($\Lambda$) is known since over
a decade [1]. Can we establish parameterized complexity dichotomy for temporal
Max SAT($\Lambda$) parameterized by $k$?

One of the most prominent examples of a temporal CSP languages is
$\Lambda=\\{x=y,x\neq y,x<y,x\leq y\\}$, called a _point algebra_. Here,
CSP($\Lambda$) is known to be polynomial-time solvable. We observe that Max
SAT($\Lambda$) is equivalent to (unweighted) Directed Symmetric Multicut.

In one direction, given an unweighted Directed Symmetric Multicut instance
$(G,\mathcal{T},k)$, we set $X=V(G)$, model every arc $(u,v)\in E(G)$ as a
constraint $u\leq v$ and each pair $uv\in\mathcal{T}$ as $k+1$ copies of a
constraint $u\neq v$. Intuitively, a desired assignment
$\alpha:V(G)\to\mathbb{Q}$ maps all vertices of the same strong connected
component to the same number, and otherwise sorts the strong connected
components according to a topological ordering.

The other direction is slightly more involved due to some technicalities.
First, we replace each constraint $x=y$ with a pair of constraints $x\leq y$
and $y\leq x$; note that we will never want to delete both such constraints.
Similarly, we replace each constraint $x<y$ with $x\neq y$ and $x\leq y$;
again we will never want to delete both resulting constraints. Thus, we can
assume that the instance uses only $x\neq y$ and $x\leq y$ constraints. Then,
for every constraint $x\neq y$, we introduce fresh copies $x^{\prime}$ and
$y^{\prime}$ of $x$ and $y$, introduce constraints $x\leq x^{\prime}$,
$x^{\prime}\leq x$, $y\leq y^{\prime}$, $y^{\prime}\leq y$, and $k+1$ copies
of $x^{\prime}\neq y^{\prime}$, and delete $x\neq y$. Now deleting $x\neq y$
is equivalent to deleting one of the inequalities, say $x\leq x^{\prime}$, and
setting $x^{\prime}$ to some very small number different than $y$ and
$y^{\prime}$. Thus, we end up in an instance where only $x\leq y$ and $x\neq
y$ constraints are present, and the latter constraints are always undeletable
(appear in batches of $k+1$ copies). Now, we can directly model it as Directed
Symmetric Multicut: we set $V(G)=X$, for every constraint $x\leq y$ we add an
arc $(x,y)$ and for every batch of $k+1$ constraints $x\neq y$ we add a pair
$xy$ to $\mathcal{T}$.

With a very similar reduction we observe that for
$\Lambda^{\prime}=\\{x<y,x\leq y\\}$ the problem Max SAT($\Lambda^{\prime}$)
is equivalent to (unweighted) Directed Subset Feedback Edge Set: every
constraint $x<y$ is equivalent to a red arc $(x,y)$ and every constraint
$x\leq y$ is equivalent to a non-red arc $(x,y)$.

Therefore, the unresolved status of the parameterized complexity of Directed
Symmetric Multicut stands as the main obstacle to obtain a dichotomy for
parameterized complexity of Max SAT($\Lambda$) for temporal CSP languages
$\Lambda$, parameterized by the deletion budget $k$.

## References

  * [1] Manuel Bodirsky and Jan Kára.  The complexity of temporal constraint satisfaction problems.  J. ACM, 57(2):9:1–9:41, 2010.  doi:10.1145/1667053.1667058.
  * [2] Nicolas Bousquet, Jean Daligault, and Stéphan Thomassé.  Multicut is FPT.  SIAM J. Comput., 47(1):166–207, 2018.  doi:10.1137/140961808.
  * [3] Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon.  A fixed-parameter algorithm for the directed feedback vertex set problem.  J. ACM, 55(5), 2008.
  * [4] Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk.  Designing FPT algorithms for cut problems using randomized contractions.  SIAM J. Comput., 45(4):1171–1229, 2016.  doi:10.1137/15M1032077.
  * [5] Rajesh Chitnis, László Egri, and Dániel Marx.  List ${H}$-coloring a graph by removing few vertices.  Algorithmica, 78(1):110–146, 2017.  doi:10.1007/s00453-016-0139-6.
  * [6] Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and Dániel Marx.  Directed subset feedback vertex set is fixed-parameter tractable.  ACM Trans. Algorithms, 11(4):28:1–28:28, 2015.  doi:10.1145/2700209.
  * [7] Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx.  Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset.  SIAM J. Comput., 42(4):1674–1696, 2013.
  * [8] Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh, and Magnus Wahlström.  Randomized contractions meet lean decompositions.  ACM Trans. Algorithms, 17(1):6:1–6:30, 2021.  doi:10.1145/3426738.
  * [9] Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk.  On group feedback vertex set parameterized by the size of the cutset.  Algorithmica, 74(2):630–642, 2016.  doi:10.1007/s00453-014-9966-5.
  * [10] Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk.  On multiway cut parameterized above lower bounds.  TOCT, 5(1):3, 2013.  URL: http://doi.acm.org/10.1145/2462896.2462899, doi:10.1145/2462896.2462899.
  * [11] Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk.  Subset feedback vertex set is fixed-parameter tractable.  SIAM J. Discrete Math., 27(1):290–309, 2013.  URL: http://dx.doi.org/10.1137/110843071, doi:10.1137/110843071.
  * [12] Eduard Eiben, Clément Rambaud, and Magnus Wahlström.  On the parameterized complexity of symmetric directed multicut.  In IPEC 2022, 2022.  To appear; available at https://arxiv.org/abs/2208.09017.
  * [13] Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, and Prafullkumar Tale.  Parameterized complexity of weighted multicut in trees.  In WG 2022, 2022.
  * [14] Sylvain Guillemot.  FPT algorithms for path-transversal and cycle-transversal problems.  Discrete Optimization, 8(1):61–71, 2011.
  * [15] Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, and Manuel Sorge.  Fixed-parameter tractability of directed multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation.  CoRR, abs/2207.07425, 2022.  arXiv:2207.07425, doi:10.48550/arXiv.2207.07425.
  * [16] Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida.  Half-integrality, lp-branching, and FPT algorithms.  SIAM J. Comput., 45(4):1377–1411, 2016.  doi:10.1137/140962838.
  * [17] Ken-ichi Kawarabayashi and Mikkel Thorup.  The minimum k-way cut of bounded size is fixed-parameter tractable.  In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 160–169. IEEE Computer Society, 2011.  doi:10.1109/FOCS.2011.53.
  * [18] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Solving hard cut problems via flow-augmentation.  CoRR, abs/2007.09018, 2020.  URL: https://arxiv.org/abs/2007.09018, arXiv:2007.09018.
  * [19] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Solving hard cut problems via flow-augmentation.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 149–168. SIAM, 2021.  doi:10.1137/1.9781611976465.11.
  * [20] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Directed flow-augmentation.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 938–947. ACM, 2022.  doi:10.1145/3519935.3520018.
  * [21] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Flow-augmentation III: complexity dichotomy for boolean csps parameterized by the number of unsatisfied constraints.  CoRR, abs/2207.07422, 2022.  arXiv:2207.07422, doi:10.48550/arXiv.2207.07422.
  * [22] Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlström.  Fixed-parameter tractability of multicut in directed acyclic graphs.  SIAM J. Discrete Math., 29(1):122–144, 2015.  URL: http://dx.doi.org/10.1137/120904202, doi:10.1137/120904202.
  * [23] Stefan Kratsch and Magnus Wahlström.  Compression via matroids: A randomized polynomial kernel for odd cycle transversal.  ACM Transactions on Algorithms, 10(4):20, 2014.  URL: http://doi.acm.org/10.1145/2635810, doi:10.1145/2635810.
  * [24] Stefan Kratsch and Magnus Wahlström.  Representative sets and irrelevant vertices: New tools for kernelization.  J. ACM, 67(3):16:1–16:50, 2020.  doi:10.1145/3390887.
  * [25] Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh.  When recursion is better than iteration: A linear-time algorithm for acyclicity with few error vertices.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1916–1933. SIAM, 2018.  doi:10.1137/1.9781611975031.125.
  * [26] Dániel Marx.  Parameterized graph separation problems.  Theor. Comput. Sci., 351(3):394–406, 2006.
  * [27] Dániel Marx, Barry O’Sullivan, and Igor Razgon.  Finding small separators in linear time via treewidth reduction.  ACM Transactions on Algorithms, 9(4):30, 2013.  URL: http://doi.acm.org/10.1145/2500119, doi:10.1145/2500119.
  * [28] Dániel Marx and Igor Razgon.  Constant ratio fixed-parameter approximation of the edge multicut problem.  Inf. Process. Lett., 109(20):1161–1166, 2009.  doi:10.1016/j.ipl.2009.07.016.
  * [29] Dániel Marx and Igor Razgon.  Fixed-parameter tractability of multicut parameterized by the size of the cutset.  In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 469–478. ACM, 2011.  doi:10.1145/1993636.1993699.
  * [30] Dániel Marx and Igor Razgon.  Fixed-parameter tractability of multicut parameterized by the size of the cutset.  In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 469–478. ACM, 2011.  doi:10.1145/1993636.1993699.
  * [31] Dániel Marx and Igor Razgon.  Fixed-parameter tractability of multicut parameterized by the size of the cutset.  SIAM J. Comput., 43(2):355–388, 2014.  URL: http://dx.doi.org/10.1137/110855247, doi:10.1137/110855247.
  * [32] Marcin Pilipczuk and Magnus Wahlström.  Directed multicut is W[1]-hard, even for four terminal pairs.  ACM Trans. Comput. Theory, 10(3):13:1–13:18, 2018.  doi:10.1145/3201775.
  * [33] Igor Razgon and Barry O’Sullivan.  Almost 2-SAT is fixed-parameter tractable.  J. Comput. Syst. Sci., 75(8):435–450, 2009.
  * [34] Bruce A. Reed, Kaleigh Smith, and Adrian Vetta.  Finding odd cycle transversals.  Oper. Res. Lett., 32(4):299–301, 2004.  doi:10.1016/j.orl.2003.10.009.
  * [35] Saket Saurabh.  What’s next? future directions in parameterized complexity, 2017.  Recent Advances in Parameterized Complexity school, Tel Aviv, December 2017.  URL: https://rapctelaviv.weebly.com/uploads/1/0/5/3/105379375/future.pdf.


# A Study on the Inductance and Thermal Regression and Optimization for
Automatic Layout Design of Power Modules

Victor Parque, Aiki Nakamura, Tomoyuki Miyashita  Department of Modern
Mechanical Engineering
Waseda University
3-4-1 Okubo, Shinjuku, Tokyo, Japan
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Power modules with excellent inductance and temperature metrics are
significant to meet the rising sophistication of energy demand in new
technologies. In this paper, we use a surrogate-based approach to render
optimal layouts of power modules with feasible and attractive inductance-
temperature ratios at low computational budget. In particular, we use the
class of feedforward networks to estimate the surrogate relationships between
power module layout-design variables and inductance-temperature factors
rendered from simulations; and Differential Evolution algorithms to optimize
and locate feasible layout configurations of power module substrates
minimizing inductance and temperature ratios. Our findings suggest the
desirable classes of feedforward networks and gradient-free optimization
algorithms being able to estimate and optimize power module layouts
efficiently and effectively.

###### Index Terms:

power modules, neural networks, automatic layout design, system
identification, optimization

##  I Introduction

Power modules are essential to meet the rising sophistication and demands for
efficient and cost-effective conversion of electrical energy in new consumer
and industrial technology. New materials, such as Silicon Carbide (SiC), and
new circuit manufacturing methods, such as 3-dimensional wiring, have enabled
new frontiers towards the smaller size and the higher speeds of switching
while ensuring reasonable thermal loads.

When designing the layout and the packaging structures of power modules,
minimizing the (parasitic) inductance and the heat dissipation are relevant to
meet loads reliably and safely[1, 2]. As such, approaches derived from
gradient-free optimization techniques have attracted the attention of the
community. For instance, [3] use Genetic Algorithm (GA) and Dijkstra for
layout optimization of a buck converter board. [4] used GA to design layouts
of silicon carbide (SiC) modules with low parasitic inductance and resistance
and small footprint. [5] used sequential quadratic programming (SQP) to
optimize the number of LEDs and their placement in a substrate of a multi-chip
LED package. Hao et, al. [6] used NSGA-II with cycle-route limits and ANSYS
Q3D for minimal parasitic inductance, Abe et. al.[7] proposed a routing-based
approach for three-dimensional power modules with minimal inductance, and
Nakamura et. al. [8] used NSGA-II considering inductance and thermal
performance as goals.

It is well understood that both (expert-based) iterative design and
optimization frameworks are time and resource consuming. Also, when new
layouts are to be designed, knowledge of previous iterations is lost in
population-based schemes. In this paper, we aim at finding optimal
configurations of design-layout variables of power modules by a surrogate-
based approach through nonlinear regression and optimization machinery. Thus,
our key contributions are:

Figure 1: Overview of the layout of a power module.

  * •

We performed computational experiments outlining the regression capability of
$n=36$ parameters involving the layout-design of components of a class of
power module (Fig. 1)[8] to performance factors in terms of control path
inductance ($f_{1}$), main path inductance ($f_{2}$), and maximum temperature
in the substrate ($f_{3}$). Our results show the attractive regression
performance of a class of network with 10 layers and 7580 nodes, achieving
Mean Squared Error (MSE) in the order of $10^{-6}$ for $f_{1}$, $10^{-7}$ for
$f_{2}$, and $0.19$ for $f_{3}$.

  * •

We used the best obtained surrogate functions (neural networks) to
optimize/locate the feasible/attractive layout configurations of power module
substrates aiming to minimize a weighted-composition function of control path
inductance, main path inductance, and maximum temperature in the substrate by
using Differential Evolution machinery. Our computational experiments show the
feasibility of convergence at feasible regions at low computational budgets.

##  II Approach

Our approach is inspired by the use of surrogates in expensive optimization
problems[9]. We first aim at computing

$\lambda_{i}:x\rightarrow f_{i},$ (1)

in which $x\in\mathbb{R}^{n}$ is the set of observations of design variables
of power module layouts, and $f_{i}$ is the set of observations of performance
metrics of the power modules obtained from NSGA-II and design/simulation
experiments[8]. We consider the power module substrate studied in [7] and [8],
which considers the $n=36$ parameters to determine the locations/layout of
components and to minimize the control path inductance ($f_{1}$), the main
path inductance ($f_{2}$), and the maximum temperature in the substrate
($f_{3}$). The mapping $\lambda_{i}$ can be computed by Feedforward Networks
or Symbolic Regression schemes; and once reasonable mapping functions
$\lambda_{i}$ are found, we aim at solving the following

$\displaystyle\underset{x}{\text{Minimize}}$ $\displaystyle
F(x)=\sum_{i=1}^{3}w_{i}\lambda_{i}(x)$ (2) subject to $\displaystyle
x\in\mathbf{X}$

where $x\in\mathbb{R}^{n}$ is the optimization variable encoding the layout of
the power module, $\mathbf{X}$ is the search space of feasible power modules,
and $w_{i}$ are weights encoding the user-defined preference on the
performance metric (inductances and temperature). Although the above-mentioned
approach has been used in expensive optimization problems[9], the use of
surrogates in power module optimization has received little attention.

##  III Computational Simulations

In order to evaluate the feasibility of our approach, we tackle (1) by a
nonlinear regression scheme through Feedforward Networks with up to 7580 nodes
distributed in up to 10 layers, as shown by Table III (best in bold). Although
learning each of the neural network takes a few seconds/minutes, the
convergence is competitive in the range of $10^{-3}$ to $10^{-1}$ MSE, as
shown by Fig. 2, implying the reasonable approximation of control path
inductance ($f_{1}$ at $9.78\times 10^{-6}$), the main path inductance
($f_{2}$ at $8.25\times 10^{-7}$), and maximum temperature in the substrate
($f_{3}$ at $0.19$) as shown by Fig. 3.

As such, we used the best obtained performance functions $\lambda_{i}$
($i\in[1,3]$) in terms of neural network schemes to tackle (2) by population-
based gradient free optimization algorithms. For rigorous evaluations, we use
the class of algorithms inspired by Differential Evolution considering diverse
forms of selection, mutation and adaptation mechanisms:

  * •

DERAND: DE/rand/1/bin Strategy[10],

  * •

DEBEST: DE/best/1/bin Strategy[10],

  * •

DESPS: DE with Speciation Strategy[11],

  * •

SHADE: Success-History based Adaptive DE[12],

  * •

RBDE: Rank-based Differential Evolution[13],

  * •

JADE: Adaptive DE with External Archive[14],

  * •

DEGL: DE with Local and Global Neighborhoods[15],

  * •

DESIM: DE with Similarity Based Mutation[16],

  * •

DCMAEA: Differential CMAE[17],

  * •

OBDE: Opposition Based DE[18],

TABLE I: Configuration of Neural Net models.

[0.1em,red5]  Neural Model Number of nodes, and layer composition 1 20 10 2 50
20 10 3 100 50 20 10 4 500 100 50 20 10 5 500 100 20 10 6 1000 100 50 20 10 7
1000 100 10 8 400 300 200 100 50 20 10 9 1000 300 200 100 50 20 10 10 5000
1000 500 400 300 200 100 50 20 10

Algorithm parameters involve population size 10, probability of crossover
$0.5$, scaling factor for difference of vectors $0.7$, and 10 independent runs
(due to the stochastic nature of the optimization algorithms). Other
parameters followed the suggested values. For a feasibility study, we
considered an scenario in which the weight on temperature of the substrate is
higher ($w_{1}=w_{2}=1,~{}w_{3}=2$), and another scenario for equal weight on
inductance and temperature ($w_{1}=w_{2}=w_{3}=1$). Although mean convergence
occurs relatively quick (at 100-300 function evaluations), the standard
deviation and the minimum objective functions follow a decreasing trend,
implying the feasibility to locate attractive regions of the search space of
high-performing power module layouts. Among the studied algorithms, we also
note that the class of exploration-focused and diversity-induced algorithms,
such as DERAND, OBDE and DESIM underperform their counterparts with
exploitation and parameter adaptation schemes (statistical comparisons based
on Wilcoxon at 5% significance level). By looking at the obtained results in
Fig. 2 \- Fig. 4, we can observe the feasibility of learning/approximating
surrogate functions able to estimate performance metrics related to inductance
and temperature of power module layouts, and use those surrogates to
optimize/locate feasible and attractive layout configurations of power module
substrates. The future work is expected to evaluate and extend the use of
surrogates to propose unique/initial configurations for power modules.

[0.25em,gray3] (a) Learning performance. Dark (bright) colors imply neural
networks with small (large) number of layers (refer to Table I).
---
$f_{1}$ $f_{2}$ $f_{3}$
[dotted] (b) Overview of training times. The numbers in the x-axis refer to
neural networks from Table I.
$f_{1}$ $f_{2}$ $f_{3}$
[dotted] (c) Overview of prediction performance of best obtained models.
[0.25em,gray3]
Figure 2: Overview of (a) the learning convergence, (b) the training times,
(c) the predictive ability of best obtained models.

Figure 3: Overview of performance metrics for Power Modules. [0.25em,gray3]
(a) Scenario 1: $w_{1}=1,~{}w_{2}=1,~{}w_{3}=2$.
---
Mean Convergence Standard Deviation Minimum Convergence
[dotted] (a) Scenario 2: $w_{1}=1,~{}w_{2}=1,~{}w_{3}=1$.
Mean Convergence Standard Deviation Minimum Convergence
[dotted] (c) Overview of the statistical comparisons.
Scenario 1 Scenario 2
[0.25em,gray3]
Figure 4: Overview of optimization results: convergences in different
scenarios, statistical comparisons.

## References

  * [1] H. A. Mantooth and S. S. Ang, “Packaging architectures for silicon carbide power electronic modules,” in _2018 International Power Electronics Conference_ , 2018, pp. 153–156.
  * [2] G. Nan, Z. Xie, X. Guan, X. Ji, and D. Lin, “Constructal design for the layout of multi-chip module based on thermal-flow-stress coupling calculation,” _Microelectronics Reliability_ , vol. 127, p. 114417, 2021.
  * [3] W. Belloumi, A. Bréard, O. Hajji, C. Vollaire, and J. B. H. Slama, “Automatic pcb layout optimization of a dc-dc converter through genetic algorithm regarding emc constraints,” _IEEE Access_ , vol. 9, pp. 149 870–149 882, 2021.
  * [4] Y. Mei, B. Hao, Y. Chen, M. Wang, X. Li, and G.-Q. Lu, “Efficient layout design automation for multi-chip sic modules targeting small footprint and low parasitic,” _IET Power Electronics_ , vol. 13, no. 10, pp. 2069–2076, 2020.
  * [5] K. Ben Abdelmlek, Z. Araoud, K. Charrada, and G. Zissis, “Optimization of the thermal distribution of multi-chip led package,” _Applied Thermal Engineering_ , vol. 126, pp. 653–660, 2017.
  * [6] B. Hao, Y. Mei, and P. Ning, “A hybrid genetic algorithm for automatic layout design of power module,” in _2017 18th International Conference on Electronic Packaging Technology (ICEPT)_ , 2017, pp. 1143–1146.
  * [7] Y. Abe, A. Hirao, R. Kato, Y. Ikeda, V. Parque, M. K. Faiz, M. Yoshida, and T. Miyashita, “Design optimization of copper patterns and location of power semiconductors and terminals,” in _2021 International Conference on Electronics Packaging (ICEP)_ , 2021, pp. 157–158.
  * [8] A. Nakamura, M. Yoshida, and T. Miyashita, “Multi-objective design optimization of power module performances,” in _2022 International Conference on Electronics Packaging (ICEP)_ , 2022, pp. 157–158.
  * [9] V. Parque and T. Miyashita, “A method to learn high-performing and novel product layouts and its application to vehicle design,” _Neurocomputing_ , vol. 248, pp. 41–56, 2017.
  * [10] R. Storn and K. Price, “Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces,” _Journal of Global Optimization_ , vol. 11, no. 4, pp. 341–359, Dec 1997.
  * [11] S. Guo, C. Yang, P. Hsu, and J. S. . Tsai, “Improving differential evolution with a successful-parent-selecting framework,” _IEEE Transactions on Evolutionary Computation_ , vol. 19, no. 5, pp. 717–730, Oct 2015\.
  * [12] R. Tanabe and A. Fukunaga, “Success-history based parameter adaptation for differential evolution,” in _2013 IEEE Congress on Evolutionary Computation_ , 2013, pp. 71–78.
  * [13] A. M. Sutton, M. Lunacek, and L. D. Whitley, “Differential evolution and non-separability: Using selective pressure to focus search,” in _9th Annual Conference on Genetic and Evolutionary Computation_ , ser. GECCO ’07. ACM, 2007, pp. 1428–1435.
  * [14] J. Zhang and A. C. Sanderson, “Jade: Adaptive differential evolution with optional external archive,” _IEEE Transactions on Evolutionary Computation_ , vol. 13, no. 5, pp. 945–958, Oct 2009.
  * [15] S. Das, A. Abraham, U. K. Chakraborty, and A. Konar, “Differential evolution using a neighborhood-based mutation operator,” _IEEE Trans. on Evolutionary Computation_ , vol. 13, no. 3, pp. 526–553, June 2009.
  * [16] E. Segredo, E. Lalla-Ruiz, and E. Hart, “A novel similarity-based mutant vector generation strategy for differential evolution,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , ser. GECCO ’18. New York, NY, USA: ACM, 2018, pp. 881–888.
  * [17] S. Ghosh, S. Das, S. Roy, S. M. Islam, and P. Suganthan, “A differential covariance matrix adaptation evolutionary algorithm for real parameter optimization,” _Information Sciences_ , vol. 182, no. 1, pp. 199–219, 2012\.
  * [18] S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “Opposition-based differential evolution,” _IEEE Transactions on Evolutionary Computation_ , vol. 12, no. 1, pp. 64–79, Feb 2008.