11institutetext:  Dept. of Engineering, University of Perugia, Italy
11email<EMAIL_ADDRESS>Department of Computer
Science, University of Bergen, Norway
22email<EMAIL_ADDRESS>Department of Computer Science, University of Arizona, USA
33email<EMAIL_ADDRESS>44institutetext: Department of Computer
Science, University of Würzburg, Germany
44email<EMAIL_ADDRESS>
# Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph
Problem††thanks: Research started at the Dagstuhl Seminar 23162: New Frontiers
of Parameterized Complexity in Graph Drawing, April 2023, and partially
supported by: $(i)$ University of Perugia, Ricerca Base 2021, Proj. “AIDMIX —
Artificial Intelligence for Decision Making: Methods for Interpretability and
eXplainability”; $(ii)$ MUR PRIN Proj. 2022TS4Y3N - “EXPAND: scalable
algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked
Data”, $(iii)$ MUR PRIN Proj. 2022ME9Z78 - “NextGRAAL: Next-generation
algorithms for constrained GRAph visuALization”, $(iv)$ the Research Council
of Norway project BWCA 314528, $(v)$ the European Research Council (ERC) grant
LOPPRE 819416, and $(vi)$ NSF-CCF 2212130.

Walter Didimo 11 Fedor V. Fomin 22 Petr A. Golovach 22 Tanmay Inamdar 22
Stephen Kobourov 33 Marie Diana Sieper 44

###### Abstract

A vertex of a plane digraph is _bimodal_ if all its incoming edges (and hence
all its outgoing edges) are consecutive in the cyclic order around it. A plane
digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart
of many types of graph layouts, such as upward drawings, level-planar
drawings, and L-drawings. If the graph is not bimodal, the _Maximum Bimodal
Subgraph (MBS)_ problem asks for an embedding-preserving bimodal subgraph with
the maximum number of edges. We initiate the study of the MBS problem from the
parameterized complexity perspective with two main results: (i) we describe an
FPT algorithm parameterized by the branchwidth (and hence by the treewidth) of
the graph; (ii) we establish that MBS parameterized by the number of non-
bimodal vertices admits a polynomial kernel. As the byproduct of these
results, we obtain a subexponential FPT algorithm and an efficient polynomial-
time approximation scheme for MBS.

###### Keywords:

bimodal graphs, maximum bimodal subgraph, parameterized complexity, FPT
algorithms, polynomial kernel, approximation scheme

##  1 Introduction

Let $G$ be a plane digraph, that is, a planar directed graph with a given
planar embedding. A vertex $v$ of $G$ is _bimodal_ if all its incoming edges
(and hence all its outgoing edges) are consecutive in the cyclic order around
$v$. In other words, $v$ is bimodal if the circular list of edges incident at
$v$ can be split into at most two linear lists, where all edges in the same
list are either all incoming or all outgoing $v$. Graph $G$ is _bimodal_ if
all its vertices are bimodal. Bimodality is a key property at heart of many
graph drawing styles. In particular, it is a necessary condition for the
existence of _level-planar_ and, more generally, _upward planar_ drawings,
where the edges are represented as curves monotonically increasing in the
upward direction according to their orientations [DBLP:books/ph/BattistaETT99,
DBLP:journals/tsmc/BattistaN88, DBLP:reference/algo/Didimo16,
DBLP:conf/gd/JungerLM98]; see Fig. 1. Bimodality is also a sufficient
condition for _quasi-upward planar_ drawings, in which edges are allowed to
violate the upward monotonicity a finite number of times at points called
_bends_ [DBLP:journals/algorithmica/BertolazziBD02, DBLP:conf/gd/BinucciGLT21,
DBLP:journals/cj/BinucciD16]; see Fig. 1. It has been shown that bimodality is
also a sufficient condition for the existence of _planar L-drawings_ of
digraphs, in which distinct L-shaped edges may overlap but not cross
[DBLP:journals/jgaa/AngeliniCCL22, DBLP:conf/mfcs/AngeliniCCL22,
DBLP:journals/ijfcs/KariOALBDPRT18a]; see Fig. 1. A generalization of
bimodality is $k$-modality. Given a positive even integer $k$, a plane digraph
is _$k$ -modal_ if the edges at each vertex can be grouped into at most $k$
sets of consecutive edges with the same orientation [DBLP:conf/esa/VialLG19].
In particular, it is known that $4$-modality is necessary for planar
L-drawings [DBLP:conf/gd/ChaplickCCLNPTW17].

While testing if a digraph $G$ admits a bimodal planar embedding can be done
in linear time [DBLP:journals/algorithmica/BertolazziBD02], a natural problem
that arises when $G$ does not have such an embedding is to extract from $G$ a
subgraph of maximum size (i.e., with the maximum number of edges) that
fulfills this property. This problem is NP-hard, even if $G$ has a given
planar embedding and we look for an embedding-preserving maximum bimodal
subgraph [DBLP:journals/comgeo/BinucciDG08]. We address exactly this fixed-
embedding version of the problem, and call it the _Maximum Bimodal Subgraph_
(MBS) problem.

Figure 1: (a) An upward planar drawing. (b) A quasi-upward planar drawing,
where edge $e$ makes two bends (the two horizontal tangent points). (c) A
bimodal digraph (above) and a corresponding planar L-drawing (below).

Contribution. While a heuristic and a branch-and-bound algorithm are given in
[DBLP:journals/comgeo/BinucciDG08] to solve MBS (and also to find a maximum
upward-planar digraph), here we study this problem from the parameterized
complexity and approximability perspectives (refer to [CyganFKLMPPS15,
FominLSZ19] for an introduction to parameterized complexity). More precisely,
we consider the following more general version of the problem with weighted
edges; it coincides with MBS when we restrict to unit edge weights.

MWBS$(G,w)$ (_Maximum Weighted Bimodal Subgraph_). _Given a plane digraph $G$
and an edge-weight function $w:E(G)\rightarrow\mathbb{Q}^{+}$, compute a
bimodal subgraph of $G$ of maximum weight, i.e., whose sum of the edge weights
is maximum over all bimodal subgraphs of $G$._

Our contribution can be summarized as follows.

$-$ Structural parameterization. We show that MWBS is FPT when parameterized
by the _branchwidth_ of the input digraph $G$ or, equivalently, by the
_treewidth_ of $G$ (Sect. 3). Our algorithm deviates from a standard dynamic
approach for graphs of bounded treewidth. The main difficulty here is that we
have to incorporate the “topological” information about the given embedding in
the dynamic program. We accomplish this via the sphere-cut decomposition of
Dorn et al. [DBLP:journals/algorithmica/DornPBF10].

$-$ Kernelization. Let $b$ be the number of non-bimodal vertices in an input
digraph $G$. We construct a polynomial kernel for the decision version of MWBS
parameterized by $b$ (Sect. 4). Our kernelization algorithm performs in
several steps. First we show how to reduce the instance to an equivalent
instance whose branchwidth is $\mathcal{O}(\sqrt{b})$. Second, by using
specific gadgets, we compress the problem to an instance of another problem
whose size is bounded by a polynomial of $b$. In other words, we provide a
polynomial compression for MWBS. Finally, by the standard arguments,
[FominLSZ19, Theorem 1.6], based on a polynomial reduction between any NP-
complete problems, we obtain a polynomial kernel for MWBS.

By pipelining the crucial step of the kernelization algorithm with the
branchwidth algorithm, we obtain a parameterized subexponential algorithm for
MWBS of running time $2^{\mathcal{O}(\sqrt{b})}\cdot n^{\mathcal{O}(1)}$.
Since $b\leq n$, this also implies an algorithm of running time
$2^{\mathcal{O}(\sqrt{n})}$. Note that our algorithms are asymptotically
optimal up to the _Exponential Time Hypothesis_ (ETH) [ImpagliazzoP99,
ImpagliazzoPZ01]. The NP-hardness result of MBS (and hence of MWBS) given in
[DBLP:journals/comgeo/BinucciDG08] exploits a reduction from Planar-3SAT. The
number of non-bimodal vertices in the resulting instance of MBS is linear in
the size of the Planar-3SAT instance. Using the standard techniques for
computational lower bounds for problems on planar graphs [CyganFKLMPPS15], we
obtain that the existence of an $2^{o(\sqrt{b})}\cdot n^{\mathcal{O}(1)}$-time
algorithm for MBWS would contradict ETH.

$-$ Approximability. We provide an Efficient Polynomial-Time Approximation
Scheme (EPTAS) for MWBS, based on Baker’s (or shifting) technique [Baker94].
Namely, using our algorithm for graphs of bounded branchwidth, we give an
$(1+\epsilon)$-approximation algorithm that runs in
$2^{\mathcal{O}(1/\epsilon)}\cdot n^{\mathcal{O}(1)}$ time.

Full proofs of the results marked with an asterisk (*), as well as additional
definitions and technical details, are given in appendix.

##  2  Definitions and Terminology

Let $G$ be a digraph. We denote by $V(G)$ and $E(G)$ the set of vertices and
the set of edges of $G$. Throughout the paper we assume that $G$ is planar and
that it comes with a planar embedding; such an embedding fixes, for each
vertex $v\in V(G)$, the clockwise order of the edges incident to $v$. We say
that $G$ is a _planar embedded digraph_ or simply that $G$ is a _plane
digraph_.

Branch decomposition and sphere-cut decomposition. A _branch decomposition_ of
a graph $G$ defines a hierarchical clustering of the edges of $G$, represented
by an unrooted proper binary tree, that is a tree with non-leaf nodes of
degree three, whose leaves are in one-to-one correspondence with the edges of
$G$. More precisely, a branch decomposition of $G$ consists of a pair $\langle
T,\xi\rangle$, where $T$ is an unrooted proper binary tree and
$\xi:\mathcal{L}(T)\leftrightarrow E(G)$ is a bijection between the set
$\mathcal{L}(T)$ of the leaves of $T$ and the set $E(G)$ of the edges of $G$.
For each arc $a$ of $T$, denote by $T^{a}_{1}$ and $T^{a}_{2}$ the two
connected components of $T\setminus\\{a\\}$, and, for $i=1,2$, let $G^{a}_{i}$
be the subgraph of $G$ that consists of the edges corresponding to the leaves
of $T^{a}_{i}$. The _middle set_ $\operatorname{mid}(a)\subseteq V(G)$ is the
intersection of the vertex sets of $G^{a}_{1}$ and $G^{a}_{2}$, i.e.,
$\operatorname{mid}(a):=V(G^{a}_{1})\cap V(G^{a}_{2})$. The _width_
$\beta(\langle T,\xi\rangle)$ of $\langle T,\xi\rangle$ is the maximum size of
the middle sets over all arcs of $T$, i.e., $\beta(\langle
T,\xi\rangle)=\max\\{\lvert\operatorname{mid}(a)\rvert:a\in E(T)\\}$. An
_optimal branch decomposition_ of $G$ is a branch decomposition with minimum
width; this width is called the _branchwidth_ of $G$ and is denoted by
$\operatorname{\rm bw}(G)$.

Figure 2: A plane graph $G$ and a sphere-cut decomposition of $G$; three
nooses are highlighted on $G$ for the arcs $a$, $b$, and $c$ of the
decomposition tree.

A sphere-cut decomposition is a special type of branch decomposition (see Fig.
2). Let $G$ be a connected planar graph, topologically drawn on a sphere
$\Sigma$. A _noose_ $O$ of $G$ is a closed simple curve on $\Sigma$ that
intersects $G$ only at vertices and that traverses each face of $G$ at most
once. The _length_ of $O$ is the number of vertices that $O$ intersects. Note
that, $O$ bounds two closed discs $\Delta_{O}^{1}$ and $\Delta_{O}^{2}$ in
$\Sigma$; we have $\Delta_{O}^{1}\cap\Delta_{O}^{2}=O$ and
$\Delta_{O}^{1}\cup\Delta_{O}^{2}=\Sigma$. Let $\langle T,\xi\rangle$ be a
branch decomposition of $G$. Suppose that for each arc $a$ of $T$ there exists
a noose $O_{a}$ that traverses exactly the vertices of $\operatorname{mid}(a)$
and whose closed discs $\Delta_{O_{a}}^{1}$ and $\Delta_{O_{a}}^{2}$ enclose
the drawings of $G_{1}^{a}$ and of $G_{2}^{a}$, respectively. Denote by
$\pi_{a}$ the circular clockwise order of the vertices in
$\operatorname{mid}(a)$ along $O_{a}$ and let $\Pi=\\{\pi_{a}:a\in E(T)\\}$
the set of all circular orders $\pi_{a}$. The triple $\langle
T,\xi,\Pi\rangle$ is a _sphere-cut decomposition_ of $G$. We assume that the
vertices of $\operatorname{mid}(a)=V(G_{1}^{a})\cap V(G_{2}^{a})$ are
enumerated according to $\pi_{a}$. Since a noose $O_{a}$ traverses each face
of $G$ at most once, both graphs $G_{1}^{a}$ and $G_{2}^{a}$ are connected.
Also, the nooses are pairwise non-crossing, i.e., for any pair of nooses
$O_{a}$ and $O_{b}$, we have that $O_{b}$ lies entirely inside
$\Delta_{O_{a}}^{1}$ or entirely inside $\Delta_{O_{a}}^{2}$. For a noose
$O_{a}$, we define $\operatorname{mid}(O_{a})=\operatorname{mid}(a)$, or in
general, we define $\operatorname{mid}(\phi)$ to be the vertices cut by
$\phi$. We rely on the following result on the existence and computation of a
sphere-cut decomposition [DBLP:conf/wg/JacobP22] (see also
[DBLP:journals/algorithmica/DornPBF10]).

######  Proposition 1 ([DBLP:conf/wg/JacobP22]).

Let $G$ be a connected graph embedded in the sphere with $n$ vertices and
branchwidth $\ell\geq 2$. Then there exists a sphere-cut decomposition of $G$
with width $\ell$, and it can be computed in $\mathcal{O}(n^{3})$ time.

We remark that the branchwidth $\operatorname{\rm bw}(G)$ and the treewidth
$\operatorname{\rm tw}(G)$ of a graph $G$ are within a constant factor:
$\operatorname{\rm bw}(G)-1\leq\operatorname{\rm
tw}(G)\leq\lfloor\frac{3}{2}\operatorname{\rm bw}(G)\rfloor-1$ (see
[DBLP:journals/jct/RobertsonS91]).

##  3 FPT Algorithms for MWBS by Branchwidth

In this section we describe an FPT algorithm parameterized by branchwidth. We
first introduce configurations, which encode on which side of a closed curve
and in what order in a bimodal subgraph for a vertex $v$ the switches between
incoming to outgoing edges happen.

######  Definition 1 (Configuration).

Let $C=\\{(i),(o),(i,o),(o,i),(o,i,o),(i,o,i)\\}$. Let $G$ be a graph embedded
in the sphere $\Sigma$, $\phi$ be a noose in $\Sigma$ with a prescribed
inside, $v\in\operatorname{mid}{(\phi)}$, and $X\in C$. Let $E^{v,\phi}$ be
the set of edges incident to $v$ in $\phi$. We say $v$ has _configuration_ $X$
in $\phi$, if $E^{v,\phi}$ can be partitioned into sets such that:

  1. 1.

For every $x\in X$, there is a (possibly empty) set $E_{x}$ associated with
it.

  2. 2.

Every set associated with an $i$ ($o$) contains only in- (/out-) edges of $v$.

  3. 3.

For every set, the edges contained in it are successive around $v$.

  4. 4.

The sets $E_{x}$ appear clockwise (seen from $v$) in the same order in $G$
inside $\phi$ as the $x$ appear in $X$.

For every $v\in\operatorname{mid}{(\phi)}$, let $X_{v}$ be a configuration of
$v$ in $\phi$. We say $X_{\phi}=\\{X_{v}\mid
v\in\operatorname{mid}{(\phi)}\\}$ is a _configuration set_ of $\phi$.

If $G$ is bimodal, then for every noose $\phi$ and every vertex
$v\in\operatorname{mid}{(\phi)}$, $v$ must have at least one configuration
$X\in C$ in $\phi$. Note that configurations and configuration sets are not
unique, as seen in Fig. 3. A vertex can even have all configurations if it has
no incident edges in $\phi$. The next definition is needed to encode when
configurations can be combined in order to obtain bimodal vertices.

######  Definition 2 (Compatible configurations).

Let $X,X^{\prime},X^{*}\in C$ be configurations. We say $X,X^{\prime}$ are
_compatible configurations_ or short _compatible_ , if by concatenating
$X,X^{\prime}$ and deleting consecutive equal letters, the result is a
substring of $(o,i,o)$ or $(i,o,i)$. Note that it is not important in which
order we concatenate $X,X^{\prime}$. See Figure 3. We say $X$ and $X^{\prime}$
are _compatible with respect to $X^{*}$_ if by concatenating $X,X^{\prime}$
(in this order) and deleting consecutive equal letters, the result is a
substring of $X^{*}$.

A configuration $X$ can have several compatible configurations, for example
$(i,o)\in C$ is compatible with $(o),(i)$ and $(o,i)$. From these $(o,i)$ is
in some sense maximal, meaning that configurations $(o)$ and $(i)$ are
substrings of $(o,i)$. Given a configuration $X$, a _maximal compatible
configuration_ $X^{\prime}$ of $X$ is a configuration that is compatible with
$X$, and all other compatible configurations of $X$ are substrings of
$X^{\prime}$. Observe that every configuration has a unique maximal compatible
configuration, they are pairwise: $(i)-(i,o,i)$, $(o)-(o,i,o)$ and
$(o,i)-(i,o)$.

We say a noose $\phi_{3}$ is _composed_ of the nooses $\phi_{1}$ and
$\phi_{2}$, if the edges of $G$ in $\phi_{3}$ are partitioned by $\phi_{1}$
and $\phi_{2}$. If a noose $\phi_{3}$ is composed of nooses $\phi_{1}$ and
$\phi_{2}$, and there exists a vertex
$v\in\operatorname{mid}(\phi_{1})\cap\operatorname{mid}(\phi_{2})\cap\operatorname{mid}(\phi_{3})$,
such that in $\phi_{3}$ around $v$, all adjacent edges of $v$ in $\phi_{1}$
are clockwise before all adjacent edges of $v$ in $\phi_{2}$. If
$X,X^{\prime}$ and $X^{*}$ are nooses and $X$ and $X^{\prime}$ are compatible
with respect to $X^{*}$, and $v$ has configuration $X$ in $\phi_{1}$ and
configuration $X^{\prime}$ in $\phi_{2}$, then it has configuration $X^{*}$ in
$\phi_{3}$. See Figure 3.

If a curve $\phi$ contains only one edge on its inside, finding maximal
subgraphs for a configuration inside $\phi$ is easy.

Figure 3:  (a) A vertex with configurations $(o,i),(o,i,o)$ and $(i,o,i)$ in
$\phi$. The most restricted and thus minimal configuration is $(o,i)$. (b) A
vertex with configuration $(o,i,o)$ in $\phi$ and $(o)$ outside of $\phi$.
Concatenating $(o,i,o)$ with $(o)$ and deleting consecutive equal letters
results in $(o,i,o)$, the result is a substring of $(o,i,o)$, thus $(o,i,o)$
and $(o)$ are compatible. (c) Note that $\phi_{3}$ is composed of $\phi_{1}$
and $\phi_{2}$; the inside of $\phi_{1}$, the inside of $\phi_{2}$ and the
outside of $\phi_{3}$ are clockwise in this order around $v$ with
configuration $(i,o)$ in $\phi_{1}$ and $(o)$ in $\phi_{2}$. They can be
concatenated to configuration $(i,o)$ in $\phi_{3}$, while $(i,o)$ and $(o)$
are compatible w.r.t. $(i,o)$, but not $(o,i)$.

######  Lemma 1 (*).

Let $G$ be a graph embedded in the sphere $\Sigma$, let $e=\\{u,v\\}$ be an
edge and let $\phi$ be a noose that cuts $G$ only in $u$ and $v$, such that
$e$ is in $\phi$ and all other edges are on the outside of $\phi$. Let
$X_{u},X_{v}$ be prescribed configurations. Then we can compute in
$\mathcal{O}(1)$ time the maximum subgraph $G^{\prime}$ of $G$ such that $u,v$
have configuration $X_{u}$ respectively $X_{v}$ in $\phi$ in $G^{\prime}$.

We will now see how we can compute optimal subgraphs bottom-up.

######  Lemma 2 (*).

Let $G$ be a graph embedded in the sphere $\Sigma$, let
$\phi_{1},\phi_{2},\phi_{3}$ be nooses with length at most $\ell$ each, and
let $E_{\phi_{1}},E_{\phi_{2}},E_{\phi_{3}}$ be the sets of edges contained
inside the respective noose with $E_{\phi_{1}},E_{\phi_{2}}$ being a partition
of $E_{\phi_{3}}$. Let $X_{\phi_{3}}$ be a configuration set for $\phi_{3}$.
Let further for every configuration set $X_{\phi_{1}}$ ($X_{\phi_{2}}$) of
$\phi_{1}$ ($\phi_{2}$), the maximum subgraph that has configuration set
$X_{\phi_{1}}$ ($X_{\phi_{2}}$) and is bimodal in $\phi_{1}$ ($\phi_{2}$) be
known. Then a maximum subgraph $G^{\prime}$ of $G$ that has configuration set
$X_{\phi_{3}}$ and is bimodal in $\phi_{3}$ can be computed in
$\mathcal{O}(6^{2\ell})\cdot n^{\mathcal{O}(1)}$ time.

If a noose $\phi$ contains only $e\in E$, we have only two options in $\phi$:
delete $e$ or do not. Testing which is optimal can be done in constant time,
this leads to Lemma 1. Now let $\phi_{3}$ be a noose that contains more than
one edge, let $\phi_{1},\phi_{2}$ be two nooses that partition the inside of
$\phi_{3}$, and let $X_{\phi_{3}}$ be a given configuration set. If we already
know optimal solutions for any given configuration set in $\phi_{1}$
($\phi_{2}$) (which we already computed when traversing the sphere-cut
decomposition bottom up), we can guess for some optimal solution for
$\phi_{3}$ for every
$v\in\operatorname{mid}(\phi_{1})\cap\operatorname{mid}(\phi_{2})$ the
configuration it has in $\phi_{1}$ and in $\phi_{2}$. This gives us
configuration sets $X_{\phi_{1}}$ and $X_{\phi_{2}}$ for $\phi_{1}$ and
$\phi_{2}$, respectively (for every
$v\in\operatorname{mid}(\phi_{1})\setminus\operatorname{mid}(\phi_{2})$ we
take its configuration in $X_{\phi_{3}}$). We obtain the corresponding
solution $G^{\prime}$ that coincides with the optimal solution for $\phi_{1}$
($\phi_{2}$) in $\phi_{1}$ ($\phi_{2}$) respecting $X_{\phi_{1}}$
($X_{\phi_{2}}$) and that coincides with $G$ outside of $\phi_{3}$. Since
$|\operatorname{mid}(\phi_{1})\cap\operatorname{mid}(\phi_{2})|\leq\ell$, we
achieve the same by enumerating all possible configurations for
$\operatorname{mid}(\phi_{1})\cap\operatorname{mid}(\phi_{2})$, compute the
corresponding solutions and take the maximum in $\mathcal{O}(6^{2\ell})\cdot
n^{\mathcal{O}(1)}$ time, leading to Lemma 2. We now obtain the following
theorem.

######  Theorem 3.1 (*).

There is an algorithm that solves MWBS$(G,w)$ in
$2^{\mathcal{O}(\operatorname{\rm bw}(G))}\cdot n^{\mathcal{O}(1)}$ time. In
particular, MWBS is FPT when parameterized by branchwidth.

###### Sketch.

Assume that $G$ is connected (otherwise process every connected component
independently). If $\operatorname{\rm bw}(G)=1$, $G$ is a star and we can
compute an optimal solution in polynomial time. Otherwise, according to
Proposition 1 we can compute a sphere-cut decomposition $\langle
T,\xi,\Pi\rangle$ for $G$ with optimal width $\ell$. We pick any leaf of $T$
to be the root $r$ of $T$. For every noose $O$ corresponding to an arc of $T$
let $X_{O}$ be a configuration set for $O$. Then we define $E_{(O,X_{O})}$ to
be edge set of minimum weight, such that $G\setminus E_{(O,X_{O})}$ is bimodal
inside of $O$ and has configuration set $X_{O}$ in $O$. We now compute the
$E_{(O,X_{O})}$ bottom-up. For a noose $O$ corresponding to a leaf-arc in $T$,
Lemma 1 shows that we can compute all possible values of $E_{(O,X_{O})}$ in
linear time. For a noose $O$ corresponding to a non-leaf arc in $T$, Lemma 2
shows that we can compute $E_{O,X_{O}}$ for a given $X_{O}$ in
$\mathcal{O}(6^{2\ell})\cdot n^{\mathcal{O}(1)}$ time, and thus all entries
for $O$ in $\mathcal{O}(6^{3\ell})\cdot n^{\mathcal{O}(1)}$ time. Let $e\in E$
be the edge associated with $r$. We have only two options left, delete $e$ or
do not. In both cases we obtain the optimal solution for the rest of $G$ from
the values $E_{(O,X_{O})}$. The overall running time is
$2^{\mathcal{O}(\ell)}\cdot n^{\mathcal{O}(1)}$. ∎

Since our input graphs are planar, we immediately obtain a subexponential
algorithm for MWBS because for a planar graph $G$, $\operatorname{\rm
bw}(G)=\mathcal{O}(\sqrt{n})$[FominT06].

######  Theorem 3.2.

MWBS$(G=(V,E),w)$ can be solved in $2^{\mathcal{O}(\sqrt{n})}$ time.

##  4 Compression for MWBS by $b$

Throughout this section we assume that (i) the weights are rational, that is,
for $(G,w)$, $w\colon V(G)\rightarrow\mathbb{Q}^{+}$ and (ii) we consider the
decision version of MWBS, that is, additionally to $(G,w)$, we are given a
target value $W\in\mathbb{Q}^{+}$ and the task is to decide whether $G$ has a
bimodal subgraph $G^{*}$ with $w(E(G^{*}))\geq W$.

Further definitions. For simplicity, we say that a bimodal vertex of $G$ is a
_good_ vertex, and that a non-bimodal vertex is a _bad_ vertex. We denote by
${\cal G}(G)$ and ${\cal B}(G)$ the sets of good and bad vertices of $G$,
respectively. Given a vertex $v\in V(G)$, an _in-wedge_ (resp. _out-wedge_) of
$v$ is a maximal circular sequence of consecutive incoming (resp. outgoing)
edges of $v$. Clearly, if $v$ is bimodal it has at most one in-wedge and at
most one out-wedge. Given a vertex $v\in{\cal B}(G)$, a _good edge-section_ of
$v$ is a maximal consecutive sequence of in- and out- wedges of $v$, such that
no edge is incident to another bad vertex.

######  Observation 1.

Let $(G,w)$ be an instance of MWBS with $b$ bad vertices, and let $v\in{\cal
B}(G)$. Then $v$ can have at most $b-1$ good edge-sections.

We introduce a generalization of MWBS called Cut-MWBS$(G,w,\mathcal{E})$
(_maximum weighted bimodal subgraph with prescribed cuts_). Given a plane
digraph $G$, an edge-weight function $w:E(G)\rightarrow\mathbb{Q}^{+}$, and a
partition $\mathcal{E}$ of $E(G)$, compute a bimodal subgraph $G^{\prime}$ of
$G$ of maximum weight, i.e., whose sum of the edge weights is maximum over all
bimodal subgraphs of $G$, under the condition that for every set
$E_{i}\in\mathcal{E}$, either all $e\in E_{i}$ are still present in
$G^{\prime}$ or none of them are. We can see that every instance $(G,w)$ of
MWBS is equivalent to the instance $(G,w,\\{\\{e\\}\mid e\in E(G)\\})$ of Cut-
MWBS, and thus Cut-MWBS is NP-hard. Also, the decision variant of the problem
is NP-complete.

We now give reduction rules for the MWBS to Cut-MWBS compression, and prove
that each of them is _sound_ , i.e., it can be performed in polynomial time
and the reduced instance is solvable if and only if the starting instance is
solvable.

######  Reduction Rule 1.

Let $(G,w)$ be an instance of MWBS, and $v\in V(G)$ be an isolated vertex.
Then, let $(G^{\prime},w)$ be the new instance, where
$V(G^{\prime})=V(G)\setminus\\{v\\}$.

######  Reduction Rule 2.

Let $(G,w)$ be an instance of MWBS with the target value $W$, and $u,v\in{\cal
G}(G)$ be such that $(u,v)$ is an edge. Then, the resulting instance is
$(G^{\prime},w)$, where $G^{\prime}=G-(u,v)$, and the new target value is
$W^{\prime}=W-w(u,v)$.

######  Reduction Rule 3.

Let $(G,w)$ be an instance of MWBS and $v\in{\cal G}(G)$ of degree $\geq 2$.
Let $(G^{\prime},w)$ be the new instance, where in $G^{\prime}$ we replace
each edge $e=(u,v)$ (resp. $e=(v,u)$) where $u\in{\cal G}(G)$ with another
edge $e^{\prime}=(u,x_{uv})$ (resp. $e^{\prime}=(x_{uv},u)$), where $x_{uv}$’s
are distinct vertices created for each such edge, and each $e^{\prime}$ is
embedded within the embedding of $e$, where $w(e^{\prime})=w(e)$ (see Fig. 4).

Figure 4: A bimodal vertex (a) before and (b) after Reduction rule 3 is
applied.

######  Claim 1 (*).

Reduction rules 1, 2 and 3 are sound.

By applying Reductions 1, 2 and 3 exhaustively, we get Lemma 3, which is
already enough to give a subexponential FPT algorithm by $b$ (Theorem 4.1).

######  Lemma 3 (*).

Given an instance $(G,w)$ of MWBS, there exists a polynomial-time algorithm to
obtain an equivalent instance $(G^{\prime},w)$ with $G^{\prime}$ being a
subgraph of $G$, such that (i) $|{\cal B}(G^{\prime})|\leq|{\cal B}(G)|$, (ii)
${\cal G}(G^{\prime})$ is an independent set in $G^{\prime}$, and (iii) for
all $v\in{\cal G}(G^{\prime})$, $\deg(v)=1$ in the underlying graph of
$G^{\prime}$.

######  Theorem 4.1.

There exists an algorithm that solves MWBS$(G,w)$ with $b$ bad vertices in
$2^{\mathcal{O}(\sqrt{b})}\cdot n^{\mathcal{O}(1)}$ time.

###### Proof.

By Lemma 3, $(G,w)$ is equivalent to $(G^{\prime},w)$ with at most $b$
vertices of degree $>1$, which we can compute in polynomial time. This implies
$\operatorname{\rm bw}(G^{\prime})=\mathcal{O}(\operatorname{\rm
tw}(G^{\prime}))=\mathcal{O}(\sqrt{b})$, and we can apply Theorem 3.1 to
obtain an algorithm that computes a solution for $(G^{\prime},w)$ in
$2^{\mathcal{O}(\operatorname{\rm
bw}(G^{\prime}))}|V(G^{\prime})|^{\mathcal{O}(1)}$ time. ∎

We now describe how we can partition, for a given input, all good-edge
sections into edge sets in such a way that there exists an optimal solution in
which every set is either contained or deleted completely, and the total
number of sets is bounded in a function of $b$. We will then show how we can
replace the sets with edge sets of size at most two. The main difficulty will
be to ensure that sets that exclude each other continue to do so in the
reduced instance.

######  Lemma 4 (*).

Let $(G,w)$ be an instance of MWBS with $n$ vertices and $b$ bad vertices,
such that ${\cal G}(G)$ is an independent set in $G$ and $\mathrm{deg}(v)=1$
for all $v\in{\cal G}(G)$. Let further $v\in{\cal B}(G)$, and let $S$ be a
good edge-section of $v$. Then $S$ can be partitioned into at most 26 sets
$S_{1},\dots,S_{26}$, such that for every optimal solution
$G^{\prime}\subseteq G$ of $MWBS(G,w)$, there exists an optimal solution
$G^{*}\subseteq G$ of $MWBS(G,w)$, such that $G^{\prime}$ and $G^{*}$
coincides on $G\setminus S$, and for every $i$, $S_{i}$ is either contained or
removed completely in $G^{*}$.

Further, there exists a partition $P_{1},\dots,P_{j}$ of
$\\{S_{1},\dots,S_{26}\\}$, such that for all $P_{i}$: (1) $|P_{i}|\leq 2$,
(2) the edges in $P_{i}$ are consecutive in $S$ and (3) if
$P_{i}=\\{\mathcal{S}_{1},\mathcal{S}_{2}\\}$, then $\mathcal{S}_{1}$ consists
of outgoing edges of $v$ iff $\mathcal{S}_{1}$ consists of incoming edges of
$v$, and at least one of $\mathcal{S}_{1},\mathcal{S}_{2}$ does not form a set
of consecutive edges in $S$.

To show this, we enclose $S$ in a curve $\phi$, and then compute for every
given configuration $X$ the maximal subgraph $G^{\prime}$ such that $v$ has
configuration $X$ in $\phi$. This yields a set of at most 12 possible
locations for switches between incoming and outgoing edges in $S$, which gives
a partition of $S$ into at most 13 sets (corresponding to $P_{1},\dots,P_{j}$)
that do not contain a switch, and thus at most 26 sets that will not be
separated by an optimal solution, corresponding to $S_{1},\dots,S_{26}$. We
now describe a parameter-preserving reduction from MWBS to Cut-MWBS.

######  Lemma 5 (*).

Given an instance $(G,w)$ of MWBS with $b$ bad vertices, we can find in
polynomial time an instance $(G^{\prime},w,\mathcal{E})$ of Cut-MWBS, so that:
(i) For every $\mathcal{E}_{i}\subseteq\mathcal{E}$ with
$|\mathcal{E}_{i}|\geq 2$, there exists a bad vertex $v\in G^{\prime}$ and a
good edge-section $S$ of $v$, so that $\mathcal{E}_{i}$ is a subset of $S$ and
$\mathcal{E}_{i}$ contains only outgoing or only incoming edges of $v$. (ii)
$|{\cal B}(G^{\prime})|\leq b$, (iii) $|\mathcal{E}|=\mathcal{O}(b^{2})$, (iv)
$(G,w)$ and $(G^{\prime},w,\mathcal{E})$ have the same optimal cost, (v) there
exists a partition $P_{1},\dots,P_{j}$ of $\mathcal{E}$, such that
$|P_{i}|\leq 2$ for all $P_{i}$, (vi) if $|P_{i}|=1$, then the edges-set
contained in $P_{i}$ is either an edge between two bad vertices, or there
exists a bad vertex $v\in G^{\prime}$ and good edge-section $S$ of $v$, such
that the edges contained in $P_{i}$ are all consecutive in $S$, and, (vii) if
$|P_{i}|=2$ with $P_{i}=\\{\mathcal{E}_{1},\mathcal{E}_{2}\\}$, there exists
some $v\in{\cal B}(G^{\prime})$ and a good edge-section $S$ of $v$, such that
the edges in $P_{i}$ are all consecutive in $S$; and $\mathcal{E}_{1}$
consists of outgoing edges of $v$ if and only if $\mathcal{E}_{1}$ consists of
incoming edges of $v$, and at least one of $\mathcal{E}_{1},\mathcal{E}_{2}$
does not form a set of consecutive edges in $S$.

Figure 5: (a) Illustration for Lemmas 4 and 5. The gray dashed lines
correspond to a set of switches between the optimal solution we will choose;
they impose the partition $P_{1},\dots,P_{13}$. $S_{1}$ ($S_{2}$) are the
incoming (outgoing) edges of $P_{1}$, respectively. (b) The same vertex after
transition to Cut-MWBS by Lemma 5, and after Reduction Rule 4 (5) got applied
to $P_{2}$ ($P_{1}$), respectively.

See Fig. 5 for a visualization. We obtain this transformation by applying
Lemma 3 in order to get a simplified equivalent instance $G^{\prime}$. Let
$E_{\mathrm{rest}}$ be all edges incident to two bad vertices. For every bad
vertex $v$ and every good edges section $S$ of $v$, let $\mathcal{S}_{v,S}$ be
the partition of $S$ obtained from Lemma 4. We define $\mathcal{E}=\\{e\mid
e\in E_{\mathrm{rest}}\\}\cup\bigcup_{v,S}\mathcal{S}_{v,S}$. This defines the
instance $(G^{\prime},w,\mathcal{E})$ of Cut-MWBS. We will now further reduce
the size of $(G,w,\mathcal{E})$.

######  Reduction Rule 4.

Let $(G,w,\mathcal{E})$ be an instance of Cut-MWBS with properties (i) to
(vii) of Lemma 5. Let $v\in{\cal B}(G)$, let $S$ be a good edge-section of
$v$, and let $\mathcal{E}_{i}\in\mathcal{E}$ such that
$\mathcal{E}_{i}\subseteq S$ is a _consecutive_ set of edges in $S$. Then let
$(G^{\prime},w^{\prime},\mathcal{E^{\prime}})$ be the new instance that is
obtained from $(G,w,\mathcal{E})$ by deleting all edges (and their incident
good vertices) but one edge $e$ out of $\mathcal{E}_{i}$, and assigning
$w^{\prime}(e)=w(\mathcal{E}_{i})$.

######  Reduction Rule 5.

Let $(G,w,\mathcal{E})$ be an instance of Cut-MWBS with the properties (i) to
(vii) of Lemma 5. Let further $v\in{\cal B}(G)$, let $S$ be a good edge-
section of $v$, and let
$\mathcal{E}_{\mathrm{in}},\mathcal{E}_{\mathrm{out}}\in\mathcal{E}$ such that
$\mathcal{E}_{\mathrm{in}},\mathcal{E}_{\mathrm{out}}\subseteq S$,
$\mathcal{E}_{\mathrm{in}}$ are all incoming to $v$,
$\mathcal{E}_{\mathrm{out}}$ are all outgoing of $v$,
$\mathcal{E}_{\mathrm{in}}\cup\mathcal{E}_{\mathrm{out}}$ is a consecutive set
of edges in $S$, and at least one of $\mathcal{E}_{\mathrm{in}}$ or
$\mathcal{E}_{\mathrm{out}}$ does not form a consecutive set of edges in $S$.
We construct a new edge-set $e_{1},e_{2},e_{3},e_{4}$ as follows:
$e_{1},e_{3}$ are incoming for $v$, $e_{2},e_{4}$ are outgoing of $v$, and all
of $e_{1},e_{2},e_{3},e_{4}$ are incident to a newly inserted (good) vertex
$v_{e_{k}}$ for $k\in\\{1,\dots,4\\}$. We set
$w^{\prime}(e_{1})=w^{\prime}(e_{4})=0$,
$w^{\prime}(e_{2})=w(\mathcal{E}_{\mathrm{out}})$ and
$w^{\prime}(e_{3})=w(\mathcal{E}_{\mathrm{in}})$. Further we assign
$e_{1},e_{3}\in\mathcal{E}_{\mathrm{in}}$ and
$e_{2},e_{4}\in\mathcal{E}_{\mathrm{out}}$. Let
$(G^{\prime},w^{\prime},\mathcal{E})$ be the new instance that is obtained
from $(G,w,\mathcal{E})$ by replacing the edges in
$\mathcal{E}_{i}\cup\mathcal{E}_{j}$ with the consecutive sequence
$e_{1},e_{2},e_{3},e_{4}$.

######  Claim 2 (*).

Reductions 4 and 5 are sound.

######  Lemma 6 (*).

Let $(G,w,\mathcal{E})$ be an instance of Cut-MWBS with $b$ bad vertices and
properties (i) till (vii) of Lemma 5. Then we can compute in polynomial time
an equivalent instance $(G^{\prime},w^{\prime},\mathcal{E}^{\prime})$ such
that $V(G^{\prime})=\mathcal{O}(b^{2})$.

See Fig. 5 for an illustration. We compute
$(G^{\prime},w^{\prime},\mathcal{E}^{\prime})$ by applying Reductions 4 and 5
exhaustively. To bound the size of the weights $w$, we use the approach of
Etscheid et al. [EtscheidKMR17] and the well-known Theorem 4.2. This yields
the compression of MWBS (Theorem 4.3) and a kernel for MWBS (Theorem 4.4).

######  Theorem 4.2 ([frank1987application]).

There is an algorithm that, given a vector $\omega\in\mathbb{Q}^{r}$ and an
integer $N$, in polynomial time finds a vector $\bar{\omega}$ such that
$||\bar{\omega}||_{\infty}=2^{\mathcal{O}(r^{3})}$ and
$\text{sign}(\omega\cdot b)=\text{sign}(\bar{\omega}\cdot b)$ for all vectors
$b\in\mathbb{Z}^{r}$ with $||b||_{1}\leq N-1$.

######  Theorem 4.3 (*).

There exists a polynomial-time algorithm that, given an instance $(G,w)$ of
MWBS with $b$ bad vertices and a target value $W$, computes an instance
$(G^{\prime},w^{\prime},\mathcal{E})$ of Cut-MWBS with size
$\mathcal{O}(b^{8})$, and a new target value $W^{\prime}$ with size
$\mathcal{O}(b^{6})$, such that there exists a solution for $(G,w)$ of cost
$W$ if and only if there exists a solution for
$(G^{\prime},w^{\prime},\mathcal{E})$ of cost $W^{\prime}$.

######  Theorem 4.4 (*).

The decision version of MWBS parameterized by the number of bad vertices $b$
admits a polynomial kernel.

##  5 Efficient PTAS for MWBS and Final Remarks

We sketch our Efficient Polynomial-Time Approximation Scheme (EPTAS) for MWBS,
i.e., a $(1-\epsilon)$-approximation that runs in
$2^{\mathcal{O}(1/\epsilon)}\cdot n^{\mathcal{O}(1)}$ time. We use Baker’s
technique [Baker94] to design our EPTAS. Our goal is to reduce the problem to
(multiple instances of) the problem, where the treewidth (hence, branchwidth)
of the graph is bounded by $\mathcal{O}(1/\epsilon)$, at the expense of an
$\epsilon$-factor loss in cost. Then, we can use our single-exponential
algorithm in the branchwidth to solve each such instance exactly, which
implies a $(1-\epsilon)$-approximation.

We sketch the details of this reduction. W.l.o.g. assume that the graph is
connected. We perform a breadth-first search starting from an arbitrary vertex
$v\in V(G)$, and partition the vertex-set into layers $L_{0},L_{1},\ldots$,
where $L_{i}$ is the set of vertices at distance _exactly_ $i$ from $v$ in the
_undirected_ version of $G$. It is known that the treewidth of the subgraph
induced by any $d$ consecutive layers is upper bounded by $\mathcal{O}(d)$ –
this follows from a result of Bodlaender [Bodlaender98], which states that the
treewidth of a planar graph with diameter $D$ is $\mathcal{O}(D)$. Let
$t=1/\epsilon$, and for each $0\leq i\leq t$, let $E^{(i,i+1)}$ denote edges
$uv$ such that $u\in L_{j}$, $v\in L_{j+1}$ with $j\mod t=i$. By an averaging
argument, there exists an index $0\leq i\leq t$, such that the total
contribution of all the edges from an optimal solution (i.e., the set of edges
inducing a maximum-weight bimodal subgraph) that belong to $E^{(i,i+1)}$, is
at most $1/t=\epsilon$ times the weight of the optimal solution. Since we do
not know this index $i$, we consider all values of $i$, and consider the
subproblems obtained by deleting the edges. Then, the graph breaks down into
multiple connected components, and the treewidth of each component is
$\mathcal{O}(1/\epsilon)$. We solve each such subproblem optimally in time
$2^{\mathcal{O}(1/\epsilon)}\cdot n^{\mathcal{O}(1)}$ using Theorem 3.1, and
combine the solutions for the subproblems to obtain a solution for the
original instance. Note that the graph obtained by combining the optimal
solutions for the subproblems is bimodal, and for the correct value of $i$,
the weight of the graph is at least $1-\epsilon$ times the optimal cost. That
is, the combined solution is a $(1-\epsilon)$-approximation.

######  Theorem 5.1 (*).

There exists an algorithm that runs in time $2^{\mathcal{O}(1/\epsilon)}\cdot
n^{\mathcal{O}(1)}$ and returns a $(1-\epsilon)$-approximate solution for the
given instance of MWBS. That is, MWBS admits an EPTAS.

We note that Baker’s technique can also be used to obtain an EPTAS with the
similar running for the _minimization_ variant of MWBS. Although the high
level idea is similar, the details are more cumbersome.

Final Remarks. We conclude by suggesting some open questions. One natural
problem is to ask for a maximum $k$-modal subgraph for any given even integer
$k\geq 2$; we believe that our ideas can be extended to this more general
setting. Another natural variant of MBS is to limit the number of edges that
we can delete to get a bimodal subgraph by an integer $h$; in this setting,
$h$ becomes another parameter in addition to those we have considered.
Finally, studying MBS in the variable embedding setting is an interesting
future direction.

## References

  * [1] Angelini, P., Chaplick, S., Cornelsen, S., Da Lozzo, G.: Planar L-drawings of bimodal graphs. J. Graph Algorithms Appl. 26(3), 307–334 (2022). https://doi.org/10.7155/jgaa.00596
  * [2] Angelini, P., Chaplick, S., Cornelsen, S., Lozzo, G.D.: On upward-planar L-drawings of graphs. In: Szeider, S., Ganian, R., Silva, A. (eds.) 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria. LIPIcs, vol. 241, pp. 10:1–10:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.MFCS.2022.10
  * [3] Angelini, P., Da Lozzo, G., Bartolomeo, M.D., Donato, V.D., Patrignani, M., Roselli, V., Tollis, I.G.: Algorithms and bounds for L-drawings of directed graphs. Int. J. Found. Comput. Sci. 29(4), 461–480 (2018). https://doi.org/10.1142/S0129054118410010
  * [4] Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach. 41(1), 153–180 (1994)
  * [5] Bertolazzi, P., Di Battista, G., Didimo, W.: Quasi-upward planarity. Algorithmica 32(3), 474–506 (2002). https://doi.org/10.1007/s00453-001-0083-x
  * [6] Binucci, C., Di Giacomo, E., Liotta, G., Tappini, A.: Quasi-upward planar drawings with minimum curve complexity. In: Purchase, H.C., Rutter, I. (eds.) Graph Drawing and Network Visualization - 29th International Symposium, GD 2021, Tübingen, Germany, September 14-17, 2021. Lecture Notes in Computer Science, vol. 12868, pp. 195–209. Springer (2021). https://doi.org/10.1007/978-3-030-92931-2_14
  * [7] Binucci, C., Didimo, W.: Computing quasi-upward planar drawings of mixed graphs. Comput. J. 59(1), 133–150 (2016). https://doi.org/10.1093/comjnl/bxv082
  * [8] Binucci, C., Didimo, W., Giordano, F.: Maximum upward planar subgraphs of embedded planar digraphs. Comput. Geom. 41(3), 230–246 (2008). https://doi.org/10.1016/j.comgeo.2008.02.001
  * [9] Bodlaender, H.L.: A partial _k_ -arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1-2), 1–45 (1998). https://doi.org/10.1016/S0304-3975(97)00228-4
  * [10] Chaplick, S., Chimani, M., Cornelsen, S., Lozzo, G.D., Nöllenburg, M., Patrignani, M., Tollis, I.G., Wolff, A.: Planar l-drawings of directed graphs. In: Frati, F., Ma, K. (eds.) Graph Drawing and Network Visualization \- 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017\. Lecture Notes in Computer Science, vol. 10692, pp. 465–478. Springer (2017). https://doi.org/10.1007/978-3-319-73915-1_36
  * [11] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015). https://doi.org/10.1007/978-3-319-21275-3
  * [12] Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)
  * [13] Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Trans. Syst. Man Cybern. 18(6), 1035–1046 (1988). https://doi.org/10.1109/21.23105
  * [14] Didimo, W.: Upward graph drawing. In: Encyclopedia of Algorithms, pp. 2308–2312 (2016). https://doi.org/10.1007/978-1-4939-2864-4_653
  * [15] Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions. Algorithmica 58(3), 790–810 (2010). https://doi.org/10.1007/s00453-009-9296-1
  * [16] Etscheid, M., Kratsch, S., Mnich, M., Röglin, H.: Polynomial kernels for weighted problems. J. Comput. Syst. Sci. 84, 1–10 (2017). https://doi.org/10.1016/j.jcss.2016.06.004
  * [17] Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization. Theory of parameterized preprocessing. Cambridge University Press, Cambridge (2019)
  * [18] Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. J. Graph Theory 51(1), 53–81 (2006). https://doi.org/10.1002/jgt.20121
  * [19] Frank, A., Tardos, É.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7, 49–65 (1987). https://doi.org/10.1007/BF02579200
  * [20] Impagliazzo, R., Paturi, R.: Complexity of k-sat. In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999. pp. 237–240. IEEE Computer Society (1999). https://doi.org/10.1109/CCC.1999.766282
  * [21] Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001). https://doi.org/10.1006/jcss.2001.1774
  * [22] Jacob, H., Pilipczuk, M.: Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. In: Bekos, M.A., Kaufmann, M. (eds.) Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022. Lecture Notes in Computer Science, vol. 13453, pp. 287–299. Springer (2022). https://doi.org/10.1007/978-3-031-15914-5_21
  * [23] Jünger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S. (ed.) Graph Drawing, 6th International Symposium, GD’98, Montréal, Canada, August 1998, Proceedings. Lecture Notes in Computer Science, vol. 1547, pp. 224–237. Springer (1998). https://doi.org/10.1007/3-540-37623-2_17
  * [24] Robertson, N., Seymour, P.D.: Graph minors. x. obstructions to tree-decomposition. J. Comb. Theory, Ser. B 52(2), 153–190 (1991). https://doi.org/10.1016/0095-8956(91)90061-N
  * [25] Robertson, N., Seymour, P.D.: Graph minors. x. obstructions to tree-decomposition. J. Comb. Theory, Ser. B 52(2), 153–190 (1991). https://doi.org/10.1016/0095-8956(91)90061-N
  * [26] Vial, J.J.B., Da Lozzo, G., Goodrich, M.T.: Computing $k$-modal embeddings of planar digraphs. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany. LIPIcs, vol. 144, pp. 19:1–19:16. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.ESA.2019.19

##  Appendix 0.A Appendix

###  0.A.1 Details for Section 2

We refer to the books [CyganFKLMPPS15, FominLSZ19] for an introduction to the
parameterized complexity area. Formally, a _parameterized problem_ is a
language $L\subseteq\Sigma^{*}\times\mathbb{N}$ where $\Sigma$ is a finite
alphabet. Thus, an input of $L$ is a pair $(I,k)$ where $I$ is a string
encoding the instance and $k\in\mathbb{N}$ is a _parameter_. The computational
complexity is measured as a function of $|I|$ and $k$. A problem $L$ is said
to be _fixed-parameter tractable_ (FPT) if it can be solved in
$f(k)\cdot|I|^{\mathcal{O}(1)}$ time for some function $f$.

A _kernelization_ algorithm or _kernel_ for a parameterized problem $L$ is a
polynomial-time algorithm that, given an instance $(I,k)$ of $L$, outputs an
instance $(I^{\prime},k^{\prime})$ of the same problem such that (i) $(I,k)\in
L$ if and only if $(I^{\prime},k^{\prime})\in L$ and (ii)
$|I^{\prime}|+k^{\prime}\leq f(k)$ for a computable function $f$. The function
$f$ is called the _size_ of the kernel; a kernel is polynomial of $f$ is a
polynomial. Similarly, a _compression_ of $L$ into a (non-parameterized)
problem $L^{\prime}$ is a polynomial-time algorithm that for an instance
$(I,k)$ of $L$, outputs an instance $I^{\prime}$ of $L^{\prime}$ such that (i)
$(I,k)\in L$ if and only if $I^{\prime}\in L$ and (ii) $|I^{\prime}|\leq f(k)$
for a computable function $f$.

###  0.A.2 Details for Section 3

See 1

###### Proof.

Since the inside of $\phi$ contains only $e$, testing whether non-deleting $e$
fulfills both $X_{u}$ and $X_{v}$ can be done in constant time. Knowing
whether or not $e$ needs to be deleted gives us $G^{\prime}$. ∎

See 2

###### Proof.

We will show that an optimal solution for $\phi_{3}$ with the given
configuration set can be obtained from optimal solutions for $\phi_{1}$,
$\phi_{2}$. First, we show that there exist configurations $X_{\phi_{1}}$ and
$X_{\phi_{2}}$ such that the optimal subgraph $G^{\prime}$ is optimal in
$\phi_{1}$ and $\phi_{2}$ with regard to these configurations as well.

Assume its not optimal in $\phi_{1}$. Since $G^{\prime}$ is bimodal in
$\phi_{3}$, we know that it has a configuration set $X_{\phi_{1}}$ for
$\phi_{1}$, therefore, the restriction of $G^{\prime}$ to the left side of
$\phi_{1}$ is not an optimal solution under the condition that is bimodal in
$\phi_{1}$ and has $X_{\phi_{1}}$ as configuration set.

Now let $G_{\phi_{1}}$ be an optimal solution under these conditions, and let
$G^{\prime\prime}$ be the subgraph, that coincides with $G_{\phi_{1}}$ on the
inside of $\phi_{1}$ and with $G^{\prime}$ on the outside. This solution has a
lower cost then $G^{\prime}$, since the cost on the inside of $\phi_{1}$ got
lower, and the cost on the rest stays the same as in $G^{\prime}$.

To show that $G^{\prime\prime}$ is a valid solution, we need to show that it
is bimodal in $\phi_{3}$ and has configuration $X_{\phi_{3}}$. To show that
$G^{\prime\prime}$ is bimodal it is sufficient to consider those vertices that
are cut by both $\phi_{1},\phi_{2}$, since the bimodality of all other
vertices inside of $\phi_{3}$ follows from the bimodality of $G^{\prime}$ and
$G_{\phi_{1}}$. Let $v$ be a vertex cut by both $\phi_{1}$ and $\phi_{2}$. Let
$X_{v}^{1},X_{v}^{2}$ the configuration of $v$ regarding $\phi_{1},\phi_{2}$
respectively. Since $v$ is bimodal in $G^{\prime}$, $X_{v}^{1}$ and
$X_{v}^{2}$ are compatible. Since compatible configurations imply bimodality
and $v$ still has those configurations in $G^{\prime\prime}$, it is bimodal in
$G^{\prime\prime}$. In order to show that $G^{\prime\prime}$ is still of
configuration $X_{\phi_{3}}$, it suffices to consider the vertices $v$ that
are cut by all of $\phi_{1},\phi_{2},\phi_{3}$, since the rest of the vertices
on $\phi_{3}$ has the same configuration as in $G^{\prime}$ and thus as in
$X_{\phi_{3}}$. Let $v$ be such a vertex, let $X_{v}^{1},X_{v}^{2}$ be the
minimal of $v$ regarding $\phi_{1},\phi_{2}$ respectively, and let $X_{v}$ be
the configuration of $v$ regarding $\phi_{3}$. Since $G^{\prime}$ is a valid
solution, $X_{v}^{1}$ and $X_{v}^{2}$ are compatible with respect to $X_{v}$.
Since we did not change the configuration of $v$ in $G^{\prime\prime}$
regarding $\phi_{1}$, and the ability to form a configuration depends only on
that, $v$ is of configuration $X_{v}$ for $\phi_{3}$ in $G^{\prime\prime}$ as
well. This is a contradiction to the assumption that $G^{\prime}$ was optimal.

The same argument also shows that, given the right configuration sequence
$X_{\phi_{1}}$ for $\phi_{1}$ and any arbitrary optimal solution
$G_{\phi_{1}}$, there exists an optimal solution $G^{*}$ which is bimodal
inside of $\phi_{3}$, has the required configuration sequence $X_{\phi_{3}}$
and coincides with $G_{\phi_{1}}$ on the inside of $\phi_{3}$.

Since the situation is the symmetrical for $\phi_{2}$, we can find the optimal
solution for the given configuration set $X_{\phi_{3}}$ by exhaustively trying
all combinations of configuration sets for $\phi_{1},\phi_{2}$ and computing
the optimal value obtainable this way. Since $\phi_{1},\phi_{2}$ have width at
most $\ell$, and there are at most 6 configurations per vertex, the number of
configurations is bounded by $6^{2\ell}$. Since we already know optimal
solutions for all configuration sets of $\phi_{1}$, $\phi_{2}$, we can compute
the optimal solution of every valid configuration set by computing the cost
for $\phi_{1}$ and $\phi_{2}$, and taking the solution with the lowest overall
cost, which requires only polynomial time. Hence, the overall running time is
$\mathcal{O}(6^{2\ell})\cdot n^{\mathcal{O}(1)}$. ∎

See 3.1

###### Proof.

Let $(G,w)$ be an instance of MWBS with $n$ vertices. Without loss of
generality, $G$ is embedded in the sphere $\Sigma$. Let $\langle
T,\xi,\Pi\rangle$ be a sphere-cut decomposition of $G$ with minimum width
$\ell$, which can be computed in $\mathcal{O}(n^{3})$ time.

Without loss of generality, $G$ is connected (otherwise, the optimal solution
can be computed for each connected component independently). If $G$ has
branchwidth 1, then it is a disjoint union of stars [RobertsonS91]. For a
star, we can compute the optimal bimodal subgraph in quadratic time by trying
all combinations to switch from incoming to outgoing edge for $v$, all other
vertices are already bimodal since they have only one incident edge. We assume
therefore that $G$ has branchwidth $\ell>1$, and know from Proposition 1 that
we can obtain an optimal sphere-cut decomposition $\langle T,\xi,\Pi\rangle$
of $G$ in $\mathcal{O}(n^{3})$ time. Let $\ell$ be the width of $\langle
T,\xi,\Pi\rangle$.

Let $r\in T$ be an arbitrary leaf of $T$ that we choose as a root, and let
$e_{r}$ be the edge of $G$ associated with $r$. In this way we can assume that
$T$ is rooted and directed, such that $r$ has outdegree 0 and every other node
in $T$ has outdegree precisely 1. We know that every arc $a\in E(T)$
corresponds to a noose $O$ that cuts precisely $\operatorname{mid}(a)$ in
order $\pi_{a}$. Every noose $O$ bounds two closed discs in $\Sigma$, we
define the inside of every $O$ to be the one that does not contain $e_{r}$. We
now describe a dynamic program that computes an optimal solution for $(G,w)$.
Let $O$ be a noose and let $X_{O}$ be a configuration set for $O$. Then we
define $E_{(O,X_{O})}$ to be an edge set of minimum weight, such that
$G\setminus E_{(O,X_{O})}$ is bimodal inside of $O$ and has the configuration
set $X_{O}$ regarding $O$. We will now show how the entries $E_{(O,X_{O})}$
can be computed bottom-up for every noose in the sphere-cut decomposition.

We will have to start with the entries of leaves in $T$. Let $u\in V(T),u\neq
r$ be a leaf of $T$, let $e=(v_{1},v_{2})$ be the edge in $G$ associated with
$u$, let $a$ be the unique outgoing arc of $u$, and let $O_{a}$ be the noose
corresponding to $a$. We can see that $O_{a}$ is a closed curve with
$\operatorname{mid}(a)=\\{v_{1},v_{2}\\}$, and the inside of $O_{a}$ contains
precisely $e$. Now let $X_{O_{a}}$ be a configuration set for $O_{a}$.
According to Lemma 1 we can compute $E_{(O_{a},X_{O_{a}})}$ in constant time.
Since $|\operatorname{mid}(a)|=2$, we have precisely $6^{2}=36$ and thus a
constant number of configuration sets for $O_{a}$, and can compute all entries
for $O_{a}$ in $\mathcal{O}(1)$ time.

Now let $u\in V(T)$ be an internal vertex of $T$, let $a$ be the unique
outgoing arc of $u$, let $O_{a}$ be the noose corresponding to $a$. Let
$E_{(O^{\prime},X_{O^{\prime}})}$ already be computed for every noose
$O^{\prime}$ corresponding to an arc in the sub-tree rooted by $u$ and for
every configuration set $X_{O^{\prime}}$ of $O^{\prime}$. We know that $O_{a}$
is a closed curve with width at most $\ell$. We further know that the inside
of $O_{a}$ is partitioned by two nooses that also have width at most $\ell$.
Now let $X_{O_{a}}$ be a configuration set for $O_{a}$. According to Lemma 2
we can compute $E_{(O_{a},X_{O_{a}})}$ in $\mathcal{O}(6^{2\ell})\cdot
n^{\mathcal{O}(1)}$ time. Since $|\operatorname{mid}(a)|\leq\ell$, we have at
most $6^{\ell}$ configuration sets for $O_{a}$, and can thus compute all
entries for $O_{a}$ in $\mathcal{O}(6^{2\ell})\cdot n^{\mathcal{O}(1)}$ time.
Since every arc of $T$ is either incoming for a leaf or an internal vertex of
$T$, all table entries can be computed in this manner. Since
$|E(T)|=\mathcal{O}(|E(G)|)=\mathcal{O}(|V(G)|)$, this can be done in
$\mathcal{O}(6^{2\ell})\cdot n^{\mathcal{O}(1)}$ time.

Recall that $e_{r}=(v_{o},v_{i})$ is the edge associated with the root $r$ of
$T$. Let $a$ be the incident (incoming) arc of $r$ in $T$, and let $O_{a}$ be
the noose associated with $a$. Assume that there exists an optimal solution
$G^{\prime}$ for MWBS$(G,w)$ such that $e_{r}\notin E(G^{\prime})$, and let
$E_{\mathrm{opt}}=E(G)\setminus E(G^{\prime})$ Then $G^{\prime}$ is bimodal in
$O_{a}$. On the other hand, every subgraph of $G$ that is bimodal inside of
$O_{a}$ is an optimal solution for $(G,w)$. Let $E^{*}_{\setminus
e_{r}}=\min_{X_{O_{a}}}\\{E_{(O_{a},X_{O_{a}})}\\}$, with $X_{O_{a}}$ being a
configuration set of $O_{a}$. Since every subgraph of $G$ that is bimodal
inside of $O_{a}$ has a configuration set for $O_{a}$, the graph
$G^{*}_{\setminus e_{r}}=(V,E\setminus E^{*}_{\setminus e_{r}})$ is an optimal
solution for MWBS$(G,w)$. Since all table-entries are known, and there are at
most $36$ configuration sets for $O_{a}$, we can compute $E^{*}_{\setminus
e_{r}}$ and thus $G^{*}_{\setminus e_{r}}$ in linear time.

Now assume that there exists an optimal solution $G^{\prime}$ for $(G,w)$ with
$e_{r}\in E(G^{\prime})$, and let $E_{\mathrm{opt}}=E(G)\setminus
E(G^{\prime})$. Then $G^{\prime}$ is bimodal in $O_{a}$, has configuration
$(i,o,i)$ in $v_{i}$, and has configuration $(o,i,o)$ in $v_{o}$. On the other
hand, every subgraph of $G$ bimodal inside of $O_{a}$, containing $e_{r}$,
with configuration $(i,o,i)$ in $v_{i}$ and configuration $(o,i,o)$ in $v_{o}$
regarding $O_{a}$ is an optimal solution for MWBS$(G,w)$. Set the
configuration set $X_{O_{a}}=(X_{v_{i}}=(i,o,i),X_{v_{o}}=(o,i,o))$. We then
know that $E^{*}_{e_{r}}=E_{(O_{a},X_{O_{a}})}$ is an edge set of minimal cost
such that $G^{*}_{e_{r}}=(V(G),E(G)\setminus E^{*}_{\setminus e_{r}})$ is an
optimal solution for MWBS$(G,w)$. Since all table-entries are known, we
already have $E^{*}_{\setminus e_{r}}$ and can thus compute $G^{*}_{\setminus
e_{r}}$ in linear time.

Since one of these two cases must be fulfilled in any optimal solution, one of
$G^{*}_{\setminus e_{r}}$ and $G^{*}_{e_{r}}$ must be an optimal solution for
MWBS$(G,w)$, and we can find it in linear time.

Since we could compute a sphere-cut decomposition $\langle T,\xi,\Pi\rangle$
in $\mathcal{O}(n^{3})$ time, since all table-entries $E_{(O,X_{O})}$ could be
computed in $\mathcal{O}(6^{2\ell})\cdot n^{\mathcal{O}(1)}$ time, and since
$G^{*}_{e_{r}}$ and $G^{*}_{e_{r}}$ could be computed in linear time, the
overall running time of the algorithm is $2^{\mathcal{O}(\ell)}\cdot
n^{\mathcal{O}(1)}$. ∎

###  0.A.3 Details for Section 4

See 1 Proof. The soundness of Reduction rule 1 is straightforward.

Now consider Reduction rule 2. Consider an edge $(u,v)$ between two bimodal
vertices $u$ and $v$. Suppose that $G^{*}$ a bimodal subgraph of $G$ of weight
at least $W$. Then $\hat{G}=G^{*}-(u,v)$ is a bimodal subgraph of $G^{\prime}$
and $w(E(\hat{G}))\geq W-w(u,v)=W^{\prime}$. In the reverse direction, let
$\hat{G}$ be a bimodal subgraph of $G^{\prime}$ of weight at least
$W^{\prime}$. Without loss of generality we can assume that $V(\hat{G})=V(G)$.
Consider $G^{*}$ obtained from $\hat{G}$ by the addition of $(u,v)$. We have
that $G^{*}$ is bimodal because $u$ and $v$ are bimodal in $G$. Thus, $G^{*}$
is a bimodal subgraph of $G$ of weight at least $W=W^{\prime}+w(u,v)$.

Finally, we show that Reduction rule 3 is sound. For this, we assume that
$v\in\mathcal{G}(G)$ and $G^{\prime}$ is obtained from $G$ by the replacement
of $(u,v)\in E(G)$ by $(u,x_{xy})$ for all $u\in V$ that are adjacent to $v$,
where $x_{uv}$ is the vertex constructed for $(u,v)$.

Let $G^{*}$ be a bimodal subgraph of $G$ of maximum weight, and let $u\in V$,
$u$ adjacent to $v$. If $(u,v)\notin E(G^{*})$, we define $\hat{G}$ to be the
spanning subgraph of $G^{\prime}$ with $E(\hat{G})=E(G^{*})$ and observe that
$\hat{G}$ is a bimodal subgraph of $G$ because $x_{uv}$ is an isolated vertex
of $\hat{G}$. Trivially, $w(E(\hat{G}))\geq w(E(G^{*}))$. Otherwise, if
$(u,v)\in E(G^{*})$, we construct the spanning subgraph $\hat{G}$ of
$G^{\prime}$ by setting
$E(\hat{G})=(E(G^{*})\setminus\\{(u,v)\\})\cup\\{(u,x_{uv})\\}$. Notice that
$w(E(\hat{G}))\geq w(E(G))$. Furthermore, $x_{uv}$ is bimodal because it is
incident only to $(u,x_{uv})$. This implies that $\hat{G}$ is a bimodal
subgraph of $G^{\prime}$ whose weight is at least the weight of $G$.

For the opposite direction, assume that $\hat{G}$ is a bimodal subgraph of
$G^{\prime}$ of maximum weight. If $(u,x_{uv})\notin E(\hat{G})$, we set
$G^{*}$ be the spanning subgraph of $G$ with $E(G^{*})=E(\hat{G})$. Then
$G^{*}$ is bimodal and $w(E(G^{*}))\geq w(E(\hat{G}))$. Suppose that
$(u,x_{uv})\in E(\hat{G})$. Then we define $G^{*}$ to be the spanning subgraph
of $G$ with $E(G^{*})=(E(\hat{G})\setminus\\{(u,x_{uv})\\})\cup\\{(u,v)\\}$.
By definition, $w(E(G^{*}))=w(E(G^{\prime}))$. Because $v$ is a bimodal vertex
of $G$, we have that $v$ is bimodal in $G^{*}$. Therefore, $G^{*}$ is a
bimodal subgraph of $G$ whose weight is at least the weight of $\hat{G}$.
Thus, Reduction rule 3 is sound. This concludes the proof. $\blacksquare$

See 3

###### Proof.

Let $(G^{\prime},w)$ be the instance of MWBS obtained by applying reductions
1, 2 and 3 exhaustively. Since none of them introduces new bad vertices, (i)
is fulfilled. Let $v\in{\cal G}(G^{\prime})$. If $v$ were adjacent to another
good vertex, we could apply reduction 2. Thus, (ii) is fulfilled. If
$deg(v)>1$, reduction 3 could be applied. If $deg(v)=0$, reduction 1 could be
applied. Thus, (iii) is fulfilled. It is left to show that the number of
reduction steps is bounded in a polynomial. Reduction 1 is performed at most
once for every already existing vertex and at most once for every vertex
introduced by an iteration of reduction 3. Since the number of new vertices
introduced over all iterations of reduction 3 is bounded in $2\cdot|E(G)|$,
reduction 1 is performed at most $|V(G)|+2|E(G)|$ times. Reduction 2 is
performed at most $|E|$ times, since it always deletes an edge, and the number
of edges stays the same during the other reductions. Reduction 3 is performed
at most once per preexisting vertex and never for any new vertex introduced
during an iteration of it, so it is performed at most $|V(G)|$ times. Thus,
the total number of reductions steps is linear in the size of $G$, and the
algorithm runs in polynomial time. ∎

See 4

###### Proof.

Since $S$ is a good edge-section, and all good incident vertices of $S$ have
degree 1, we can draw a curve $\phi$ into $G^{\prime}$ such that $\phi$ cuts
$G$ only in $v$, and has precisely $S$ and the respective incident good
vertices of $S$ in its interior.

######  Claim 3.

Given a configuration $X$, we can in polynomial time compute a subset $S_{X}$
of $S$ of minimal cost, such that $v$ has configuration $X$ in $\phi$ if
$S_{X}$ is removed.

Proof. Edge-deletion till fulfillment of a configuration is equivalent to
finding the (at most two) switches from a group of incoming edges to a group
of outgoing edges and vice versa. Since there are at most two switches, the
number of possibilities is bounded by $\mathcal{O}(n^{2})$. Once the placement
of the switches is known, the corresponding costs are equivalent to the weight
of the set of edges that are in the section of opposite type (incoming instead
of outgoing or vice versa). $S_{X}$ is chosen as the set of edges with minimal
cost obtained this way. $\blacksquare$

Now let $G^{\prime}$ be an optimal solution for $(G,w)$. We know that $v$ has
a configuration in $G^{\prime}$ regarding $\phi$, let $X$ be the minimal
configuration for which this is true. Since bimodality of $v$ in $G^{\prime}$
does not change if we change the inside of $\phi$ as long as $v$ keeps
configuration $X$, we can construct another solution $G^{*}$ for $(G,w)$ that
coincides with $G^{\prime}$ on the outside of $\phi$ and with $G\setminus
S_{X}$ on the inside of $\phi$. Since $S_{X}$ had the minimal cost for
configuration $X$, the cost of $G^{*}$ is not bigger than the cost of
$G^{\prime}$, thus $G^{*}$ is an optimal solution for $(G,w)$.

There are at most 6 configurations possible for $v$ regarding $\phi$, and
every configuration is associated with at most 2 switches, therefore we can
separate $S$ in 12 places and thus partition it in into 13 sets
$S^{1},\dots,S^{13}$, such that there exists an optimal solution $G^{*}$ for
which no switch from incoming to outgoing edges (or vice versa) happens inside
of a $S^{i}$. Now let $S^{i}$ be such a set, and let $\mathrm{In}(S^{i})$ and
$\mathrm{Out}(S^{i})$ denote the incoming and outgoing edges of $S^{i}$,
respectively. Since no switch happens inside of $S^{i}$, $\mathrm{In}(S^{i})$
is either contained or removed completely in $G^{*}$. The same is true for
$\mathrm{Out}(S^{i})$. This gives us a partition
$\\{\mathrm{In}(S^{i}),\mathrm{Out}(S^{i})\mid 1\leq i\leq 13\\}$ of $S$ with
at most 26 sets that has the wanted properties.

We get the partition $P_{1},\dots,P_{j}$ of
$\\{\mathrm{In}(S^{i}),\mathrm{Out}(S^{i})\mid 1\leq i\leq 13\\}$, if we set
$P_{i}=\\{\mathrm{In}(S^{i}),\mathrm{Out}(S^{i})\\}$ and then remove all empty
sets. ∎

See 5

###### Proof.

According to Lemma 3, we can find in polynomial time an equivalent instance
$(G^{\prime},w)$, such that $|{\cal B}(G^{\prime})|\leq b$ (which already
impies (ii)); ${\cal G}(G^{\prime})$ being an independent set in $G^{\prime}$,
and for all $v\in{\cal G}(G^{\prime})$, $\deg(v)=1$. We will not change the
graph further, this already implies (ii) We are now able to apply Lemma 4 to
$(G^{\prime},w)$. For every $v\in{\cal B}(G^{\prime})$ and every good edge-
section $S$ of $v$, let $\mathcal{S}_{v,S}$ denote a partition of $S$ as
described in Lemma 4.

Let $E_{\mathrm{rest}}$ denote the set of all edges that are not contained in
some $\mathcal{S}_{v,S}$. We define $\mathcal{E}=\\{\cup_{v\in{\cal
B}(G^{\prime}),S}\mathcal{S}_{v,S}\\}\cup\\{\\{e\\}\mid e\in
E_{\mathrm{rest}}\\}$. Since every edge can be contained in at most one
$\mathcal{S}_{v,S}$, $\mathcal{E}$ is a partition of $E(G^{\prime})$. Thus,
$(G^{\prime},w,\mathcal{E})$ is an instance of Cut-MWBS.

We show that $(G^{\prime},w,\mathcal{E})$ has the described properties.
Clearly, every solution for $(G^{\prime},w,\mathcal{E})$ is one for
$(G^{\prime},w)$ as well. The other way around, we can find an optimal
solution for $(G^{\prime},w)$ that for any given $E_{i}\in\mathcal{E}$ either
removes all edges in $E_{i}$ or none by iteratively applying Lemma 4. This is
an optimal solution for $(G^{\prime},w,\mathcal{E})$ as well, and (iv) is
fulfilled.

Let $\mathcal{E}_{i}\subseteq\mathcal{E}$ with $|\mathcal{E}_{i}|\geq 2$. Then
$\mathcal{E}_{i}\in\mathcal{S}_{v,S}$ for some $v\in{\cal B}(G^{\prime})$ and
some good edge-section $S$ of $v$, with only incoming or only outgoing edges
of $v$ by construction, and thus (i) is fulfilled.

Now let $e$ be an edge incident to a bad vertex $v$ and to some good vertex
$u$. By definition, $e$ is contained in some good edge-section. Observation 1
gives us that there exist at most $b\cdot(b-1)$ good edge-sections in total.
Since every good edge-section got partitioned into at most 26 sets, we know
that $|\\{\cup_{v\in{\cal
B}(G^{\prime}),S}\mathcal{S}_{v,S}\\}|=\mathcal{O}(b^{2})$. Since the number
of edges incident to two bad vertices is bounded by $\mathcal{O}(b)$,
$|\mathcal{E}|=\mathcal{O}(b^{2})$ as well and (iii) is fulfilled.

Since we obtain every set $\mathcal{E}_{i}$ with more than 1 vertex out of
some set $S^{i}$ of consecutive edges, and we take all edges of a specific
type, (v) till (vii) are fulfilled by the properties of the partition
$P_{1},\dots,P_{j}$ of $\\{S_{1},\dots,S_{2}6\\}$ of Lemma 4. ∎

See 2 Proof. If $\mathcal{E}_{i}\subseteq S$ is a consecutive set of edges in
$S$, it clearly suffices to choose one representative for a consecutive set of
edges $\mathcal{E}_{i}$ in $S$ that are all part of the same in-wedge or out-
wedge, and reduction 4 is sound.

To show soundness of 5, consider an optimal deletion set $E_{\mathrm{opt}}$
for $(G,w,\mathcal{E})$, in which no switch of $v$ between incoming and
outgoing vertices or vice versa happens in the consecutive edge sequence of
$\mathcal{E}_{\mathrm{in}}\cup\mathcal{E}_{\mathrm{out}}$. Thus,
$\mathcal{E}_{\mathrm{in}}$ is deleted in the optimal solution if and only if
$\mathcal{E}_{\mathrm{out}}$ is not deleted in the optimal solution. Let
without loss of generality $\mathcal{E}_{\mathrm{in}}\in E_{\mathrm{opt}}$.
Thus,
$E^{\prime}_{\mathrm{opt}}=E_{\mathrm{opt}}\setminus\mathcal{E}_{\mathrm{in}}\cup\\{e_{1},e_{3}\\}$
has the same cost as $E_{\mathrm{opt}}$, and it is a valid solution deletion
set for $(G^{\prime},w^{\prime},\mathcal{E})$ since the outgoing vertices
$e_{2},e_{4}$ do not violate bimodality. We can obtain an optimal solution for
$(G,w,\mathcal{E})$ out of one for $(G^{\prime},w^{\prime},\mathcal{E})$ in
the same manner. $\blacksquare$

See 6

###### Proof.

Apply Reductions 4 and 5 exhaustively to $(G,w,\mathcal{E})$ in order to
obtain $(G^{\prime},w^{\prime},\mathcal{E}^{\prime})$. Then,
$|\mathcal{E^{\prime}}_{i}|\leq 2$ for all
$\mathcal{E^{\prime}}_{i}\in\mathcal{E^{\prime}}$. Since
$\mathcal{E^{\prime}}$ is a partition of $E(G^{\prime})$, we have
$|E(G^{\prime})|\leq
2|\mathcal{E^{\prime}}|=|\mathcal{E}|=\mathcal{O}(b^{2})$. Since none of the
reduction rules creates isolated vertices, size of $V(G)$ is bounded by
$\mathcal{O}(b^{2})$ as well. ∎

See 4.3

###### Proof.

We first apply Lemma 5 and then Lemma 6 to obtain an instance
$(G,w,\mathcal{E})$ of Cut-MWBS with $|V(G)|=\mathcal{O}(b^{2})$ and the same
optimal cost as MWBS$(G,w)$. Let $r=|E(G)|+1=\mathcal{O}(b^{2})$, and let
$\omega=(w(e_{1}),w(e_{2}),\ldots,w(e_{m}),W)\in\mathbb{Q}^{r}$, where the
edges in $G$ are indexed in an arbitrary order. Using Theorem 4.2, we obtain a
vector $\bar{\omega}$ such that $\text{sign}(\omega\cdot
x)=\text{sign}(\bar{\omega}\cdot x)$ for each $x\in\mathbb{Z}^{r}$ with
$||x||_{1}\leq r-1$. Now consider an edge set $F\subseteq E(G)$ upon whose
deletion we obtain an optimal solution for $(G,w,\mathcal{E})$, and consider
the vector $x_{F}\in\\{-1,0,1\\}^{r}$ such that

$x_{F}(e_{i})=\begin{cases}1&\text{ if }e_{i}\in F,\\\ 0&\text{ if
}e_{i}\not\in F\end{cases}$

and the last ($r$st) coordinate of $b_{F}$ is equal to $-1$. Then, note that
$\omega\cdot x_{F}=\sum_{e_{i}\in F}w(e_{i})-W$, which means that $F$ is a
feasible solution if and only if $\omega\cdot x\leq 0$, i.e.,
$\text{sign}(\omega\cdot x_{F})\neq 1$. Since the new vector $\bar{\omega}$
preserves the sign of inner product with all such vectors $x_{F}$, it follows
that the (in-)feasibility of all weighted solutions is preserved w.r.t. the
new weight vector $\bar{\omega}$. Thus, the new weights of the edges are given
by the respective entries in $\bar{\omega}$, and the new target weight
$\bar{W^{\prime}}$ is given by the last entry of $\bar{\omega}$. Since each
entry in $\bar{\omega}$ is an integer whose absolute value is bounded by
$2^{\mathcal{O}(b^{6})}$, it follows that we need $\mathcal{O}(b^{8})$ bits to
encode $\bar{\omega}$. ∎

See 4.4

###### Proof.

We can compute an $(G^{\prime},w^{\prime},\mathcal{E})$ of Cut-MWBS with size
$\mathcal{O}(b^{8})$, and a new target value $W^{\prime}$ with size
$\mathcal{O}(b^{6})$ in polynomial time, such that there exists an solution
for $(G,w)$ of cost $W$ if and only if there exists a solution for
$(G^{\prime},w^{\prime},\mathcal{E})$ of cost $W^{\prime}$ according to
Theorem 4.3. Since the decision versions of MWBS and Cut-MWBS are both NP-
complete, there exists a polynomial-time reduction from the decision version
of Cut-MWBS onto the decision version of MWBS (see e.g. [FominLSZ19, Theorem
1.6]). Using this reduction, we can compute a new instance $(G^{*},w^{*})$ of
MWBS and some $W^{*}$ such that there exists a solution for $(G^{*},w^{*})$ of
cost at most $W^{*}$ if and only if there exists a solution for
$(G^{\prime},w^{\prime},\mathcal{E})$ of cost at most $W^{\prime}$, such that
the size of $(G^{*},w^{*})$ is bounded in a polynomial of the size of
$(G^{\prime},w^{\prime},\mathcal{E})$ and thus in a polynomial of $b$. ∎

##  Appendix 0.B EPTAS for MWBS

In this section, we use Baker’s technique [Baker94] to prove the following
theorem. See 5.1

###### Proof.

For a directed graph $H$, let $\overline{H}$ denote its undirected version.
Let $(G,w)$ be the given instance of MWBS. Let $E^{*}\subseteq E(G)$ denote an
optimal solution, i.e., a maximum-weight subset of edges such that
$G^{*}=G[E^{*}]$ is bimodal. Let $OPT=w(E^{*})$ denote the weight of the
solution. Without loss of generality, we assume $\overline{G}=(V,F)$ is
connected – otherwise we can use the following algorithm on each connected
component separately.

Let $t=\lceil 1/\epsilon\rceil$. Fix an arbitrary vertex $v\in
V(\overline{G})$. For any $i\geq 0$, let $L_{i}$ denote the set of vertices
that are at distance exactly $i$ from $v$ in $\overline{G}$. Note that any
$u\in L_{i}$ has neighbors in $L_{j}$ such that $|i-j|\leq 1$. For $i\geq 0$,
let $E^{(i,i+1)}\subseteq E(G)$ denote the set of directed edges with one
endpoint in $L_{i}$ and other endpoint in $L_{i+1}$. For each $E^{(i,i+1)}$,
let $F^{(i,i+1)}$ denote the corresponding set of undirected edges.

######  Observation 2.

For some $i\in\left\\{0,1,\ldots,t-1\right\\}$, it holds that
$w(E^{(i,i+1)}\cap E^{*})\leq\frac{1}{t}\cdot OPT$.

###### Proof.

Follows from the fact that the sets $E^{(i,i+1)}$ and $E^{(j,j+1)}$ are
pairwise disjoint for distinct $i,j$. ∎

For each $0\leq i\leq t-1$, let $G_{i}$ denote the graph $G-E^{(i,i+1)}$. Note
that each connected component in $\overline{G_{i}}$ is induced by vertices
belonging to at most $t$ consecutive layers, and hence, using standard
arguments (e.g., [CyganFKLMPPS15]), the treewidth of $\overline{G_{i}}$ is
bounded by $O(t)=O(1/\epsilon)$. Our algorithm performs the following
operations for each $0\leq i\leq t-1$. We solve MWBS on each connected
component of $G_{i}$ separately, in time $2^{O(1/\epsilon)}\cdot n^{O(1)}$,
using the algorithm from Theorem 3.1. Let $G^{\prime}_{i}$ denote the graph
obtained by taking the disjoint union of the solutions for all subgraphs. It
is easy to see that the resulting graph is bimodal. Finally, for the correct
value of $i$, i.e., that guaranteed by Observation 3, we know that the total
weight of edges in $|E^{(i,i+1)}\cap E^{*}|\leq\epsilon\cdot OPT$; whereas the
edges in $E^{*(i,i+1)}\setminus E^{*}$ do not contribute to $OPT$. It follows
that the total weight of the edges in $G^{\prime}_{i}$ is at least
$(1-\epsilon)\cdot OPT$. ∎

Note that here we designed an approximation version for the maximization
objective of MWBS, i.e., where we want to maximize the total weight of the
bimodal subgraph. We can also consider the minimization objective, where the
goal is to minimize the total weight of the edges removed to obtain a bimodal
subgraph. Note that although the decision versions of the two objectives are
equivalent, approximation for one version does not necessarily imply a good
approximation for the other. Nevertheless, we can adapt Baker’s technique to
design an EPTAS, i.e., $(1+\epsilon)$-approximation for the minimization
objective as well. However, a formal description of this algorithm is quite
tedious, since simply deleting the edges of $E^{(i,i+1)}$ as in above, is not
sufficient. Instead, we need to “copy” the edges of $E^{(i,i+1)}$ to
subproblems on “both sides” in an appropriate manner. In the following
theorem, we give a formal description of the EPTAS for the minimization
variant.

######  Theorem 0.B.1.

There exists an $(1+\epsilon)$-approximation for the minimization variant of
MWBS that runs in time $2^{O(1/\epsilon)}\cdot n^{O(1)}$. That is, the
minimization variant of MWBS admits an EPTAS.

###### Proof.

Let $t=\lceil 2/\epsilon\rceil$. Fix an arbitrary vertex $v\in
V(\overline{G})$. For any $i\geq 0$, let $L_{i}$ denote the set of vertices
that are at distance exactly $i$ from $v$ in $\overline{G}$. Note that any
$u\in L_{i}$ has neighbors in $L_{j}$ such that $|i-j|\leq 1$. For $i\geq 0$,
let $E^{(i,i+1)}\subseteq E(G)$ denote the set of directed edges that with one
endpoint in $L_{i}$ and other endpoint in $L_{i+1}$. For each $E^{(i,i+1)}$,
let $F^{(i,i+1)}$ denote the corresponding set of undirected edges.

######  Observation 3.

For some $i\in\left\\{0,1,\ldots,t-1\right\\}$, it holds that
$w(E^{(i,i+1)}\cap E^{*})\leq\frac{1}{t}\cdot OPT$.

###### Proof.

Follows from the fact that the sets $E^{(i,i+1)}$ and $E^{(j,j+1)}$ are
pairwise disjoint for distinct $i,j$. ∎

Figure 6: Construction of graphs $G(i,j-1)$ and $G(i,j)$ using layers. Observe
that the vertex $w\in L_{ji}$ is split into multiple copies in
$\widetilde{L_{ji}}$, and the edge $(u,v)$ where $u,v\in L_{(j+1)i+1}$ is not
retained in $G(i,j)$ after making copies of the respective vertices. However,
$w$ is kept as “original” in $L_{ji}$ in the graph $G(i,j)$. Finally, note
that the blue edges in the original graph belongs to $E^{(i,i+1)}$, and
corresponds to two copies – one in $G(i,j-1)$ and the other in $G(i,j)$. This
is why we incur the additive factor $2\cdot 1/t\cdot OPT$ when combining the
solutions.

For any integer $i\in\\{0,1,\ldots,t-1\\}$, we construct a graph $G_{i}$ by
taking a disjoint union of graphs $G(i,j)$ for $j\geq 0$, constructed as
follows.

For $j=0$, the graph $G(i,0)$ is defined on vertex set $L_{0}\cup
L_{1}\cup\ldots L_{i}$, along with a special vertex set $\tilde{L_{i+1}}$
defined later. All edges $e=(u,v)$, with $u,v\in L_{0}\cup L_{1}\cup\ldots\cup
L_{i}$ are present in $G(i,0)$. Next, consider edges with exactly one endpoint
in $L_{i}$ and the other in $L_{i+1}$, and we “split” the vertices in
$L_{i+1}$ to form $\tilde{L_{i+1}}$, such that each vertex in
$\widetilde{L_{i+1}}$ has exactly one edge incident to it. More formally,
consider an edge $e=(u,v)$ with $u\in L_{i}$ and $v\in L_{i+1}$. Then, we add
a new vertex $w_{(u,v)}$ to $\widetilde{L_{i+1}}$, and we add an edge
$(u,w_{(u,v)})$. Similarly, for an edge $(u^{\prime},v^{\prime})$ with
$u^{\prime}\in L_{i+1}$ and $v^{\prime}\in L_{i}$, we add a new vertex
$w_{(u^{\prime},v^{\prime})}$ to $\tilde{L_{i+1}}$, and add an edge
$(w_{(u^{\prime},v^{\prime})},v^{\prime})$. Note that each vertex in
$\tilde{L_{i+1}}$ has degree $1$, and is trivially bimodal.

For $j\geq 1$, the graph $G(i,j)$ is defined on the vertex set
$\widetilde{L_{ji}}\cup L_{ji+1}\cup L_{ji+2}\ldots\cup
L_{(j+1)i}\cup\widetilde{L_{(j+1)i+1}}$, where the sets $\tilde{L_{ji}}$ and
$\tilde{L_{(j+1)i+1}}$ are obtained by “splitting” the vertices in $L_{ji}$
and $L_{(j+1)i+1}$, respectively. More formally, the edge set of $G(i,j)$ is
constructed as follows. All edges with both endpoints in $L_{ji+1}\cup
L_{ji+2}\ldots\cup L_{(j+1)i}$ are retained in $G(i,j)$. For each edge $(u,v)$
with $u\in L_{ji}$ and $v\in L_{ji+1}$, we add a new vertex $w_{(u,v)}$ in
$\tilde{L_{ji}}$ and add an edge $(w_{(u,v)},v)$. The other case with
$(u^{\prime},v^{\prime})$ where $u^{\prime}\in L_{ji+1}$ and $v^{\prime}\in
L_{ji}$ is defined analogously. Finally, the set $\tilde{L_{(j+1)i+1}}$ is
defined analogously. Note that that newly created edge in $G(i,j)$ for $j\geq
0$ retains its original weight in $G_{i}$.

First, we observe that the treewidth of $G_{i}$ is bounded by $O(t)$, since it
is obtained by taking at most $t+2$ consecutive BFS layers ([CyganFKLMPPS15]).
Furthermore, each edge $(u,v)\in E^{(i,i+1)}$ corresponds to exactly two
copies in $G_{i}$ after the splitting process. Let $E^{\prime}$ denote the set
that includes both the copies of edges in $E^{*}\cap E^{(i,i+1)}$. Then,
observe that $\tilde{E^{*}_{i}}\coloneqq(E^{*}\setminus E^{(i,i+1)})\cup
E^{\prime}$ is a feasible solution for $G_{i}$, i.e.,
$G_{i}\setminus\tilde{E^{*}}$ is bimodal, and $w(\tilde{E^{*}_{i}})\leq
w(E^{*})+2\cdot w(E^{*}\cap E^{(i,i+1)})$. Furthermore, consider any feasible
solution $F_{i}$ to $G_{i}$, and map it back to the original graph $G$ to
obtain a solution $F$, as follows. If at least one copy of an edge is included
in $F_{i}$, then we add it to $F$. We observe that $G\setminus F$ is bimodal,
and $w(F)\leq w(F_{i})$. From this discussion and from Observation 3, it
follows that there exists some $i^{*}\in\\{0,1,\ldots,t-1\\}$, such that
$OPT(G_{i})\leq(1+2/t)\cdot OPT(G)$.

Now, our algorithm proceeds as follows. We create the graph $G_{i}$ for each
$i\in\\{0,1,\ldots,t-1\\}$, and use Theorem 3.1 to find an optimal solution in
time $2^{O(t)}\cdot n^{O(1)}$, and we map each optimal solution back to $G$ as
described above. We output the minimum-weight solution found in this manner
over all $i\in\\{0,1,\ldots,t-1\\}$. From the previous paragraph, it follows
the cost of this solution is at most $(1+2/t)\cdot OPT(G)\leq(1+\epsilon)\cdot
OPT(G)$. ∎