Multicut Problems in Almost-Planar Graphs:
the Dependency of Complexity on the Demand Pattern

Most NP-hard problems remain NP-hard when restricted to planar graphs, unless they become trivial or irrelevant on planar graphs. There are very few NP-hard problems that are polynomial-time solvable on planar graphs for some nontrivial and interesting reason. One such case is the Multiway Cut problem: given a graph $G$ and a set $T\subseteq V(G)$ of terminals, the task is to find a multiway cut $S$ of minimum weight, that is, a set $S\subseteq E(G)$ such that every component of $G\setminus S$ contains at most one terminal. Dahlhaus et al. [3] showed that Multiway Cut in general graphs is $\mathrm{𝖭𝖯}$-hard even for three terminals, while it is polynomial-time solvable on planar graphs for every fixed number $|T|$ of terminals. The exponent of $n$ in the algorithm of Dahlhaus et al. [3] is $O(|T|)$. Later, the dependence was improved to $O(\sqrt{|T|})$ [10, 2], which was shown to be optimal under the Exponential-Time Hypothesis (ETH) [11, 1]. The results were extended to bounded-genus graphs, again with an essentially best possible form of the exponent [1, 2].

Multicut is a generalization of Multiway Cut where not all terminals need to be separated from each other, but the input specifies which pairs of terminals need to be separated (and we do not care whether other pairs are separated or not).

Let us observe that Multiway Cut is the special case of Multicut when $H$ is a complete graph on $T$. Colin de Verdière [2] presented an algorithm for Multicut where the exponent of the running time is $O(\sqrt{|T|})$, similarly to Multiway Cut. However, it is no longer clear anymore that this algorithm is a tight, optimal result and cannot be improved in some cases: it could be that there are special cases, special type of demand graphs where significantly better algorithms are possible. For example, if $H$ is a biclique (complete bipartite graph), then Multicut can be solved in polynomial time by a reduction to a minimum weight $s-t$ cut problem. A very natural question to consider is the case when $H$ is a complete 3-partite graph. This special case is the Group 3-Terminal Cut problem: given a graph $G$ with three sets of terminals $T_1$, $T_2$, $T_3$, the task is to find a set $S$ of edges of minimum total weight such that $G\setminus S$ has no path between any vertex of $T_i$ and any vertex of $T_j$ for all distinct $i,j\in [3]$. While a general Multicut algorithm solves Group 3-Terminal Cut with the exponent of the running time being the square root of the number of terminals, the lower bounds for Multiway Cut do not imply that this dependence is optimal.

Focke et al. [5] systematically analyzed which types of demand graphs make the problem more tractable. The question was explored in the following setting. Let $\mathscr{H}$ be a class of graphs (i.e., a set of graphs closed under isomorphism). Then we denote by Multicut($\mathscr{H}$) the special case of Multicut that contains only instances $(G,H)$ where $H\in \mathscr{H}$. For example, if $\mathscr{H}$ is the class of cliques, then Multicut($\mathscr{H}$) is exactly Multiway Cut.

Ideally, for every class $\mathscr{H}$ of graphs, we would like to understand the best possible running time of Multicut($\mathscr{H}$) on planar graphs. In order to make the question more robust, Focke et al. [5] considered only classes $\mathscr{H}$ satisfying a mild closure property. We say that $H^{\prime }$ is a projection of $H$ if $H^{\prime }$ can be obtained from $H$ by deleting vertices and identifying pairs of independent vertices. Moreover, a class of graphs $\mathscr{H}$ is projection-closed if, whenever $H\in \mathscr{H}$ and $H^{\prime }$ is a projection of $H$, then $H^{\prime }\in \mathscr{H}$ also holds. The intuition is that an instance having demand graph $H^{\prime }$ can be easily simulated by an instance having demand graph $H$, thus it is reasonable to assume we only consider classes of demand graphs closed under this operation.

Let us consider some easy cases first. As we mentioned before, the Multicut problem can be solved in polynomial time by a reduction to $s-t$ minimum cut if the demand graph is a biclique. Furthermore, if $H$ has only two edges, then a similar reduction is known [8, 12]. Isolated vertices of $H$ clearly do not play any role in the problem. We say that $H$ is a trivial pattern if, after removing isolated vertices, it is either a biclique or has at most two edges. An extended biclique is a graph that consists of a complete bipartite graph together with a set of isolated vertices. Let $\mu$ be the minimum number of vertices that need to be deleted to make a graph $H$ an extended biclique. Then we say that $H$ has distance $\mu$ to extended bicliques. Moreover, we say that a graph class $\mathscr{H}$ has bounded distance to extended bicliques if there is a constant $\mu$ such that every $H\in \mathscr{H}$ has distance at most $\mu$ to extended bicliques.

For planar graphs, Focke et al. [5] give the following characterization:

That is, depending on whether $\mathscr{H}$ has bounded distance to extended bicliques, the number $t$ of terminals has to appear in the exponent. Focke et al. [5] precisely characterized how the complexity changes if we move from planar graphs to bounded-genus graphs. As we can see, the parameter genus can appear in the exponent in different ways, depending on $\mathscr{H}$.

Focke et al. [5] also considered a much more restricted extension of planar graphs than bounded-genus graphs: graphs that can be made planar by deleting a few edges. We use $\text{planar}+\pi e$ for the class of graphs that can be made planar by removing at most $\pi$ edges. Given an instance $(G,H)$, we use $\pi$ for the smallest integer such that $G$ is in $\text{planar}+\pi e$.

Observe that in Theorem 1.2, the algorithmic results are stated for the edge-weighted version, while the lower bounds are stated for the unweighted version. In fact, edge-weights do not make much difference in Theorem 1.2, as polynomial edge weights can be simulated by parallel edges without changing the genus of the graphs. However, this simulation can easily change the number $\pi$ of edges that needs to be deleted to make the graph planar. This means that if we consider the influence of the parameter $\pi$ on the running time, the edge-weighted and the unweighted problem may behave differently. Focke et al. [5] characterized the influence of this parameter in the edge-weighted case:

Observe that $\pi$ has a different form of influence on the exponent compared to genus: it is $O(\sqrt{\pi })$ instead of $O(g)$ in the case of bounded distance to extended bicliques, and $O(\sqrt{\pi +t})$ instead of $O(\sqrt{g^2+gt+t})$ in the unbounded distance case. Intuitively, having $\pi$ extra edges is a much more restricted extension of planar graphs than having genus $g$, and consequently, the parameter $\pi$ has a much weaker influence on the exponent than genus has.

For unweighted graphs, Focke et al. [5] showed that the problem is easier than the edge-weighted version and the parameter $\pi$ can be removed from the exponent.

However, this result leaves open the question what happens in unweighted Multicut($\mathscr{H}$) if $\mathscr{H}$ has bounded distance to extended bicliques. Based on Theorems 1.2 and 1.3, one would expect that it is possible to remove the number $t$ of terminals from the exponent as well.

Some basic notation on sets, graphs, and multicuts can be found in the full version. We now give some less well-known, problem-specific definitions.

An extended biclique decomposition of a graph $H$ is a partition $(B_1,B_2,I,X)$ of $V(H)$ such that all vertices of $I$ are isolated in $H-X$, $E(H)$ contains the edge $t_1{t}_2$ for all $t_1\in B_1$ and $t_2\in B_2$, and $H[B_i]$ is an edgeless graph for $i\in [2]$. We use ${\mathscr{H}}_{\mu }$ for the set of graphs $H$ that admit an extended biclique decomposition $(B_1,B_2,I,X)$ with $|X|\le \mu$.

We now review the concept of so-called multicut duals, which will play a crucial role throughout the article. Recall that an instance $(G,H)$ of Multicut is planar if $G$ is given in the form of a graph cellularly embedded in the plane. Given a graph $C$ that is embedded in the plane and in general position with $G$, we denote by $e_G(C)$ those edges of $G$ that are crossed by at least one edge of $C$. The weight $w(C)$ of $C$ is defined to be $w(e_G(C))$ where $w$ is the weight function associated with $G$. A multicut dual for $(G,H)$ is a graph $C$ embedded in the plane that is in general position with $G$ and has the property that, for every $t_1,t_2\in V(H)$ with $t_1{t}_2\in E(H)$, the terminals $t_1$ and $t_2$ are contained in different faces of $C$.

The following result is an immediate consequence of Lemmas 2.3 and 2.4 in [6].

In order to make use of the topology of certain multicut duals, we need two results related to treewidth. The first one of the following two results provides a sufficient criterion for the treewidth of certain graphs being bounded and the second one allows to exploit bounded treewidth algorithmically.

The following result can be obtained from Theorem 3.2 in [4] and the fact that the treewidth of any graph can only be larger than its branchwidth by a constant factor.

An extended planar instance $(G,H,F^{\ast })$ of Multicut is a planar instance $(G,H)$ of Multicut together with a set $F^{\ast }$ of faces of $G$ which is given with the input. Given a set $F^{\ast }$ of faces of $G$ and a multicut dual $C$ for $(G,H)$, let $C-F^{\ast }$ be the graph obtained from $C$ by removing every vertex that is in a face of $F^{\ast }$ and removing every edge that intersects a face of $F^{\ast }$. The following result is the restriction of Theorem 1.11 in [6] to the planar setting.

In this section, we give an overview of the proof of the following result, whose complete proof can be found in the full version. See 1.5 Throughout this section, we say that an instance $(G,H)$ of Multicut is $\text{<em class="ltx\_emph ltx\_font\_sansserif ltx\_font\_upright">planar</em>}+\pi e$ if a set $E_{\pi }\subseteq E(G)$ is given with the instance such that $|E_{\pi }|=\pi$ and $G\setminus E_{\pi }$ is planar. We further use $T$ for $V(H)$, $W$ for $V(E_{\pi })$, and $G_0$ for $G\setminus E_{\pi }$. Also, for some $S\subseteq E(G)$, we use $S_0$ for $S\setminus E_{\pi }$. We say that $(G,H)$ is connected if $G$ is connected.

The overall algorithmic strategy for Theorem 1.5 is to run an algorithm on the given instance that either produces a minimum multicut for the instance or computes a collection of instances for which the parameters in consideration are smaller and such that from minimum multicuts of all those instances, a minimum multicut for the original instance can be computed. We need the following definitions.

Given instances $(G,H)$ and $(G^{\prime },H^{\prime })$ of Multicut, $(G^{\prime },H^{\prime })$ is a subinstance of $(G,H)$ if $G^{\prime }$ is a labelled subgraph of $G$ and $H^{\prime }$ is a labelled induced sungraph of $H$. Next, an extended subinstance of $(G,H)$ consists of a set $S^{\prime }\subseteq E(G)$ and a subinstance $(G^{\prime },H^{\prime })$ of $(G,H)$ with $E(G^{\prime })\cap S^{\prime }=\mathrm{\varnothing }$. When we say that an extended subinstance $(S^{\prime },(G^{\prime },H^{\prime }))$ has certain properties which can only be associated to an instance of Multicut, we refer to $(G^{\prime },H^{\prime })$. Next, we say that an extended subinstance $(S^{\prime },(G^{\prime },H^{\prime }))$ of $(G,H)$ is optimumbound for $(G,H)$ if $S^{\prime }\cup S^{\prime \prime }$ is a minimum multicut for $(G,H)$ for every minimum multicut $S^{\prime \prime }$ for $(G^{\prime },H^{\prime })$.

The main technical difficulty is to prove the following result, which shows that the above described reduction to smaller instances exists for connected instances. With this result at hand, Theorem 1.5 follows readily. In particular, if disconnected instances are created, they can easily be reduced to instances corresponding to the components of the graph. Further observe that $\mu$ cannot increase when moving to a subinstance as the new demand graph is an induced subgraph of the previous one.

We now give an overview of the proof of Lemma 3.1. Let $(G,H)$ be a $\text{planar}+\pi e$ instance of Multicut. The idea is to have a branching algorithm that gradually guesses more and more crucial information about a minimum multicut for $(G^{\prime },H^{\prime })$ while the number of directions it branches into remains bounded. The current status of this procedure is displayed by a subpartition of the vertices of $V(G)$ with some extra properties. More formally, a state is a subpartition $𝒫$ of $V(G)$ with $W\cup T\subseteq \bigcup 𝒫$ and $Y\cap (W\cup T)\ne \mathrm{\varnothing }$ for all $Y\in 𝒫$. Given a certain state, the objective is to understand whether there exists a minimum multicut $S$ for $(G,H)$ such that the structure of the components of $G_0\setminus S$ reflects the structure of $𝒫$. In order to make this more formal, we need the following definitions: Given a set $V$ and two subpartitions ${𝒫}^1$ and ${𝒫}^2$ of $V$, we say that ${𝒫}^2$ extends ${𝒫}^1$ if $|{𝒫}^1|=|{𝒫}^2|$ and for every $Y\in {𝒫}^1$, there exists some $\overline{Y}\in {𝒫}^2$ with $Y\subseteq \overline{Y}$ such that for any distinct $Y_1,Y_2\in {𝒫}^1$, we have $\overline{Y_1}\ne \overline{Y_2}$. Given a set $S\subseteq E(G)$, we use $S_0$ for $S\cap E(G_0)$ and $𝒦(G_0\setminus S_0)$ for the unique partition of $V(G)$ in which two vertices are in the same partition class if and only if they are in the same component of $G_0\setminus S_0$. For a state $𝒫$, we say that a multicut $S$ for $(G,H)$ respects $𝒫$ if $𝒦(G_0\setminus S_0)$ extends $𝒫$ and we say that a state is valid if there exists a minimum multicut for $(G,H)$ respecting it. Further, $𝒫$ is maximum valid if $|𝒫|$ is maximum among all valid states.

The idea of our algorithm now consists of considering a valid state, choosing a vertex that is not contained in any class of the state and making the classes larger by adding this vertex to one of them. As we do not know which class this vertex should be added to, we try all classes of the state and branch in these directions. The difficulty is now to carefully choose the vertex in consideration and make some additional modifications on the states so that this procedure terminates sufficiently fast.

In order to be able to explain how this works, we first need some more definitions. Given disjoint sets $Y_1,Y_2\subseteq V(G)$, we use ${\lambda }_{G_0}(Y_1,Y_2)$ to denote the size of the smallest set of edges in $E(G_0)$ whose deletion from $G_0$ results in a graph in which there exists no component containing both a vertex of $Y_1$ and a vertex of $Y_2$. Next, for a state $𝒫$ and some $Y\in 𝒫$, we define ${\alpha }_{G,𝒫}(Y)={\lambda }_{G_0}(Y,\bigcup 𝒫\setminus Y)-{\lambda }_{G_0}(Y\cap (W\cup T),W\cup T\setminus Y)$. Intuitively speaking, this measure describes how much more costly it is to separate the class from the other classes of the state in comparison to only separating the corresponding elements of $W\cup T$. Given a state $𝒫$, we now classify its classes according to their value of $\alpha$ and the value of $\alpha$ of their neighboring classes. More formally, given a state $𝒫$ and some $Y\in 𝒫$, we say that $Y$ is fat in $𝒫$ if ${\alpha }_{G_0,𝒫}(Y)\ge \pi (t+1)+1$. For some $Y\in 𝒫$ that is not fat, we say that $Y$ is fat-neighboring in $𝒫$ if there exists some fat $Y^{\prime }\in 𝒫$, some $u\in Y$, and some $v\in Y^{\prime }$ such that $uv\in E(G_0).$ Finally, for some $Y\in 𝒫$ which is neither fat nor fat-neighboring in $𝒫$, we say that $Y$ is thin in $𝒫$. We refer by ${𝒫}_{\text{fat}},{𝒫}_{\text{f-n}}$, and ${𝒫}_{\text{thin}}$ to the fat, fat-neighboring, and thin classes of $𝒫$, respectively.

In order to make use of this distinction, we crucially need a structural property of minimum multicuts for $(G,H)$. Namely, the following result shows that, for any minimum multicut $S$ for $(G,H)$ and any vertex set of a component of $G_0\setminus S_0$, one of two things holds: either the value of $\alpha$ is not too large or a terminal of $X$ is close to this vertex set in a certain sense, where $(B_1,B_2,I,X)$ is an extended biclique decomposition of $H$. In order to measure this proximity of certain vertex sets with respect to a multicut, we introduce the following notion: Let $S\subseteq E(G)$, and $Y_1,Y_2\subseteq V(G)$. Then we denote by ${\text{dist}}_{G_0,S_0}(Y_1,Y_2)$ the smallest integer $q$ such that $G_0$ contains a $Y_1{Y}_2$-path $P$ with $|E(P)\cap S_0|=q$. We are now ready to state the following structural result for minimum multicuts.

We now explain the strategy of our algorithm. Given a state with an extra property that will be explained later, we choose a vertex that is not contained in any class of the state and has a neighbor in a thin class of the state in $G_0$. We then guess a partition class which this vertex will be added to and modify the state accordingly. In order to show the functionality of this algorithm, there are two points that need further explanation. First, we need to explain how to conclude when the described modification is no longer possible and second, we need to explain why this procedure terminates sufficiently fast.

We first explain the scenario that we can no longer execute the described modification, so there does not exist any vertex in the graph that is not contained in any class of the state $𝒫$ in consideration and that has a neighbor in a thin class of $𝒫$ in $G_0$. We call such a state complete, all other states are called incomplete. For complete states, we need to consider two different cases, depending on whether $𝒫$ contains a thin class.

The case that there exists a thin class $Y$ can be handled with elementary means. Observe that for this thin class, all its neighbors in $G_0$ are contained in a different class of $𝒫$. Hence, if $𝒫$ is valid, then all edges in ${\delta }_{G_0}(Y)$ are contained in a minimum multicut for $(G,H)$. We can hence delete these edges and solve the remaining instance, which turns out to be significatly smaller in a certain sense. This is subsumed in the following result.

We now turn to the case that $𝒫$ does not contain a thin set. In order to handle this case, geometrical arguments on multicut duals will be needed. Namely, we show that if $𝒫$ is valid and does not contain a thin set, then the problem of finding a minimum multicut for $(G,H)$ can be reduced to solving a planar instance of multicut, which can be solved sufficiently fast due to Theorem 2.3 and an argument on the treewidth of the multicut duals for this instance. Formally, we prove the following result, where $\tau (𝒫)$ denotes the sum of the number of components of $G_0[Y]$ over all $Y\in 𝒫$.

It remains to show that we can design our procedure so that we reach a complete state sufficiently fast. In order to keep track of the progress of our algorithm, we need a measure of how far advanced a given state is. To this end, given a state $𝒫$, we first define an integer $\kappa (𝒫,Y)$ for every $Y\in 𝒫$ by

Now, we define $\kappa (𝒫)={\sum }_{Y\in 𝒫}\kappa (𝒫,Y)$.

Our objective is to make the value of $\kappa$ increase in each iteration of the algorithm. In order to make this possible, we need that the addition of a vertex to a given set in the state makes the value of $\alpha$ of this set increase. In order for that to hold, we need the classes in the state to be as large as possible in a certain sense. More precisely, given a graph $G$ and two disjoint sets $Y_1,Y_2\subseteq V(G)$, we say that a set $Y_3$ is relevant for $(Y_1,Y_2)$ in $G$ if $Y_1\subseteq Y_3,Y_2\cap Y_3=\mathrm{\varnothing },d_G(Y_3)={\lambda }_G(Y_1,Y_2)$ and $Y_3$ is maximum among all sets with these properties. Further, we say that a state $𝒫$ is relevant if for all $Y\in 𝒫$, we have that $Y$ is a relevant set for $(Y,\bigcup 𝒫\setminus Y)$. Luckily, the following result whose proof needs some careful reconfiguration arguments, allows us to turn arbitrary states in consideration into relevant ones without dropping any important properties.

With this result at hand, we can handle incomplete states. As pointed out before, given an incomplete relevant state $𝒫$, we choose a vertex $u_0\in V(G)\setminus \bigcup 𝒫$ that has a neighbor in a thin class $Y$ of $𝒫$. We now consider all states that are obtained by adding $u_0$ to one of these partition classes. If $u_0$ is added to a thin or a fat-neighboring partition class, then, as $𝒫$ is relevant, the value of $\alpha$ increases for this class and hence $\kappa$ increases. If $u_0$ is added to a fat class, then $Y$ becomes fat-neighboring and hence $\kappa$ also increases. This shows that a complete state can be reached sufficiently fast. In order to apply Lemma 3.4, we also need to make sure that $\tau (𝒫)$ does not increase too fast. However, this follows readily by construction. Our handling of relevant incomplete states is subsumed in the following result.

The overall strategy for handling Lemma 3.1 is now to apply Lemma 3.5 and Lemma 3.6 until we are left with a collection of complete states. These can then be handled by Lemma 3.3 and Lemma 3.4.

In this section, a drawing of a graph $G$ consists of a mapping of the vertices of $G$ to points in the plane and a mapping of the edges of $G$ to curves in the plane connecting their endpoints such that all vertices and edges of $G$ are in general position except the required adjacencies and such that in any point not corresponding to a vertex, at most two edges intersect. An edge crossing refers to a point that does not correspond to a vertex and in which two edges intersect. Given an instance $(G,H)$ of Multicut  we use $cr$ for the crossing number of a graph $G$, which is defined to be the smallest integer $k$ such that there exists a drawing of $G$ with exactly $k$ edge crossings. The following is the main result of this section. See 1.7 In order to make our algorithm work, rather than just the crossing number of a graph, we also need to have an optimal drawing available. This can be achieved through the following result due to Grohe [7].

Formally, an instance $(G,H)$ of Multicut is called crossing-planar if $G$ is given as a drawing of a graph. Given a crossing-planar instance, we denote by $E_{cr}$ the set of edges in $E(G)$ crossing at least one other edge of $E(G)$ and we set $\overline{cr}=|E_{cr}|$. Observe that $\overline{cr}$ can be arbitrarily large in comparison to $cr$ as $\overline{cr}$ refers to the given drawing and $cr$ to an optimal drawing of the abstract graph $G$. However, when considering an optimal drawing of $G$, we have $\overline{cr}\le 2cr$ as every crossing involves 2 edges.

For our algorithm, it will be convenient to assume that the instances in consideration satisfy a technical extra condition. Namely, a crossing-planar instance $(G,H)$ of Multicut is called normalized if every $e\in E_{cr}$ is of infinite weight. Observe that for any normalized crossing-planar instance $(G,H)$ of Multicut, any finite multicut $S$ of $(G,H)$ and any $e\in E_{cr}$, we have that $V(e)$ is contained in one component of $G\setminus S$. Our main technical contribution is proving the restriction of Theorem 1.7 to normalized instances.

The simple proof that Theorem 4.2 implies Theorem 1.7 is postponed to the full version. It remains to prove Theorem 4.2.

Given a normalized crossing-planar instance $(G,H)$ of Multicut, we denote by $\mathscr{H}$ the set of graphs $H^{\prime }$ on $V(H)\cup V(E_{cr})$ and we use $G^{\prime }$ for $G\setminus E_{cr}$. Further, we let $F^{\ast }$ denote the faces of $G^{\prime }$ which contain a pair of crossing edges in $G$. The main technical difficulty for the proof of Theorem 4.2 is contained in the following result.

Due to space restrictions, the full proof of Lemma 4.3 is postponed to the full version. We now give an overview of the proof of Lemma 4.3.

Let $(B_1,B_2,I,X)$ be an extended biclique decomposition of $H$ with $|X|=\mu$. Further, let $S^{\ast }$ be a minimum weight multicut for $(G,H)$ such that $S^{\ast }$ minimizes the number of elements of $V(H)\cup V(E_{cr})$ that are in a component of $G\setminus S^{\ast }$ that also contains a terminal of $X$. In the following, we use $\overline{X}$ for the set of elements of $V(H)\cup V(E_{cr})$ that are in a component of $G\setminus S^{\ast }$ that also contains a terminal of $X$, we use $\overline{B_1}$ for the set of elements of $(V(H)\cup V(E_{cr}))\setminus \overline{X}$ that are in a component of $G\setminus S^{\ast }$ that also contains a terminal of $B_1$, and we use $\overline{B_2}$ for $(V(H)\cup V(E_{cr}))\setminus (\overline{X}\cup \overline{B_1})$. Observe that $(\overline{B_1},\overline{B_2},\overline{X})$ is a partition of $V(H)\cup V(E_{cr})$. We now define $H^{\prime }$ to be the complete multipartite graph on $V(H)\cup V(E_{cr})$ such that $\overline{B_1}$ and $\overline{B_2}$ are partition classes and such that for every component of $G\setminus S^{\ast }$ that contains at least one terminal of $X$, all the elements of $\overline{X}$ contained in this component form a partition class.

This finishes the description of $H^{\prime }$. Observe that $H^{\prime }\in \mathscr{H}$. Further observe that $H$ is a subgraph of $H^{\prime }$.The following two claims directly imply that every minimum weight multicut for $(G^{\prime },H^{\prime })$ is also a minimum weight multicut for $(G,H^{\prime })$. Claim 4.4 will be reused for the proof of the treewidth bound. These claims mainly follow from the construction of $(G^{\prime },H^{\prime })$.

We are now ready to conclude that any minimum weight multicut $S$ for $(G^{\prime },H^{\prime })$ is a minimum weight multicut for $(G,H)$. First observe that $S$ is a multicut for $(G,H)$ by Claim 4.4 and as $H$ is a subgraph of $H^{\prime }$. Further, by Claim 4.5 and the minimality of $S$, we obtain $w(S)\le w(S^{\ast })$ where $w$ is the weight function associated to $G$. By the minimality of $S^{\ast }$, the statement follows.

In the following, let $C$ be a subcubic, inclusion-wise minimal, minimum weight multicut dual for $(G^{\prime },H^{\prime })$. We will give the desired treewidth bound on $C$. Let $S^{\prime }=E_G(C)$ and observe that $S^{\prime }$ is a minimum weight multicut for $(G^{\prime },H^{\prime })$ by Lemma 2.1. It hence follows from the first part of the lemma that $S^{\prime }$ is also a minimum weight multicut for $(G,H)$. Further, we use $C^{\prime }$ for $C-F^{\ast }$.

Our strategy for proving the second part of the lemma is to show that the faces of $C^{\prime }$ containing a terminal of $\overline{X}$ form a small set of faces that is close to every face of $C^{\prime }$ in a certain sense. We first give the following result showing that the number of such faces is small indeed. Its proof uses the fact that $S^{\ast }$ is chosen so that the size of $\overline{X}$ is minimized and the fact that $S^{\prime }$ is a minimum weight multicut for $(G,H)$.

The next result uses the structure of $H$.

We are now ready to conclude the desired treewidth bound on $C^{\prime }$. Let $C^{\prime \prime }$ be a component of $C^{\prime }$. For every face $f$ of $C^{\prime \prime }$, we now introduce a vertex $z_f$ that shares an edge with every vertex that is incident to $f$. Let $C_0^{\prime \prime }$ be the resulting graph. It turns out that $C_0^{\prime \prime }$ is a planar graph and the vertices corresponding to faces containing terminals of $\overline{X}$ form a 3-dominating set in $C_0^{\prime \prime }$. By Proposition 2.2 and $|A|\le |X|\le \mu$, we obtain that $\text{tw}(C_0^{\prime \prime })=O(\sqrt{\mu })$ and hence $\text{tw}(C^{\prime })=O(\sqrt{\mu })$. This allows to conclude Lemma 4.3.

With Lemma 4.3 at hand, it is easy to conclude Theorem 4.2. The proof can be found in the full version.