11institutetext: Institute of Engineering Sciences, Universidad de O’Higgins,
Rancagua, Chile, 11email<EMAIL_ADDRESS>22institutetext: Eindhoven
University of Technology, Eindhoven, Netherlands, 22email: {d.v.p.hyatt-
<EMAIL_ADDRESS>33institutetext: Bocconi University, Milan,
Italy, 33email<EMAIL_ADDRESS>
# Node Connectivity Augmentation of Highly Connected Graphs

Waldo Galvez 11 Dylan Hyatt-Denesik 22 Afrouz Jabal Ameli 22 Laura Sanità 33

###### Abstract

Node-connectivity augmentation is a fundamental network design problem. We are
given a $k$-node connected graph $G$ together with an additional set of links,
and the goal is to add a cheap subset of links to $G$ to make it $(k+1)$-node
connected.

In this work, we characterize completely the computational complexity status
of the problem, by showing hardness for all values of $k$ which were not
addressed previously in the literature.

We then focus on $k$-node connectivity augmentation for $k=n-4$, which
corresponds to the highest value of $k$ for which the problem is NP-hard. We
improve over the previously best known approximation bounds for this problem,
by developing a $\frac{3}{2}$-approximation algorithm for the weighted
setting, and a $\frac{4}{3}$-approximation algorithm for the unweighted
setting.

##  1 Introduction

Connectivity augmentation is among the most fundamental problems in network
design. Here we are given a $k$-(edge- or node-)connected graph and a set of
additional edges (called _links_). The goal is to select the cheapest subset
of links to add to the graph, in order to increase its connectivity to $k+1$.

When dealing with _edge-connectivity_ , the problem is quite well understood:
$k$-edge-connectivity augmentation is APX-hard for any $k\geq 1$, and in fact,
for any given $k$ the problem can be reduced to the case $k=2$ (see [12]). In
the past years, several constant-factor approximation results have been
developed in the literature for edge-connectivity augmentation [1, 5, 9, 10,
13, 16, 20, 22, 24, 25], culminating with the recent breakthroughs in [8, 26].

When dealing with _node-connectivity_ , the problem is instead much less
understood, both from a computational complexity and an approximation point of
view. From a complexity perspective, there is no known reduction that allows
us to focus on a particular value of $k$ (like e.g. $k=2$ for the edge-
connectivity case). The problem is known to be APX-hard for $k\geq 1,k\leq
n-n^{c}$ (with $n$ being the number of nodes of the graph and $c$ being any
fixed constant) [18]111Although not stated explicitly in the reference, the
reduction requires that $k\leq n-n^{c}$ in order to have polynomial running
time. A more detailed discussion in Appendix 0.A even if all the link weights
are $1$ (known as the _unweighted setting_), but for high values of $k$ the
complexity is not completely settled. Bérczi et al. [6] observe that the
problem is polynomial-time solvable for $k=n-2$ and $k=n-3$, and it is NP-hard
for $k=n-4$ when links allow general weights (known as the _weighted
setting_). Still, the complexity status is open for $k=n-4$ in the unweighted
setting, as well as for any value of $k$ somewhat between $n-4$ and the
previously mentioned bound of $n-n^{c}$.

Also from an approximation perspective, the results are fewer compared to the
edge-connectivity case, and mostly concentrate on small values of $k$. For
$k=1$, Frederickson and JáJá [14] give a 2-approximation. Recently, this bound
has been improved in the unweighted case [2, 17, 20]. A $2$-approximation is
also known for $k=2$ [3], which can be improved in the unweighted setting when
the input graph is a cycle [15]. For any fixed $k$, the weighted version of
the problem admits a $(4+\varepsilon)$-approximation if $n$ is large enough
[21] (see also [11]). For arbitrary values of $k$, it is still open whether a
constant approximation is achievable or not, and the best known factor is
$O\left(\log\left(\min\left\\{\frac{n}{n-k},n-k\right\\}\right)\right)$ [19].
Note that this implies a $O(1)$-approximation for most values of $k$, except
for “intermediate” ones like, e.g., $n-n^{c}$ for $0<c<1$.

###  1.1 Our results and techniques

As a first result, we completely settle the computational complexity status of
the problem. In Section 5, we prove that $(n-d)$-node connectivity
augmentation is NP-hard (in fact, APX-hard) for $d\geq 4,d=O(n^{c})$, with $c$
being any positive constant, even in the unweighted setting. Our result
complements the result of Kortsarz et al. [18], and hence completes the
picture regarding the complexity status of this classical and fundamental
problem.

We prove this result by first showing APX-hardness for the case $d=4$ (i.e.
$(n-4)$-node-connectivity augmentation), reducing from a variant of SAT
denoted as 3-SAT-4, whose optimization version is known to be APX-hard [4]. We
then employ an approximation preserving reduction from $(n-d)$-node
connectivity augmentation to $(n-(d+1))$-node connectivity augmentation, that
holds whenever $d=O(n^{c})$. We remark here that our reduction is different
from the hardness construction of [6], as their result heavily relies on the
fact that the links have different weights.

We then focus on the approximability of the $k$-node-connectivity augmentation
problem for $k=n-4$ which, as we just discussed, corresponds to the highest
value of $k$ for which the problem is NP-hard. The best approximation factor
known for this problem is a $2$-approximation (which follows e.g. from [19]).
In Section 3, we improve over this result by giving a
$\frac{3}{2}$-approximation for the problem. In Section 4, we improve further
the approximability to $\frac{4}{3}$ in the unweighted setting.

Our approximation algorithms are combinatorial, and rely on the following
ingredients. First, we reformulate the problem as a particular _covering_
problem in the complement of the graph, as done also in [6] (see also [7]). In
particular, one easily observes that an $(n-d)$-node-connected graph $G$ is
_not_ $(n-(d-1))$-node-connected if and only if the complement of $G$ has some
complete bipartite graphs (which we call _obstructions_) as edge-induced
subgraphs. Therefore, the augmentation problem can be reformulated as the
problem of selecting links in the complement of $G$ in order to cover all such
obstructions (see Definition 1). For $d=4$, this covering problem becomes a
generalization of the _edge cover_ problem, in which one wants to select
links, but in addition to covering all vertices, one also wants to cover all
cycles of length $4$ in the graph. For the weighted version of this problem,
we first compute a suitable partial (infeasible) solution that has at most
half of the cost of the optimal one, and then show that we can solve the
remaining instance in polynomial time via a reduction to edge cover. For the
unweighted version, the approach is somewhat opposite: our algorithm starts by
computing a particular edge cover of the instance, and then adjusts the
solution to cover the additional obstructions represented by the 4-cycles,
while carefully bounding the cost increase.

As our results show, better constant approximation factors can be obtained
(not surprisingly) using ad-hoc techniques for very large values of $k$. We
believe that studying the problem for such values can be instrumental to the
development of useful tools and techniques, which seems to be needed to
understand the approximability of the general node-connectivity augmentation
problem.

###  1.2 Organization of the paper

In Section 2, we reformulate the $(n-d)$-node-connectivity augmentation
problem as a _covering_ problem that we refer to as $d$-Obstruction Covering,
and further investigate the properties of $d$-Obstruction Covering instances
for the case $d=4$. In Section 3, we provide our $3/2$-approximation algorithm
for the $(n-4)$-Node-Connectivity Augmentation problem, and then in Section 4
we provide an improved $4/3$-approximation for the unweighted version of the
problem. In Section 5 we prove that the $(n-d)$-Node-Connectivity Augmentation
problem is APX-hard for any $d\geq 4$, with $d=O(n^{c})$ for any fixed
constant $c$. Due to space constraints, several proofs are deferred to the
Appendix.

##  2 From connectivity augmentation to obstruction covering

As a first step, we reformulate our problem as a covering problem, called the
$d$-Obstruction Covering problem, which we define next. In the following, we
denote by $K_{i,j}$ the complete bipartite graph that has $i$ nodes in one
bipartition and $j$ nodes in the other bipartition.

######  Definition 1 ($d$-Obstruction Covering)

We are given a value $d\leq n$, a graph $G=(V,E)$ of $n$ nodes that has no
$K_{i,j}$ edge-induced subgraph for any $i,j:i+j>d$, and a subset of links
$L\subseteq E$ with associated costs $c(\ell)\geq 0,\forall\ell\in L$. We want
to compute a minimum-cost subset of links $F\subseteq L$ such that every
$K_{i,j}$ edge-induced subgraph of $G$ with $i+j=d$ contains a link of $F$.

For a given $d$-Obstruction Covering instance, we call $K_{i,j}$ a _forbidden_
subgraph if $i+j>d$, and an _obstruction_ if $i+j=d$. An obstruction $K_{i,j}$
is _covered_ by link $\ell\in L$ if $\ell$ is an edge of $K_{i,j}$.

As already observed in [6, 7], the $(n-d)$-node-connectivity augmentation
problem is equivalent to solving $d$-Obstruction Covering in the complement of
the original graph, hence being an equivalent reformulation. See Appendix 0.D
for a detailed proof.

###### Theorem 2.1

There is an approximation-preserving reduction from the $(n-d$)-node-
connectivity augmentation problem to the $d$-Obstruction Covering problem.

Using Theorem 2.1, we can focus on showing a $3/2$-approximation algorithm for
the $4$-Obstruction Covering problem. We denote by $(G=(V,E),d,L,c)$ a
$d$-Obstruction Covering instance. If $c(\ell)=1$ for all $\ell\in L$, then we
call this instance _unweighted_ and refer to it as $(G,d,L)$ instead. Note
that an unweighted instance $(G,d,L)$ is equivalent to instance $(G,d,E,c)$
where $c(e)=1$ for $e\in L$, and $c(e)=\infty$ otherwise. We refer to
$K_{2,2}$ edge-induced subgraphs of $G$ as _squares_ , and to nodes that do
not belong to any square as _lonely nodes_. For any subgraph $C$ of $G$, we
denote by $V(C)$ the set of its vertices, and by $E(C)$ the corresponding set
of edges.

###### Definition 2

A graph is called a ladder if it has maximum degree $3$, and one can label its
nodes as $v_{1},v_{2},\ldots,v_{r},u_{1},u_{2},\ldots,u_{r}$ ($r\geq 2$) such
that, for every $1\leq i<r$, the subgraph induced by the nodes $u_{i},$
$v_{i},$ $v_{i+1},$ and $u_{i+1}$ is a square with edges
$u_{i}v_{i},v_{i}v_{i+1},v_{i+1}u_{i+1},u_{i+1}u_{i}$. We refer to the number
of squares in this sequence ($r-1$) as the length of the ladder. A graph is
called a hexagon if it has a spanning edge-induced subgraph that is isomorphic
to the graph in Figure 1.(b).

(a)
$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$
(b) $v_{1}$$v_{2}$$v_{0}$$v_{6}$$v_{5}$$v_{4}$$v_{3}$

Figure 1: (a) An example of a ladder $C$, with $r=6$. (b) An example of a
hexagon.

For a given ladder, a labelling of the nodes according to the above definition
is called a _consistent_ labelling.

Let $C$ be a hexagon or a ladder, that is an edge-induced subgraph of a given
graph $G=(V,E)$. We will let $\delta(V(C))$ denote the set of edges between
$V(C)$ and $V\setminus V(C)$, and to simplify notation, we will let
$\delta(C)\coloneqq\delta(V(C))$. We say that the degree of $C$ is
$|\delta(C)|$ (i.e., the number of edges between $V(C)$ and $V\setminus
V(C)$). We say that a node $v$ is a _corner_ of $C$, if $v$ is incident to an
edge in $\delta(C)$. Observe that if $G$ is a graph of a $4$-Obstruction
Covering instance, then a corner $v$ has degree $3$ because $K_{1,4}$ is a
forbidden subgraph. In this case, note that a hexagon has at most three
corners and a ladder has at most four corners. From now on, whenever we use
the word subgraph, we refer to edge-induced subgraph (unless specified
otherwise).

Let $(G=(V,E),4,L,c)$ be a $4$-Obstruction Covering instance. The following
theorem is a useful structural result, which states that we can decompose $G$
into node-disjoint hexagons, lonely nodes, and ladders of maximal length. Its
proof can be found in Appendix 0.E.

###### Theorem 2.2

We can find in polynomial time node-disjoint subgraphs $R,G_{1},G_{2},$
$\ldots,G_{k}$ of $G$ such that:

  * •

Each $G_{i}$ is a hexagon or a ladder of maximal length. If $G_{i}$ is a
ladder, then we also have a consistent labelling.

  * •

$V(R)=V\backslash\left(V(G_{1})\cup V(G_{2})\ldots\cup V(G_{k})\right)$ is a
set of lonely nodes.

  * •

For every square subgraph $S$ of $G$, there exists an index $i$ such that
$V(S)\subseteq V(G_{i})$.

The decomposition provided by Theorem 2.2 is useful for our purposes, because
it is possible to develop a Dynamic Programming based algorithm that solves
the $4$-Obstruction Covering problem when restricted to a ladder or a hexagon
(in fact, something slightly more general than that). The following theorem,
whose proof is deferred to Appendix 0.B, provides a precise statement of which
instances can be solved.

######  Theorem 2.3 ()

Let $C=(V,E)$ be a ladder with a given consistent labelling or a hexagon.
Given edge weights $w:E\rightarrow\mathbb{R}$ and node covering requirements
$h:V\rightarrow\\{0,1\\}$, we can find in polynomial time a minimum cost set
$F\subseteq E$ such that, for every square $S$ in $C$, $F\cap
E[S]\neq\emptyset$, and for every $v\in V$ with $h(v)=1$, at least one edge of
$F$ is incident to $v$.

In particular, we can use Theorem 2.3 to solve each ladder or hexagon of
degree zero optimally.

###### Corollary 1

Consider a $4$-Obstruction Covering instance $(G,4,L,c)$, and a given
decomposition of $G$ into lonely nodes $R$, and disjoint hexagon or ladder
subgraphs $G_{1},\dots,G_{k}$ (as in Theorem 2.2). For any $G_{i}$ of degree
$0$, one can find in polynomial time an optimal covering of every obstruction
in $G_{i}$.

Thanks to Corollary 1, we can assume that $G$ contains no hexagons or ladders
of degree $0$. Moreover, we assume that $G$ is connected, as we can apply our
algorithm to each connected component individually.

##  3  A $\frac{3}{2}$-approximation for Weighted $(n-4)$-node connectivity
augmentation

In this section, we will prove the following theorem.

###### Theorem 3.1

There is a polynomial time $3/2$-approximation algorithm for the $(n-4)$-Node-
Connectivity Augmentation problem.

We first give a high-level description of the algorithm. By Theorem 2.1 we
focus on $4$-Obstruction Covering instances. For a $4$-Obstruction Covering
instance $(G,4,L,c)$, we consider a fixed optimal solution $opt$, with cost
$c(opt)$. We apply Theorem 2.2 to $G$ to find node-disjoint hexagons and
ladders $G_{1},\dots,G_{k}$, and lonely nodes $R$. Our algorithm first finds a
partial solution $F_{1}$, with cost $c(F_{1})\leq\frac{1}{2}c(opt)$, that
covers at least the corners of hexagons and ladders $G_{1},\dots,G_{k}$ whose
degree is at least three. We then remove $F_{1}$ from $E$, leaving an instance
with only ladders and hexagons of degree $1$ or $2$. We then compute a special
edge cover $F_{2}$, to take care of all the remaining obstructions, with cost
$c(F_{2})\leq c(opt)$. Putting $F_{1}$ and $F_{2}$ together then defines a
feasible solution of cost at most $\frac{3}{2}c(opt)$. We now give more
details about the computation of these partial solutions.

To compute the partial solution $F_{1}$, we make use of the following useful
Corollary of Petersen’s Theorem[23]. It is proved in Appendix 0.F.1.

###### Corollary 2

Let $G$ be a $4$-regular graph. Then, we can decompose $G$ into two
$2$-regular spanning subgraphs in polynomial time.

We also make use of a slight generalization of the Edge Cover problem, denoted
as Minimum $N$-Edge Cover problem. Given a graph $G=(V,E)$, a subset
$N\subseteq V$, and an edge cost function $c:E\rightarrow\mathbb{R}$, we want
to find a minimum cost subset $E^{\prime}\subseteq E$, such that the endpoints
of $E^{\prime}$ contain $N$. The following lemma follows easily from the fact
that the Edge Cover problem is polynomial-time solvable, but for the sake of
completeness its proof can be found in Appendix 0.C.

######  Lemma 1 ()

The Minimum $N$-Edge Cover problem can be solved efficiently.

We now consider node-disjoint hexagons and ladders $G_{1},$ $\dots,G_{k}$, and
lonely nodes $R$ obtained from Theorem 2.2. Denote the corners of ladders and
hexagons of degree at least 3 by $N$, that is, each node of a ladder or
hexagon that is adjacent to a node outside the ladder or hexagon containing it
is in $N$. By Lemma 1, we compute a minimum cost $N$-edge cover, that we
denote by $E_{C}$. As nodes of $N$ (together with their neighbours) induce a
subset of the obstructions that must be covered (they are nodes of degree $3$,
hence each with its neighbours induces $K_{1,3}$), it is clear that
$c(E_{C})\leq c(opt)$. We then construct a 4-regular graph $G^{\prime}$ using
$E_{C}$, and apply Corollary 2 to find a subset of edges of cost
$\leq\frac{1}{2}c(opt)$.

We begin with $G^{\prime}=(V^{\prime}=\emptyset,E^{\prime}=\emptyset)$, and
costs $c^{\prime}:E^{\prime}\rightarrow\mathbb{R}$. For every $G_{i}$,
$i=1,\dots,k$ of degree at least $3$ in $G$, add corresponding node $g_{i}$ to
$V^{\prime}$.

We next add edges to $E^{\prime}$: consider the links of $E_{C}$ in an
arbitrary but fixed order, say $\ell_{1},...,\ell_{|E_{C}|}$. For any endpoint
$u$ of $\ell_{i}$ that is not incident to any $\ell_{j}$ for $j<i$, we say
that $u$ is _satisfied_ by $\ell_{i}$. Note, each corner is satisfied by
exactly one link $\ell_{i}$. For link $\ell_{i}=uv\in E_{C}$, suppose
$\ell_{i}$ has two endpoints in $N$ in (possibly equal) subgraphs $G_{a}$ and
$G_{b}$, $a,b\in\\{1,\dots,k\\}$. If both $u$ and $v$ are satisfied by
$\ell_{i}$, then we add an edge $g_{a}g_{b}$, with label $\ell_{i}$, to
$E^{\prime}$ with cost $c^{\prime}(g_{a}g_{b})=c(\ell_{i})$ (adding a loop in
$G^{\prime}$ with cost $c(\ell_{i})$ if $G_{a}=G_{b}$). If exactly one
endpoint $u\in\ell_{i}$ is not satisfied by $\ell_{i}$, say $u\in G_{a}$, then
we add a dummy node $\bar{u}$ to $V^{\prime}$ and add edge $\bar{u}g_{b}$,
with label $\ell_{i}$, to $E^{\prime}$ with cost
$c^{\prime}(\bar{u}g_{b})=c(\ell_{i})$. If both endpoints of $\ell_{i}$ are
satisfied already, then we remove $\ell_{i}$ from $E_{C}$ for no loss of
feasibility and no increase in cost as the edge costs are non-negative.

Now consider a link $\ell_{i}=uv\in E_{C}$ that has exactly one endpoint in
$N\cap G_{a}$ for some $a\in\\{1,\dots,k\\}$, say $v\in G_{a}$. If $v$ is
satisfied by $\ell_{i}$, we add a dummy node $\bar{u}$ to $V^{\prime}$ and add
an edge $\bar{u}g_{a}$, with label $\ell_{i}$, and cost
$c^{\prime}(\bar{u}g_{a})=c(\ell_{i})$ to $E^{\prime}$. If this $v$ is already
satisfied, then we can simply remove $\ell_{i}$ from $E_{C}$. Notice that, if
$G^{\prime}$ is not $4$-regular, then we can add a polynomial number of dummy
nodes to $V^{\prime}$ and zero cost dummy edges to $E^{\prime}$ such that
$G^{\prime}$ becomes $4$-regular (see Appendix 12 for more details).

By applying Corollary 2, we find two edge disjoint $2$-regular spanning
subgraphs $H_{1}$ and $H_{2}$ such that $H_{1}\cup H_{2}=G^{\prime}$ and
$\min\\{c(E(H_{1})),c(E(H_{2}))\\}\leq\frac{1}{2}c(opt)$. The minimum cost set
$H\in\\{H_{1},H_{2}\\}$ induces our choice of $F_{1}\subseteq L$.

In order to compute the second part of the solution, denoted $F_{2}$, we use
$F_{1}$ to find a $4$-Obstruction Covering instance
$(G^{\prime\prime}=(V^{\prime\prime},E^{\prime\prime}),4,L^{\prime\prime},c^{\prime\prime})$
with cost $c^{\prime\prime}:E^{\prime\prime}\rightarrow\mathbb{R}$, such that
the subgraphs $G_{1}^{\prime},\dots,G_{k}^{\prime}$ found by Theorem 2.2 have
degree at most $2$. We begin with $G^{\prime\prime}=G$. For every $f\in
F_{1}$, if $f\in\delta(G_{i})$, for some $i\in\\{1,\dots,k\\}$, we remove $f$
from $E^{\prime\prime}$. If $f\in E[G_{i}]$ for some $i\in\\{1,\dots,k\\}$,
then $f$ satisfies at least one node in $N\cap V(G_{i})$. For such a link
$f\in E[G_{i}]$ with endpoint $u$, since $u\in N\cap V(G_{i})$, $u$ has degree
$3$ and must be incident to an edge $uv\in\delta(G_{i})$. We add a dummy node
$\bar{u}$ to $G^{\prime\prime}$ and remove $uv$ from $G^{\prime\prime}$ and
replace it with $\bar{u}v$, giving it label $uv$, with cost
$c^{\prime\prime}(\bar{u}v)=c^{\prime}(uv)$. Finally, we set
$c^{\prime\prime}(f)=0$. We prove the following lemma in Appendix 0.F.3

###### Lemma 2

$(G^{\prime\prime},4,L^{\prime\prime},c^{\prime\prime})$ is a $4$-Obstruction
Covering instance such that:

  1. 1.

The subgraphs $G_{1}^{\prime},\dots,G_{k}^{\prime}$ found by Theorem 2.2 each
have degree $1$ or $2$;

  2. 2.

The cost of the optimal solution to
$(G^{\prime\prime},4,L^{\prime\prime},c^{\prime\prime})$ is at most $c(opt)$;
and

  3. 3.

Given a solution $F$ to
$(G^{\prime\prime},4,L^{\prime\prime},c^{\prime\prime})$ of cost
$c^{\prime\prime}(F)$, we can find in polynomial time a solution to
$(G,4,L,c)$ of cost $c^{\prime\prime}(F)+c(F_{1})$.

The last ingredient is the following lemma, proven in Appendix 0.F.4, which
essentially shows that the instance
$(G^{\prime\prime},4,L^{\prime\prime},c^{\prime\prime})$ is solvable in
polynomial time.

###### Lemma 3

Given a $4$-Obstruction Covering instance $(G,4,L,c)$, if the subgraphs
$G_{1},\dots,G_{k}$ found as in Theorem 2.2 have degree $1$ or $2$, then we
can find an optimal solution in polynomial time.

We now conclude putting everything together to prove Theorem 3.1.

######  Proof (Proof of Theorem 3.1)

Given an $(n-4)$-Node Connectivity Augmentation instance, we apply Theorem 2.1
to obtain an instance $(G,4,L,c)$ of $4$-Obstruction Covering. By Theorem 2.2,
we obtain node-disjoint ladders and hexagons $G_{1},\ldots,$ $G_{k}$, and
lonely nodes $R$. Using the discussion above, we can compute in polynomial
time a partial solution $F_{1}$ such that $c(F_{1})\leq\frac{1}{2}c(opt)$, to
cover a subset of the obstructions (namely, corners of ladders and hexagons of
degree at least three in this decomposition). We then construct a new instance
$(G^{\prime\prime},4,L^{\prime\prime},c^{\prime\prime})$, in which the node-
disjoint ladders and hexagons found by Theorem 2.2 have degree at most two. By
applying Lemma 3 to $(G^{\prime\prime},4,L^{\prime\prime},c^{\prime\prime})$,
we can find an optimal solution $F_{2}$ for this instance. Then, by applying
Lemma 2, we can find a solution of cost
$c(F_{1})+c(F_{2})\leq\frac{3}{2}c(opt)$ for $(G,4,L,c)$.

##  4  A $\frac{4}{3}$-approximation for unweighted $(n-4)$-node-connectivity
augmentation

In this section, we will prove the following theorem.

###### Theorem 4.1

There is a polynomial time $\frac{4}{3}$-approximation algorithm for the
unweighted $(n-4)$-Node Connectivity Augmentation problem.

We first consider an unweighted $4$-Obstruction Covering instance $(G,4,L)$,
and apply Theorem 2.2 to decompose $G$ into lonely nodes $R$, and node-
disjoint hexagons, ladders $G_{1},\dots,G_{k}$. We fix an optimal solution,
denoted $opt$.

Our algorithm will apply some preprocessing operations, and then find a
minimum size subset of edges $EC_{3}\subseteq L$, that covers every degree $3$
node in $G$ and the obstructions of every $G_{i}\in\\{G_{1},\dots,G_{k}\\}$ of
degree 1 and 2. As the obstructions covered by $EC_{3}$ are a subset of all
obstructions, we can see $c(EC_{3})\leq c(opt)$. We then show that we can
modify this solution to get a solution $APX$ that covers the remaining
obstructions, and by a careful local charging argument we will show that
$c(APX)\leq\frac{4}{3}c(opt)$.

To simplify our arguments and allow us to focus on discussing the main
technical challenges of our approach, we will assume that the subgraphs
$G_{1},\dots,G_{k}$ given by Theorem 2.2 consist only of ladders of length
$1$. Indeed, it is possible to prove that, if we aim to get a
$4/3$-approximation for the general problem, we can restrict ourselves to this
special case (see Appendix 0.G.3).

_Preprocessing and Computing $EC_{3}$_. We call a link $\ell$ _necessary_ if
there is an obstruction $O$ such that $\ell$ is the only link that can cover
$O$. Observe that any feasible solution must contain all necessary links.
Therefore, we initially take these links as part of our solution and then
remove them from $E$ and $L$ and consider the remaining instance. Thus, we
assume without loss of generality that no link in $L$ is necessary.

The following lemma, similar in spirit to Lemma 3, allows us to compute
$EC_{3}$ in polynomial time (Proof found in Appendix 0.G.1).

###### Lemma 4

Given an unweighted $4$-Obstruction Covering instance $(G,4,L)$, let
$R,G_{1},\dots,G_{k}$ be the subgraphs found as in Theorem 2.2. We can find in
polynomial time a minimum cardinality subset of links that:

  1. 1.

covers every node of degree 3, and

  2. 2.

covers every square $S$ with $V(S)\subseteq V(G_{i})$, for some
$G_{i}\in\\{G_{1},\dots,G_{k}\\}$ that has degree 1 or 2.

_Fixing the solution_. Given a subset $H\subseteq\\{G_{1},\dots,G_{k}\\}$, we
denote by $G[H]$ the subgraph induced by $\cup_{G_{a}\in H}V(G_{a})$, and
denote by $E[H]$ the edges of $G[H]$. The following lemma shows that if every
$G_{i}\in\\{G_{1},\dots,G_{k}\\}$ has degree $3$ or $4$, then we can use
$EC_{3}$ to find a feasible solution $APX$ such that
$|APX|\leq\frac{4}{3}EC_{3}$.

###### Lemma 5

Consider an unweighted $4$-Obstruction Covering instance $(G,4,L)$, with
decomposition into subgraphs $R,G_{1},\dots,G_{k}$, found by Theorem 2.2, such
that every $G_{i}\in\\{G_{1},\dots,G_{k}\\}$ is a ladder of length 1 that has
degree $3$ or $4$. Consider a partial solution $EC_{3}\subseteq L$ that covers
every degree $3$ node, but does not (necessarily) cover the squares of
$G_{i}\in\\{G_{1},\dots,G_{k}\\}$.

We can find in polynomial time, a feasible solution $APX\subseteq L$, such
that $|APX|\leq\frac{4}{3}|EC_{3}|$.

######  Proof (Sketch of Proof)

We begin by defining notation. For a square $S$, we call a corner $u\in V(S)$
a _good_ node if there is another corner $v\in V(S)$ such that $uv\in L$, and
we say $u$ is a bad node otherwise (recall, we say a node of $V(S)$ is a
corner if it is incident to an edge in $\delta(S)$). Note that the nodes of
$V(S)$ that are not corners are neither good nor bad. Note that since no links
are necessary, all nodes of a degree 4 ladder are good nodes.

We find $APX$ by performing a sequence of steps. We begin with step 1 where we
set $APX_{1}=EC_{3}$, $Y_{1}=\emptyset$, and $\mathcal{H}_{1}$ equal to the
subset of $\\{G_{1},\dots,G_{k}\\}$ whose squares are covered by $APX_{1}$.
For each step $i$, $i\geq 2$, we define

  * •

$APX_{i}\subseteq L$ to be a partial solution;

  * •

$\mathcal{H}_{i}\subseteq\\{G_{1},\dots,G_{k}\\}$ to be the set of ladders
whose squares are covered by $APX_{i}$;

  * •

$Y_{i}$ to be the subset of edges $\subseteq
APX_{i}\cap\delta(G[\mathcal{H}_{i}])$ such that every $y\in Y_{i}$ has an
endpoint in $R$.

Our goal is to compute $APX_{i}$ at $i$-th step, $i\geq 2$, such that the
following holds:

  1. (1)

The obstructions covered by $APX_{i-1}$ are a strict subset of those covered
by $APX_{i}$;

  2. (2)

$|APX_{i}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|\leq\frac{4}{3}|EC_{3}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|$, and $APX_{i}\backslash(Y_{i}\cup
E[\mathcal{H}_{i}])=EC_{3}\backslash(Y_{i}\cup E[\mathcal{H}_{i}])$.

Note that since $APX_{i}$ covers the obstructions covered by $APX_{i-1}$, we
must have $\mathcal{H}_{i-1}\subseteq\mathcal{H}_{i}$. If in iteration $i$, we
have $\mathcal{H}_{i}=\\{G_{1},\dots,G_{k}\\}$, then we are done as $APX_{i}$
covers every obstruction. If
$\mathcal{H}_{i}\subsetneq\\{G_{1},\dots,G_{k}\\}$, then we will find some
$G_{s}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$, and using $G_{s}$,
we will find $APX_{i+1}$, $\mathcal{H}_{i+1}$, and $Y_{i+1}$.

We will consider three cases for $G_{s}$, for which we now provide a brief
description. First, if $G_{s}$ has two nodes that are adjacent to nodes in $R$
or in $\mathcal{H}_{i}$. Second, if a good node of $G_{s}$ is adjacent to a
good node of some $G_{t}\notin\mathcal{H}_{i}$. And finally, if neither of the
previous cases hold, then we show $G_{s}$ is degree 3 and that a good node of
$G_{s}$ must be adjacent to a bad node of some degree 3 ladder
$G_{t}\notin\mathcal{H}_{i}$. In all cases, we will be able to find at least
three links in $\delta(G_{s})$ (and possibly $\delta(G_{t})$), such that, by
adding links to cover $G_{s}$ (and possibly $G_{t}$), we can charge the
addition of these new links to the links in $\delta(G_{s})$ (and possibly
$\delta(G_{t})$) for a $\frac{4}{3}$ fractional increase. To account for space
limitations, we only show the details of case 1 here. All cases can be found
in Appendix 0.G.2.

Case 1: there exists
$G_{s}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$, such that $G_{s}$
has two nodes that are adjacent to either a node in $R$ or in
$\mathcal{H}_{i}$. Since $G_{s}$ is degree at least $3$, there are links
$\\{\ell,\ell_{1},\ell_{2}\\}\subseteq\delta(G_{s})\cap APX_{i}$. Without loss
of generality, let the links $\ell_{1}$ and $\ell_{2}$ be the ones incident to
nodes in $\mathcal{H}_{i}$ or in $R$.

Since no links are necessary, there is a link $e\in E(G_{s})$ that shares an
endpoint with $\ell$, and we start with $APX_{i+1}\leftarrow
APX_{i}\cup\\{e\\}$. Note that this ensures that $G_{s}$ is in
$\mathcal{H}_{i+1}$, and so $\mathcal{H}_{i}\subsetneq\mathcal{H}_{i+1}$.

If any of $\ell_{1}$, $\ell_{2}$ or $\ell$ are incident to a node in $R$, then
that link is in $Y_{i+1}$. Assume $\ell$ is incident to some ladder $G_{t}$.
If $G_{t}\in\mathcal{H}_{i}$, we are done this iteration. If not, we are going
to change $APX_{i+1}$ by swapping two edges. Since $\ell$ is not necessary,
there is link $f\in E(G_{t})$ sharing an endpoint with $\ell$. We replace
$\ell$ with $f$ in $APX_{i+1}$, and so also $G_{t}$ will be in $H_{i+1}$.
Since the endpoints of $\ell$ are covered in $APX_{i+1}$ by either $\ell$ or
$\\{e,f\\}$, the obstructions in $G_{s}$ are covered, and all other
obstructions of $APX_{i}$ are covered by $APX_{i+1}$, $(1)$ holds (see Figure
2).

(a) $G_{s}$$G_{t}$$\ell$$e$$f$$\ell_{1}$$\ell_{2}$ | (b) $G_{s}$$G_{t}$$\ell$$e$$f$$\ell_{1}$$\ell_{2}$
---|---
Figure 2: (a) Ladder $G_{s}$ adjacent to two lonely nodes and ladder $G_{t}$
by links $\\{\ell,\ell_{1},\ell_{2}\\}=\delta(G_{s})$. The solution $APX_{i}$
is shown as bold edges. The red edges are not links. (b)Ladder $G_{s}$
adjacent to two lonely nodes and ladder $G_{t}$ by links
$\\{\ell,\ell_{1},\ell_{2}\\}=\delta(G_{s})$. The solution $APX_{i+1}$ is
shown as bold edges. The addition of $\\{e,f\\}$ and the removal of $\ell$ is
charged to $\\{\ell,\ell_{1},\ell_{2}\\}$.

By constructions of $APX_{i}$ and $APX_{i+1}$, we have

$\displaystyle APX_{i+1}\backslash(Y_{i+1}\cup E[\mathcal{H}_{i+1}])$
$\displaystyle=APX_{i}\backslash(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])=EC_{3}\backslash(Y_{i+1}\cup E[\mathcal{H}_{i+1}])$

To see that $|APX_{i+1}\cap(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])|\leq\frac{4}{3}|EC_{3}\cap(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])|$, observe that

$\displaystyle|EC_{3}\cap(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])|-|EC_{3}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|\coloneqq\Delta\geq 3$

where the inequality follows since $\ell,\ell_{1},\ell_{2}\notin
EC_{3}\cap(Y_{i}\cup E[\mathcal{H}_{i}])$, but are in $EC_{3}\cap(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])$. Similarly, the following inequality follows since
$APX_{i+1}\cap(Y_{i+1}\cup E[\mathcal{H}_{i+1}])$ contains
$\ell_{1},\ell_{2},e$ and exactly one of $f$ or $\ell$.

$\displaystyle|APX_{i+1}\cap(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])|-|APX_{i}\cap(Y_{i}\cup E[\mathcal{H}_{i}])|=\Delta+1$

So as $i$ increases by one, the increase on the right hand side of the
inequality of (2) is at most $\frac{4}{3}$ the increase on the left hand side.
Thus, (2) holds.

Given that we are able to show (1) and (2) hold for the three cases above, we
note that for every $i\geq 1$, by (2) we have

$\displaystyle|APX_{i}|$ $\displaystyle=|APX_{i}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|+|APX_{i}\backslash(Y_{i}\cup E[\mathcal{H}_{i}])|$
$\displaystyle\leq\frac{4}{3}|EC_{3}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|+|EC_{3}\backslash(Y_{i}\cup
E[\mathcal{H}_{i}])|\leq\frac{4}{3}|EC_{3}|$

Furthermore, in each iteration we cover a new element of
$\\{G_{1},\dots,G_{k}\\}$, so after a polynomial number of iterations we have
covered every obstruction.

We can now combine these ingredients to prove Theorem 4.1 (for this simple
case). The proof for the general case can be found in Appendix 0.G.3.

######  Proof (Proof of Theorem 4.1)

Given an unweighted $(n-4)$-Node Connectivity Augmentation instance, we apply
Theorem 2.1 to obtain an unweighted $4$-Obstruction Covering instance,
$(G,4,L)$. We will show how to find a solution $APX$ with
$|APX|\leq\frac{4}{3}|opt|$. Using Theorem 2.2, we decompose $G$ into node-
disjoint subgraphs $R,G_{1},\dots,G_{k}$. By applying Lemma 4, we compute a
minimum cardinality set of links $EC_{3}\subseteq L$ that covers the
obstructions contained in every subgraph $G_{i}$ of degree $1$ and $2$, and
covers every degree $3$ node. Let
$\mathcal{H}_{0}\subseteq\\{G_{1},\dots,G_{k}\\}$ be the ladders whose
obstructions are covered by $EC_{3}$. We set $APX_{1}=EC_{3}\cap
E[\mathcal{H}_{0}]$. We create a new instance $(G^{\prime}=(V,E\backslash
APX_{1}),4,L^{\prime}=L\backslash APX_{1})$. Clearly, if we apply Theorem 2.2
to the instance $(G^{\prime},4,L^{\prime})$, we get a decomposition that
contains only ladders of degree $3$ or $4$.

We apply Lemma 5 to $(G^{\prime},4,L^{\prime})$ with $EC_{3}\setminus APX_{1}$
as our partial solution, to find a feasible solution $APX_{2}$. We let
$APX=APX_{1}\cup APX_{2}$. By applying the inequality from the statement of
Lemma 5, we upper bound $|APX|$ as

$|APX_{1}|+|APX_{2}|\leq|EC_{3}\cap
E[\mathcal{H}_{0}]|+\frac{4}{3}|EC_{3}\setminus
E[\mathcal{H}_{0}]|\leq\frac{4}{3}|EC_{3}|\leq\frac{4}{3}|opt|.$

##  5  Hardness of Unweighted Node Connectivity Augmentation

In this section, we will prove that the $d$-Obstruction Covering problem is
APX-hard for any $d\geq 4$ with $d=O(n^{c})$ for any fixed constant $c$. To
prove this, we introduce a variant of the 3-SAT problem, denoted
_3-SAT-(2,2)_.

######  Definition 3 (3-SAT-(2,2) problem)

The 3-SAT-(2,2) problem is the special case of 3-SAT where each variable
occurs exactly twice as a positive literal and twice as a negative literal in
the boolean formula $\mathcal{I}$. The corresponding optimization version of
the problem is denoted as MAX-3-SAT-(2,2).

The following lemma shows that this special case of 3-SAT is as hard as the
original problem. Its full proof can be found in Appendix 0.H.1

###### Lemma 6

The 3-SAT-(2,2) problem is NP-hard.

We will now prove the following preliminary hardness result for our problem.

###### Theorem 5.1

The $4$-Obstruction Covering problem is NP-hard.

In order to prove Theorem 5.1, we will provide a polynomial-time reduction
from 3-SAT-(2,2). Let $\mathcal{I}$ be an instance of 3-SAT-(2,2), we will
construct an instance $(G_{\mathcal{I}},4,L_{\mathcal{I}})$ of the
$4$-Obstruction Covering problem as follows:

  * •

For each clause $C$ in $\mathcal{I}$, we add node $C$ to $G_{\mathcal{I}}$. We
call these _clause nodes_.

  * •

For each variable $x\in I$, we add a subgraph $H_{x}$ to $G_{\mathcal{I}}$,
where $H_{x}$ is defined by six _variable nodes_ $x_{1},\dots,x_{6}$, and
edges $\\{x_{1}x_{2},x_{2}x_{3},x_{3}x_{4},x_{4}x_{5},x_{5}x_{6},$
$x_{1}x_{6},x_{2}x_{5}\\}$. The edges $\\{x_{1}x_{2},$ $x_{2}x_{3},$
$x_{4}x_{5},$ $x_{5}x_{6}\\}$ are included into $L$.

  * •

For (possibly equal) clauses $C_{1},C_{2}$ containing the positive literals of
$x$, we add edges $\\{x_{1}C_{1},x_{4}C_{2}\\}$ to both $G$ and $L$. For
(possibly equal) clauses $C_{3},C_{4}$ containing the negative literals of
$x$, we add edges $\\{x_{3}C_{3},x_{6}C_{4}\\}$ to both $G_{\mathcal{I}}$ and
$L$.

See Figure 3 (Left) for a depiction of the gadget. By construction, the graph
is $3$-regular and no three nodes have two common neighbors, so it is not
difficult to show that the defined instance is valid. The proof of the
following proposition can be found in Appendix 0.H.2.

$x$$\bar{x}$$\bar{x}$$x$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$C_{1}$$C_{3}$$C_{2}$$C_{4}$$x$$\bar{x}$$\bar{x}$$x$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$C_{1}$$C_{3}$$C_{2}$$C_{4}$$y_{1}$$y_{2}$$z_{1}$$z_{2}$

Figure 3: Left: Subgraph $H_{x}$ and clause nodes $C_{1},C_{2},C_{3},C_{4}$
containing $x$, from the reduction in Theorem 5.1, for variable $x$ in
$\mathcal{I}$. Here the links of $H_{x}$ are denoted by the black edges.
Right: The extension of $\mathcal{I}$ to larger values of $d$ (in this case,
$d=6$). It can be seen that the set of links is the same, but the obstructions
have a more of nodes.

###### Proposition 1

The graph $G_{\mathcal{I}}$ defined above does not contain neither $K_{1,4}$
nor $K_{2,3}$ as subgraph. Thus, $(G_{\mathcal{I}},4,L_{\mathcal{I}})$ is a
valid instance of the $4$-Obstruction Covering problem.

In the following two lemmas we show how to translate a feasible assignment of
values for instance $\mathcal{I}$ into an optimal solution of
$(G_{\mathcal{I}},4,L_{\mathcal{I}})$ and back.

###### Lemma 7

Let $k$ be the number of variables in the 3-SAT-(2,2) instance $\mathcal{I}$.
If $\mathcal{I}$ is satisfiable, then there is a feasible solution to the
$4$-Obstruction Covering instance $(G_{\mathcal{I}},4,L_{\mathcal{I}})$ of
size $4k$.

###### Proof

Consider a satisfying assignment for instance $\mathcal{I}$. For each variable
$x$ in $\mathcal{I}$, if $x$ is set to true (resp. false), then for the
(possibly equal) clauses $C_{1}$ and $C_{2}$ containing the positive (resp.
negative) literals of $x$, we take the links $x_{1}C_{1}$ and $x_{4}C_{2}$
(resp. $x_{3}C_{3},x_{6}C_{4}$), as well as the links
$\\{x_{2}x_{3},x_{5}x_{6}\\}$ (resp. $\\{x_{1}x_{2},x_{4}x_{5}\\}$). This way,
since the assignment satisfies $\mathcal{I}$, all the obstructions $K_{1,3}$
defined by clause nodes are covered. The $K_{1,3}$ obstructions defined by
variable nodes and the $K_{2,2}$ obstructions of each $H_{x}$ are also covered
by the links $\\{x_{2}x_{3},x_{5}x_{6}\\}$ or $\\{x_{1}x_{2},x_{4}x_{5}\\}$
depending on the case. Therefore, we have a feasible solution for the
$4$-Obstruction Covering instance $(G_{\mathcal{I}},4,L_{\mathcal{I}})$ of
size $4k$.

###### Lemma 8

Let $k$ be the number of variables in the 3-SAT-(2,2) instance $\mathcal{I}$.
If there is a feasible solution to the $4$-Obstruction Covering instance
$(G_{\mathcal{I}},4,L_{\mathcal{I}})$ of size $4k$, then $\mathcal{I}$ is
satisfiable.

###### Proof

Note, for a given variable $x$ in $\mathcal{I}$, any links taken to cover
obstructions in subgraph $H_{x}$ do not cover obstructions from subgraph
$H_{y}$ for variable $y\neq x$. Hence, the size of any feasible solution
$F\subseteq L_{\mathcal{I}}$ to $(G_{\mathcal{I}},L_{\mathcal{I}})$ is equal
to $\sum_{x\in\mathcal{I}}:\\{\ell\in F|\ell\text{ incident to }v\in
V(H_{x})\\}|$. Observe that every feasible solution must contain at least four
links incident to a nodes $V(H_{x})$ as we must have at least one link
incident to every vertex in $\\{x_{1},x_{2},\ldots,x_{6}\\}$. Therefore in a
feasible solution of size $4k$, for each variable $x\in\mathcal{I}$ we have
exactly four links with an endpoint in $V(H_{x})$. Furthermore for each
variable $x$, such a solution has exactly one link incident on each $x_{i}$
for every $i\in\\{1,3,4,6\\}$.

We will prove we can assume the feasible solution of size $4k$ to
$(G_{\mathcal{I}},L_{\mathcal{I}})$ has the following structure: for each
subgraph $H_{x}$, either we have the links between $x_{1}$ and $x_{4}$ and
their corresponding adjacent clause nodes plus $x_{2}x_{3}$ and $x_{5}x_{6}$,
or the links between $x_{3}$ and $x_{6}$ and their corresponding adjacent
clause nodes plus $x_{1}x_{2}$ and $x_{4}x_{5}$.

Suppose that for some variable $x\in\mathcal{I}$, we cover the obstructions of
$H_{x}$ with a different set of links.

Case 1, we choose at least three links from $H_{x}$: Let us assume without
loss of generality that these links are
$\\{x_{1}x_{2},x_{2}x_{3},x_{4}x_{5}\\}$. Since the solution is feasible, it
must contain either the link between $x_{6}$ and its adjacent clause node or
the link $x_{5}x_{6}$. In the first case, we can replace $x_{2}x_{3}$ with the
link joining $x_{3}$ and its adjacent clause node. In the second case, we can
replace both $x_{2}x_{3}$ and $x_{5}x_{6}$ with the corresponding links
joining them to their adjacent clause nodes, and in both cases every
obstruction in $H_{x}$ is still covered.

Case 2, case 1 does not apply: We need to cover both of the $K_{2,2}$
obstructions plus $x_{2}$ and $x_{5}$. In order to do it with two links only,
one of them must be incident to $x_{2}$ and the other to $x_{5}$. Without loss
of generality we assume our solution contains $x_{1}x_{2}$ and $x_{4}x_{5}$
and it does not contain $x_{2}x_{3}$ and $x_{5}x_{6}$. Therefore as we need to
cover $x_{3}$ and $x_{6}$ we must have the links from $x_{3}$ and $x_{6}$ to
the clause nodes in our solution. Thus our solution forms the desired
configuration.

Notice that, since the solution for $(G_{\mathcal{I}},4,L_{\mathcal{I}})$ is
feasible, every clause node is covered. It is possible to find a satisfying
assignment to the variables of $\mathcal{I}$ in the following way: For each
variable $x$, if the links incident to $x_{1}$ and $x_{4}$ and their adjacent
clause nodes are taken, then we set $x$ to be true. If the links $x_{3}$ and
$x_{6}$ and their adjacent clause nodes are taken instead, then we set $x$ to
be false.

To see that this assignment satisfies $\mathcal{I}$, suppose for the sake of
contradiction that some clause $C=(a\lor b\lor c)$ is not satisfied. Then,
none of the links between $H_{a},H_{b},H_{c}$ and $C$ are taken, and thus $C$
is uncovered. This means that the solution is not covering every obstruction
in $(G_{\mathcal{I}},L_{\mathcal{I}})$, which is a contradiction.

We can now proceed with the proof of Theorem 5.1.

######  Proof (Proof of Theorem 5.1.)

Consider an instance $\mathcal{I}$ of 3-SAT-(2,2) defined by $k$ variables. We
construct the $(n-4)$-Obstruction Covering instance
$(G_{\mathcal{I}},4,L_{\mathcal{I}})$ as described before. Thanks to Lemmas 7
and 8, $\mathcal{I}$ is satisfiable if and only if
$(G_{\mathcal{I}},4,L_{\mathcal{I}})$ admits a feasible solution of size $4k$.
Since 3-SAT-(2,2) is NP-hard (Lemma 6), the $4$-Obstruction Covering problem
is NP-hard as well.

It is possible to extend the previous hardness results to further values of
$d$, as the following theorem states (see Figure 3 (Right)). The proof of this
theorem can be found in Appendix 0.H.3

###### Theorem 5.2

For any given $d\geq 4$, $d\in O(n^{c})$ for any fixed constant $c>0$, the
$d$-Obstruction Covering problem is NP-hard.

It is possible to improve the previous results to prove that the
$d$-Obstruction Covering problem is indeed APX-hard. Our results follow from
the fact that a closely related problem to MAX-3-SAT-(2,2), known as
MAX-3-SAT-4, is APX-hard [4]. A detailed proof can be found in Appendix 0.H.4.

###### Theorem 5.3

For any given $d\geq 4$, $d\in O(n^{c})$ for any fixed constant $c>0$, the
$d$-Obstruction Covering problem is APX-hard.

## References

  * [1] D. Adjiashvili.  Beating approximation factor two for weighted tree augmentation with bounded costs.  ACM Trans. Algorithms, 15(2):19:1–19:26, 2019.
  * [2] H. Angelidakis, D. Hyatt-Denesik, and L. Sanità.  Node connectivity augmentation via iterative randomized rounding.  Mathematical Programming, pages 1–37, 2022.
  * [3] V. Auletta, Y. Dinitz, Z. Nutov, and D. Parente.  A 2-approximation algorithm for finding an optimum 3-vertex-connected spanning subgraph.  Journal of Algorithms, 32(1):21–30, 1999.
  * [4] P. Berman, A. Scott, and M. Karpinski.  Approximation hardness and satisfiability of bounded occurrence instances of sat.  Technical report, SIS-2003-269, 2003.
  * [5] J. Byrka, F. Grandoni, and A. Jabal Ameli.  Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 815–825, 2020.
  * [6] K. Bérczi and Y. Kobayashi.  An algorithm for $(n-3)$-connectivity augmentation problem: Jump system approach.  Journal of Combinatorial Theory, Series B, 102(3):565–587, 2012\.
  * [7] K. Bérczi and L. Végh.  Restricted _b_ -matchings in degree-bounded graphs.  In Integer Programming and Combinatorial Optimization, 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010\. Proceedings, volume 6080 of Lecture Notes in Computer Science, pages 43–56. Springer, 2010.
  * [8] F. Cecchetto, V. Traub, and R. Zenklusen.  Bridging the gap between tree and connectivity augmentation: unified and stronger approaches.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 370–383. ACM, 2021.
  * [9] J. Cheriyan and Z. Gao.  Approximating (unweighted) tree augmentation via lift-and-project, part I: stemless TAP.  Algorithmica, 80(2):530–559, 2018.
  * [10] J. Cheriyan and Z. Gao.  Approximating (unweighted) tree augmentation via lift-and-project, part II.  Algorithmica, 80(2):608–651, 2018.
  * [11] J. Cheriyan and L. Végh.  Approximating minimum-cost k-node connected subgraphs via independence-free graphs.  SIAM J. Comput., 43(4):1342–1362, 2014.
  * [12] E. Dinic, A. Karzanov, and M. Lomonosov.  The system of minimum edge cuts in a graph.  In book: Issledovaniya po Diskretnoǐ Optimizatsii (Engl. title: Studies in Discrete Optimizations), A.A. Fridman, ed., Nauka, Moscow, 290-306, in Russian,, 01 1976.
  * [13] S. Fiorini, M. Groß, J. Könemann, and L. Sanità.  Approximating weighted tree augmentation via chvátal-gomory cuts.  In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 817–831. SIAM, 2018.
  * [14] G. Frederickson and J. JáJá.  Approximation algorithms for several graph augmentation problems.  SIAM J. Comput., 10(2):270–283, 1981.
  * [15] W. Gálvez, F. Sanhueza-Matamala, and J. Soto.  Approximation algorithms for vertex-connectivity augmentation on the cycle.  In Jochen Koenemann and Britta Peis, editors, Approximation and Online Algorithms, pages 1–22, Cham, 2021. Springer International Publishing.
  * [16] F. Grandoni, C. Kalaitzis, and R. Zenklusen.  Improved approximation for tree augmentation: saving by rewiring.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 632–645. ACM, 2018.
  * [17] D. Hyatt-Denesik, A. Jabal Ameli, and L. Sanità.  Finding almost tight witness trees.  In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023.
  * [18] G. Kortsarz, R. Krauthgamer, and J. Lee.  Hardness of approximation for vertex-connectivity network design problems.  SIAM Journal on Computing, 33(3):704–720, 2004.
  * [19] Z. Nutov.  Approximating minimum-cost edge-covers of crossing biset-families.  Combinatorica, pages 95–114, 2014.
  * [20] Z. Nutov.  2-node-connectivity network design.  In Proceedings of the 18th International Workshop on Approximation and Online Algorithms (WAOA), volume 12806 of Lecture Notes in Computer Science, pages 220–235. Springer, 2020.
  * [21] Z. Nutov.  A 4 + _$\epsilon$_ approximation for _k_ -connected subgraphs.  In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1000–1009. SIAM, 2020.
  * [22] Z. Nutov.  Approximation algorithms for connectivity augmentation problems.  In Proceedings of the 16th International Computer Science Symposium in Russia (CSR), volume 12730, pages 321–338. Springer, 2021.
  * [23] J. Petersen.  Die theorie der regulären graphen.  Acta Math, 15(3):193–220, 1981.
  * [24] V. Traub and R. Zenklusen.  A better-than-2 approximation for weighted tree augmentation.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1–12. IEEE, 2022.
  * [25] V. Traub and R. Zenklusen.  Local search for weighted tree augmentation and steiner tree.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3253–3272. SIAM, 2022.
  * [26] V. Traub and R. Zenklusen.  A (1.5+ $\varepsilon$)-approximation algorithm for weighted connectivity augmentation.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1820–1833, 2023.

##  Appendix 0.A  Previous hardness results for Vertex-Connectivity
Augmentation

Kortsarz et al. [18] prove the following hardness result for $1$-node
connectivity augmentation.

######  Theorem 0.A.1 ([18])

There exists $\varepsilon_{0}>0$ fixed, such that it is NP-hard to approximate
$1$-Node Connectivity Augmentation within a factor better than
$1+\varepsilon_{0}$.

This result is proved via a reduction from a bounded degree version of 3D
Matching. In order to obtain analogous hardness results for $k$-Node
Connectivity Augmentation, it is argued that we can iteratively add $k-1$
nodes to the construction which are connected to all the other nodes in the
graph (this way, the graph becomes $k$ connected and the cuts that must be
covered are exactly the same). Thus, in general, if we add $t$ dummy nodes to
the instance, which has $n$ nodes, we get a graph with $n^{\prime}=n+t$ nodes
which is $(t+1)$-node connected.

In order for this procedure to be a polynomial-time reduction, it is required
that the value of $t$ is polynomially bounded with respect to $n$, let us say
at most $n^{c}$ for some constant $c>0$, which implies that the new instance
we obtain is a $(n^{\prime}-n^{\prime 1/c})$-connected graph and we wish to
augment its connectivity by one.

In particular, it is not possible for this procedure to reach a
$(n^{\prime}-d)$-connected instance where $d$ is constant or logarithmic, and
to have polynomial running time at the same time. This is also consistent with
the fact that $(n-3)$-node connectivity augmentation is polynomial-time
solvable [6].

##  Appendix 0.B  Dynamic Program for independent ladders and hexagons

In this section we prove Theorem 2.3 which we restate: See 2.3

Assume $u_{1},\ldots,u_{r+1},v_{1},\ldots,v_{r+1}$ is the given consistent
labelling of $C$ given by Theorem 2.2. If $C$ has at most $10$ nodes, then we
can enumerate over the possible edge covers to find the minimum cost covering
$F$. Notice that a hexagon has 7 nodes, thus, we can assume that $C$ is a
ladder of length at least $6$.

We denote by $D$ the possible edges in $C$ with both endpoints in
$\\{v_{1},u_{1},$ $v_{r+1},u_{r+1}\\}$. We will compute a different solution
for every possible $2^{|D|}$ combination of edges from $D$ in $F$. If we have
$e=xy\in D\cap F$, then we set $h(x)=h(y)=0$, as these endpoints are covered
by $e\in F$. Furthermore, if $v_{1}u_{1}\in D\cap F$, then we set
$w(v_{1}u_{1})=0$ to ensure we have $v_{1}u_{1}$ in the solution and we avoid
double counting. The case where $v_{r+1}u_{r+1}\in F\cap D$, is handled
similarly. Lastly, if the edges of $D$ form a square $B$, then we require that
$|F\cap D|\geq 1$. Observe that since $r\geq 5$, other than the squares
$S_{i}$, the only possible square of $C$ is $B$.

Before we define our dynamic program, in order to simplify notation, for each
$S_{i}$, $i=1,\dots,k$, we define $t_{i}\coloneqq v_{i}v_{i+1},b_{i}\coloneqq
u_{i}u_{i+1},L_{i}\coloneqq v_{i}u_{i},$ and, $L_{i+1}\coloneqq
v_{i+1}u_{i+1}$. We are now ready to define our dynamic program.

We compute from $S_{1}$ to $S_{i}$ the minimum number of links needed to cover
obstructions $S_{1},\dots,S_{i}$ and satisfy the requirements $h(v_{j})$ and
$h(u_{j})$ for $j<i$, given whether $t_{i},b_{i},L_{i+1}$ are in $F$ or not.
We let
$\mathcal{X}_{L_{i}},\mathcal{X}_{t_{i}},\mathcal{X}_{b_{i}}\in\\{0,1\\}$ be
the indicator variable for whether our solution includes $L_{i},t_{i},$ and
$b_{i}$ respectively or not. We store our solution in the table
$A[i,\mathcal{X}_{L_{i+1}},\mathcal{X}_{t_{i}},\mathcal{X}_{b_{i}}]$.

For $i=1$, $A[1,\mathcal{X}_{L_{2}},\mathcal{X}_{t_{1}},\mathcal{X}_{b_{1}}]$
is equal to

$\displaystyle\min_{\mathcal{X}_{L_{1}},\mathcal{X}_{t_{1}},\mathcal{X}_{b_{1}}\in\\{0,1\\}}\left\\{w(L_{1})\mathcal{X}_{L_{1}}+w(L_{2})\mathcal{X}_{L_{2}}+w(t_{1})\mathcal{X}_{t_{1}}+w(b_{1})\mathcal{X}_{b_{1}}\right\\}$

Subject to the requirements that (1)
$\mathcal{X}_{t_{1}}\lor\mathcal{X}_{L_{2}}=1$ if $h(v_{1})=1$ to ensure that
the coverage requirement of $v_{1}$ is met, (2)
$\mathcal{X}_{b_{1}}\lor\mathcal{X}_{L_{2}}=1$ if $h(u_{1})=1$ to ensure that
the coverage requirement of $u_{1}$ is met, and (3)
$\mathcal{X}_{t_{1}}\lor\mathcal{X}_{b_{1}}\lor\mathcal{X}_{L_{2}}=1$ or
$u_{1}v_{1}\in F\cap D$ to ensure that $S_{1}$ is covered. Since we are
considering all the possible cases by enumeration it should be clear that
$A[1,\mathcal{X}_{L_{2}},\mathcal{X}_{t_{1}},\mathcal{X}_{b_{1}}]$ is computed
correctly.

For $i\in\\{1,\dots,r-1\\}$ we set
$A[i+1,\mathcal{X}_{L_{i+2}},\mathcal{X}_{t_{i+1}},\mathcal{X}_{b_{i+1}}]$ to

$\displaystyle\min_{\mathcal{X}_{L_{i+1}},\mathcal{X}_{t_{i}},\mathcal{X}_{b_{i}}\in\\{0,1\\}}\\{$
$\displaystyle
w(L_{i+1})\mathcal{X}_{L_{i+1}}+w(t_{i+1})\mathcal{X}_{t_{i+1}}+w(b_{i+1})\mathcal{X}_{b_{i+1}}$
$\displaystyle+$ $\displaystyle
A[i,\mathcal{X}_{L_{i+1}},\mathcal{X}_{t_{i}},\mathcal{X}_{b_{i}}]\\}$

Subject to the following requirements: (1)
$\mathcal{X}_{t_{i}}\lor\mathcal{X}_{t_{i+1}}\lor\mathcal{X}_{L_{i+1}}=1$ if
$h(v_{i+1})=1$ to ensure that the coverage requirement of $v_{i+1}$ is met,
(2) similarly,
$\mathcal{X}_{b_{i}}\lor\mathcal{X}_{b_{i+1}}\lor\mathcal{X}_{L_{i+1}}=1$ if
$h(u_{i+1})=1$ to ensure that the coverage requirement of $u_{i+1}$ is met,
and (3)
$\mathcal{X}_{t_{i+1}}\lor\mathcal{X}_{b_{i+1}}\lor\mathcal{X}_{L_{i+1}}\lor\mathcal{X}_{L_{i+2}}=1$
to ensure that $S_{i+1}$ is covered.

Now by induction we can show that
$A[i,\mathcal{X}_{L_{i+1}},\mathcal{X}_{t_{i}},\mathcal{X}_{b_{i}}]$ is
computed correctly. We know that this is true for $i=1$. Assume we have
computed all the cells
$A[i-1,\mathcal{X}_{L_{i+2}},\mathcal{X}_{t_{i+1}},\mathcal{X}_{b_{i+1}}]$ for
some $i$. For each configuration of
$\mathcal{X}_{L_{i+1}},\mathcal{X}_{t_{i}},\mathcal{X}_{b_{i}}\in\\{0,1\\}$,
we can apply the inductive hypothesis to
$A[i,\mathcal{X}_{L_{i+1}},\mathcal{X}_{t_{i}},\mathcal{X}_{b_{i}}]$, to find
the minimum cost number of links needed to cover obstructions
$S_{1},\dots,S_{i}$, and satisfy requirements $h(v_{j})$ and $h(u_{j})$ for
$j<i$. We take the minimum of the configurations of
$\mathcal{X}_{L_{i+1}},\mathcal{X}_{t_{i}},\mathcal{X}_{b_{i}}\in\\{0,1\\}$
and the claim holds.

To find the minimum solution, we find

$\min_{\mathcal{X}_{L_{r+1}},\mathcal{X}_{t_{r}},\mathcal{X}_{b_{r}}\in\\{0,1\\}}A[r,\mathcal{X}_{L_{r+1}},\mathcal{X}_{t_{r}},\mathcal{X}_{b_{r}}],$

subject to the requirements

  * •

$\mathcal{X}_{t_{r}}\lor\mathcal{X}_{L_{r+1}}=1$ if $h(v_{r+1})=1$,

  * •

$\mathcal{X}_{b_{r}}\lor\mathcal{X}_{L_{r+1}}=1$ if $h(u_{r+1})=1$, and

  * •

$x_{L_{r+1}}=0$ if $u_{r+1}v_{r+1}\notin F\cap D$.

##  Appendix 0.C  Subset-Edge Cover

See 1

###### Proof

If $N=V(G)$, then we can solve the problem by finding the minimum edge cover
of $G$, which is known to be solvable in polynomial time. Now assume
$N\subsetneq V(G)$. In this case we construct a graph $G^{\prime}$, that
contains $G$ and has an additional vertex $v$. Now for every $u\in
V(G)\setminus N$, we add an edge of weight zero from $v$ to $u$ in
$G^{\prime}$. We compute the minimum weight edge cover $E^{\prime}$ of
$G^{\prime}$. Assume $E_{v}$ is the set of all edges incident to $v$ in
$G^{\prime}$. We argue that $E^{\prime\prime}:=E\setminus E_{v}$ is the
minimum weight $N$-edge cover of $G$. For this purpose it is sufficient to
observe that if $E_{1}$ is an $N$-edge cover for $G$ then $E_{1}\cup E_{v}$ is
an edge cover of $G^{\prime}$. Similarly if $E_{2}$ is an edge cover for
$G^{\prime}$ then $E_{2}\setminus E_{v}$ is an edge cover of $G$. Therefore
the cost of the minimum $N$-edge cover of $G$ is indeed equal to the cost of
the minimum edge cover of $G$. Therefore our solution,
$E^{\prime\prime}:=E\setminus E_{v}$ is a minimum $N$-edge cover.

##  Appendix 0.D  Proof of Theorem 2.1

In this section we prove Theorem 2.1. We remark that [6] shows this for $d=4$.
Here we generalize this for other values of $d$ (see [7] for a similar
discussion). To prove the Theorem we first prove the following lemma.

###### Lemma 9

Let $G=(V,E)$ be a connected graph. $G$ has a vertex cut $V^{\prime}$ of size
$r$ if and only if $\bar{G}$ contains a subgraph $K_{i,|V|-r-i}$ for some
$1\leq i<|V|-|V|^{\prime}$.

###### Proof

Assume $V^{\prime}$ is a cut of size $r$ in $G$, then $G[V\setminus
V^{\prime}]$ has at least two connected components. Let $C$ be a connected
component of $G[V\setminus V^{\prime}]$. Then in $\bar{G}$, the induced
subgraph on $V\setminus V^{\prime}$ contains a
$K_{|C_{1}|,V-|V^{\prime}|-|C_{1}|}$. Now assume $\bar{G}$ contains a subgraph
$K_{i,|V|-r-i}$ for some $1\leq i<|V|-|V|^{\prime}$. Let $(X,Y)$ be the
bipartition of this subgraph. We argue that $V^{\prime}:=V\setminus(X\cup Y)$
is a cut of size $r$. Observe that by deleting $V^{\prime}$, there will be no
edges between $X$ and $Y$. Furthermore
$|V^{\prime}|=|V|-(|X|+|Y|)=|V|-(|V|-r)=r$. Thus $V^{\prime}$ is clearly a cut
of size $r$.

######  Proof (Proof of Theorem 2.1)

Given an instance $I$ of $(n-d)$-node-connectivity Augmentation Problem on
graph $G=(V,E)$, with link set $L$ and cost $c:E\rightarrow\mathbb{R}$ for the
edges we obtain the instance of $I^{\prime}:=(\bar{G},d,L,c)$ of
$d$-Obstruction Covering problem in which $\bar{G}$ is the complement of $G$.
Observe that, using Lemma 9, $\bar{G}$ contains no forbidden subgraphs. Hence,
again by Lemma 9, $G\cup L^{\prime}$ is $(n-d+1)$-vertex-connected if and only
if $L^{\prime}$ has a link in every obstruction of $\bar{G}$.This implies that
for every subset $L^{\prime}$ of $L$, $L^{\prime}$ is a feasible solution for
$I$ if and only if $L^{\prime}$ is a feasible solution for $I^{\prime}$.

##  Appendix 0.E Proof of Theorem 2.2

In order to prove Theorem 2.2, we need the following technical lemmas.

###### Lemma 10

Let $H$ and $S$ be hexagon and square subgraphs of $G$ respectively, such that
$V(S)\cap V(H)\neq\emptyset$, and $V(S)\not\subseteq V(H)$. Then, in
polynomial time, we can find a ladder $C$ in $G$ of length three, and a
consistent labelling of $C$, such that $V(C)=V(H)\cup V(S)$.

###### Proof

Denote the nodes of $S$ by $uwzv$, and without loss of generality assume $v\in
V(S)\cap V(H)$, and $w\in V(S)\backslash V(H)$. If $S\cap H=\\{v\\}$, then $v$
is a corner of $H$ that is adjacent to two nodes in $H$ and two nodes in
$S\backslash H$, so $v$ has degree $4$ which is a contradiction. If $S\cap
H=\\{u,v\\}$, then they cannot be adjacent or else they will again have degree
$4$. So $S\cap H=\\{u,v,z\\}$ where $u$ and $z$ are corners of $H$. Which
implies that $v$ is not a corner in $H$. It is not hard to see that $S$
combined with two of the squares in $H$ gives a ladder $C$ of length three
such that $V(C)=V(H)\cup V(S).$ Note that as $|C|$ is constant in size, then
by enumeration we can compute a consistent labelling of $C$.

###### Lemma 11

Let $C$ be a ladder in $G$ with a consistent labelling. Let $S$ be a square in
$G$, such that $V(S)\cap V(C)\neq\emptyset$, and $V(S)\not\subseteq V(C)$.
Then, in polynomial time, we can find a subgraph $C^{\prime}\subseteq G$, such
that $V(C)\subsetneq V(C^{\prime})$, where $C^{\prime}$ is either a ladder
with a consistent labelling or a hexagon.

###### Proof

If the length of $C$ is 1 then $C\cup S$ is a ladder of length 2, as $G$ does
not contain a $K_{2,3}$ forbidden subgraph nor a $K_{1,4}$ forbidden subgraph.
In this case, since $|C|$ is constant in size, we can compute a consistent
labelling.

So assume the length of $C$ is at least $2$, and hence $r\geq 3$. Let
$\\{u_{1},\dots,u_{r},$ $v_{1},\dots,v_{r}\\}$ be the consistent labelling of
$C$. Since $V(S)\not\subseteq V(C)$ and the degree of nodes in $G$ is at most
$3$, then $S$ contains edges $xy$ and $x^{\prime}y^{\prime}$ such that $x$ and
$x^{\prime}$ are distinct corners of $S$ and $y$ and $y^{\prime}$ are (not
necessarily distinct) vertices in $V(S)\setminus V(C)$. Observe that $x$ and
$x^{\prime}$ must have precisely two neighbours from $V(C)$ as they are degree
$3$ in $G$, and are thus corners of $C$.

Without loss of generality, we assume $x=u_{r}$. We distinguish the following
cases: 1) If $x^{\prime}=v_{r}$, then $v_{r}u_{r}yy^{\prime}$ must be a square
in $G$. Therefore $C^{\prime}:=S\cup C$ is a ladder of size $r$. We can label
$u_{r+1}\coloneqq y$ and $v_{r+1}\coloneqq y^{\prime}$. 2) If
$x^{\prime}=v_{1}$, then in the square $S$ there must be a path of length at
most two in $C$ from $u_{r}$ to $v_{1}$ in $C$. However this contradicts the
fact that a such path does not exist as $r\geq 3$. 3) If $x^{\prime}=u_{1}$,
then in the square $S$ there must be a path $P$ of length at most two in $C$
from $u_{r}$ to $v_{1}$ in $C$. As $r\geq 3$, in order for such a path to
exist we must have $r=3$, and $P=u_{1}u_{2}u_{3}$. Therefore
$S=u_{1}u_{2}u_{3}y$, and we have $y=y^{\prime}$. In this case $S\cup C$ is a
Hexagon.

With Lemmas 10 and 11, we can prove Theorem 2.2.

######  Proof (Proof of Theorem 2.2)

We find the decomposition by performing a sequence of steps. At the $i$-th
step, assume we have subgraphs $R_{i},G_{1},G_{2},\ldots,G_{i-1}$ of $G$ such
that:

  1. 1.

$R_{i},G_{1},G_{2},\ldots,G_{i-1}$ are pairwise node-disjoint

  2. 2.

Each $G_{j}$ is either a ladder with a consistent labelling or a hexagon.

  3. 3.

For every square $S$ of $G$ and every $1\leq j<i$, if $V(S)\cap
V(G_{j})\neq\emptyset$ then $V(S)\subseteq V(G_{j})$.

  4. 4.

$V(R_{i})=V\backslash(V(G_{1})\cup V(G_{2})\ldots\cup V(G_{i-1}))$.

Initially, we set $i=1$, and note that $R_{1}=G$. At a given step $i$, if
$V(R_{i})$ contains only lonely nodes, then $R_{i},G_{1},G_{2},\ldots,G_{i-1}$
are the desired subgraphs. Otherwise we can find a square $S$ such that $V(S)$
and $V(G_{1})\cup V(G_{2})\ldots\cup V(G_{i-1})$ are disjoint, by property
(3). $S$ itself is a ladder of length one, and it is easy to find a consistent
labelling for $S$. Now, we extend $S$ to a maximal ladder or hexagon in
$R_{i}$ by repeatedly applying Lemmas 10 and 11, as we can enumerate in
polynomial time all squares and hexagons in $R_{i}$, and check if they
intersect with the nodes of $S$. In this way, we can find in polynomial time a
ladder or a hexagon $G_{i}$, such that $V(S)\subseteq V(G_{i})\subseteq
V(R_{i})$ and for every square $S^{\prime}$ of $G$, if $V(S^{\prime})\cap
V(G_{i})\neq\emptyset$ then $V(S^{\prime})\subseteq V(G_{i})$. Note that if
$G_{i}$ is a ladder, then Lemmas 10 and 11 also yield a consistent labelling.
Furthermore, by construction we keep that $G_{1},G_{2},...,G_{i}$ are node-
disjoint. Now we increase $i$ by one and go to the next step. As the size of
$V(R_{i})$ is decreasing at each step, the process terminates in polynomial
time. At termination, we reach the desired subgraphs.

##  Appendix 0.F  Missing Proofs of Section 3

###  0.F.1  Proof of Corollary 2

We first recall Petersen’s Theorem

######  Theorem 0.F.1 (Petersen’s Theorem [23])

Let $G$ be a $2k$-regular graph, for some integer $k$. Then, $G$ can be
decomposed into $k$ $2$-regular spanning subgraphs.

We are now ready to prove Corollary 2.

######  Proof (proof of Corollary 2)

Using Petersen’s Theorem $G$ has a $2$-regular spanning subgraph. We can
compute one such subgraph $G_{1}$ in polynomial time by computing a maximum
$2$-matching, which is well known to be polynomial time. Now $G_{1}$ and
$G_{2}:=G\setminus E(G_{1})$ are the desired subgraphs.

###  0.F.2  Making $G^{\prime}$ 4-regular

###### Lemma 12

Let $G^{\prime}=(V^{\prime},E^{\prime})$ be the graph constructed in Section
3. If $G^{\prime}$ is not $4$-regular, then we can add a polynomial number of
dummy nodes to $V^{\prime}$ and zero cost dummy edges to $E^{\prime}$ such
that $G^{\prime}$ becomes $4$-regular.

###### Proof

For every $g_{i}\in V^{\prime}$ with degree less than $4$ in $G^{\prime}$, we
add a dummy node $\bar{g}_{i}$ to $V^{\prime}$ and (possibly parallel) zero
cost edges $g_{i}\bar{g}_{i}$ to $E^{\prime}$ so that $g_{i}$ has degree $4$.
Observe that the dummy nodes in $V^{\prime}\backslash V(g_{1}\cup\dots\cup
g_{k})$ have degree at most $4$. For every dummy node $v\in V^{\prime}$ with
degree $1$ or $2$, we add a self loop of cost zero to $E^{\prime}$, increasing
the degree of $v$ by 2, so that $v$ has degree $3$ or $4$.

As the sum of degrees of nodes in $G^{\prime}$ is even, and all nodes in
$V^{\prime}$ have degree $3$ or $4$, we can see that there must be an even
number of degree $3$ dummy nodes. Therefore, we can pair up these dummy nodes
in an arbitrary manner and add zero cost edges to $E^{\prime}$ between these
pairs so that every node in $G^{\prime}$ has degree $4$.

###  0.F.3  Proof of Lemma 2

Let $G_{1}^{\prime},\dots,G_{k}^{\prime}$ be the subgraphs of
$G^{\prime\prime}$ found by Theorem 2.2.

  1. 1.

We consider cases defined by the edges of $H$ that are incident to
$G_{i}^{\prime}$:

     * •

$H$ has a loop on $G_{i}$. Then there is a link $f\in E[G_{i}^{\prime}]$ that
is the unique link in $F_{1}$ with an endpoint in $V(G_{i}^{\prime})$. For
each endpoint of $f$ that is a corner, by the construction of
$G^{\prime\prime}$ we create dummy nodes of these corners and change the
incident links in $\delta(G_{i}^{\prime})$ with links incident to these dummy
nodes instead. Therefore, $G_{i}^{\prime}$ will have degree $1$ or $2$ in
$G^{\prime\prime}$.

     * •

$H$ has two distinct (possibly parallel) edges incident to $G_{i}^{\prime}$,
denoted $f_{1}$ and $f_{2}$. Recall that we can observe that each corner is
satisfied by exactly one link $\ell_{i}$. Note that for every
$G_{i}^{\prime}\in\\{G_{1},\dots,G_{k}\\}$ that has degree $3$ or $4$, we can
see that that in $G^{\prime\prime}$, $G_{i}^{\prime}$ is incident to
$4-|\delta(G_{i}^{\prime})|\in\\{0,1\\}$ dummy edges using this observation.
Therefore, if the degree of $G_{i}^{\prime}$ in $G$ is 3, then $H$ must
contain at least one edge whose label is incident to $G_{i}^{\prime}$.
Similarly, if the degree of $G_{i}^{\prime}$ in $G$ is $4$, then both edges
incident to $G_{i}^{\prime}$ in $H$ have labels that are incident to
$G_{i}^{\prime}$ in $G$. In either case, we reduce the degree of
$G_{i}^{\prime}$ to $2$.

Therefore, when we create $G^{\prime\prime}$ by either removing edges in
$\delta(G_{i}^{\prime})\cap F_{1}$, or creating dummy nodes so that an edge in
$\delta(G_{i}^{\prime})$ is not incident to that dummy node, we reduce the
degree of $G_{i}^{\prime}$ to $1$ or $2$.

  2. 2.

Let $opt^{\prime\prime}$ denote the optimal solution to
$(G^{\prime\prime},4,L^{\prime\prime},c^{\prime\prime})$. The set of
obstructions of $G^{\prime\prime}$ is a (not necessarily strict) subset of the
obstructions of $G$, so edges of $opt$ (or corresponding edges created by
replacing nodes with dummy nodes) define a feasible solution to
$(G^{\prime\prime},4,L^{\prime\prime},c^{\prime\prime})$. Therefore,
$c(opt^{\prime\prime})\leq c(opt)$.

  3. 3.

Given $F$, we can find a partial solution $F_{2}$ to $(G,4,L,c)$ by taking the
edges of $F$ that are in both $E^{\prime\prime}$ and $E$, and the edges of
$F\cap E^{\prime\prime}$ that have a label in $E$. Clearly we have
$c(F_{2})=c^{\prime\prime}(F)$. The only obstructions that are uncovered by
$F_{2}$ are a subset of $N$, which are covered by $F_{1}$. Therefore, we have
a solution for $(G,L,c)$ of cost
$c(F_{2})+c(F_{1})=c^{\prime\prime}(F)+c(F_{1}).$

###  0.F.4  Proof of Lemma 3

To prove Lemma 3, we prove a slightly more general statement. We are given a
$4$-Obstruction Covering instance $(G,4,L,c)$ with subgraphs
$G_{1},\dots,G_{k}$ found by Theorem 2.2, and show that we can find in
polynomial time a partial solution $F$ that covers every degree $1$ or $2$
$G_{i}\in\\{G_{1},\dots,G_{k}\\}$ and every degree $3$ node for minimum cost
$c(F)$.

To see this, we will first show that there is a polynomial time reduction to
an instance of the $N$-Edge Cover problem $G^{\prime}=(V^{\prime},E^{\prime})$
with edge costs $c^{\prime}$ and optimal solution $F^{\prime}$, such that
$c^{\prime}(F^{\prime})=c(F)$.

First, we extend the definition of $c$ from $L$ to $E$ by setting
$c(e)=\infty$ for all $e\in E\backslash L$.

To construct the $N$-Edge Cover instance $G^{\prime}=(V^{\prime},E^{\prime})$
with edge costs $c^{\prime}$, we will replace each degree 1 or 2
$G_{i}\in\\{G_{1},\dots,G_{k}\\}$ with a certain subgraph with certain edge
costs, which we will call a degree $1$ gadget or degree $2$ gadget. We will
add all degree $3$ nodes to $N$, and a subset of the nodes of the gadgets to
$N$ and show that the optimal $N$-edge cover $F^{\prime}$ has cost
$c^{\prime}(F^{\prime})=c(F)$.

Initially, $G^{\prime}$ is equal to the subgraph induced on $G$ by the nodes
that are not in any degree 1 or 2 $G_{i}\in\\{G_{1},\dots,G_{k}\\}$. We then
consider degree 1 $G_{i}\in\\{G_{1},\dots,G_{k}\\}$ with corner $v$. We apply
Theorem 2.3 twice to the subgraph induced on $V(G_{i})$, subject to the
following requirements: 1) $v$ is covered by a link in $E[G_{i}]$, and 2) $v$
is not covered by a link in $E[G_{i}]$.

  * •

For the case where we require that $v$ is covered by a link in $E[G_{i}]$, we
define requirement function $h:V(G_{i})\rightarrow\\{0,1\\}$ by $h(v)=1$, and
for $u\in V(G_{i})\backslash\\{v\\}$, $h(u)=1$ if $u$ has degree $3$, and
$h(u)=0$ otherwise. We then apply Theorem 2.3 to the subgraph induced on
$V(G_{i})$, with edge weights $w(e)=c(e)$ for $e\in E[G_{i}]$ that do not have
$v$ as an endpoint and $w(e)=\infty$ for $e\in E[G_{i}]$ that have $v$ as an
endpoint, and requirement function $h$. We denote the cost of this by
$c_{1}^{i}$.

  * •

For the case where we require that $v$ is not covered by a link in $E(G_{i})$,
we define requirement function $h^{\prime}:V(G_{i})\rightarrow\\{0,1\\}$ by
$h^{\prime}(v)=0$, and for $u\in V(G_{i})\backslash\\{v\\}$, $h^{\prime}(u)=1$
if $u$ has degree $3$, and $h^{\prime}(u)=0$ otherwise. We then apply Theorem
2.3 to the subgraph induced on $V(G_{i})$, with edge weights
$w^{\prime}(e)=c(e)$ for $e\in E[G_{i}]$, and requirement function
$h^{\prime}$. We denote the cost of this by $c_{0}^{i}$.

We then add the nodes $v$, $v_{1}$, and $v_{0}$ to $V^{\prime}$, and add the
edges $v_{0}v_{1}$ and $v_{1}v$ to $E^{\prime}$, as well as the edge in
$\delta(G_{i})$ to $E^{\prime}$ (as this is a single edge incident to $v$). We
give these edges costs $c^{\prime}(v)=c(v)$,
$c^{\prime}(v_{0}v_{1})=c_{0}^{i}$ and $c^{\prime}(v_{1}v)=c_{1}^{i}$(see
Figure 4 (a) and (b)).We add $v$ and $v_{1}$ to $N$. We call this a degree $1$
gadget, with costs $c_{0}^{i}$ and $c_{1}^{i}$.

(a) $e$$v$ | (b) $e$$v$$c_{0}$$c_{1}$$v_{1}$$v_{0}$
---|---
(c) $e_{2}$$v_{2}$$v_{1}$$e_{1}$ | (d) $e_{2}$$v_{2}$$v_{1}$$e_{1}$$C^{\prime}$$C_{1}$$C_{2}$$C_{0}$$u_{0}$$u_{1}$
Figure 4: An example of the gadget for covering instances of degree 1 and 2
ladders. (a) a ladder $C$, with corner $v$. The minimum cost of covering all
obstructions but $v$ in $C$ is $c_{0}$, and the minimum cost of covering all
obstructions in $C$ is $c_{1}$. (b) the gadget where we replace $C$ with the
path $v_{0},v_{1},v$, with edge costs $c_{0}$ and $c_{1}$. (c) A ladder $C$
with corners $v_{1}$ and $v_{2}$. The minimum cost of covering: all
obstructions is $c_{1,2}$; of covering all obstructions but for $v_{1}$ is
$c_{2}$; of covering all obstructions but for $v_{2}$ is $c_{1}$; of covering
all but obstructions but for $v_{1}$ and $v_{2}$ is $c_{0}$. (d) the gadget
where we replace $C$ with the node $v_{1},v_{2},u_{1},u_{0}$, with edge costs
$c_{0}$, $c_{1}$, $c_{2}$, and $c_{1,2}-\min\\{c_{0},c_{1},c_{2}\\}$ .

We repeat this process of finding degree 1 gadgets for each degree 1
$G_{i}\in\\{G_{1},\dots,G_{k}\\}$.

Now consider degree 2 $G_{i}\in\\{G_{1},\dots,G_{k}\\}$, with corners $v_{1}$
and $v_{2}$. We apply Theorem 2.3 four times to the subgraph induced on
$V(G_{i})$, each time subject to one of the following requirements: 1) both
$v_{1}$ and $v_{2}$ are covered by links in $E[G_{i}]$; 2) $v_{1}$ is covered
by links in $E[G_{i}]$ but $v_{2}$ is not; 3) $v_{2}$ is covered by links in
$E[G_{i}]$ but $v_{1}$ is not, and; 4) neither $v_{1}$ nor $v_{2}$ are covered
by links in $E[G_{i}]$.

For each $v\in V(G_{i})$, we let $h(v)=1$ if $v$ is degree $3$ and $0$
otherwise. We apply Theorem 2.3 to the subgraph induced on $V(G_{i})$ in the
following ways:

  1. 1.

For the case that neither $v_{1}$ nor $v_{2}$ are covered by links in
$E[G_{i}]$, we define requirement function
$h_{0}:V(G_{i})\rightarrow\\{0,1\\}$ by $h_{0}(v_{1})=h_{0}(v_{2})=0$, and for
$u\in V(G_{i})\backslash\\{v_{1},v_{2}\\}$, $h_{0}(u)=1$ if $u$ is degree $3$,
and $h_{0}(u)=0$ otherwise. We define edge costs
$w_{0}:E[G_{i}]\rightarrow\mathbb{R}_{\geq 0}$, with $w_{0}(e)=c(e)$ for all
$e\in E[G_{i}]$ that are not incident to $v_{1}$ or $v_{2}$, and
$w_{0}(e)=\infty$ for $e\in E[G_{i}]$ that are incident to $v_{1}$ and
$v_{2}$. We apply Theorem 2.3 to the subgraph induced on $V(G_{i})$ with edge
costs $w_{0}$, and requirement function $h_{0}$, and denote the resulting cost
by $c_{0}^{i}$.

  2. 2.

For the case that both $v_{1}$ and $v_{2}$ are covered by links in $E[G_{i}]$,
we define requirement function $h_{12}:V(G_{i})\rightarrow\\{0,1\\}$ by
$h_{12}(v_{1})=h_{12}(v_{2})=1$, and for $u\in
V(G_{i})\backslash\\{v_{1},v_{2}\\}$, $h_{12}(u)=1$ if $u$ is degree $3$, and
$h_{12}(u)=0$ otherwise. We define edge costs
$w_{12}:E[G_{i}]\rightarrow\mathbb{R}_{\geq 0}$, with $w_{12}(e)=c(e)$ for all
$e\in E[G_{i}]$. We apply Theorem 2.3 to the subgraph induced on $V(G_{i})$
with edge costs $w_{12}$, and requirement function $h_{12}$, and denote the
resulting cost by $c_{12}^{i}$.

  3. 3.

For the case that $v_{1}$ is covered by links in $E[G_{i}]$ but $v_{2}$ is
not, we define requirement function $h_{1}:V(G_{i})\rightarrow\\{0,1\\}$ by
$h_{1}(v_{1})=1$, and $h_{1}(v_{2})=0$, and for $u\in
V(G_{i})\backslash\\{v_{1},v_{2}\\}$, $h_{1}(u)=1$ if $u$ is degree $3$, and
$h_{1}(u)=0$ otherwise. We define edge costs
$w_{1}:E[G_{i}]\rightarrow\mathbb{R}_{\geq 0}$, with $w_{1}(e)=c(e)$ for all
$e\in E[G_{i}]$ that are not incident to $v_{2}$, and $w_{1}(e)=\infty$ for
$e\in E[G_{i}]$ that are incident to $v_{2}$. We apply Theorem 2.3 to the
subgraph induced on $V(G_{i})$ with edge costs $w_{1}$, and requirement
function $h_{1}$, and denote the resulting cost by $c_{1}^{i}$.

  4. 4.

For the case that $v_{2}$ is covered by links in $E[G_{i}]$ but $v_{1}$ is
not, we define requirement function $h_{2}:V(G_{i})\rightarrow\\{0,1\\}$ by
$h_{2}(v_{1})=0$, and $h_{2}(v_{2})=1$, and for $u\in
V(G_{i})\backslash\\{v_{1},v_{2}\\}$, $h_{2}(u)=1$ if $u$ is degree $3$, and
$h_{2}(u)=0$ otherwise. We define edge costs
$w_{2}:E[G_{i}]\rightarrow\mathbb{R}_{\geq 0}$, with $w_{2}(e)=c(e)$ for all
$e\in E[G_{i}]$ that are not incident to $v_{1}$, and $w_{2}(e)=\infty$ for
$e\in E[G_{i}]$ that are incident to $v_{1}$. We apply Theorem 2.3 to the
subgraph induced on $V(G_{i})$ with edge costs $w_{2}$, and requirement
function $h_{2}$, and denote the resulting cost by $c_{2}^{i}$.

We now add to $V^{\prime}$ the nodes $v_{1}$ and $v_{2}$, and add the edges of
$\delta(G_{i})$ to $E^{\prime}$, with costs $c^{\prime}(v_{1})=c(v_{1})$ and
$c^{\prime}(v_{2})=c(v_{2})$. We also add nodes $u_{1}$ and $u_{0}$ to
$V^{\prime}$, and add edges $u_{0}u_{1},$ $u_{1}v_{1},$ $u_{1}v_{2},$
$v_{1}v_{2}$ to $E^{\prime}$ with costs $c^{\prime}(u_{0}u_{1})=c_{0}^{i}$,
$c^{\prime}(u_{1}v_{1})=c_{1}^{i}$, $c^{\prime}(u_{1}v_{2})=c_{2}^{i}$, and,
$c^{\prime}(v_{1}v_{2})=c_{1,2}^{i}-\min\\{c_{0}^{i},c_{1}^{i},c_{2}^{i}\\}$.
(See Figure 4.(c) and (d)).

Note that it is possible that $c^{\prime}(v_{1}v_{2})$ is negative, but as we
will see, this will not cause any problems. We call this subgraph of
$G^{\prime}$ a degree 2 gadget, with costs $c_{0}^{i}$, $c_{1}^{i}$,
$c_{2}^{i}$, and $c_{12}^{i}$ and add $u_{1},v_{1},$ and $v_{2}$ to $N$.
Lastly, we add every degree 3 node of $V^{\prime}$ to $N$.

We now wish to prove the following lemma

###### Lemma 13

For the $4$-Obstruction Covering instance $(G,4,L,c)$, there is a set of links
$F\subseteq L$, that covers every degree 1 or 2 $\\{G_{1},\dots,G_{k}\\}$ and
every degree 3 with minimum cost $c^{*}$ if and only if for the corresponding
$N$-Edge Cover instance, $(G^{\prime},c^{\prime})$, described above has an
optimal solution $F^{\prime}\subseteq E^{\prime}$ with cost $c^{*}$.

###### Proof

First, given a covering $F$ of degree $3$ nodes and degree 1 or 2 ladders and
hexagons of $G$ with minimum cost $c^{*}$, we will find an $N$-edge covering
$F^{\prime}$ of $G^{\prime}$ with cost $c^{*}$.

First, for every link $\ell\in F$ that is not in a degree 1 or 2
$G_{i}\in\\{G_{1},\dots,G_{k}\\}$, we add $\ell$ to our $N$-edge cover
$F^{\prime}$. Thus, $F^{\prime}$ covers every degree 3 node in $G^{\prime}$
that is not part of a gadget (and maybe some nodes that are) for the same cost
$F$ takes to cover.

Next, consider degree 1 or 2 $G_{i}\in\\{G_{1},\dots,G_{K}\\}$. If $G_{i}$ is
degree 1, then it is clear that $c(F\cup E[G_{i}])=c_{0}^{i}$ if $F\cap
E[G_{i}]$ does not cover the corner $v$ of $G_{i}$, and $c(F\cup
E[G_{i}])=c_{1}^{i}\\}$ if it does cover $v$. This follows by the construction
of the gadget and the definition of $c_{0}^{i}$ and $c_{1}^{i}$. Thus,
$F^{\prime}$ covers the nodes of the gadget with cost equal to that of $F$.

If $G_{i}$ is degree 2, then we can easily see the following by construction
of the gadget and the definition of $c_{0}^{i}$, $c_{1}^{i}$, $c_{2}^{i}$, and
$c_{1,2}^{i}$.

  1. 1.

If $F\cap E[G_{i}]$ covers neither $v_{1}$ nor $v_{2}$, then $c(F\cup
E[G_{i}])=c_{0}^{i}$.

  2. 2.

If $F\cap E[G_{i}]$ covers $v_{1}$ but not $v_{2}$, then $c(F\cup
E[G_{i}])=c_{1}^{i}$.

  3. 3.

If $F\cap E[G_{i}]$ covers $v_{2}$ but not $v_{1}$, then $c(F\cup
E[G_{i}])=c_{2}^{i}$.

  4. 4.

If $F\cap E[G_{i}]$ covers both $v_{1}$ and $v_{2}$, then $c(F\cup
E[G_{i}])=c_{1,2}^{i}$.

In cases $1-3$, we add to $F^{\prime}$ the edge of the degree 1 gadget that
has the corresponding cost. This covers $u_{1}$, and $F$ covers every degree
$3$ node, so it will use links in $\delta(G_{i})$ to cover whichever corner is
not covered by $F\cap E[G_{i}]$. Such an edge is added to $F^{\prime}$, so
$v_{1}$ and $v_{2}$ will also be covered by $F^{\prime}$.

In case $4$, we add the edge $v_{1}v_{2}$ to $F^{\prime}$ and the edge of
$\\{u_{0}u_{1},u_{1}v_{1},u_{1}v_{2}\\}$ with minimum cost, and by definition
of $c^{\prime}(v_{1}v_{2})$, $F^{\prime}$ has cost $c_{1,2}^{i}$ on the
gadget. Thus, $F^{\prime}$ covers the nodes of the gadget with cost equal to
that of $F$.

Therefore, we have $c^{\prime}(F^{\prime})=c(F)=c^{*}$. So it remains to show
that given a solution $F^{\prime}$ with minimum cost $c^{*}$, we can find a
set of links $F\subseteq L$ with cost $c(F)=c^{*}$ that satisfies the claim.

Given an $N$-edge covering $F^{\prime}$ of $G^{\prime}$ of minimum cost
$c^{\prime}(F^{\prime})=c^{*}$, we will find a set of edges $F\subseteq E$
that cover the degree $3$ nodes of $G$ and the degree $1/2$ ladders/hexagons
with cost $C^{*}$. We begin with $F=\emptyset$ and will add to $F$ step by
step.

First, for every edge $e\in F^{\prime}$ that is not in a gadget we add $e$ to
$F$. So $F$ covers every degree 3 node not in a degree 1 or 2
$G_{i}\in\\{G_{1},\dots,G_{k}\\}$.

We now show how to use $F^{\prime}$ to add edges to $F$ that cover degree 1 or
2 $G_{i}\in\\{G_{1},\dots,G_{k}\\}$.

#### Case 1:

First consider the case where $G_{i}$ is degree 1, and the corresponding
degree 1 gadget in $G^{\prime}$ has costs $c_{0}^{i}$ and $c_{1}^{i}$. Let $v$
denote the corner of $G_{i}$ and denote the nodes of the corresponding gadget
by $v,v_{0},v_{1}$. We consider in which cases the edges $v_{0}v_{1},v_{1}v$
are in $F^{\prime}$.

  * •

Case: $v_{0}v_{1},v_{1}v\notin F^{\prime}$. The node $v_{1}\in N$ is not
covered by $F^{\prime}$ and thus $F^{\prime}$ is not a feasible $N$-edge
cover.

  * •

Case: $v_{1}v\in F^{\prime}$. We add to $F$ the edges found by applying
Theorem 2.3 to $E[G_{i}]$ with covering requirements $h$ and edge weights $w$.
Thus, $F$ covers every square of $G_{i}$ and every degree $3$ node of $G_{i}$
with cost $c(G_{i}\cap F)=c_{1}^{i}=c^{\prime}(v_{1}v)$.

  * •

Case: $v_{0}v_{1}\in F^{\prime}$. We add to $F$ the edges found by applying
Theorem 2.3 to $E[G_{i}]$ with covering requirements $h^{\prime}$ and edge
weights $w^{\prime}$. Thus, $F\cap E[G_{i}]$ covers every square of $G_{i}$
and every degree 3 node of $G_{i}$ except $v$ with cost $c(G_{i}\cap
F)=c_{0}^{i}=c^{\prime}(v_{0}v_{1})$. Note that since $F^{\prime}$ covers $v$
but does not contain $v_{1}v$, it must contain the edge in $\delta(G_{i})$,
which is incident to $v$ and is in $F$ by construction.

  * •

Case: $v_{0}v_{1},v_{1}v\in F^{\prime}$. Since $v_{0}\notin N$, we can
conclude that at least one of $c_{0}^{i}$ or $c_{1}^{i}$ is equal to $0$.
Thus, we can remove $v_{0}v_{1}$ from $F^{\prime}$ for no increase in cost or
loss of feasibility and apply Case 2.

Thus, for any degree 1 $G_{i}\in\\{G_{1},\dots,G_{k}\\}$, $F$ covers the
squares of $G_{i}$ and the degree 3 nodes of $G_{i}$ with the same cost as
$F^{\prime}$ cover the corresponding degree 1 gadget.

#### Case 2:

Now, suppose that $G_{i}$ is degree 2, and the corresponding degree 2 gadget
in $G^{\prime}$ has costs $c_{0}^{i},c_{1}^{i},c_{2}^{i},$ and $c_{12}^{i}$.
Denote by $v_{1},v_{2}\in V(G_{i})$ the corners of $G_{i}$. We consider in
which cases the edges $u_{0}u_{1},u_{1}v_{1},u_{1}v_{2},$ and $v_{1}v_{2}$ are
in $F^{\prime}$.

  * •

Case: $\delta(u_{1})\cap F^{\prime}=\\{v_{1}v_{2}\\}$. We add to $F$ the edges
found by applying Theorem 2.3 to $E[G_{i}]$ with covering requirements
$h_{12}$ and edge weights $w_{12}$. Thus, $F$ covers every square and degree 3
node of $G_{i}$ with cost $c_{12}^{i}$. Note that since $u_{1}\in N$,
$F^{\prime}$ contains an edge of $\delta(u_{1})$ of least cost, the cost of
$F^{\prime}$ on the gadget is
$c^{\prime}(v_{1}v_{2})+\min\\{u_{1}v_{1},u_{1}v_{2},u_{0}u_{1}\\}=c_{12}^{i}$.
For the remaining cases, we assume $v_{1}v_{2}\notin F^{\prime}$.

  * •

Case: $\delta(u_{1})\cap F^{\prime}=\\{u_{1}v_{1}\\}$. We add to $F$ the edges
found by applying Theorem 2.3 to $E[G_{i}]$ with covering requirements $h_{1}$
and edge weights $w_{1}$. Thus, $F\cap E[G_{i}]$ covers every square of
$G_{i}$, every degree 3 node in $V(G_{i})$ including $v_{2}$, but not $v_{1}$,
with cost $c(G_{i}\cap F)=c_{1}^{i}$. Note that since $F^{\prime}$ covers
$v_{1}$ and $v_{2}$, but the gadget does not contain $v_{1}v_{2}$ or
$u_{1}v_{2}$, that $F^{\prime}$ must contain the edge of $\delta(G_{i})$ that
is incident to $v_{2}$, and thus $F$ also contains that edge. Thus, $F$ covers
every degree $3$ node and every square of $G_{i}$.

  * •

Case: $\delta(u_{1})\cap F^{\prime}=\\{u_{1}v_{2}\\}$. This case can be
handled similarly to Case 2.

  * •

Case: $\delta(u_{1})\cap F^{\prime}=\\{u_{0}u_{1}\\}$. We add to $F$ the edges
found by applying Theorem 2.3 to $E[G_{i}]$ with covering requirements $h_{0}$
and edge weights $w_{0}$. Thus, $F\cap E[G_{i}]$ covers every square of
$G_{i}$ and every degree 3 node except $v_{1}$ and $v_{2}$. Note that since
$F^{\prime}$ covers $v_{1}$ and $v_{2}$, it must contain both edges of
$\delta(G_{i})$, and thus by construction $F$ contains those edges as well and
thus covers every degree 3 node of $G_{i}$.

  * •

Case: $|\delta(u_{1})\cap F^{\prime}|\geq 2$. If $u_{0}u_{1}\in F^{\prime}$,
then we can remove it from $F^{\prime}$ for no loss of feasibility, and no
increase in the cost of $F^{\prime}$. If, after removing $u_{0}u_{1}$,
$|\delta(u_{1})\cap F^{\prime}|=1$, then $\delta(u_{1})\cap
F^{\prime}\in\\{u_{1}v_{1},u_{1}v_{2}\\}$ and we can consider either Case 2 or
3. So assume that $\delta(u_{1})\cap F^{\prime}=\\{u_{1}v_{1},u_{1}v_{2}\\}$.
Without loss of generality assume that $c_{1}^{i}\leq c_{2}^{i}$.

It is clear that $c_{12}^{i}\leq c_{1}^{i}+c_{2}^{i}$, and thus we can replace
$u_{1}v_{2}$ with $v_{1}v_{2}$ for a change in the cost of $F^{\prime}$ on the
degree 2 gadget from
$c^{\prime}(u_{1}v_{1})+c^{\prime}(u_{1}v_{2})=c_{1}^{i}+c_{2}^{i}$ to
$c^{\prime}(u_{1}v_{1})+c^{\prime}(v_{1}v_{2})=c_{1}^{i}+c_{12}^{i}-\min\\{c_{0}^{i},c_{1}^{i},c_{2}^{i}\\}\leq
c_{12}^{i}\leq c^{\prime}(u_{1}v_{1})+c^{\prime}(u_{1}v_{2})$. Clearly, the
feasibility of $F^{\prime}$ is maintained, and we can apply Case 1 to this
gadget.

Thus, for any degree 2 $G_{i}\in\\{G_{1},\dots,G_{k}\\}$, $F$ covers the
squares of $G_{i}$ and the degree 3 nodes of $G_{i}$ with the same cost as
$F^{\prime}$ cover the corresponding degree 2 gadget.

Therefore, given minimum $N$-edge cover $F^{\prime}$ of $G^{\prime}$ of cost
$c^{*}$, we can find edges $F\subseteq E$ of $G$ that cover every degree 3
node and every square of degree 1 or 2 $G_{i}\in\\{G_{1},\dots,G_{k}\\}$.

The proof of Lemma 3 follows directly from Lemma 13.

##  Appendix 0.G  Missing proofs of Section 4

This section includes the missing proofs of Section 4.

###  0.G.1  Proof of Lemma 4

This proof follows directly from Lemma 13 where $G$ has edge costs $c(e)=1$ if
$e\in L$ and $c(e)=\infty$ if $e\notin L$.

###  0.G.2 Proof of Lemma 5

We begin by defining notation. For a square $S$, we call a corner $u\in V(S)$
a _good_ node if there is a corner $v\in V(S)$ such that $uv\in L$, and we say
$u$ is a bad node otherwise (recall that a node of $V(S)$ is a corner if it is
incident to an edge in $\delta(S)$). Note that the nodes of $V(S)$ that are
not corners are neither good nor bad. Note that since no links are necessary,
all nodes of a degree 4 ladder are good nodes.

We find $APX$ by performing a sequence of steps. We begin with step 1 where we
set $APX_{1}=EC_{3}$, $Y_{1}=\emptyset$, and $\mathcal{H}_{1}$ equal to the
subset of $\\{G_{1},\dots,G_{k}\\}$ whose squares are covered by $APX_{1}$.
For each step $i$, $i\geq 2$, we define

  * •

$APX_{i}\subseteq L$ to be a partial solution;

  * •

$\mathcal{H}_{i}\subseteq\\{G_{1},\dots,G_{k}\\}$ to be the set of ladders
whose squares are covered by $APX_{i}$;

  * •

$Y_{i}$ to be the subset of edges $\subseteq
APX_{i}\cap\delta(G[\mathcal{H}_{i}])$ such that every $y\in Y_{i}$ has an
endpoint in $R$.

Our goal is to compute $APX_{i}$ at $i$-th step, $i\geq 2$, such that the
following holds:

  1. (1)

The obstructions covered by $APX_{i-1}$ are a strict subset of those covered
by $APX_{i}$;

  2. (2)

$|APX_{i}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|\leq\frac{4}{3}|EC_{3}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|$, and $APX_{i}\backslash(Y_{i}\cup
E[\mathcal{H}_{i}])=EC_{3}\backslash(Y_{i}\cup E[\mathcal{H}_{i}])$.

Note that since $APX_{i}$ covers the obstructions covered by $APX_{i-1}$, we
must have $\mathcal{H}_{i-1}\subseteq\mathcal{H}_{i}$. If in iteration $i$, we
have $\mathcal{H}_{i}=\\{G_{1},\dots,G_{k}\\}$, then we are done as $APX_{i}$
covers every obstruction. If
$\mathcal{H}_{i}\subsetneq\\{G_{1},\dots,G_{k}\\}$, then we will find some
$G_{s}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$, and using $G_{s}$,
we will find $APX_{i+1}$, $\mathcal{H}_{i+1}$, and $Y_{i+1}$.

We will consider three cases for $G_{s}$, for which we now provide a brief
description. First, if $G_{s}$ has two nodes that are adjacent to nodes in $R$
or in $\mathcal{H}_{i}$. Second, if a good node of $G_{s}$ is adjacent to a
good node of some $G_{t}\notin\mathcal{H}_{i}$. And finally, if neither of the
previous cases hold, then we show $G_{s}$ is degree 3 and that a good node of
$G_{s}$ must be adjacent to a bad node of some degree 3 ladder
$G_{t}\notin\mathcal{H}_{i}$. In all cases, we will be able to find at least
three links in $\delta(G_{s})$ (and possibly $\delta(G_{t})$), such that, by
adding links to cover $G_{s}$ (and possibly $G_{t}$), we can charge the
addition of these new links to the links in $\delta(G_{s})$ (and possibly
$\delta(G_{t})$) for a $\frac{4}{3}$ fractional increase.

Case 1: there exists
$G_{s}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$, such that $G_{s}$
has two nodes that are adjacent to either a node in $R$ or in
$\mathcal{H}_{i}$. Since $G_{s}$ is degree at least $3$, there are links
$\\{\ell,\ell_{1},\ell_{2}\\}\subseteq\delta(G_{s})\cap APX_{i}$. Without loss
of generality, let the links $\ell_{1}$ and $\ell_{2}$ be the ones incident to
nodes in $\mathcal{H}_{i}$ or in $R$.

Since no links are necessary, there is a link $e\in E(G_{s})$ that shares an
endpoint with $\ell$, and we start with $APX_{i+1}\leftarrow
APX_{i}\cup\\{e\\}$. Note that this ensures that $G_{s}$ is in
$\mathcal{H}_{i+1}$, and so $\mathcal{H}_{i}\subsetneq\mathcal{H}_{i+1}$.

If any of $\ell_{1}$, $\ell_{2}$ or $\ell$ are incident to a node in $R$, then
that link is in $Y_{i+1}$. Assume $\ell$ is incident to some ladder $G_{t}$.
If $G_{t}\in\mathcal{H}_{i}$, we are done this iteration. If not, we are going
to change $APX_{i+1}$ by swapping two edges. Since $\ell$ is not necessary,
there is link $f\in E(G_{t})$ sharing an endpoint with $\ell$. We replace
$\ell$ with $f$ in $APX_{i+1}$, and so also $G_{t}$ will be in $H_{i+1}$.
Since the endpoints of $\ell$ are covered in $APX_{i+1}$ by either $\ell$ or
$\\{e,f\\}$, the obstructions in $G_{s}$ are covered, and all other
obstructions of $APX_{i}$ are covered by $APX_{i+1}$, $(1)$ holds (See Figure
5).

(a) $G_{s}$$G_{t}$$\ell$$e$$f$$\ell_{1}$$\ell_{2}$ | (b) $G_{t}$$G_{s}$$e$$G_{y}$$v^{\prime}$$u^{\prime}$$v$$u$$\ell$
---|---
Figure 5: In both figures $APX_{i}$ is shown as bold edges. The red edges are
not links.
(a) Ladder $G_{s}$ adjacent to two lonely nodes and ladder $G_{t}$. We can see
$\\{\ell,\ell_{1},\ell_{2}\\}=\delta(G_{s})$. We can add $f$ and replace
$\ell$ with $e$, charge the addition of $f$ to $\ell,\ell_{1},\ell_{2}\\}$ for
an increase from $3$ links to $4$, but covering both $G_{s}$ and $G_{t}$. (b)
Ladders $G_{s}$ and $G_{t}$ with adjacent good nodes $v$ and $v^{\prime}$. We
add $uv$ and $u^{\prime}v^{\prime}$ to $APX_{i+1}$ and remove $vv^{\prime}$,
and we replace $\ell$ with $e$. Charging the addition of $vv^{\prime}$ and $e$
to $\ell,vv^{\prime},$ and the edge incident to $u^{\prime}$.

By constructions of $APX_{i}$ and $APX_{i+1}$, we have

$\displaystyle APX_{i+1}\backslash(Y_{i+1}\cup E[\mathcal{H}_{i+1}])$
$\displaystyle=APX_{i}\backslash(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])=EC_{3}\backslash(Y_{i+1}\cup E[\mathcal{H}_{i+1}])$

To see that $|APX_{i+1}\cap(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])|\leq\frac{4}{3}|EC_{3}\cap(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])|$, observe that

$\displaystyle|EC_{3}\cap(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])|-|EC_{3}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|\coloneqq\Delta\geq 3$

where the inequality follows since $\ell,\ell_{1},\ell_{2}\notin
EC_{3}\cap(Y_{i}\cup E[\mathcal{H}_{i}])$, but are in $EC_{3}\cap(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])$. Similarly, the following inequality follows since
$APX_{i+1}\cap(Y_{i+1}\cup E[\mathcal{H}_{i+1}])$ contains
$\ell_{1},\ell_{2},e$ and exactly one of $f$ or $\ell$.

$\displaystyle|APX_{i+1}\cap(Y_{i+1}\cup
E[\mathcal{H}_{i+1}])|-|APX_{i}\cap(Y_{i}\cup E[\mathcal{H}_{i}])|=\Delta+1$

So as $i$ increases by one, the increase on the right hand side of the
inequality of (2) is at most $\frac{4}{3}$ the increase on the left hand side.
Thus, (2) holds.

#### Case 2:

there exist $G_{s},G_{t}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$
such that a good node of $G_{s}$ is adjacent to a good node of $G_{t}$. Let
$u,v\in G_{s}$ and $u^{\prime},v^{\prime}\in G_{t}$ be good nodes such that
$vv^{\prime}\in L$. Since $v$ and $v^{\prime}$ are degree $3$ nodes that are
covered by $APX_{i}$, we see $vv^{\prime}\in APX_{i}$. We set
$APX_{i+1}\leftarrow
APX_{i}\cup\\{uv,u^{\prime}v^{\prime}\\}\backslash\\{vv^{\prime}\\}$. In this
case, we see that $G_{s}$ and $G_{t}$ are in $\mathcal{H}_{i+1}$, and so
$\mathcal{H}_{i}\subsetneq\mathcal{H}_{i+1}$.

Since $u$ and $u^{\prime}$ are good nodes, they are incident to links
$\ell\in\delta(G_{s})$ and $\ell^{\prime}\in\delta(G_{t})$ respectively. If
$\ell$ (resp. $\ell^{\prime}$) is incident to a node in $R$, then $\ell$
(resp. $\ell^{\prime}$) is in $Y_{i+1}$. Assume $\ell$ is incident to some
$G_{x}$ (the case for $\ell^{\prime}$ can be handled similarly if
$\ell^{\prime}$ is incident to some $G_{y}$). If $G_{x}=G_{t}$ (similarly if
$G_{y}=G_{s}$), then the endpoint of $\ell$ in $G_{t}$ cannot be adjacent to
$v^{\prime}$ or else $G[G_{t}\cup G_{s}]$ forms a ladder of length $3$,
contradicting our assumption on $G$.

If $G_{x}\in\mathcal{H}_{i}$, then $G_{x}$ is covered by $APX_{i}$ and we are
done. If $G_{x}\notin\mathcal{H}_{i}$, then $G_{x}$ is not covered by
$APX_{i}$, and since no links are necessary, there is a link $e\in E(G_{x})$
that is adjacent to $\ell$. We remove $\ell$ from $APX_{i+1}$ and add $e$, and
so $G_{x}$ is in $\mathcal{H}_{i+1}$. Since both endpoints of $\ell$ are
covered by $uv$ and $e$, $APX_{i+1}$ covers the obstructions covered by
$APX_{i}$ as well as the obstructions in $G[\mathcal{H}_{i+1}\cup Y_{i+1}]$.
(See Figure 5.)

By a similar argument to the first case, we can see that (1) and (2) hold.

#### Case 3:

Neither of the above cases hold. In this case we wish to show that every
$G_{s}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$ is degree $3$, and
that there exists a $G_{t}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$
such that $G_{t}$ has a good node that is adjacent to a bad node of $G_{s}$.
First, recall that every node of a degree 4 ladder is a good node.

First, we show that the ladders $G_{s}$ and $G_{t}$ described always exist
when cases 1 and 2 do not hold. We denote by $X_{3}$ the set of degree $3$
ladders in $\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$. Denote by $N$
the set of links between a good node and a bad node of different ladders in
$\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$. The following claim will
show that the degree 3 ladders that are not covered by $APX_{i}$ has the same
size as $N$.

###### Claim

$|X_{3}|=|N|$

###### Proof

In order to show that $|X_{3}|\geq|N|$, we show that every ladder of degree at
least three has at most one bad node. This follows from the fact that as there
exists no necessary links, then at least two of the three edges incident to
every corner of a square must be links. Therefore, in a ladder of degree four
all corners are good, and in a ladder of degree three at most one corner is
bad.

To see $|X_{3}|\leq|N|$, we first note since case 1 does not hold, a ladder in
$\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$ is adjacent to at most one
of: a lonely node, or, a ladder in $\mathcal{H}_{i}$. Secondly, since case 2
does not hold, the good nodes of ladders in $X_{3}$ are not adjacent to the
good nodes of any ladder in
$\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$. Therefore, every degree 3
ladder in $\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$ has at least one
good node adjacent to a bad node of another degree 3 ladder, and thus
$|X_{3}|\leq|N|$. And the claim is proven.

Therefore, since $|X_{3}|=|N|$, one of the good nodes of each degree 3 ladder
in $X_{3}$ is adjacent to a bad node of a ladder in $X_{3}$, and furthermore,
the other good node must be adjacent to a node in $R$ or a ladder in
$\mathcal{H}_{i}$. Since each bad node is adjacent to a degree 3 ladder, the
good nodes of degree 4 ladders can only be adjacent to either good nodes,
nodes in $R$, or elements of $\mathcal{H}_{i}$, and thus must be covered by
$APX_{i}$ since neither case (1) nor (2) hold. Therefore,
$X_{3}=\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$.

We now consider degree 3 ladder
$G_{s}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$ with bad node
$s_{1}$, and good nodes $s_{2},s_{3}$, where $s_{3}$ is adjacent to a node in
$R$ or a node in $\mathcal{H}_{i}$. And let $s_{4}$ be the node of $G_{s}$
that is not a corner. Note that $s_{1}s_{4}$ must be a link since there are no
necessary links and $s_{1}s_{2}$ cannot be a link by the definition of bad
nodes.

By the argumentation above, there is a degree 3 ladder
$G_{t}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$ with bad node
$t_{1}$, and good nodes $t_{2},t_{3}$, where $t_{3}$ is adjacent to a node in
$R$ or a node in $\mathcal{H}_{i}$, such that $s_{1}t_{2}\in APX_{i}$. Let
$e\in\delta(G_{s})\cap APX_{i}$ be incident to $s_{3}$, and
$f\in\delta(G_{t})\cap APX_{i}$ be incident to $t_{3}$. We let
$APX_{i+1}\leftarrow
APX_{i}\cup\\{s_{1}s_{4},t_{2}t_{3}\\}\backslash\\{s_{1}t_{2}\\}$, and so
$G_{s}$ and $G_{t}$ are in $\mathcal{H}_{i+1}$, and
$\mathcal{H}_{i}\subsetneq\mathcal{H}_{i+1}$. The link $e$ (resp. $f$) is in
$Y_{i+1}$ if $e$ (resp. $f$) is incident to a node in $R$. By a similar
argument to the first case we can see that $APX_{i+1}$, $Y_{i+1}$, and
$\mathcal{H}_{i+1}$ satisfy (1) and (2).

Note that for every $i\geq 1$, by (2) we have

$\displaystyle|APX_{i}|$ $\displaystyle=|APX_{i}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|+|APX_{i}\backslash(Y_{i}\cup E[\mathcal{H}_{i}])|$
$\displaystyle\leq\frac{4}{3}|EC_{3}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|+|EC_{3}\backslash(Y_{i}\cup
E[\mathcal{H}_{i}])|\leq\frac{4}{3}|EC_{3}|$

Furthermore, in each iteration we cover a new element of
$\\{G_{1},\dots,G_{k}\\}$, so after a polynomial number of iterations we will
have $\mathcal{H}_{i}=\\{G_{1},\dots,G_{k}\\}$ and we have covered every
obstruction.

###  0.G.3  Proof of Theorem 4.1

We apply Theorem 2.2 to decompose instance $(G,4,L)$ into hexagons and ladders
$G_{1},\dots,G_{k}$, and lonely nodes $R$.

We first find a partial solution $EC_{3}$ as described in Section 4 that
covers degree 3 nodes and degree 1 or 2 $G_{i}\in\\{G_{1},\dots,G_{k}\\}$ by
applying Lemma 4. We next prove Lemma 14 which shows that with $EC_{3}$ we can
find another partial solution $APX_{1}$ that covers every
$G_{i}\in\\{G_{1},\dots,G_{k}\\}$ with degree at least 2 by increasing the
number of links on $G_{i}$ by a $\frac{4}{3}$ fraction, leaving the solution
equal elsewhere. Finally, we can apply Lemma 5 to cover the remaining
$G_{i}\in\\{G_{1},\dots,G_{k}\\}$ that contain obstructions not covered by
$APX_{1}$ to find a feasible solution $APX_{2}$. Then we will show that
$APX_{2}$ has cost at most $\frac{4}{3}c|opt|$.

######  Lemma 14 ()

Consider an unweighted $4$-Obstruction Covering instance $(G,4,L)$, that
contains no ladder or hexagon of degree $1$ or $2$, with subgraphs
$R,G_{1},\dots,G_{k}$, found by Theorem 2.2. Consider partial solution
$EC_{3}\subseteq L$ that covers every degree $3$ node of $G$, but every
$G_{s}\in\\{G_{1},\dots,G_{k}\\}$ contains an obstruction that is not covered
by $EC_{3}$. We can find in polynomial time, the following:

  1. 1.

A (potentially infeasible) solution $APX\subseteq L$;

  2. 2.

A subset $\mathcal{H}\subseteq\\{G_{1},\dots,G_{k}\\}$ containing all hexagons
and ladders of length at least $2$, such that $APX$ covers every obstruction
in $G[\mathcal{H}]$, and;

  3. 3.

A subset $Y\subseteq APX\cap\delta(G[\mathcal{H}])$, such that, every $y\in Y$
has an endpoint in $R$

such that, $|APX\cap(Y\cup E[\mathcal{H}])|\leq\frac{4}{3}|EC_{3}\cap(Y\cup
E[\mathcal{H}])|$, and $APX\backslash(Y\cup
E[\mathcal{H}])=EC_{3}\backslash(Y\cup E[\mathcal{H}])$.

###### Proof

We find $APX$ by performing a sequence of steps. We begin with step 1 where we
set $APX_{1}=EC_{3}$, $Y_{1}=\emptyset$, and $\mathcal{H}_{1}=\emptyset$. For
each step $i$, $i\geq 2$, we define

  * •

$APX_{i}\subseteq L$ to a be a partial solution;

  * •

$\mathcal{H}_{i}\subseteq\\{G_{1},\dots,G_{k}\\}$ contains the set of ladders
and hexagons whose obstructions are covered by $APX_{i}$, as well as the the
set of ladders and hexagons that contain an obstruction covered by $APX_{i}$
but not covered by $APX_{i-1}$;

  * •

$Y_{i}$ to be the subset of edges $\subseteq
APX_{i}\cap\delta(G[\mathcal{H}_{i}])$ such that every $y\in Y_{i}$ has an
endpoint in $R$.

Our goal is to compute $APX_{i}$ at the $i$-th step, $i\geq 2$, such that the
following holds:

  1. (1)

The obstructions covered by $APX_{i-1}$ are a strict subset of those covered
by $APX_{i}$;

  2. (2)

$|APX_{i}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|\leq\frac{4}{3}|EC_{3}\cap(Y_{i}\cup
E[\mathcal{H}_{i}])|$, and $APX_{i}\backslash(Y_{i}\cup
E[\mathcal{H}_{i}])=EC_{3}\backslash(Y_{i}\cup E[\mathcal{H}_{i}])$.

Note that since $APX_{i}$ covers the obstructions covered by $APX_{i-1}$ we
have $\mathcal{H}_{i-1}\subseteq\mathcal{H}_{i}$, and since
$EC_{3}=\mathcal{H}_{1}$ already covers every degree 3 node, we must have
$\mathcal{H}_{i-1}\subsetneq\mathcal{H}_{i}$. If in iteration $i$, every
obstruction in a ladder or hexagon $G_{s}\in\mathcal{H}_{i}$ is covered, and
$\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$ contains no hexagons or
ladders of length at least $2$, then we define
$\mathcal{H}\coloneqq\\{G_{s}\in\mathcal{H}_{i}|\text{every obstruction of
}G_{s}\text{ is covered}\\}$, $APX\coloneqq APX_{i}$, and $Y\coloneqq Y_{i}$
and we are done. Otherwise, we will find a hexagon or ladder of length at
least 2, and use it to find $APX_{i+1},\mathcal{H}_{i+1}$, and $Y_{i+1}$.

Let $G_{s}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$ be a hexagon or
ladder of length at least 2. We will consider the cases for $G_{s}$. First, we
will deal with the cases that $G_{s}$ contains a hexagon. Then, we will assume
that $\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$ contains no hexagons,
and will consider the case where $G_{s}$ is a ladder of length at least $2$.

In both cases, for every link we add, we will be able to find at least three
links in $\delta(G_{s})$ (and possibly $\delta(G_{t}))$), such that, by adding
links to cover $(G_{s})$ (and possibly $(G_{t})$), we can charge the addition
of these new links to the links in $\delta(G_{s})$ (and possibly
$\delta(G_{t})$) for a $\frac{4}{3}$ fractional increase.

#### Case: $G_{s}$ contains a hexagon.

First, suppose $G_{s}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$
contains a hexagon. By definition, a hexagon has exactly four degree 3 nodes
whose neighbourhoods are in the hexagon. Moreover, the subgraph induced on
these nodes forms a claw (see the nodes $\\{u_{1},u_{2},u_{2},v_{0}\\}$ in
Figure 6). Therefore, in order for $EC_{3}$ to cover each of the corresponding
nodes in the hexagon of $G_{s}$, there must be at least three links
$\ell_{1},\ell_{2},\ell_{3}\in EC_{3}\cap E[G_{s}]$. By definition of
$APX_{i}$, we must have $\ell_{1},\ell_{2},\ell_{3}\in APX_{i}$. Let
$S\subseteq G_{s}$ denote the square that is not covered by $\mathcal{H}_{i}$.
Since no links are necessary, there is a link $\ell\in E[S]\cap L$. See Figure
6 for a visual example of this step.

(a) $v_{1}$$v_{0}$$v_{2}$$v_{3}$$S$$u_{1}$$u_{2}$$u_{3}$ | (b) $v_{1}$$v_{2}$$v_{r}$$v_{r+1}$$u_{1}$$u_{2}$$u_{r}$$u_{r+1}$
---|---
Figure 6: (a) A hexagon, with uncovered square $S$ shown in green edges. The
nodes $v_{0},v_{1},v_{2}$ and $v_{3}$ are degree three and must be covered by
links that are in $E(S)$ (example links are shown with dashed red lines). To
cover $S$ we can select an edge $\ell\in E(S)$ and add it to the solution,
charging its addition to the dashed edges in $G_{s}$.
(b) A ladder of length at least 2. Edges that are not links are shown in red,
and edges that are links are shown in black. In this case, both of the squares
$S_{1}$ and $S_{r}$ may be blockers depending on which links are in our
initial partial solution, since the nodes $v_{1},u_{1},$ and $v_{r+1}$ are
degree 3 but the edges $v_{1}v_{2}$, $u_{1}u_{2}$, and $v_{r}v_{r+1}$ are not
links.

We set $APX_{i+1}\leftarrow APX_{i}\cup\\{\ell\\}$. Therefore,
$\mathcal{H}_{i}\subsetneq\mathcal{H}_{i+1}$, since $\mathcal{H}_{i+1}$
contains $G_{s}$, and $APX_{i+1}$ satisfies condition (1). By construction, we
have

$\displaystyle|APX_{i+1}\backslash E[G_{s}]|=|APX_{i}\backslash
E[G_{s}]|,\hskip 13.0pt|APX_{i+1}\cap E[G_{s}]|=|APX_{i}\cap E[G_{s}]|+1$

Therefore, we have that

$\displaystyle 3$
$\displaystyle\leq|EC_{3}\cap(Y_{i+1}\cup\mathcal{H}_{i+1})|-|EC_{3}\cap(Y_{i}\cup\mathcal{H}_{i})|\coloneqq\Delta$
$\displaystyle 4$
$\displaystyle\leq|APX_{i+1}\cap(Y_{i+1}\cup\mathcal{H}_{i+1})|-|APX_{i}\cap(Y_{i}\cup\mathcal{H}_{i})|=\Delta+1$

So the left hand side of our desired inequality increases by at least
$\Delta+1$, while the left hand side increases by at least
$\frac{4}{3}\Delta$. We can see that $\Delta\geq 3$ since
$\ell,\ell_{1},\ell_{2}\in EC_{3}$, so the desired inequality holds.

#### Case: the set $\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$ contains
no hexagons at all.

So $G_{s}$ is a ladder of length at least 2 with no hexagon. Applying Theorem
2.2, let $G_{s}$ have consistent labelling
$v_{1},\dots,v_{r+1},u_{1},\dots,u_{r+1}$. Enumerate the squares of $G_{s}$ as
$S_{j}=v_{j}u_{j}u_{j+1}v_{j+1}$, for $j=1,\dots,r$. Furthermore, we assume
that if exactly one of $S_{1}$ and $S_{r}$ are not covered by $APX_{i}$, the
consistent labelling of $G_{s}$ is given such that $S_{r}$ is uncovered.

To find $APX_{i+1}$, we will cover $G_{s}$ in a sequence of steps, iteratively
guaranteeing that the squares of $G_{s}$ are covered one by one in increasing
order of index. To do this, we will begin with a partial solution
$F_{0}\coloneqq APX_{i}$ and will find a sequence of partial solutions
$F_{0},F_{1},F_{2},\dots$. These solutions will satisfy the requirement that
$F_{\sigma}$ covers the obstructions covered by $F_{0},\dots,F_{\sigma-1}$,
and if $F_{\sigma-1}$ contains a square $S_{j}$ of least index that is not
covered, then $F_{\sigma}$ will cover $S_{j}$. Therefore, after at most $r+1$
iterations, we will have computed $F_{0},\dots,F_{\sigma}$, and $F_{\sigma}$
will cover every obstruction of $G_{s}$ and we can set $APX_{i+1}\coloneqq
F_{\sigma}$.

We will show that if we must add a link $\ell$ to $F_{\sigma}$ we can either
remove an edge from $APX_{i}$ or find a set of at least 3 links
$\ell_{1},\ell_{2},\ell_{3}\in APX_{i}$ to charge the addition of $\ell$ to.
We guarantee the following about $\ell_{1},\ell_{2},\ell_{3}$ and
$F_{\sigma}$;

  * (a)

$\ell_{1},\ell_{2},\ell_{3}\in EC_{3}$;

  * (b)

$\ell_{1},\ell_{2},\ell_{3}\in E(G_{s})\cup\delta(G_{s})$;

  * (c)

$\ell_{1},\ell_{2},\ell_{3}$ can not been have charged to before iteration
$i$.

  * (d)

$|F_{\sigma}|\leq\frac{4}{3}|EC_{3}|$.

As previously stated, we begin with $F_{0}\coloneqq APX_{i}$. When we consider
$F_{\sigma}$, if every square of $G_{s}$ is covered, then we let
$APX_{i+1}\coloneqq F_{\sigma}$, and we are done. Otherwise, let $S_{j}$ be
the square of least index that is not covered by $F_{\sigma}$.

Before we continue, we define some notation. For partial solution
$F_{\sigma}$, we call the square $S_{1}\subseteq E(G_{s})$ a _blocker_ of
$F_{\sigma}$ when a) $S_{1}$ is not covered by $F_{\sigma}$, (hence $S_{r}$ is
not covered) and; b) $v_{1}v_{2}\notin L$ if $v_{1}$ is degree $3$, and
$u_{1}u_{2}\notin L$ if $u_{1}$ is degree $3$. Similarly, we call the square
$S_{r}\subseteq E(G_{s})$ a blocker of $F_{\sigma}$ when a) $S_{r}$ is not
covered by $F_{\sigma}$, and; c) $v_{r}v_{r+1}\notin L$ if $v_{r+1}$ if
$v_{r+1}$ is degree 3, and $u_{r}u_{r+1}\notin L$ when $u_{r+1}$ is degree 3.
See Figure 6 for an example where $S_{1}$ and $S_{r}$ both satisfy part (2)
the definition of blockers.

Suppose that $S_{1}$ and $S_{r}$ both satisfy the part (b) of the definition
of blockers for $F_{\sigma}$. We will show that if $r=2$ or $3$ that we can
assume that at most one of $S_{1}$ and $S_{r}$ satisfy part (a) of the
definition of blocker for $F_{\sigma}$, that is, that at most one is not
covered by $F_{\sigma}$. For $r=2$, the nodes $v_{2}=v_{r}$ and $u_{2}=u_{r}$
are degree 3 and must be covered by $APX_{i}$, and thus by $F_{\sigma}$,
therefore, at least one of $S_{1}$ or $S_{2}$ will contain a link and thus
will be covered and cannot be a blocker.

If $r=3$, if $S_{1}$ and $S_{2}$ both satisfy the part (b) of the definition
of blockers for $F_{\sigma}$, it is not hard to see that the edges
$v_{2}u_{2}$ and $v_{3}u_{3}$ must b e links, since no links are necessary. If
$S_{1}$ and $S_{2}$ satisfy part (a) of of the definition of blockers for
$F_{\sigma}$, then for $F_{\sigma}$ to cover all degree 3 nodes while $S_{1}$
and $S_{3}$ are uncovered we must have $v_{2}v_{3},u_{3}u_{2}\in F_{\sigma}$
and thus in $L$. So we replace $F_{\sigma}$ with
$F_{\sigma}\cup\\{v_{2}u_{2},v_{3}u_{3}\\}\backslash\\{v_{2}v_{3},u_{2}u_{3}\\}$.

To show this, we consider the cases for $\sigma$: when $j=1$, when
$j\in\\{2,\dots,r-1\\}$, and when $j=r$.

#### Case:

$j=1$. Note that in this case $\sigma=0$. Since $G_{s}$ is degree at least 3,
we assume without loss of generality that our labelling is such that $v_{1}$
is incident to an edge $v_{1}w\in\delta(G_{s})\cap F_{0}$. By our assumption
on the labelling of $G_{s}$, it must be that both $S_{1}$ and $S_{r}$ are
uncovered by $F_{\sigma}$.

If exactly one of $S_{1}$ and $S_{r}$ is a blocker, then we assume that our
labelling is such that $S_{1}$ is not a blocker. We consider the cases arising
from whether $S_{1}$ is a blocker or not.

  * •

Case: $S_{1}$ not a blocker, thus at least one of $v_{1}v_{2},u_{1}u_{2}\in
L$. Assume without loss of generality that $v_{1}v_{2}\in L$. Set
$F_{1}\leftarrow F_{0}\cup\\{v_{1}v_{2}\\}$. $EC_{3}$, and thus $F_{0}$ covers
every degree $3$ node, so we have $u_{2}u_{3},v_{2}v_{3}\in F_{0}\cap EC_{3}$.
We charge the addition of $v_{1}v_{2}$ to $v_{1}w,v_{2}v_{3},u_{2}u_{3}\in
EC_{3}$.

We now help ensure that $v_{2}v_{3}$ and $u_{2}u_{3}$ are not charged to
again. If $r=2$, then $S_{r}$ is covered.

If $r>2$ and $S_{3}$ is not covered by $F_{0}$. Since no links are necessary,
there is a link $\ell\in L\cap\delta(v_{3})\cap E[S_{3}]$ that is not in
$F_{0}$. We change $F_{1}\leftarrow
F_{1}\cup\\{\ell\\}\backslash\\{v_{2}v_{3}\\}$. Note that $F_{1}$ now covers
both $S_{1}$ and $S_{3}$, in addition to the obstructions previously covered
for no change in size, so we do not need to find links in $APX_{i}$ to charge
$\ell$ to.

To help ensure that $v_{1}w\in\delta(G_{s})\cap APX_{i}$ is charged to only
once, consider the following cases.

    * –

Case: if $w\in R$ or if $w\in G_{x}$ such that every obstruction of $G_{s}$ is
covered, we are done with this iteration, and we see that $v_{1}w$ is in
$Y_{i+1}$.

    * –

Case: $w\in G_{x}$ for some $G_{x}\notin\mathcal{H}_{i+1}$. Let $S\subseteq
G_{x}$ be the square of $G_{x}$ that contains $w$. If $S$ is covered by
$F_{1}$, we are done. If not, since no link is necessary, there is a link
$\ell^{\prime}\in E(S)\cap L$ that is adjacent to $v_{1}w$. We set
$F_{1}\leftarrow F_{1}\cup\\{\ell^{\prime}\\}\backslash\\{v_{1}w\\}$. So
$F_{1}$ now covers both $S_{1}$ and $S$, in addition to the obstructions
previously covered, for no increase in size. Thus, we do not need to find
links in $EC_{3}$ to charge $\ell^{\prime}$ to. We see that $G_{x}$ is in
$\mathcal{H}_{i+1}$.

  * •

Case: $S_{1}$ is a blocker, thus $v_{1}v_{2}\notin L\cap E[S_{1}]$ (and
possibly $u_{1}u_{2}\notin L\cap E[S_{1}]$). By our assumption on the
labelling of $G_{s}$, both $S_{1}$ and $S_{r}$ are blockers, thus $r\geq 4$ by
the discussion on blockers above. Furthermore, since $S_{1}$ is a blocker,
$v_{1}u_{1},v_{2}u_{2}$ must be in $E(S_{1})\cap L$ since no links are
necessary, and $v_{2}v_{3},u_{2}u_{3}\in F_{0}$ since $F_{0}$ covers all
degree 3 nodes. We consider cases for which edges are in $F_{0}$ and $L$.

    * –

Case: $v_{3}u_{3}\in L\cap F_{0}$. We set $F_{1}\leftarrow
F_{0}\cup\\{v_{2}u_{2}\\}\backslash\\{u_{2}u_{3}\\}$. Since $v_{3}u_{3}\in
F_{0}$, the obstructions of $APX_{i}$ are still covered.

    * –

Case: $v_{3}u_{3}\in L\backslash F_{0}$. We set $F_{1}\leftarrow
F_{0}\\{v_{2}u_{2},v_{3}u_{3}\\}\backslash\\{v_{2}v_{3},u_{2}u_{3}\\}$.
Obviously, all obstructions of $APX_{i}$ are still covered.

In either case, the size of $F_{1}$ is no more than the size of $F_{0}$ and we
do not need to find links in $EC_{3}$ to charge $v_{2}v_{3}$ to.

In the following cases, $v_{3}u_{3}\notin L$, and so $v_{3}v_{4},u_{3}u_{4}\in
L$ since no links are necessary.

    * –

Case: at least one of $v_{3}v_{4}$ or $u_{3}u_{4}\in F_{0}$ (without loss of
generality $v_{3}v_{4}\in F_{0}$). We set $F_{1}\leftarrow
F_{0}\cup\\{v_{2}u_{2}\\}\backslash\\{v_{2}v_{3}\\}$, so $F_{1}$ covers
$S_{1}$ and $S_{2}$ with $v_{2}u_{2}$, in addition to the obstructions it
previously covered, for no change in size, so we do not need to find links in
$EC_{3}$ to charge $v_{2}u_{2}$ to.

    * –

Case: $v_{3}v_{4},u_{3}u_{4}\notin F_{0}$. We set $F_{1}\leftarrow
F_{0}\cup\\{v_{2}u_{2},v_{3}v_{4},u_{3}u_{4}\\}$
$\backslash\\{v_{2}v_{3},u_{2}u_{3}\\}$. So we must find at least 3 links in
$APX_{i}$ to charge one of $v_{2}u_{2},v_{3}v_{4},u_{3}u_{4}$ to. We know that
$r\geq 4$, and that both $v_{4}$ and $u_{4}$ are covered by $F_{0}$ so at
least one of $v_{4}u_{4},v_{4}v_{5},u_{4}u_{5}$ must be in $F_{0}$.

If $v_{4}u_{4}\in F_{0}$, then we can charge $v_{2}u_{2}$ to
$v_{2}v_{3},u_{2}u_{3},v_{4}u_{4}\in EC_{3}\cap APX_{i}$. Note that $F_{1}$
now covers $S_{1}$, $S_{2}$, $S_{3}$, and $S_{4}$.

If $v_{4}u_{4}\notin F_{0}$, then $v_{4}v_{5},u_{4}u_{5}\in F_{0}$ since
$v_{4}$ and $u_{4}$ are covered by $F_{0}$. In this case we charge
$v_{2}u_{2}$ to $v_{2}v_{3},u_{2}u_{3},v_{4}v_{5}\in APX_{i}$. If $r<6$ or
$S_{5}$ is covered by $F_{0}$, then we are done with this iteration. So assume
that $r\geq 6$, and $S_{5}$ is not covered by $F_{0}$. Then there must be a
link $\ell\in E(S_{5})\cap L\cap\delta(v_{5})$. We set $F_{1}\leftarrow
F_{1}\cup\\{\ell\\}\backslash\\{v_{4}v_{5}\\}$.

#### Case:

$j\in\\{2,\dots,r-1\\}$. $S_{j}$ is not covered, but $v_{j-1},v_{j},u_{j-1},$
and $u_{j}$ are covered, since $APX_{i}$ covers every degree $3$ node.
Therefore, it is clear that $u_{j-1}u_{j},$ $v_{j-1}v_{j},$ $u_{j+1}u_{j+2},$
$v_{j+1}v_{j+2}\in APX_{i}\cap F_{\sigma}$. Since no link is necessary, we
know at least one of $v_{j}v_{j+1},$ $v_{j+1}u_{j+1},u_{j}u_{j+1}\in L$. Let
$\ell\in\\{v_{j}v_{j+1},$ $v_{j+1}u_{j+1},$ $u_{j}u_{j+1}\\}\cap L$ be a link
from these three. Set $F_{\sigma+1}\leftarrow F_{\sigma}\cup\\{\ell\\}$, and
charge $\ell$ to $u_{j-1}u_{j},$ $v_{j-1}v_{j},$ $u_{j+1}u_{j+2}\in APX_{i}$.

To help ensure that no links of $APX_{i}$ are charged twice, we consider the
case $j<r-1$, and $S_{j+2}$ is not covered by $F_{\sigma+1}$. Then there is
$\ell^{\prime}\in E(S_{j+2})\cap L\cap\delta(u_{j+2})$. We set
$F_{\sigma+1}\leftarrow
F_{\sigma+1}\cup\\{\ell^{\prime}\\}\backslash\\{u_{j+1}u_{j+2}\\}$, so
$F_{\sigma+1}$ covers both $S_{j}$ and $S_{j+2}$, in addition to the
obstructions it previously covered. If $r=j-1$, then every square of $G_{s}$
is covered by $F_{\sigma+1}$.

#### Case:

$j=r$. Since $G_{s}$ is degree at least $3$, there is a $w\in V(G)$ such that
$v_{r+1}w$ or $u_{r+1}w\in APX_{i}\cap\delta(G_{s})$, we assume without loss
of generality that $u_{r+1}w\in APX_{i}\cap\delta(G_{s})$. Since no link is
necessary, there is a link $\ell\in S_{r}$ incident to $u_{r+1}$. Set
$F_{\sigma+1}\leftarrow F_{\sigma}\cup\\{\ell\\}$ and charge the addition of
$\ell$ to $u_{r-1}u_{r},v_{r-1}v_{r},u_{r+1}w\in APX_{i}$.

To help ensure that $u_{r+1}w\in\delta(G_{s})\cup APX_{i}$ is not charged to
again, we consider if $w\in R$ or $w\in V(G_{x})$ for some
$G_{x}\in\\{G_{1},\dots,G_{k}\\}$. If $w\in R$, we are done with this
iteration, and $u_{r+1}w$ is in $Y_{i+1}$. If not, then there is some
$G_{x}\in\\{G_{1},\dots,G_{k}\\}$ such that $w\in V(G_{x})$.

If $w\in G_{x}$ such that every obstruction of $G_{s}$ is covered, then we are
done with this iteration. So assume this is not the case, and let $S\subseteq
G_{x}$ be the square that contains $w$. if $S$ is covered by $F_{\sigma+1}$,
we are done with this iteration. So assume that $S$ is not covered by
$F_{\sigma+1}$. Since no link is necessary, there is a link $\ell^{\prime}\in
E(S)\cap L$ that is incident to $w$. We set $F_{\sigma+1}\leftarrow
F_{\sigma+1}\cup\\{\ell^{\prime}\\}\backslash\\{u_{r+1}w\\}$. So
$F_{\sigma+1}$ now covers both $S_{r}$ and $S$ in addition to the obstructions
previously covered, for no change in size. Thus, we do not need to find links
in $APX_{i}$ to charge $\ell^{\prime}$ to. We see that $G_{x}$ is in
$\mathcal{H}_{i+1}$.

It remains to show that no link in $EC_{3}$ is charged to more than once. So
assume for contradiction that link $\ell\in EC_{3}$ is charged to a second
time in step $i+1$ when we are constructing $APX_{i+1}$. Let
$G_{s}\in\\{G_{1},\dots,G_{k}\\}\backslash\mathcal{H}_{i}$ be the ladder that
is being covered in step $i$. First, suppose $\ell\in E(G_{S})$. By property
(b), this implies that $G_{s}$ was covered in a previous iteration, and thus
$G_{s}\in\mathcal{H}_{i}$, a contradiction.

So suppose that $\ell\in\delta(G_{s})$. By construction $\ell$ is charged to
only when the incident square in $G_{s}$ is not covered by $APX_{i}$, and by
$EC_{3}$. However, since $\ell$ has been charged to before, its other endpoint
must be some $G_{t}\in\\{G_{1},\dots,G_{k}\\}$ that has a square incident to
$\ell$ that was uncovered before that iteration. However, in our construction,
when we charge to $\ell\in\delta(G_{t})$ the first time, we replace $\ell$ by
a link in $G_{s}$ if the incident square in $G_{s}$ is uncovered. Therefore,
$G_{s}\in\mathcal{H}_{i}$, a contradiction. With Lemma 14 and Lemma 5, we have
the ingredients necessary to prove Theorem 4.1.

######  Proof (proof of Theorem 4.1)

Given an unweighted $(n-4)$-Node Connectivity Augmentation instance, we apply
Theorem 2.1 to obtain an instance $(G,4,L)$ of unweighted $d$-Obstruction
Covering. We will show how to find a solution $APX$ with
$|APX|\leq\frac{4}{3}|opt|$. Using Theorem 2.2, we decompose $G$ into node-
disjoint hexagons and ladders $G_{1},\dots,G_{k}$, and lonely nodes $R$. We
will compute the solution $APX$ by adding partial solutions.

By applying Lemma 4, we compute a minimum cardinality subset of links
$EC_{3}\subseteq L$ that covers the obstructions contained in every subgraph
$G_{i}$ of degree $1$ and $2$ and every degree $3$ node. Let
$\mathcal{H}_{0}\subseteq\\{G_{1},\dots,G_{k}\\}$ denote the ladders and
hexagons covered by $EC_{3}$. We set $APX_{0}\coloneqq EC_{3}\cap
E[\mathcal{H}_{0}]$, and remove these edges from $G$ to get new
$4$-Obstruction Covering instance $(G^{\prime}=(V,E^{\prime}),4,L^{\prime})$,
where $E^{\prime}=E\backslash APX_{0}$, and $L^{\prime}=L\backslash APX_{0}$.
We apply Theorem 2.2 to find decomposition
$R^{\prime},G_{1}^{\prime},\dots,G_{k_{1}}^{\prime}$. Observe that by
construction of $G^{\prime}$, $G_{1}^{\prime},\dots,G_{k_{1}}^{\prime}$
contain only ladders of degree $3$ and $4$.

We apply Lemma 14 to $(G^{\prime},4,L^{\prime})$ with partial solution
$EC_{3}\backslash APX_{0}$, to find a new partial solution $F_{1}$. We also
find a subset of ladders
$\mathcal{H}_{1}\subseteq\\{G_{1}^{\prime},\dots,G_{k_{1}}^{\prime}\\}$ whose
obstructions are covered by $F_{1}$, and a set of links $Y_{1}\subseteq
F_{1}\cap\delta(G^{\prime}[\mathcal{H}_{1}])$ where every $y\in Y_{1}$ has an
endpoint in $R^{\prime}$. We set $APX_{1}\coloneqq F_{1}\cap(Y_{1}\cup
E^{\prime}[\mathcal{H}_{1}])$, and remove $APX_{1}$ from $G^{\prime}$ to get
new $4$-Obstruction Covering instance $(G^{\prime\prime},4,L^{\prime\prime})$
where $G^{\prime\prime}=(V^{\prime},E^{\prime}\backslash APX_{1})$ and
$L^{\prime\prime}=L^{\prime}\backslash APX_{1}$. We apply Theorem 2.2 to find
decomposition
$R^{\prime\prime},G_{1}^{\prime\prime},\dots,G_{k_{2}}^{\prime\prime}$.
Observe that by Lemma 14,
$G_{1}^{\prime\prime},\dots,G_{k_{2}}^{\prime\prime}$ contains only ladders of
length $1$ and degree $3$ or $4$.

Lastly, we apply Lemma 5 with $F_{1}\backslash APX_{1}$ as our partial
solution, to find a feasible solution $APX_{2}$. We denote the ladders covered
by $APX_{2}$ by
$\mathcal{H}_{2}\coloneqq\\{G_{1}^{\prime\prime},\dots,G_{k_{3}}^{\prime\prime}\\}$
.

We define $APX\coloneqq APX_{0}\cup APX_{1}\cup APX_{2}$. By construction
$APX_{0}$, $APX_{1}$, and $APX_{2}$ are pairwise disjoint. To see that $APX$
is a feasible solution to $(G,4,L)$, first observe that
$\mathcal{H}_{0},\mathcal{H}_{1},$ and $\mathcal{H}_{2}$ are also pairwise
disjoint and
$\mathcal{H}_{0}\cup\mathcal{H}_{1}\cup\mathcal{H}_{2}=\\{G_{1},\dots,G_{k}\\}$,
so $APX$ covers every obstruction of $\\{G_{1},\dots,G_{k}\\}$, in addition,
$EC_{3}$ covers every obstruction in $R$, and $APX$ covers every obstruction
covered by $EC_{3}$ so $APX$ is feasible.

$\displaystyle APX=$ $\displaystyle APX_{0}\cup APX_{1}\cup
APX_{2}=APX_{0}\cup(F_{1}\cap(Y_{1}\cup E^{\prime}[\mathcal{H}_{1}]))\cup
APX_{2}$ $\displaystyle=$ $\displaystyle(EC_{3}\cap
E[H_{0}])\cup(F_{1}\cap(Y_{1}\cup E[\mathcal{H}_{1}]))\cup APX_{2}$

Therefore, $|APX|$ is equal to

$\displaystyle=$ $\displaystyle|APX_{0}|+|F_{1}\cap(Y_{1}\cup
E[\mathcal{H}_{1}])|+|APX_{2}|$ $\displaystyle\leq$
$\displaystyle|APX_{0}|+\frac{4}{3}|(EC_{3}\backslash
APX_{0})\cap(APX_{1})|+\frac{4}{3}|F_{1}\backslash(APX_{1})|$ $\displaystyle=$
$\displaystyle|APX_{0}|+\frac{4}{3}|(EC_{3}\backslash
APX_{0})\cap(APX_{1})|+\frac{4}{3}|(EC_{3}\backslash
APX_{0})\backslash(APX_{1})|$ $\displaystyle<$
$\displaystyle\frac{4}{3}|APX_{0}|+\frac{4}{3}|EC_{3}\backslash
APX_{0}|=\frac{4}{3}|EC_{3}|\leq\frac{4}{3}|opt|$

Where the inequality above follows by application of the inequalities found in
Lemmas 14, and 5. The second equality follows from the equality in Lemmas 14.
The final inequality above follows since $opt$ is a feasible solution to the
$N$-edge cover problem that $EC_{3}$ solves.

##  Appendix 0.H  Missing proofs of Section 5

Along this section, we will refer to the following special case of the 3-SAT
problem, known as 3-SAT-4.

######  Definition 4 (3-SAT-4 problem)

The 3-SAT-4 problem is the special case of 3-SAT where each variable appears
exactly four times in the boolean formula $\mathcal{I}$. The corresponding
optimization version of the problem is denoted as MAX-3-SAT-4.

The 3-SAT-4 problem is known to be NP-hard, and furthermore its optimization
version is known to be APX-hard [4].

###  0.H.1  Proof of Lemma 6

Consider a 3-SAT-4 instance $\mathcal{I}_{4}$. Our goal is to construct a
3-SAT-(2,2) instance $\mathcal{I}_{2,2}$ in such a way that
$\mathcal{I}_{2,2}$ is satisfiable if and only if $\mathcal{I}_{4}$ is
satisfiable.

We distinguish three types of variables in $\mathcal{I}_{4}$: the variables
that occur exactly four times as positive or four times as negative literals,
the variables that occur three times as positive literals or three times as
negative literals, and the variables that occur twice as positive literals. We
will construct the new instance $\mathcal{I}_{2,2}$ by initially setting it to
be equal to $\mathcal{I}_{4}$ and then remove or change literals of the first
two types in order to turn the formula into a 3-SAT-(2,2) instance.

First, suppose a variable $x$ occurs as $4$ positive literals in
$\mathcal{I}_{2,2}$ (the case of negative literals can be handled
symmetrically). In this case, we can assume that $x$ is true and remove the
clauses containing $x$ from $\mathcal{I}_{2,2}$. For the variables left in
$\mathcal{I}_{2,2}$ that occur less than 4 times after the removal, we will
add dummy clauses and variables to bring them back. For each such literal $y$
that was removed, we add dummy variables $d_{y,1}$ and $d_{y,2}$ and the
clauses

$(y\lor d_{y,1}\lor
d_{y,2})\wedge(d_{y,1}\lor\bar{d}_{y,1}\lor\bar{d}_{y,1})\wedge(d_{y,2}\lor\bar{d}_{y,2}\lor\bar{d}_{y,2}).$

We remark that, if more than one literal associated to the same variable were
removed, we create different variables for them in the process. If the
variables $d_{y,1}$ and $d_{y,2}$ are set to true, then the three clauses are
satisfied regardless of the value of the variable corresponding to literal
$y$, so we obtain an equivalent formula without variables occurring four times
as positive literals.

Suppose that $x$ occurs as $3$ positive literals in $\mathcal{I}_{2,2}$ (the
case of negative literals can be handled symmetrically). We introduce new
variables $y_{x},z_{x},w_{x}$ to $\mathcal{I}_{2,2}$, then select two
arbitrary positive literals of $x$ and replace one with $y_{x}$ and the other
with $z_{x}$. We then add the clauses

$(x\lor\bar{y}_{x}\lor\bar{y}_{x})\wedge(y_{x}\lor\bar{z}_{x}\lor\bar{z}_{x})\wedge(z_{x}\lor\bar{w}_{x}\lor\bar{w}_{x})\wedge(w_{x}\lor
w_{x}\lor\bar{x}).$

These new clauses are satisfied if and only if $x=y=z=w$. Moreover, it is not
hard to see that now there are two positive literals and two negative literals
for $x,y,z,w$. In conclusion, $\mathcal{I}_{2,2}$ is equivalent to
$\mathcal{I}_{4}$ and a valid 3-SAT-(2,2) instance.

###  0.H.2  Proof of Proposition 1

First of all, since $G_{\mathcal{I}}$ is a $3$-regular graph, it does not
contain $K_{1,4}$ as subgraph. Therefore, the only forbidden subgraph we need
to show does not exist is $K_{2,3}$. Assume, for the sake of contradiction,
that $F$ is a $K_{2,3}$ subgraph of $G_{\mathcal{I}}$. Let $v\in F$ be degree
$3$ in $F$, we will distinguish two cases:

  * •

If $v$ is a clause node in $G_{\mathcal{I}}$, say corresponding to clause $C$,
then its neighbors are three variable nodes $x_{i},y_{j},z_{k}$ for
$i,j,k\in\\{1,3,4,6\\}$, for some (possibly equal) variables $x,y,z$. If any
two such variables are different, then their only common neighbor is $v$, and
hence it cannot be part of a $K_{2,3}$. On the other hand, if the three
neighbors of $v$ belong to the same subgraph $H_{x}$, by construction there
are always two such variable nodes without common neighbors other than $v$
(either $x_{1}$ and $x_{4}$, or $x_{3}$ and $x_{6}$), hence again $v$ cannot
be part of a $K_{2,3}$

  * •

If $v$ is a variable node in some subgraph $H_{x}$, we consider two cases: if
$v=x_{1}$ (the cases $x_{3},x_{4}$ or $x_{6}$ are symmetric), its neighbors in
$G_{\mathcal{I}}$ are $x_{2}$, $x_{6}$ and some clause node, but the only node
connected to $x_{2}$ and $x_{6}$ is $x_{5}$, which is not connected to any
clause node; hence, $x_{1}$ cannot be part of a $K_{2,3}$. If $v=x_{2}$ (the
case of $x_{5}$ is symmetric), its neighbors in $G_{\mathcal{I}}$ are $x_{1}$,
$x_{5}$ and $x_{3}$ but they do not have two neighbors in common. Hence, no
variable node can be part of a $K_{2,3}$.

Thus, $(G_{\mathcal{I}},4,L_{\mathcal{I}})$ is a valid instance of the
$4$-Obstruction Covering problem.

###  0.H.3  Proof of Theorem 5.2

Given a $3$-SAT-$(2,2)$ instance $\mathcal{I}$, we first create the
$(n-4)$-Obstruction Covering instance $(G_{\mathcal{I}},4,L_{\mathcal{I}})$ as
described in the proof of Theorem 5.1. We will modify it to obtain an
$d$-Obstruction Covering instance
$(G_{\mathcal{I}}^{\prime},d,L_{\mathcal{I}}^{\prime})$, and show that finding
an optimal covering of the obstructions in $G_{\mathcal{I}}^{\prime}$ implies
whether a satisfying assignment exists for $\mathcal{I}$ or not.