11institutetext: Hasso Plattner Institute, University of Potsdam, Potsdam
14482, Germany
11email: {First name.Last<EMAIL_ADDRESS>
# Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal
Graphs

Katrin Casel 11 0000-0001-6146-8684 Tobias Friedrich 11 0000-0003-0076-6308
Davis Issac 11 0000-0001-5559-7471 Aikaterini Niklanovits 11
0000-0002-4911-4493 Ziena Zeif 11 0000-0003-0378-1458

###### Abstract

In the 1970s, Győri and Lovász showed that for a $k$-connected $n$-vertex
graph, a given set of terminal vertices $t_{1},\dots,t_{k}$ and natural
numbers $n_{1},\dots,n_{k}$ satisfying $\sum_{i=1}^{k}n_{i}=n$, a connected
vertex partition $S_{1},\dots,S_{k}$ satisfying $t_{i}\in S_{i}$ and
$|S_{i}|=n_{i}$ exists. However, polynomial algorithms to actually compute
such partitions are known so far only for $k\leq 4$. This motivates us to take
a new approach and constrain this problem to particular graph classes instead
of restricting the values of $k$. More precisely, we consider $k$-connected
chordal graphs and a broader class of graphs related to them. For the first
class, we give an algorithm with $\mathcal{O}(n^{2})$ running time that solves
the problem exactly, and for the second, an algorithm with
$\mathcal{O}(n^{4})$ running time that deviates on at most one vertex from the
required vertex partition sizes.

###### Keywords:

Győri-Lovász theorem chordal graphs HHD-free graphs.

##  1 Introduction

Partitioning a graph into connected subgraphs is a fundamental task in graph
algorithms. Such _connected_ partitions occur as desirable structures in many
application areas such as image processing [9], road network decomposition
[10], and robotics [18].

From a theoretical point of view, the existence of a partition into connected
components with certain properties also gives insights into the graph
structure. In theory as well as in many applications, one is interested in a
connected partition that has a given number of subgraphs of chosen respective
sizes. With the simple example of a star-graph, it is observed that not every
graph admits a connected partition for any such choice of subgraph sizes. More
generally speaking, if there exists a small set of $t$ vertices whose removal
disconnects a graph (_separator_), then any connected partition into $k>t$
subgraphs has limited choice of subgraph sizes. Graphs that do not contain
such a separator of size less than $k$ are called $k$-_connected_.

On the other hand, Győri and Lovász independently showed that $k$-connectivity
is not just necessary but also sufficient to enable a connected partitioning
into $k$ subgraphs of required sizes, formally stated by the following result.

######  Győri-Lovász Theorem ([5],[8])

Let $k\geq 2$ be an integer, $G=(V,E)$ a $k$-connected graph,
$t_{1},\ldots,t_{k}\in V$ distinct vertices and
$n_{1},\ldots,n_{k}\in\mathbb{N}$ such that $\sum_{i=1}^{k}n_{i}=|V|$. Then
$G$ has disjoint connected subgraphs $G_{1},\ldots G_{k}$ such that
$|V(G_{i})|=n_{i}$ and $t_{i}\in V(G_{i})$ for all $i\in[k]$.

The caveat of this famous result is that the constructive proof of it yields
an exponential time algorithm. Despite this result being known since 1976, to
this day we only know polynomial constructions for restricted values of $k$.
Specifically, in 1990 Suzuki et al. [16] provided such an algorithm for $k=2$
and also for $k=3$ [15]. Moreover in 1994 Wada et al. [17] also provided an
extended result for $k=3$. For the case of $k=4$ Nakano et al. [11] gave a
linear time algorithm for the case where $k=4$, $G$ is planar and the given
terminals are located on the same face of a plane embedding of $G$, while in
2016 Hoyer and Thomas [6] provided a polynomial time algorithm for the case of
$k=4$. And so far, this is where the list ends, thus for $k\geq 5$ it remains
open whether there even exists a polynomial time construction.

Towards a construction for general $k$, we consider restricting the class of
$k$-connected graphs instead of the values of $k$. More precisely, we consider
(generalizations of) _chordal_ $k$-connected graphs. A graph is called
_chordal_ , if it does not contain an induced cycle of length more than three.
The restriction to chordal graphs is known to often yield tractability for
otherwise NP-hard problems, for example chromatic number, clique number,
independence number, clique covering number, stable set and treewidth
decomposition [14]. Apart from the interest chordal graphs have from a graph
theoretic point of view, their structural properties have also been proven
useful in biology when it comes to studying multidomain proteins and network
motifs (see e.g. [13, 12]).

#### Our contribution

To the best of our knowledge, this paper is the first to pursue the route of
restricting the Győri-Lovász Theorem to special graph classes in order to
develop a polynomial construction for general values of $k$ on a non-trivial
subclass of $k$-connected graphs. We believe that in general considering the
structure of the minimal separators of a graph is promising when it comes to
developing efficient algorithms for the Győri-Lovász Theorem.

We give a constructive version of the Győri-Lovász Theorem for _chordal_
$k$-connected graphs with a running time in $\mathcal{O}(|V|^{2})$. Observe
here that this construction works for all values of $k$. Then we show how this
result can be generalized in two directions.

First, we generalize our result to the vertex weighted version of the Győri-
Lovász Theorem (as proven independently by Chandran et al. [2], Chen et al.
[3] and Hoyer [6]), specifically deriving the following theorem.

###### Theorem 1.1

Let $k\geq 2$ be an integer, $G=(V,E,w)$ a vertex-weighted $k$-connected
chordal graph with $w\colon V\to\mathbb{N}$, $t_{1},\ldots,t_{k}\in V$
distinct vertices, and $w_{1},\ldots,w_{k}\in\mathbb{N}$ with $w_{i}\geq
w(t_{i})$ and $\sum_{i=1}^{k}w_{i}=w(V)$ for all $i\in[k]$. A partition
$S_{1},\dots,S_{k}$ of $V$, such that $G[S_{i}]$ is connected, $t_{i}\in
S_{i}$ and $w_{i}-w_{\mathit{max}}<w(S_{i})<w_{i}+w_{\mathit{max}}$, for all
$i\in[k]$, can be computed in time $\mathcal{O}(|V|^{2})$.

We further use this weighted version to derive an approximate version of the
Győri-Lovász Theorem for a larger graph class. Specifically we define
$\text{I}_{j}^{i}$ to contain all graphs that occur from two distinct
chordless $C_{j}$’s that have at least $i$ vertices in common. We focus on
$\text{I}_{4}^{2}$-free combined with HH-free graphs. More specifically, we
consider the subclass of $k$-connected graphs that contain no hole or house as
subgraph (see preliminaries for the definitions of structures such as hole,
house etc.) and that does not contain two distinct induced $C_{4}$ that share
more than one vertex. We call this class of graphs $\text{HHI}_{4}^{2}$-free.
Note that $\text{HHI}_{4}^{2}$-free, apart from being a strict superclass of
chordal graphs, is also a subclass of HHD-free graphs (that is house, hole,
domino-free graphs), a graph class studied and being used in a similar manner
as chordal graphs as it is also a class where the minimum fill-in set is
proven to be polynomially time solvable [1] (see also [7] for NP-hard problems
solved in polynomial time on HHD-free graphs). Taking advantage of the fact
that given an $\text{HHI}_{4}^{2}$-free graph, the subgraph formed by its
induced $C_{4}$ has a treelike structure, we are able to derive the following
result.

###### Theorem 1.2

Let $k\geq 2$ be an integer, $G=(V,E,w)$ a vertex-weighted $k$-connected
$\text{HHI}_{4}^{2}$-free graph with $w\colon V\to\mathbb{N}$,
$t_{1},\ldots,t_{k}\in V$ distinct vertices, and
$w_{1},\ldots,w_{k}\in\mathbb{N}$ with $w_{i}\geq w(t_{i})$ and
$\sum_{i=1}^{k}w_{i}=w(V)$ for all $i\in[k]$. A partition $S_{1},\dots,S_{k}$
of $V$, such that $G[S_{i}]$ is connected, $t_{i}\in S_{i}$ and
$w_{i}-2w_{\mathit{max}}<w(S_{i})<w_{i}+2w_{\mathit{max}}$, for all $i\in[k]$,
can be computed in time $\mathcal{O}(|V|^{4})$.

Notice that the above theorem implies a polynomial time algorithm with an
additive error of $1$ for the unweighted case.

##  2 Preliminaries

All graphs mentioned in this paper are undirected, finite and simple. Given a
graph $G$ and a vertex $v\in V(G)$ we denote its _open neighborhood_ by
$N_{G}(v):=\\{u\in V(G)\mid uv\in E(G)\\}$ and by $N_{G}[v]$ its _closed
neighborhood_ , which is $N(v)\cup\\{v\\}$. Similarly we denote by
$N_{G}(S):=\bigcup_{v\in S}N_{G}(v)\setminus S$ the open neighborhood of a
vertex set $S\subseteq V(G)$ and by $N_{G}[S]:=N_{G}(S)\cup S$ its closed
neighborhood. We omit the subscript $G$ when the graph we refer to is clear
from the context. A vertex $v\in V(G)$ is _universal to a vertex set $S\subset
V(G)$_ if $S\subseteq N(v)$. Let $G$ be a graph and $S\subseteq V(G)$. The
_induced subgraph_ from $S$, denoted by $G[S]$, is the graph with vertex set
$S$ and all edges of $E(G)$ with both endpoints in $S$.

A graph $G$ is _chordal_ if any cycle of $G$ of size at least $4$ has a chord
(i.e., an edge linking two non-consecutive vertices of the cycle). A vertex
$v\in V(G)$ is called _simplicial_ if $N[v]$ induces a clique. Based on the
existence of simplicial vertices in chordal graphs, the following notion of
vertex ordering was given. Given a graph $G$, an ordering of its vertices
$(v_{1},\ldots,v_{n})$ is called _perfect elimination ordering_ (p.e.o.) if
$v_{i}$ is simplicial in $G[\\{v_{i},v_{i+1},\ldots,v_{n}\\}]$ for all
$i\in[n]$. Given such an ordering $\sigma:V(G)\rightarrow\\{1,\ldots,n\\}$ and
a vertex $v\in V(G)$ we call $\sigma(v)$ the _p.e.o. value of $v$_. Rose et
al. [14] proved that a p.e.o. of any chordal graph can be computed in linear
time.

Let $e=\\{u,v\\}$ be an edge of $G$. We denote by $G/e$ the graph
$G^{\prime}$, that occurs from $G$ by the contraction of $e$, that is, by
removing $u$ and $v$ from $G$ and replacing it by a new vertex $z$ whose
neighborhood is $\left(N(u)\cup N(v)\right)\setminus\\{u,v\\}$.

A graph $G$ is _connected_ if there exists a path between any pair of distinct
vertices. Moreover, a graph is _$k$ -connected_ for some $k\in\mathbb{N}$ if
after the removal of any set of at most $k-1$ distinct vertices $G$ remains
connected. Given a graph $G$ and a vertex set $S\subseteq V(G)$, we say that
$S$ is a _separator_ of $G$ if its removal disconnects $G$. We call $S$ a
_minimal separator_ of $G$ if the removal of any subset $S^{\prime}\subseteq
V(G)$ with $|S^{\prime}|<|S|$ results in a connected graph.

We now define some useful subgraphs, see also Figure 1 for illustrations. An
induced chordless cycle of length at least $5$ is called a _hole_. The graph
that occurs from an induced chordless $C_{4}$ where exactly two of its
adjacent vertices have a common neighbor is called a _house_. When referring
to just the induced $C_{3}$ that is part of a house we call it _roof_ while
the induced $C_{4}$ is called _body_. Two induced $C_{4}$ sharing exactly one
edge form a _domino_. A graph that contains no hole, house or domino as an
induced subgraph is called HHD-free. We call a graph that consists of two
$C_{4}$ sharing a vertex, and an edge that connects the two neighbors of the
common vertex in a way that no other $C_{4}$ exists a _double house_.

Lastly, let $G=(V,E)$ be a $k$-connected graph, let $t_{1},\ldots,t_{k}\in V$
be $k$ distinct vertices, and let $n_{1},\ldots,n_{k}$ be natural numbers
satisfying $\sum_{i=1}^{k}n_{i}=|V|$. We call $S_{1},\ldots S_{k}\subseteq
V(G)$ a _GL-Partition of $G$_ if $S_{1},\ldots S_{k}$ forms a partition of
$V(G)$, such that for all $i\in[k]$ we have that $G[S_{i}]$ is connected,
$t_{i}\in S_{i}$ and $|S_{i}|=n_{i}$. When there exists an $l\in\mathbb{N}$,
such that for such a partition only $n_{i}-l\leq|S_{i}|\leq n_{i}+l$ holds
instead of $|S_{i}|=n_{i}$, we say that $S_{1},\ldots,S_{k}$ is a _GL-
Partition of $G$ with deviation $l$_.

Figure 1: Specific subgraphs used throughout the paper, from left to right:
house, double house, domino and hole example

##  3 GL-Partition for Chordal Graphs

We present a simple implementable algorithm with quadratic running time that
computes GL-Partitions in chordal graphs. We then show that a slight
modification of our algorithm is sufficient to compute a GL-Partition on a
vertex weighted graph, thus proving Theorem 1.1.

Due to space restrictions the proof of Lemma 1 has been moved to Appedix 0.B,
and the proof of correctness of Algorithm 2 to Appendix 0.A.

###  3.1 GL-Partition for Unweighted Chordal Graphs

For simplicity, we first prove the restricted version of Theorem 1.1 to
unweighted graphs. We use a p.e.o. to compute a vertex partition, as described
formally in Algorithm 1. This algorithm receives as input a $k$-connected
chordal graph $G=(V,E)$, terminal vertices $t_{1},\ldots,t_{k}\in V$, and
natural numbers $n_{1},\ldots,n_{k}$ satisfying $\sum_{i=1}^{k}n_{i}=n$, and
outputs connected vertex sets $S_{1},\ldots,S_{k}\subseteq V$ such that
$|S_{i}|=n_{i}$ and $t_{i}\in S_{i}$. In the beginning of the algorithm we
initialize each set $S_{i}$ to contain only the corresponding terminal vertex
$t_{i}$, and add vertices iteratively to the non-full sets ($S_{i}$’s that
have not reached their demanded size). We say a vertex $v$ is assigned if it
is already part of some $S_{i}$ and unassigned otherwise. At each iteration,
the unassigned neighborhood of the union of the previously non-full sets is
considered, and the vertex with the minimum p.e.o. value is selected to be
added to a non-full set. In case there is more than one non-full set in the
neighborhood of this vertex, it is added to the one with lowest priority,
where the priority of each set is defined to be the largest p.e.o. value of
its vertices so far. The algorithm terminates once all vertices are assigned,
in $\mathcal{O}({|V|}^{2})$ time.

Input: $k$-connected chordal graph $G=(V,E)$, terminal vertices
$t_{1},\ldots,t_{k}\in V$, and natural numbers $n_{1},\ldots,n_{k}$ satisfying
$\sum_{i=1}^{k}n_{i}=n$

Output: Connected vertex sets $S_{1},\ldots,S_{k}\subseteq V$ such that
$|S_{i}|=n_{i}$ and $t_{i}\in S_{i}$

1

2$\sigma$ $\leftarrow$ Compute p.e.o. of $G$ as function $\sigma\colon
V\to|V|$

3

4$S_{i}\leftarrow\\{t_{i}$}, for all $i\in[k]$

5while  _$\bigcup_{i\in[k]}S_{i}\neq V(G)$_ do

6

7 $I\leftarrow\\{i\in[k]\mid|S_{i}|<n_{i}\\}$

8 $V^{\prime}\leftarrow N(\bigcup_{i\in
I}S_{i})\setminus\bigcup_{i\in[k]\setminus I}S_{i}$

9 $v^{\prime}\leftarrow\operatorname*{arg\,min}_{v\in V^{\prime}}\sigma(v)$

10 $J\leftarrow\left\\{i\in I\mid v\in N(S_{i})\right\\}$

11 $j^{\prime}\leftarrow$ $\operatorname*{arg\,min}_{j\in
J}\max(\sigma(S_{j}))$

12 $S_{j^{\prime}}\leftarrow S_{j^{\prime}}\cup\\{v^{\prime}\\}$

13 end while

14

return $S_{1},\dots,S_{k}$

Algorithm 1 ChordalGL

For the correctness of Algorithm 1 it is enough to show that the unassigned
neighborhood $V^{\prime}$ of all non-full sets is not empty in each iteration
of the while-loop, since this implies that we enlarge a non-full set (in the
algorithm denoted as $S_{j^{\prime}}$) by one vertex (in the algorithm denoted
as $v^{\prime}$) while maintaining the size of all remaining sets. That is, in
each iteration we make progress in the sense that $|\bigcup_{i\in[k]}S_{i}|$
increases while maintaining the invariant $|S_{i}|\leq n_{i}$ for all
$S_{i}$’s. Note that $v^{\prime}\in N(S_{j^{\prime}})$ which in turn implies
that $G[S_{i}]$ is always connected for all $i\in[k]$. Finally, by
$\sum_{i=1}^{k}n_{i}=n$ and through the way we update $I$ we ensure that the
algorithm (or while-loop) terminates as $\bigcup_{i\in[k]}S_{i}=V$ only if we
have $|S_{i}|=n_{i}$ for all $S_{i}$’s.

Towards proving the required lemmata for the correctness of Algorithm 1 we
make the following observation for the p.e.o. of a graph.

###### Lemma 1

Let $\sigma$ be a p.e.o of a graph $G=(V,E)$ and
$P=\\{v_{1},v_{2},\ldots,v_{k}\\}$ a vertex set of $G$ that induces a simple
path with endpoints $v_{1}$ and $v_{k}$. Then
$\sigma(v_{i})>\min\\{\sigma(v_{1}),\sigma(v_{k})\\}$ for all
$i=2,\ldots,k-1$.

###### Lemma 2

In each iteration of the while-loop in Algorithm 1 we have
$V^{\prime}\neq\varnothing$.

###### Proof

We first define the $z$-connecting neighborhood of a vertex $v$ to be the
neighbors of $v$ that are included in some induced path connecting $v$ to $z$.

We prove that every non-full set $S_{i}$ contains a vertex in its neighborhood
$N(S_{i})$ that is unassigned, which implies that $V^{\prime}\neq\varnothing$.
Assume for a contradiction that at some iteration of our algorithm there is an
non-full set $S_{i}$ whose neighborhood is already assigned to other sets. Let
$v$ be the vertex of $S_{i}$ of maximum $\sigma$ value among its vertices and
$z$ be the vertex of maximum $\sigma$ value among the unassigned vertices.
Note that $vz\not\in E(G)$. Let $\mathcal{P}$ be the set of all simple induced
paths of $G$ with endpoints $z$ and $v$. Consider now the following cases:

  1. 1.

If $\sigma(z)>\sigma(v)$, we get from Lemma 1 that every internal vertex of
each path in $\mathcal{P}$ has higher $\sigma$ value than $v$. Note that no
vertex of $S_{i}$ is an internal vertex of some path in $\mathcal{P}$, since
all of them have smaller $\sigma$ value than $v$ by the selection of $v$.
Denote the $z$-connecting neighborhood of $v$ by $C$.

Let $a,b$ be two vertices in $C$ and assume that $a,b\in S_{j}$ for some $j$.
Assume also that during our algorithm, $a$ is added to $S_{j}$ before $b$.
Since all vertices of $S_{i}$ have smaller $\sigma$ value than both $a$ and
$b$, and $a$ is added to $S_{j}$ before $b$, the moment $b$ is added to
$S_{j}$, $S_{i}$ has already been formed. Consider now the iteration that this
happens. Since $b\in N(v)$, $G[S_{i}\cup\\{b\\}]$ is connected. Moreover since
$\sigma(a)>\sigma(v)$ and $S_{i}$ is not full, $b$ should be added to $S_{i}$
instead of $S_{j}$. As a result each set apart from $S_{i}$ contains at most
one such neighbor of $v$, and hence $|C|<k$.

Observe that $G\setminus C$ has no induced path connecting $z$ and $v$ which
in turn implies that $G\setminus C$ has no $z-v$ path in general. However,
this contradicts the $k$-connectivity of $G$.

  2. 2.

If $\sigma(z)<\sigma(v)$, since $z$ is the unassigned vertex of the highest
$\sigma$ value among all unassigned vertices, and by Lemma 1 all vertices in
$\mathcal{P}$ have greater $\sigma$ value than $z$, all of its $v$-connecting
neighbors in $\mathcal{P}$ are already assigned in some set. Denote the set of
$v$-connecting neighbors of $z$ by $C$.

Assume now that there are two vertices of $C$, $a$ and $b$, that are contained
in some $S_{j}$ and assume also without loss of generality that $a$ was added
to $S_{j}$ before $b$. Note that since $\sigma(z)<\sigma(b)$ at each iteration
of our algorithm $z$ is considered before $b$ to be added to some set if the
induced graph remains connected. As a result, after $a$ is added to $S_{j}$,
the induced subgraph $G[S_{j}\cup\\{z\\}]$ is connected and hence $z$ should
be added to $S_{j}$ before $b$.

This means that each set contains at most one $v$-connecting neighbor of $z$
and therefore $|C|<k$. Since $G\setminus C$ has no induced path connecting $z$
and $v$, there is no $z$-$v$-path in $G\setminus C$, which contradicts the
$k$-connectivity.

###### Corollary 1

At each iteration of Algorithm 1, unless all vertices are assigned, the
neighborhood of each non-full set contains at least one unassigned vertex.

In the weighted case we use the above corollary of Lemma 2. In particular, it
follows from Corollary 1 that as long as we do not declare a set to be full,
we ensure that we are able to extend it by a vertex in its neighborhood that
is unassigned. Note that in the weighted case we do not know in advance how
many vertices are in each part.

###  3.2 GL-Partition for Weighted Chordal Graphs

With a slight modification of Algorithm 1 we can compute the weighted version
of a GL-Partition. In particular, we prove Theorem 1.1.

The input of our algorithm differs from the unweighted case by having a
positive vertex-weighted graph $G=(V,E,w)$ and instead of demanded sizes
$n_{1},\dots,n_{k}$ we have demanded weights $w_{1},\dots,w_{k}$ for our
desired vertex sets $S_{1},\dots,S_{k}$, where $\sum_{i=1}^{k}w_{i}=w(V)$.
Note also that $w(S_{i})$ is not allowed to deviate more than
$w_{\mathit{max}}=\max_{v\in V}w(v)$ from $w_{i}$, i.e.
$w_{i}-w_{\mathit{max}}<w(S_{i})<w_{i}+w_{\mathit{max}}$.

Input: $k$-connected vertex-weighted chordal graph $G(V,E,w)$, terminal
vertices $t_{1},\ldots,t_{k}\in V$, and positive weights $w_{1},\ldots,w_{k}$
satisfying $\sum_{i=1}^{k}w_{i}=w(V)$

Output: Connected vertex sets $S_{1},\ldots,S_{k}\subseteq V$ such that
$w_{i}-w_{\max}<w(S_{i})<w_{i}+w_{\max}$ and $t_{i}\in S_{i}$

1

2$\sigma$ $\leftarrow$ Compute p.e.o. of $G$ as function $\sigma\colon
V\to|V|$

3

4$S_{i}\leftarrow\\{t_{i}$}, for all $i\in[k]$

5$I\leftarrow\\{i\in[k]\mid w(S_{i})<w_{i}\\}$

6while  _$|I|\neq 1$ and $\bigcup_{i\in[k]}S_{i}\neq V(G)$_ do

7

8 $V^{\prime}\leftarrow N(\bigcup_{i\in
I}S_{i})\setminus\bigcup_{i\in[k]\setminus I}S_{i}$

9 $v^{\prime}\leftarrow\operatorname*{arg\,min}_{v\in V^{\prime}}\sigma(v)$

10 $J\leftarrow\left\\{i\in I\mid v\in N(S_{i})\right\\}$

11 $j^{\prime}\leftarrow$ $\operatorname*{arg\,min}_{j\in
J}\max(\sigma(S_{j}))$

12 if  _$w(S_{j^{\prime}})+w(v^{\prime}) <w_{j^{\prime}}$_ then

13 $S_{j^{\prime}}\leftarrow S_{j^{\prime}}\cup\\{v^{\prime}\\}$

14 end if

15 else

16 $I\leftarrow I\setminus\\{j^{\prime}\\}$

17 if  _$\sum_{i\in[k]\setminus I}(w_{i}-w(S_{i}))\geq 0$ or
$w(S_{j^{\prime}})+w(v^{\prime})=w_{j^{\prime}}$_ then

18 $S_{j^{\prime}}\leftarrow S_{j^{\prime}}\cup\\{v^{\prime}\\}$

19 end if

20

21 end if

22

23 end while

If $|I|=1$, assign all vertices $V\setminus\bigcup_{i\in[k]}S_{i}$ (possibly
empty) to $S_{j}$ with $j\in I$.

Algorithm 2 WeightedChordalGL

Again we set each terminal vertex $t_{i}$ to a corresponding set $S_{i}$, and
enlarge iteratively the non-full weighted sets ($S_{i}$’s that are not
declared as full). One difference to the previous algorithm is that we declare
a set $S_{i}$ as full weighted set, if together with the next vertex to be
potentially added its weight would exceed $w_{i}$. After that, we decide
whether to add the vertex with respect to the currently full weighted sets.
Similar to Algorithm 1 we interrupt the while-loop if $S_{1},\dots,S_{k}$
forms a vertex partition of $V$ and the algorithm terminates. However, to
ensure that we get a vertex partition in every case, we break the while-loop
when only one non-full weighted set is left and assign all remaining
unassigned vertices to it.

Observe that we can make use of Corollary 1, since Algorithm 2 follows the
same priorities concerning the p.e.o. as Algorithm 1. Basically, it implies
that as long we do not declare a set as full weighted set and there are still
unassigned vertices then those sets have unassigned vertices in its
neighborhood.

We conclude this section by extending the above algorithms to graphs having
distance $k/2$ from being chordal. In particular this corollary is based on
the observation that an edge added to a graph does not participate in any of
the parts those algorithms output if both of its endpoints are terminal
vertices.

###### Corollary 2

Let $G$ be a $k$-connected graph which becomes chordal after adding $k/2$
edges. Given this set of edges, a GL-Partition (also its weighted version) can
be computed in polynomial time but without fixed terminals.

##  4 GL-Partition for $\text{HHI}_{4}^{2}$-free

This section is dedicated to the proof of Theorem 1.2. The underlying idea for
this result is to carefully contract edges to turn a $k$-connected
$\text{HHI}_{4}^{2}$-free graph into a chordal graph that is still
$k$-connected. Note that we indeed have to be very careful here to find a set
of contractions, as we need it to satisfy three seemingly contradicting
properties: removing all induced $C_{4}$, preserving $k$-connectivity, and
contracting at most one edge adjacent to each vertex. The last property is
needed to bound the maximum weight of the vertices in the contracted graph.
Further, we have to be careful not to contract terminal vertices.

The computation for the unweighted case of the partition for Theorem 1.2 is
given in Algorithm 3 below, which is later extended to the weighted case as
well. Note that we can assume that $n_{i}\geq 2$ since if $n_{i}=1$ for some
$i\in[k]$ we simply declare the terminal vertex to be the required set and
remove it from $G$. This gives us a $(k-1)$-connected graph and $k-1$ terminal
vertices.

Before starting to prove the Lemmata required for the correctness of Algorithm
3 we give a structural insight which is used in almost all proofs of the
following Lemmata. Due to space restrictions the proofs of Lemmata 3 to 6, 8
and 10 have been moved to Appendix 0.B.

###### Lemma 3

Given an $\text{HHI}_{4}^{2}$-free graph $G$ and an induced $C_{4}$,
$C\subseteq V(G)$, then any vertex in $V(G)\setminus C$ that is adjacent to
two vertices of $C$ is universal to $C$. Moreover, the set of vertices that
are universal to $C$ induces a clique.

Input: $k$-connected $\text{HHI}_{4}^{2}$-free graph $G(V,E)$, terminal
vertices $t_{1},\ldots,t_{k}\in V$, and positive integers
$n_{1},\ldots,n_{k}\geq 2$ satisfying $\sum_{i=1}^{k}n_{i}=n$

Output: Connected vertex sets $S_{1},\ldots,S_{k}\subseteq V$ such that
$n_{i}-1\leq|S_{i}|\leq n_{i}+1$ and $t_{i}\in S_{i}$

1

2Add an edge between each pair of non-adjacent terminals that are part of an
induced $C_{4}$

3$\mathcal{C}\leftarrow$ Set of all induced $C_{4}$ in $G$.

4$G^{\prime}\leftarrow$
$(\bigcup_{C\in\mathcal{C}}V(C),\bigcup_{C\in\mathcal{C}}E(C))$

5$E^{\prime}\leftarrow\varnothing$

6while  _$\mathcal{C}\neq\varnothing$_ do

7 Select three vertices $v_{1},v_{2},v_{3}$ in $G^{\prime}$ and the
corresponding cycle $C\in\mathcal{C}$ that satisfies that for all
$C^{\prime}\in\mathcal{C}\setminus\\{C\\}$ we have
$V(C^{\prime})\cap\\{v_{1},v_{2},v_{3}\\}=\varnothing$.

8 Pick a vertex $v$ from $v_{1},v_{2},v_{3}$ that is not a terminal vertex and
add an incident edge of $v$ in $G^{\prime}[\\{v_{1},v_{2},v_{3}\\}]$ to
$E^{\prime}$.

9 Remove the cycle $C$ from $\mathcal{C}$ and the vertices $v_{1},v_{2},v_{3}$
from $G^{\prime}$.

10 end while

11

12Transform $G$ to a weighted graph $G^{\prime\prime}$ by contracting each
edge of $E^{\prime}$ in $G$, assigning to each resulting vertex as weight the
number of original vertices it corresponds to.

13$S_{1},\dots S_{k}\leftarrow$ Run Algorithm 2 with $G^{\prime\prime}$, the
given set of terminals $t_{1},\ldots,t_{k}$, and the size (or weight) demands
$n_{1},\ldots,n_{k}$ as input.

Reverse the edge contraction of $E^{\prime}$ in the sets $S_{1},\dots,S_{k}$
accordingly.

Algorithm 3 $\text{HHI}_{4}^{2}$-free GL

###### Lemma 4

Let $G$ be an $\text{HHI}_{4}^{2}$-free graph. If $G$ contains a double house
as a subgraph then at least one of the two $C_{4}$ in it has a chord.

$u_{13}$$u_{11}$$u_{3}$$u_{1}$$u_{21}$$u_{2}$$u_{22}$$C^{1}$$C^{2}$

$z_{2}$$z_{1}$$z_{3}$$z_{4}$$u$$w$$u_{1}$$u_{3}$$u_{2}$$w_{2}$$w_{3}$$w_{1}$

$v_{2}$$v_{3}$$v_{1}$$v_{4}$$u$$w$$u_{1}$$u_{2}$$w_{1}$$w_{2}$

Figure 2: Illustrations for the vertex namings used in proofs, from left to
right: Lemma 4, Lemma 7 and Lemma 8

The following lemma captures the essence of why the algorithm provided in this
section cannot be applied also on HHD-free graphs, since it holds for
$\text{HHI}_{4}^{2}$-free graphs but not for HHD-free graphs. Think for
example of a simple path $P$ of length $5$ and a vertex disjoint induced
chordless $C_{4}$, $C$. Consider also each vertex of $P$ being universal to
$C$. Observe that this graph is HHD- but not $\text{HHI}_{4}^{2}$-free. Every
two non adjacent vertices of $C$ together with the endpoints of $P$ create an
induced chordless $C_{4}$. Adding a chord connecting the two endpoints of $P$
creates a hole and hence the resulting graph is not HHD-free.

###### Lemma 5

Let $G$ be a $\text{HHI}_{4}^{2}$-free graph and
$C=\\{v_{1},v_{2},v_{3},v_{4}\\}$ an induced $C_{4}$ in $G$. Then the graph
$G^{\prime}$ created by adding the chord $v_{1}v_{3}$ to $G$ is
$\text{HHI}_{4}^{2}$-free and has one less induced $C_{4}$ than $G$.

An essential property of the graph class we work on is being closed under
contraction, since our algorithm is based on contracting edges iteratively
until the resulting graph becomes chordal. Before proving this property
though, although “after an edge contraction a new cycle is created” is
intuitively clear, we formally define what it means for a $C_{4}$ to be “new”.

###### Definition 1

Let $G$ be a graph, $uv\in E(G)$ and $G^{\prime}=G/uv$. Let also $w$ be the
vertex of $G^{\prime}$ that is created by the contraction of $uv$. We say that
an induced cycle $C$ containing $w$ in $G^{\prime}$ is new if
$N_{C}(w)\not\subseteq N_{G}(v)$ and $N_{C}(w)\not\subseteq N_{G}(u)$.

###### Lemma 6

$\text{HHI}_{4}^{2}$-free graphs are closed under contraction of an edge of an
induced $C_{4}$.

In order to prove that the contractions of our algorithm do not affect the
connectivity, we first study the possible role of vertices on an induced
$C_{4}$ in minimal separators in $\text{HHI}_{4}^{2}$-free graphs.

###### Lemma 7

Let $G$ be a $k$-connected $\text{HHI}_{4}^{2}$-free graph for $k\geq 5$. Then
no three vertices of an induced $C_{4}$ belong in the same minimal separator.

###### Proof

Let $G$ be a $k$-connected $\text{HHI}_{4}^{2}$-free graph for $k\geq 5$ and
$v_{1},v_{2},v_{3},v_{4}$ vertices that induce a $C_{4}$, $C$. Assume that
$v_{1},v_{2},v_{3}$ belong in the a same minimal separator $S$ and hence,
$(G\setminus\\{v_{1},v_{2},v_{3}\\})$ is only $k-3$ connected. Let also $u$
and $w$ be two distinct vertices belonging in different connected components
of $G\setminus S$.

Consider now the chordal graph $G^{\prime}$ created, by adding $v_{2}v_{4}$ to
$C$ and one chord to each other induced $C_{4}$ of $G$. By Lemma 5 this is
possible by adding exactly one chord to each induced $C_{4}$ of $G$ \- in
particular each addition does not create new induced $C_{4}$. Since
$G^{\prime}$ is chordal each minimal separator induces a clique, and hence
$v_{1},v_{2},v_{3}$ cannot be part of the same minimal separator in
$G^{\prime}$ because they do not induce a triangle in $G^{\prime}$. Thus
$G^{\prime}\setminus S$ remains connected.

Let $P_{1}$ be a $u-w$ path in $G^{\prime}\setminus S$ that contains a minimal
number of added edges. Let $z_{1}z_{3}\in E(P_{1})$ be one of the added edges,
such that $z_{3}$ is closer to $u$ on $P_{1}$ than $z_{1}$. Note that $z_{1}$
and $z_{3}$ are part of some induced $C_{4}$,
$C^{\prime}=\\{z_{1},z_{2},z_{3},z_{4}\\}$ in $G$. Since $z_{1}z_{3}$ cannot
be replaced by neither $z_{1}z_{2},z_{2}z_{3}$, nor $z_{1}z_{4},z_{4}z_{3}$
(otherwise we get a path with strictly less added edges than $P_{1}$) it
follows that $z_{2},z_{4}\in S$.

We will use the $u-w$ paths through $S$ in $G$ to reach a contradiction. Since
$S$ is a minimal $u-w$ separator in $G$, there are two internally vertex
disjoint $u-w$ paths $P_{2}$ and $P_{3}$, with $P_{2}\cap S=\\{z_{2}\\}$ and
$P_{3}\cap S=\\{z_{4}\\}$. Let $w_{2}$ be the neighbor of $z_{2}$ on $P_{2}$
closer to $w$, $w_{1}$ the respective neighbor of $z_{1}$ on $P_{1}$ and
$w_{3}$ the respective neighbor of $z_{4}$ on $P_{3}$. Let also $u_{1}$,
$u_{2}$, $u_{3}$ be the corresponding neighbors of these paths closer to $u$.
See the illustration in Figure 2 for these namings, keeping in mind that it
could be $w_{1}\in\\{w_{2},w_{3}\\}$ or $u_{1}\in\\{u_{2},u_{3}\\}$ or also
$w_{1}=w_{2}=w_{3}=w$ or $u_{1}=u_{2}=u_{3}=u$.

We claim that, in $G$, $z_{3}$ is adjacent to a vertex on $P_{2}^{[w_{2},w]}$
or $P_{3}^{[w_{3},w]}$. Assume otherwise, and assume that $P_{2}^{[w_{2},w]}$,
$P_{3}^{[w_{3},w]}$ are induced paths in $G$ (shortcut them otherwise). If
$w_{2}=w_{3}$ then notice that $w_{2}=w=w_{3}$. In order for
$z_{3},z_{2},z_{4},w$ not to induce a $C_{4}$ with three common vertices to
$C$, $z_{3}$ has to be adjacent to $w$ which is on $P_{2}^{[w_{2},w]}$. If
$w_{2}\neq w_{3}$ then assume without loss of generality that $w_{2}\neq w$.
In order to not be a hole, there has to be a chord in the cycle build by
$P_{2}^{[w_{2},w]}$, $P_{3}^{[w_{3},w]}$ with $z_{4},z_{3},z_{2}$. By
assumption, this chord cannot be from $z_{3}$, so it has to involve $z_{4}$ or
$z_{2}$. Since $P_{2}^{[w_{2},w]}$ and $P_{3}^{[w_{3},w]}$ are induced and
$w_{2}\neq w$, either $w_{2}$ is adjacent to $z_{4}$, or $w_{3}\neq w$ is
adjacent to $z_{2}$. Both cases create a $C_{4}$ that has three vertices in
common with $C$, ($w_{2},z_{2},z_{3},z_{4}$, and $w_{3},z_{2},z_{3},z_{4}$,
resp.) and since $z_{4}z_{2}\notin E(G)$, the added chord for these $C_{4}$
has to be $w_{2}z_{3}$, resp. $w_{3}z_{3}$, leading again to $z_{3}$ being
adjacent to some vertex on $P_{2}^{[w_{2},w]}$ or $P_{3}^{[w_{3},w]}$.

Thus we conclude that $z_{3}$ is adjacent to a vertex $x$ on
$P_{2}^{[w_{2},w]}$ or $P_{3}^{[w_{3},w]}$ in $G$. This however allows to
create a path from $u$ to $w$ with (at least) one added edge less than $P_{1}$
in $G$ (since $P_{2},P_{3}$ do not contain any added edges). Specifically, if
$x$ is on $P_{2}$ we get $P_{1}^{\prime}=P_{1}^{[u,z_{3}]}xP_{2}^{[x,w]}$ and
if $x\in P_{3}$, $P_{1}^{\prime}=P_{1}^{[u,z_{3}]}xP_{3}^{[x,w]}$.

Since $C^{\prime}$ was an arbitrary cycle we conclude that $v_{1},v_{2},v_{3}$
cannot be part of the same minimal separator in $G$.

###### Lemma 8

Let $G$ be an $\text{HHI}_{4}^{2}$-free $k$-connected graph and
$C=\\{v_{1},v_{2},v_{3},v_{4}\\}$ be an induced $C_{4}$. The graph
$G^{\prime}=G/v_{1}v_{2}$ is still $k$-connected.

Now, we finally look specifically at Algorithm 3, and first show that its
subroutine creating $G^{\prime\prime}$ works correctly.

###### Lemma 9

Given an $\text{HHI}_{4}^{2}$-free graph $G$, the vertices selected in line 6
of Algorithm 3 indeed exist as long as an induced $C_{4}$ exists.

###### Proof

Let $G$ be an $\text{HHI}_{4}^{2}$-free graph and $\mathcal{C}$ the set of all
induced $C_{4}$ in $G$, consider the bipartite graph $T$ constructed through
the following procedure: Its vertices are partitioned into two sets $B$, and
$S$ referred to as _big_ and _small_ vertices of $T$, respectively. Each big
vertex represents an induced $C_{4}$ of $\mathcal{C}$ while each small vertex
represents a vertex of $G$ participating in at least two induced $C_{4}$. Each
small vertex is adjacent to the big vertices which represent a $C_{4}$ this
vertex participates in. We claim that with this definition $T$ is indeed a
tree (actually a forest). Assume now for a contradiction that $T$ contains a
cycle and let $C$ be one of the shortest such cycles in $T$.

First, consider the case that $C$ has length $l\geq 6$. Since $T$ is
bipartite, due to its construction, $l$ is even and the vertices of
$C=\\{s_{1},b_{1},s_{2},b_{2},\ldots,s_{l/2},b_{l/2}\\}$ alternate between big
and small. We denote by $P_{b_{i}}^{s_{w},s_{z}}$ a shortest path containing
edges from the $C_{4}$ represented by the big vertex $b_{i}$ with endpoints
the vertices represented by $s_{w}$ and $s_{z}$. Due to $C$, the cycle
$P_{b_{1}}^{s_{1},s_{l/2}}\ldots P_{b_{l}/2}^{s_{l/2-1},s_{l/2}}$ exists in
$G$ as a subgraph. Note that since we have assumed that $C$ is a minimal
length cycle of $T$ it is also chordless. Hence, in order for a hole not to be
an induced subgraph of $G$ at least one chord must exist connecting two
vertices corresponding to two small ones of $T$. This however would create a
double house as a subgraph with the two $C_{4}$ forming it being the two that
correspond to big vertices of $T$. By Lemma 4 this means that one of the
$C_{4}$ is not induced, a contradiction to the construction of $T$. Notice
also that in the case where $l=6$ we directly find a double house and reach a
contradiction using the same arguments.

Moreover the assumption that $l=4$, leads us to a contradiction to the fact
that two $C_{4}$ have at most one vertex in common. Hence, $T$ is a forest and
the vertices mentioned in line 6 are the ones belonging only to a cycle
represented by one leaf belonging in $B$.

###### Lemma 10

Given an $\text{HHI}_{4}^{2}$-free graph $G$, lines 1-10 of Algorithm 3
transforms $G$ into a weighted chordal graph $G^{\prime\prime}$, with the same
connectivity as $G$ and such that each vertex from $G$ is involved in at most
one edge contraction to create $G^{\prime\prime}$.

At last, notice that we can easily alter Algorithm 3 to also work for weighted
graphs, with the simple change of setting the weights of a vertex in
$G^{\prime\prime}$ in line 10 to the sum of the weights of the original
vertices it was contracted from. With this alteration, we can conclude now the
proof of Theorem 1.2 with the following.

###### Lemma 11

Algorithm 3 works correctly and runs in time $\mathcal{O}(|V|^{4})$.

###### Proof

By Lemma 10, $G^{\prime\prime}$ is a chordal graph with maximum vertex weight
$2w_{\mathit{max}}$. Further, observe that we did not merge terminal vertices
with each other, thus we can properly run Algorithm 2 on it. By the
correctness of this algorithm (Theorem 1.1), we know that $S_{1},\dots,S_{k}$
in line 11 is a GL-partition for $G^{\prime\prime}$ with deviation
$2w_{\mathit{max}}$. Since reversing edge-contraction does not disconnect
these sets, the unfolded sets $S_{1},\dots,S_{k}$ are thus also a GL-partition
for $G$ with deviation $2w_{\mathit{max}}$; note here that the only edges we
added to create $G^{\prime\prime}$ are between terminal vertices, which are in
separate sets $S_{i}$ by definition.

The most time consuming part of Algorithm 3 is the preprocessing to transform
the input graph into a weighted chordal graph which requires
$\mathcal{\mathcal{O}}({|V|}^{4})$ time in order to find all the induced
$C_{4}$ (note that the induced $C_{4}$ are at most $(n-4)/3$ since they induce
a tree).

Moreover, as is the case for chordal graphs, we can sacrifice terminals to
enlarge the considered graph class.

###### Corollary 3

Let $G$ be a $k$-connected graph which becomes $\text{HHI}_{4}^{2}$-free after
adding $k/2$ edges. Then, given those edges, a GL-Partition of $G$ with
deviation $1$ (also its weighted version with deviation $2w_{max}-1$) can be
computed in polynomial time but without fixed terminals.

## References

  * [1] Broersma, H., Dahlhaus, E., Kloks, T.: Algorithms for the treewidth and minimum fill-in of HHD-free graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG). pp. 109–117 (1997). https://doi.org/10.1007/BFb0024492, https://doi.org/10.1007/BFb0024492
  * [2] Chandran, L.S., Cheung, Y.K., Issac, D.: Spanning tree congestion and computation of generalized Györi-Lovász partition. In: International Colloquium on Automata, Languages, and Programming, (ICALP). LIPIcs, vol. 107, pp. 32:1–32:14 (2018). https://doi.org/10.4230/LIPIcs.ICALP.2018.32, https://doi.org/10.4230/LIPIcs.ICALP.2018.32
  * [3] Chen, J., Kleinberg, R.D., Lovász, L., Rajaraman, R., Sundaram, R., Vetta, A.: (almost) tight bounds and existence theorems for single-commodity confluent flows. Journal of the ACM 54(4), 16 (2007). https://doi.org/10.1145/1255443.1255444, https://doi.org/10.1145/1255443.1255444
  * [4] Fulkerson, D., Gross, O.: Incidence matrices and interval graphs. Pacific Journal of Mathematics 15(3), 835–855 (1965)
  * [5] Győri, E.: On division of graphs to connected subgraphs, combinatorics. In: Colloq. Math. Soc. Janos Bolyai, 1976 (1976)
  * [6] Hoyer, A.: On the independent spanning tree conjectures and related problems. Ph.D. thesis, Georgia Institute of Technology (2019)
  * [7] Jamison, B., Olariu, S.: On the semi-perfect elimination. Advances in Applied Mathematics 9(3), 364–376 (1988)
  * [8] Lovász, L.: A homology theory for spanning tress of a graph. Acta Mathematica Hungarica 30(3-4), 241–251 (1977)
  * [9] Lucertini, M., Perl, Y., Simeone, B.: Most uniform path partitioning and its use in image processing. Discrete Applied Mathematics 42(2), 227–256 (1993). https://doi.org/10.1016/0166-218X(93)90048-S, https://doi.org/10.1016/0166-218X(93)90048-S
  * [10] Möhring, R.H., Schilling, H., Schütz, B., Wagner, D., Willhalm, T.: Partitioning graphs to speedup Dijkstra’s algorithm. ACM Journal of Experimental Algorithmics 11 (2006). https://doi.org/10.1145/1187436.1216585, https://doi.org/10.1145/1187436.1216585
  * [11] Nakano, S., Rahman, M.S., Nishizeki, T.: A linear-time algorithm for four-partitioning four-connected planar graphs. Information Processing Letters 62(6), 315–322 (1997). https://doi.org/10.1016/S0020-0190(97)00083-5, https://doi.org/10.1016/S0020-0190(97)00083-5
  * [12] Przytycka, T.M.: An important connection between network motifs and parsimony models. In: International Conference on Research in Computational Molecular Biology (RECOMB). vol. 3909, pp. 321–335. Springer (2006). https://doi.org/10.1007/11732990_27, https://doi.org/10.1007/11732990_27
  * [13] Przytycka, T.M., Davis, G.B., Song, N., Durand, D.: Graph theoretical insights into evolution of multidomain proteins. Journal of Computational Biology 13(2), 351–363 (2006). https://doi.org/10.1089/cmb.2006.13.351, https://doi.org/10.1089/cmb.2006.13.351
  * [14] Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing 5(2), 266–283 (1976). https://doi.org/10.1137/0205021, https://doi.org/10.1137/0205021
  * [15] Suzuki, H., Takahashi, N., Nishizeki, T., Miyano, H., Ueno, S.: An algorithm for tripartitioning 3-connected graphs. Journal of Information Processing Society of Japan 31(5), 584–592 (1990)
  * [16] Suzuki, H., Takahashi, N., Nishizeki, T.: A linear algorithm for bipartition of biconnected graphs. Information Processing Letters 33(5), 227–231 (1990). https://doi.org/10.1016/0020-0190(90)90189-5, https://doi.org/10.1016/0020-0190(90)90189-5
  * [17] Wada, K., Kawaguchi, K.: Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG). vol. 790, pp. 132–143. Springer (1993). https://doi.org/10.1007/3-540-57899-4_47, https://doi.org/10.1007/3-540-57899-4_47
  * [18] Zhou, X., Wang, H., Ding, B., Hu, T., Shang, S.: Balanced connected task allocations for multi-robot systems: An exact flow-based integer program and an approximate tree-based genetic algorithm. Expert Systems with Applications 116, 10–20 (2019). https://doi.org/10.1016/j.eswa.2018.09.001, https://doi.org/10.1016/j.eswa.2018.09.001

##  Appendix 0.A Correctness of Algorithm 2 (WeightedChordalGL)

For the correctness Algorithm 2, we need to prove that all vertices are
assigned, i.e. the algorithm terminates, and if this is the case, then
$S_{1},\dots,S_{k}$ corresponds to a connected vertex partition satisfying the
required weight conditions for each $S_{i}$. We start by proving that the
Algorithm 2 eventually ends up assigning all vertices into connected vertex
sets.

###### Lemma 12

Algorithm 2 terminates, such that all vertices are assigned, where $G[S_{i}]$
is connected for all $i\in[k]$. Further, the while-loop iterates at most $|V|$
times.

###### Proof

Similarly to Algorithm 1, because we add only vertices to non-full weighted
sets from its unassigned neighborhood, the $S_{i}$s correspond always to
connected vertex sets. Note that by Corollary 1 as long as we have non-full
weighted sets and unassigned vertices, the while-loop makes progress in the
sense that either an unassigned vertex becomes assigned or a set is declared
to be a full weighted set. Thus, if there are unassigned vertices after the
while-loop, and we have $|I|=1$ and we assign the remaining ones to the last
non-full weighted set $S_{j}$ with $j\in I$ (cf. line 2). Observe that
Corollary 1 implies that $G[S_{j}]$ is still connected after adding the
remaining vertices.

For the second part of the lemma, when we reach the while loop, there are
exactly $|V|-k$ unassigned vertices. Except of at most $k$ times an unassigned
vertex becomes assigned in an iteration of the while-loop. This in turn
implies that we have not more than $|V|$ iterations.

The running time in Theorem 1.1 is $\mathcal{O}(|V|^{2})$ since the while-loop
iterates at most $|V|$ times and each operation in this loop runs in
$\mathcal{O}(|V|)$ time. Hence, to prove Theorem 1.1 it remains to show that
the required weight condition for each part of the connected vertex partition
$S_{1},\dots,S_{k}$ is satisfied.

The indices in $I$ denote the non-full weighted sets and therefore,
$\overline{I}:=[k]\setminus I$ the indices of the full weighted sets.
Declaring a set $S_{j^{\prime}}$ as complete weighted set, i.e. we remove
$j^{\prime}$ from $I$, implies that $w(S_{j^{\prime}})+w(v^{\prime})\geq
w_{j^{\prime}}$. If $w(S_{j^{\prime}})+w(v^{\prime})\neq w_{j^{\prime}}$,
whether we add $v^{\prime}$ to $S_{j^{\prime}}$ depends on whether the value
of $\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))$ is less than zero or not.
Basically, this sum serves to balance the variations in the required weights
of the sets $S_{1},\dots,S_{k}$, and determines the moment we declare
$S_{j^{\prime}}$ to be a full weighted set whether we want
$w(S_{j^{\prime}})<w_{j^{\prime}}$ or $w(S_{j^{\prime}})>w_{j^{\prime}}$.
During the algorithm the sum $\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))$
satisfies the following invariant.

###### Lemma 13

In the Algorithm 2, before reaching line 2 we have each time
$|\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))|<w_{\mathit{max}}$.

###### Proof

We prove this lemma by induction on $|\overline{I}|$. After assigning each
terminal to a corresponding vertex set, we initialize $I$ by $I=\\{i\in[k]\mid
w(S_{i})<w_{i}\\}$. That is, $\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))=0$,
since either $\overline{I}=\varnothing$ or each $i\in\overline{I}$ satisfy
$w(S_{i})=w_{i}$ by $w(t_{i})\leq w_{i}$.

Assume $|\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))|<w_{\mathit{max}}$ for
$|\overline{I}|\leq\ell<k$ and we now add $j^{\prime}$ to $\overline{I}$
according to the algorithm, i.e. we remove $j^{\prime}$ from $I$. First, we
show that $|w_{j}-w(S_{j^{\prime}})|<w_{\mathit{max}}$ in both possible future
cases $v^{\prime}\in S_{j^{\prime}}$ or $v^{\prime}\notin S_{j^{\prime}}$. By
$w(S_{j}\cup\\{v^{\prime}\\})=w_{j}$ we have added $v^{\prime}$ to
$S_{j^{\prime}}$ and $|w_{j}-w(S_{j^{\prime}})|=0<w_{\mathit{max}}$ holds.
Thus, we can assume that $w(S_{j^{\prime}}\setminus\\{v^{\prime}\\})<w_{j}$
and $w(S_{j^{\prime}}\cup\\{v^{\prime}\\})>w_{j^{\prime}}$ which in turn
results to
$|w_{j^{\prime}}-w(S_{j^{\prime}}\cup\\{v^{\prime}\\})|<w_{\mathit{max}}$ and
$|w_{j^{\prime}}-w(S_{j^{\prime}}\setminus\\{v^{\prime}\\})|<w_{\mathit{max}}$
by $w(v^{\prime})\leq w_{\mathit{max}}$.

If $w(S_{j^{\prime}}\cup\\{v^{\prime}\\})=0$, we have
$\sum_{i\in\overline{I}\setminus\\{j^{\prime}\\}}(w_{i}-w(S_{i}))=\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))$
and we are done by the induction hypotheses

We can assume that $w(S_{j^{\prime}}\cup\\{v^{\prime}\\})>w_{j^{\prime}}$. If
$0\leq\sum_{i\in\overline{I}\setminus\\{j^{\prime}\\}}(w_{i}-w(S_{i}))<w_{\mathit{max}}$
we add $v^{\prime}$ to $S_{j^{\prime}}$. It follows that
$\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))<\sum_{i\in\overline{I}\setminus\\{j^{\prime}\\}}(w_{i}-w(S_{i}))$
by $w_{j^{\prime}}-w(S_{j^{\prime}})<0$. By
$-w_{\mathit{max}}<w_{j}-w(S_{j^{\prime}})<0$ the sums might deviate by at
most $w_{\mathit{max}}-1$ from each other. Thus, by
$\sum_{i\in\overline{I}\setminus\\{j^{\prime}\\}}(w_{i}-w(S_{i}))\geq 0$ we
obtain $|\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))|<w_{\mathit{max}}$.

In case
$-w_{\mathit{max}}<\sum_{i\in\overline{I}\setminus\\{j^{\prime}\\}}(w_{i}-w(S_{i}))<0$
we do not add $v^{\prime}$ to $S_{j^{\prime}}$ and obtain
$\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))>\sum_{i\in\overline{I}\setminus\\{j^{\prime}\\}}(w_{i}-w(S_{i}))$
by $w_{j^{\prime}}-w(S_{j^{\prime}})>0$. Furthermore, by
$0<w_{j}-w(S_{j^{\prime}})<w_{\mathit{max}}$ the sums deviate by at most
$w_{\mathit{max}}-1$ from each other and finally, by
$\sum_{i\in\overline{I}\setminus\\{j^{\prime}\\}}(w_{i}-w(S_{i}))<0$ we obtain
$|\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))|<w_{\mathit{max}}$.

With Lemma 13 we prove now the last part of the proof Theorem 1.1.

###### Lemma 14

If Algorithm 2 terminates, then we have
$w_{i}-w_{\mathit{max}}<w(S_{i})<w_{i}+w_{\mathit{max}}$ for each $i\in[k]$.

###### Proof

The sets in $S_{1},\dots,S_{k}$ with indices $[k]\setminus I$ in the
initialization of $I$, i.e. $I=\\{i\in[k]\mid w(S_{i})<w_{i}\\}$, satisfy
clearly its weight conditions as $w(t_{i})\leq w_{i}$ for all $i\in[k]$. Next,
we show that each set that is declared as full weighted set in the while-loop
satisfies its weight condition, i.e. $|w_{i}-w(S_{i})|<w_{\mathit{max}}$ for
$i\in\overline{I}$. According to Algorithm 2 let $j^{\prime}$ be the index
that we remove from $I$ and consider $S_{j^{\prime}}$ before possibly adding
$v^{\prime}$ to it. $w(S_{j^{\prime}})<w_{j^{\prime}}$ and
$w(S_{j^{\prime}})+w(v^{\prime})\geq w_{j^{\prime}}$ implies that
$w(S_{j^{\prime}})<w_{j^{\prime}}+w_{\mathit{max}}$ independent of
$v^{\prime}$ being added to $S_{j^{\prime}}$ or not by $w(v^{\prime})\leq
w_{\mathit{max}}$. Similarly, $w(S_{j^{\prime}})+w(v^{\prime})>w_{j^{\prime}}$
implies that $w(S_{j^{\prime}})>w_{j^{\prime}}-w_{\mathit{max}}$. In case
$w(S_{j^{\prime}})=w_{j^{\prime}}-w_{\mathit{max}}$ and
$w(v^{\prime})=w_{\mathit{max}}$ the algorithm adds $v^{\prime}$ to
$S_{j^{\prime}}$ (cf. line 2) and we have
$w_{j^{\prime}}-w(S_{j^{\prime}}\cup\\{v^{\prime}\\})=0<w_{\mathit{max}}$.

Hence, it remains to prove that the weight conditions are satisfied from the
non-full sets if either the while-loop terminates with all vertices assigned,
or with $|I|=1$. We start with the former case. If all vertices are assigned
we have
$\sum_{i=1}^{k}(w_{i}-w(S_{i}))=\sum_{i=1}^{k}w_{i}-\sum_{i=1}^{k}w(S_{i}))=w(V)-w(V)=0$.
Let $I$ be the indices of the non-full weighted sets after the while-loop is
terminated with all vertices assigned and recall $\overline{I}=[k]\setminus
I$. Each non-full weighted set $S_{i}$ for $i\in I$ satisfies $w(S_{i})<w_{i}$
and therefore $\sum_{i\in I}w_{i}-w(S_{i})>0$ as each value $w_{i}-w(S_{i})$
is greater than zero. Thus, by
$\sum_{i=1}^{k}(w_{i}-w(S_{i}))=\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))+\sum_{i\in
I}(w_{i}-w(S_{i}))=0$ we have $\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))<0$ and
by Lemma 13 $-w_{\mathit{max}}<\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))<0$.
Suppose there is an $i\in I$ with $w_{i}-w(S_{i})\geq w_{\mathit{max}}$. This
would imply that $0=\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))+\sum_{i\in
I}(w_{i}-w(S_{i}))>-w_{\mathit{max}}+\sum_{i\in I}(w_{i}-w(S_{i}))\geq-
w_{\mathit{max}}+w_{\mathit{max}}=0$, which is a contradiction.

It remains to consider the case that the while-loop terminates when $|I|=1$.
Let say $I=\\{\ell\\}$ and the remaining unassigned vertices are already added
to $S_{\ell}$ according to line 2. Same as above, the $S_{i}$’s with
$i\in[k]\setminus\\{\ell\\}=\overline{I}$ satisfy its required weight
condition and hence, we need to show that
$w_{\ell}-w_{\mathit{max}}<w(S_{\ell})<w_{\ell}+w_{\mathit{max}}$ holds. By
$\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))+\sum_{i\in
I}(w_{i}-w(S_{i}))=\sum_{i\in\overline{I}}(w_{i}-w(S_{i}))+(w_{\ell}-w(S_{\ell}))=0$
we obtain $\sum_{i\in\overline{I}}(w_{i}-w(S_{i})=w(S_{\ell})-w_{\ell}$. As a
result, since $|\sum_{i\in\overline{I}}(w_{i}-w(S_{i})|<w_{\mathit{max}}$ by
Lemma 13, it follows that $|w(S_{\ell})-w_{\ell}|<w_{\mathit{max}}$.

##  Appendix 0.B Omitted Proofs

### Proof of Lemma 1

###### Proof

Assume for a contradiction that there is an index $j\in\\{2,\ldots,k-1\\}$
such that $\sigma(v_{j})=\min_{i\in[k]}\\{\sigma(v_{i})\\}$. As a result
$\sigma(v_{j-1})>\sigma(v_{j})$ and $\sigma(v_{j})<\sigma(v_{j+1})$. This
means however when $v_{j}$ is assigned a $\sigma$ value, none of $v_{j-1}$ and
$v_{j+1}$ have been assigned such a value. Since $v_{j}$ is a simplicial
vertex at that point, its neighbors that still have not been assigned a
$\sigma$ value induce a clique. Hence, $v_{j-1}v_{j+1}\in E(G)$, which
contradicts the fact that $P$ induces a simple path.

### Proof of Lemma 3

###### Proof

Let $v\in V\setminus C$ be adjacent to two vertices $u$ and $w$ in $C$. If
$uw\in E(G)$ then, since $G$ is house-free, $v$ is also adjacent to at least
one vertex of $C$ other than $u$ and $w$. Then however, if $v$ is only
adjacent to three vertices of $C$, it induces a $C_{4}$ with two of the
adjacent and the non adjacent vertex, that shares 3 vertices with $C$. In the
case where $uw\not\in E(G)$, in order to not have two induced $C_{4}$ sharing
three vertices, $v$ has to also be adjacent to another vertex of $C$, which
leads us to the previous case where $v$ is adjacent to two vertices of $C$
inducing an edge and hence universal to $C$.

Moreover notice that any set of universal vertices to $C$, induces a clique
since otherwise two induced $C_{4}$ exist that share two vertices (consider
$C$ and the $C_{4}$ induced by two non adjacent vertices that are universal to
$C$ and two non adjacent vertices of $C$).

### Proof of Lemma 4

###### Proof

Let $G$ be an $\text{HHI}_{4}^{2}$-free graph and $H$ be a subgraph of $G$
that is a double house. As illustrated in Figure 2, we denote by $C^{1}$ and
$C^{2}$ the two induced $C_{4}$ of $H$, by $u_{1}$ their common vertex, by
$u_{2}$ and $u_{3}$ the ones adjacent to $u_{1}$ and to each other, belonging
in $C^{2}$ and $C^{1}$, respectively and finally by $u_{ij}$ the vertex of
$C_{i}$ that is adjacent to $u_{j}$.

Notice that by Lemma 3, since $u_{2}$ is adjacent to two vertices of $C^{1}$
it is universal to $C^{1}$, while the same holds for $u_{3}$ and $C^{2}$.
After adding those edges to $H$ however $u_{21}$ is adjacent to two of the
vertices of $C^{1}$, and hence is universal to $C^{1}$ in $G$, while the same
holds for $u_{11}$ and $C^{2}$. After this addition however $u_{13}$ is
adjacent to both $u_{2}$ and $u_{21}$ of $C^{2}$ and hence universal to
$C^{2}$, which creates the chord $u_{13}u_{1}$ in $C^{1}$ that concludes this
proof.

### Proof of Lemma 5

###### Proof

Assume for a contradiction that the addition of $v_{1}v_{3}$ creates a new
induced $C_{4}$, $C^{\prime}=\\{v_{1}^{\prime},v_{1},v_{3},v_{3}^{\prime}\\}$,
where $v_{1}^{\prime}$, and $v_{3}^{\prime}$ are the neighbors on $C^{\prime}$
of $v_{1}$ and $v_{3}$ respectively. Notice that $v_{1}^{\prime}$ and
$v_{3}^{\prime}$ do not belong in $C$. In order for
$v_{1},v_{2},v_{3},v_{3}^{\prime},v_{1}^{\prime}$ not to induce a hole in $G$,
either $v_{1}^{\prime}$ or $v_{3}^{\prime}$, say $v_{1}^{\prime}$, has to also
be adjacent to either $v_{2}$ or $v_{3}$. This however, due to Lemma 3, means
that $v_{1}^{\prime}$ is universal to $C$ in $G$, which creates a chord on
$C^{\prime}$.

It remains now to show that $G^{\prime}$ is still $\text{HHI}_{4}^{2}$-free.
Using similar arguments as before we see that no hole is formed from the
addition of $v_{1}v_{3}$ and since no new $C_{4}$ is formed also, the
remaining $C_{4}$ keep having pairwise at most one vertex in common. Assume
now for a contradiction that adding $v_{1}v_{3}$ creates an induced house $H$
in $G^{\prime}$. Since, as we showed above, $v_{1}v_{3}$ does not participate
in any induced $C_{4}$ it must be one of the two roof’s edges. Notice also
that from the vertices of $C$, only $v_{1}$ and $v_{3}$ participate in this
house because otherwise $G$ would contain two induced $C_{4}$ sharing two
vertices. Let $u$ be the third vertex of the roof and notice that by Lemma 3,
$u$ is also adjacent to $v_{2}$ and $v_{4}$, and let $w$ and $z$ be the
remaining two vertices of the house (assume that $wu,zv_{3}\in E(G)$). In
order for $wzv_{2}v_{3}u$ not to induce a house in $G$ either $v_{2}z\in E(G)$
or $v_{2}w\in E(G)$. Notice that through these cases we conclude, again by
Lemma 3, that either $w$ or $z$ is universal to $C$. We have assumed however
that $H$ is an induced house, hence $w$ is not universal to $C$ because that
would create a chord in the body of the house. As a result $z$ is universal to
$C$, which again leads to a contradiction to the fact that $H$ is an induced
house because of the edge $v_{1}z$.

### Proof of Lemma 6

###### Proof

As we have stated before $\text{HHI}_{4}^{2}$-free graphs are in particular
HHD-free. Since HHD-free graphs are closed under edge contraction, no hole or
house occurs after contracting any edge of an $\text{HHI}_{4}^{2}$-free graph.

Let $C=\\{v_{1},v_{2},v_{3},v_{4}\\}$ be an induced $C_{4}$ in $G$ and
consider contracting the edge $v_{1}v_{2}$. Let $G^{\prime}$ be the graph
resulting from this contraction, and let $v_{12}$ be the newly added vertex.

We first show that contracting $v_{1}v_{2}$ does not create any new $C_{4}$.
Assume for a contradiction that $G^{\prime}$ contains a new induced $C_{4}$,
$C^{\prime}=\\{v_{12},u_{1},u_{2},u_{3}\\}$.

  * •

$v_{3}\not\in C^{\prime}$

Let $u_{1},u_{2}$ be the neighbors of $v_{12}$ on $C^{\prime}$. Since
$C^{\prime}$ is new we have that $u_{1}v_{1},u_{2}v_{2}\in E(G)$ and
$u_{1}v_{2},u_{2}v_{1}\not\in E(G)$. In order for
$u_{3},u_{2},v_{2},v_{1},u_{1}$ to not induce a hole in $G$, at least one of
$u_{3}v_{1},u_{3}v_{2},u_{1}u_{2}$ has to also exists as edges in $G$. This
however would create a chord in $C^{\prime}$ which contradicts our assumption
that $C^{\prime}$ is an induced $C_{4}$ in $G^{\prime}$.

  * •

$v_{3}\in C^{\prime}$

In order for $v_{12}v_{3}$ not to be a chord in $C^{\prime}$, this edge
participates in the induced $C_{4}$, and also $u_{1},u_{3}\neq v_{2},v_{4}$
(assuming $v_{3}=u_{2}$ and that $u_{3}v_{3},u_{1}v_{12}\in E(G^{\prime})$).
Since $C^{\prime}$ is new and $v_{2}v_{3}\in E(G)$ we conclude that
$v_{1}u_{1}\in E(G)$ and $v_{2}u_{1}\not\in E(G)$. Notice now that in order
for $v_{1},u_{1},v_{2},v_{3},u_{3}$ not to induce a hole in $G$, $u_{3}$
should be adjacent in $G$ to either $v_{1}$ or $v_{2}$. This however would
create a chord on $C^{\prime}$ in $G^{\prime}$ which leads to a contradiction.

Now it remains to show that contracting $v_{1}v_{2}$ does not create two
induced $C_{4}$ that share more than one vertex. Assume now for a
contradiction that $G^{\prime}$ contains two $C_{4}$
$Z=\\{z_{1},z_{2},z_{3},z_{4}\\}$, $W=\\{w_{1},w_{2},w_{3},w_{4}\\}$ that
share more than one vertex.

First, assume that $Z$ and $W$ share an edge, thus let $z_{1}=w_{1}$ and
$z_{2}=w_{2}$ be two of the common vertices of $Z$ and $W$. We can directly
assume that $z_{1}=v_{12}$, and $z_{3},z_{4}\notin W$ and $w_{3},w_{4}\notin
Z$, since previously any pair of $C_{4}$ shared at most one vertex. By Lemma
5, contracting $v_{1}v_{2}$ did not create any new induced $C_{4}$, thus $Z$
and $W$ with the vertex $v_{12}$ replaced by either $v_{1}$ or $v_{2}$ were
already induced $C_{4}$ in $G$, so assume that $\\{v_{1},w_{2},w_{3},w_{4}\\}$
induces a $C_{4}$ in $G$.

Since $G$ was $\text{HHI}_{4}^{2}$-free it follows that $v_{1}$ is not
adjacent to $z_{4}$ (otherwise $\\{v_{1},w_{2},w_{3},w_{4}\\}$ and
$\\{v_{1},z_{2},z_{3},z_{4}\\}$ are two induced $C_{4}$ sharing more than one
vertex), thus $\\{v_{2},z_{2},z_{3},z_{4}\\}$ also induces a $C_{4}$ in $G$.

Then, however in order for $v_{1},v_{2},z_{2},w_{3},w_{4}$ not to induce a
house in $G$ either $w_{3}$ or $w_{4}$ is adjacent to $v_{2}$, which would
create a chord in $W$ after the contraction of $v_{1}v_{2}$ that leads to a
contradiction.

It remains to consider the case that $Z$ and $W$ share two non-adjacent
vertices, i.e. $w_{1}=z_{1}=v_{12}$ and $w_{3}=z_{3}$ are the two common
vertices. Similarly to the previous case, we can use Lemma 5 to assume that
$\\{v_{1},w_{2},w_{3},w_{4}\\}$ and $\\{v_{2},z_{2},z_{3},z_{4}\\}$ are
induced $C_{4}$ in $G$. Since $v_{1},v_{2},z_{2},z_{3}$ does not create an
induced house or hole together with $w_{2}$ or $w_{4}$, it follows that either
$v_{1}$ is adjacent to $z_{3}$, which would create a chord for $Z$ in
$G^{\prime}$, or $w_{2}$ and $w_{4}$ are adjacent to $v_{1}$ or $z_{2}$. In
the latter case, $w_{2}$ and $w_{4}$ are adjacent to more than one vertex of
the induced $C_{4}$ $Z$, which means they are both universal to $Z$ and have
to form a clique by Lemma 3. Then however $w_{2}w_{4}$ is a chord for $W$ in
$G^{\prime}$.

### Proof of Lemma 8

###### Proof

Assume for a contradiction that $G^{\prime}$ is only $k-1$-connected, thus
there is a separator of size $k-1$ that disconnects two distinct vertices $u$
and $w$ in $G^{\prime}$.

Since the connectivity between $u$ and $w$ dropped after contracting
$v_{1}v_{2}$, in $G$ there are two internally vertex disjoint paths $P_{1}$
and $P_{2}$ that connect $u$ and $w$ such that $v_{1}\in P_{1}$ and $v_{2}\in
P_{2}$. We can further assume that $P_{1}$ and $P_{2}$ are two such paths of
minimal length, respectively. Denote also by $u_{1}$ and by $w_{1}$ the
neighbors of $v_{1}$ on $P_{1}$ which are closer to $u$ and $w$, respectively.
(See the right illustration in Figure 2 for an example of these namings,
keeping in mind that it could be that $u_{1}=u_{2}=u$ and/or $w_{1}=w_{2}=w$.)
Similarly, denote by $u_{2}$ and $w_{2}$ these neighbors of $v_{2}$ on
$P_{2}$.

In order for $v_{1}$, $v_{2}$ and $u$ not to be part of an induced hole (given
that $u_{1}$ and $u_{2}$ are not $u$) either $u_{1}u_{2}\in E(G)$ or
$u_{1}v_{2}\in E(G)$ or $u_{2}v_{1}\in E(G)$. The first case, however, if no
other edges existed, would create a domino while the other cases form a house.
Hence at least one of the edges $u_{1}v_{3}$, $u_{1}v_{4}$, $u_{2}v_{3}$,
$u_{2}v_{4}$ exists. Similarly, assuming that neither $w_{1}$ nor $w_{2}$ is
equal to $w$, since our graph is $\text{HHI}_{4}^{2}$-free, also one of
$w_{1}v_{3}$, $w_{1}v_{4}$, $w_{2}v_{3}$, $w_{2}v_{4}$ exists. We show now
that by using the remaining vertices of $C$ we can recreate the two vertex
disjoint paths that previously existed in $G$.

  1. 1.

$u_{1}v_{3}\in E(G)$

    1. (a)

$w_{1}v_{3}\in E(G)$: Notice that the two $u-w$ vertex disjoint paths are
preserved in $G^{\prime}$, specifically
$P_{1}^{\prime}=P_{1}^{[u,u_{1}]}v_{3}P_{1}^{[w_{1},w]}$ and
$P_{2}^{\prime}=P_{2}$ (where in $P_{2}$ we have instead of $v_{2}$ the newly
created vertex $v_{12}$).

    2. (b)

$w_{1}v_{4}\in E(G)$:
$P_{1}^{\prime}=P_{1}^{[u,u_{1}]}v_{3}v_{4}P_{1}^{[w_{1},w]}$,
$P_{2}^{\prime}=P_{2}$

    3. (c)

$w_{2}v_{3}\in E(G)$:
$P_{1}^{\prime}=P_{1}^{[u,u_{1}]}v_{3}w_{2}P_{2}^{[w_{2},w]}$,
$P_{2}^{\prime}=P_{2}^{[u,v_{12}]}P_{1}^{[v_{12},w]}$

    4. (d)

$w_{2}v_{4}\in E(G)$:
$P_{1}^{\prime}=P_{1}^{[u,u_{1}]}v_{3}v_{4}w_{2}P_{2}^{[w_{2},w]}$,
$P_{2}^{\prime}=P_{2}^{[u,v_{12}]}P_{1}^{[v_{12},w]}$

  2. 2.

$u_{1}v_{4}\in E(G)$

    1. (a)

$w_{1}v_{3}\in E(G)$:
$P_{1}^{\prime}=P_{1}^{[u,u_{1}]}v_{4}v_{3}P_{1}^{[w_{1},w]}$ and
$P_{2}^{\prime}=P_{2}$

    2. (b)

$w_{1}v_{4}\in E(G)$:
$P_{1}^{\prime}=P_{1}^{[u,u_{1}]}v_{4}P_{1}^{[w_{1},w]}$,
$P_{2}^{\prime}=P_{2}$

    3. (c)

$w_{2}v_{3}\in E(G)$:
$P_{1}^{\prime}=P_{1}^{[u,u_{1}]}v_{4}v_{3}w_{2}P_{2}^{[w_{2},w]}$,
$P_{2}^{\prime}=P_{2}^{[u,v_{12}]}P_{1}^{[v_{12},w]}$

    4. (d)

$w_{2}v_{4}\in E(G)$:
$P_{1}^{\prime}=P_{1}^{[u,u_{1}]}v_{4}w_{2}P_{2}^{[w_{2},w]}$,
$P_{2}^{\prime}=P_{2}^{[u,v_{12}]}P_{1}^{[v_{12},w]}$

  3. 3.

The remaining cases are symmetrical to the ones written above.

Similar arguments can be used to find such paths if $u_{1}=u_{2}=u$ or
$w_{1}=w_{2}=w$.

Due to Lemma 7 we know that $v_{3}$ and $v_{4}$ are free to be used for the
creation of the above paths since they can not be part of the same minimal
separator as $v_{1}$ and $v_{2}$.

### Proof of Lemma 10

###### Proof

Observe that by Lemma 5 we can safely add the edges in line 1, in the sense
that we still have an $\text{HHI}_{4}^{2}$-free graph, and that we do not
create new $C_{4}$ that our terminal vertices might participate in. Thus, the
graph we consider moving forward in the algorithm is $\text{HHI}_{4}^{2}$-free
and the induced $C_{4}$ considered in line 2 do not contain two non-adjacent
terminals.

Consider now the tree $T$ constructed by $\mathcal{C}$ in Lemma 9. We proceed
in arguing that the contraction order described in line 6 of Algorithm 3 is
indeed the desired one.

Let $v$ be a leaf of $T$. If $v\in S$ (representing a single vertex in $G$)
then delete $v$ and update $T$ accordingly. If $v\in B$ then consider the
induced $C_{4}$ corresponding to $v$. The fact that $v$ is a leaf in $T$ means
that there are at least three vertices in the corresponding $C_{4}$ that are
not included in any other induced $C_{4}$ of $G$. These three vertices
$v_{1},v_{2},v_{3}$ are candidates for line 6 of Algorithm 3, and after
removal of them and the $C_{4}$ corresponding to $v$ in $G^{\prime}$ in line
8, removing $v$ from $T$ yields a tree for which this procedure can be
repeated.

Since we remove all vertices involved in a contracted edge from $G^{\prime}$
as soon as their first adjacent edge is chosen, we can ensure that no vertex
is contracted twice. Thus when we create $G^{\prime\prime}$ all vertices
indeed have maximum weight at most 2.