University of Warwick,
UKsiddharth.gupta.1@warwick.ac.ukhttps://orcid.org/0000-0003-4671-9822Supported
by Engineering and Physical Sciences Research Council (EPSRC) grant
EP/V007793/1. Ben Gurion University of the Negev,
<EMAIL_ADDRESS>in part by the Israeli Smart Transportation
Research Center and by the Lynne and William Frankel Center for Computing
Science at Ben-Gurion University. Ben Gurion University of the Negev,
Israelmeiravze@bgu.ac.ilhttps://orcid.org/0000-0002-3636-5322Supported by the
European Research Council (ERC) grant titled PARAPATH. Siddharth Gupta, Guy
Sa’ar, and Meirav Zehavi [500]Theory of computation Fixed parameter
tractability [500]Theory of computation Approximation algorithms analysis
Neeldhara Misra and Magnus Wahlström 2 18th International Symposium on
Parameterized and Exact Computation (IPEC 2023) IPEC 2023 IPEC 2023 September
6–8, 2023 Amsterdam, The Netherlands 285 6

# Collective Graph Exploration Parameterized by Vertex Cover

Siddharth Gupta  Guy Sa’ar  Meirav Zehavi

###### Abstract

We initiate the study of the parameterized complexity of the Collective Graph
Exploration (CGE) problem. In CGE, the input consists of an undirected
connected graph $G$ and a collection of $k$ robots, initially placed at the
same vertex $r$ of $G$, and each one of them has an energy budget of $B$. The
objective is to decide whether $G$ can be _explored_ by the $k$ robots in $B$
time steps, i.e., there exist $k$ closed walks in $G$, one corresponding to
each robot, such that every edge is covered by at least one walk, every walk
starts and ends at the vertex $r$, and the maximum length of any walk is at
most $B$. Unfortunately, this problem is NP-hard even on trees [Fraigniaud et
al., 2006]. Further, we prove that the problem remains W[1]-hard parameterized
by $k$ even for trees of treedepth $3$. Due to the para-NP-hardness of the
problem parameterized by treedepth, and motivated by real-world scenarios, we
study the parameterized complexity of the problem parameterized by the vertex
cover number ($\mathsf{vc}$) of the graph, and prove that the problem is
fixed-parameter tractable (FPT) parameterized by $\mathsf{vc}$. Additionally,
we study the optimization version of CGE, where we want to optimize $B$, and
design an approximation algorithm with an additive approximation factor of
$O(\mathsf{vc})$.

###### keywords:

Collective Graph Exploration, Parameterized Complexity, Approximation
Algorithm, Vertex Cover, Treedepth

##  1 Introduction

Collective Graph Exploration (CGE) is a well-studied problem in computer
science and robotics, with various real-world applications such as network
management and fault reporting, pickup and delivery services, searching a
network, and so on. The problem is formulated as follows: given a set of
robots (or agents) that are initially located at a vertex of an undirected
graph, the objective is to explore the graph as quickly as possible and return
to the initial vertex. A graph is _explored_ if each of its edges is visited
by at least one robot. In each time step, every robot may move along an edge
that is incident to the vertex it is placed at. The total time taken by a
robot is the number of edges it traverses. The exploration time is the maximum
time taken by any robot. In many real-world scenarios, the robots have limited
energy resources, which motivates the minimization of the exploration time
[7].

The CGE problem can be studied in two settings: _offline_ and _online_. In the
offline setting, the graph is known to the robots beforehand, while in the
online setting, the graph is unknown and revealed incrementally as the robots
explore it. While CGE has received considerable attention in the online
setting, much less is known in the offline setting (Section 1.1). Furthermore,
most of the existing results in the offline setting are restricted to trees.
Therefore, in this paper, we investigate the CGE problem in the offline
setting for general graphs, and present some approximation and parameterized
algorithms with respect to the vertex cover number of the graph.

###  1.1 Related Works

As previously mentioned, the CGE problem is extensively studied in the online
setting, where the input graph is unknown. As we study the problem in the
offline setting in this paper, we only give a brief overview of the results in
the online setting, followed by the results in the offline setting.

Recall that, in the online setting, the graph is unknown to the robots and the
edges are revealed to a robot once the robot reaches a vertex incident to the
edge. The usual approach to analyze any online algorithm is to compute its
_competitive ratio_ , which is the worst-case ratio between the cost of the
online and the optimal offline algorithm. Therefore, the first algorithms for
CGE focused on the competitive ratios of the algorithms. In [13], an algorithm
for CGE for trees with competitive ratio $O(\frac{k}{\log k})$ was given.
Later in [15], it was shown that this competitive ratio is tight. Another line
of work studied the competitive ratio as a function of the vertices and the
depth of the input tree [4, 9, 15, 11, 8, 20]. We refer the interested readers
to a recent paper by Cosson et al. [6] and the references within for an in-
depth discussion about the results in the online setting.

We now discuss the results in the offline setting. In [1], it was shown that
the CGE problem for edge-weighted trees is NP-hard even for two robots. In [2,
19], an $(2-2/(k+1))$-approximation was given for the optimization version of
CGE for edge-weighted trees where we want to optimize $B$. In [13], the NP-
hardness was shown for CGE for unweighted trees as well. In [10], a
$2$-approximation was given for the optimization version of CGE for unweighted
trees where we want to optimize $B$. In the same paper, it was shown that the
optimization version of the problem for unweighted trees is XP parameterized
by the number of robots.

###  1.2 Our Contribution and Methods

In this paper, we initiate the study of the CGE problem for general unweighted
graphs in the offline setting and obtain the following three results. We first
prove that CGE is FPT parameterized by $\mathsf{vc}$, where $\mathsf{vc}$ is
the vertex cover number of the input graph. Specifically, we prove the
following theorem.

######  Theorem 1.1.

CGE is in FPT parameterized by $\mathsf{vc}(G)$, where $G$ is the input graph.

We then study the optimization version of CGE where we want to optimize $B$
and design an approximation algorithm with an additive approximation factor of
$O(\mathsf{vc})$. Specifically, we prove the following theorem.

######  Theorem 1.2.

There exists an approximation algorithm for CGE that runs in time
$\mathcal{O}((|V(G)|+|E(G)|)\cdot k)$, and returns a solution with an additive
approximation of $8\cdot\mathsf{vc}(G)$, where $G$ is the input graph and $k$
is the number of robots.

Finally, we show a border of (in-)tractability by proving that CGE is
W[1]-hard parametrized by $k$, even for trees of treedepth $3$. Specifically,
we prove the following theorem.

######  Theorem 1.3.

CGE is W[1]-hard with respect to $k$ even on trees whose treedepth is bounded
by $3$.

We first give an equivalent formulation of CGE based on Eulerian cycles (see
Lemma 3.2). We obtain the FPT result by using Integer Linear Programming
(ILP). By exploiting the properties of vertex cover and the conditions given
by our formulation, we show that a potential solution can be encoded by a set
of variables whose size is bounded by a function of vertex cover.

To design the approximation algorithm, we give a greedy algorithm that
satisfies the conditions given by our formulation. Again, by exploiting the
properties of vertex cover, we show that we can satisfy the conditions of our
formulation by making optimal decisions at the independent set vertices and
using approximation only at the vertex cover vertices.

To prove the W-hardness, we give a reduction from a variant of Bin Packing,
called Exact Bin Packing (defined in Section 2). We first prove that Exact Bin
Packing is W[1]-hard even when the input is given in unary. We then give a
reduction from this problem to CGE to obtain our result.

###  1.3 Choice of Parameter

As mentioned in the previous section, we proved that CGE is W[1]-hard
parameterized by $k$ even on trees of treedepth $3$. This implies that we
cannot get an FPT algorithm parameterized by treedepth and $k$ even on trees,
unless $\textsf{FPT}=\textsf{W[1]}$. Thus, we study the problem parameterized
by the vertex cover number of the input graph, a slightly weaker parameter
than the treedepth.

Our choice of parameter is also inspired by several practical applications.
For instance, consider a delivery network of a large company. The company has
a few major distributors that receive the products from the company and can
exchange them among themselves. There are also many minor distributors that
obtain the products only from the major ones, as this is more cost-effective.
The company employs $k$ delivery persons who are responsible for delivering
the products to all the distributors. The delivery persons have to start and
end their routes at the company location. Since each delivery person has a
maximum working time limit, the company wants to minimize the maximum delivery
time among them. This problem can be modeled as an instance of CGE by
constructing a graph $G$ that has a vertex for the company and for each
distributor and has an edge between every pair of vertices that correspond to
locations that can be reached by a delivery person. The $k$ robots represent
the $k$ delivery persons and are placed at the vertex corresponding to the
company. Clearly, $G$ has a small vertex cover, as the number of major
distributors is much smaller than the total number of distributors.

For another real-world example where the vertex cover is small, suppose we
want to cover all the streets of the city as fast as possible using $k$ agents
that start and end at a specific street. The city has a few long streets and
many short streets that connect to them. This situation is common in many
urban areas. We can represent this problem as an instance of CGE by creating a
graph $G$ that has a vertex for each street and an edge between two vertices
if the corresponding streets are adjacent. The $k$ robots correspond to the
$k$ agents. Clearly, $G$ has a small vertex cover, as the number of long
streets is much smaller than the total number of streets.

##  2 Preliminaries

For $k\in\mathbb{N}$, let $[k]$ denote the set $\\{1,2,\ldots,k\\}$. For a
multigraph $G$, we denote the set of vertices of $G$ and the multiset of edges
of $G$ by $V(G)$ and $E(G)$, respectively. For $u\in V(G)$, the set of
neighbors of $u$ in $G$ is $\mathsf{N}_{G}(u)=\\{v\in V\leavevmode\nobreak\
|\leavevmode\nobreak\ \\{u,v\\}\in E(G)\\}$. When $G$ is clear from the
context, we refer to $\mathsf{N}_{G}(u)$ as $\mathsf{N}(u)$. The multiset of
neighbors of $u$ in $G$ is the multiset $\widehat{\mathsf{N}}_{G}(u)=\\{v\in
V\leavevmode\nobreak\ |\leavevmode\nobreak\ \\{u,v\\}\in E(G)\\}$ (with
repetition). When $G$ is clear from the context, we refer to
$\widehat{\mathsf{N}}_{G}(u)$ as $\widehat{\mathsf{N}}(u)$. The degree of $u$
in $G$ is $|\widehat{\mathsf{N}}_{G}(u)|$ (including repetitions). Let
$\widehat{E}$ be a multiset with elements from $E(G)$. Let
$\mathsf{Graph}(\widehat{E})$ denote the multigraph
$(V^{\prime},\widehat{E})$, where $V^{\prime}=\\{u\leavevmode\nobreak\
|\leavevmode\nobreak\ \\{u,v\\}\in\widehat{E}\\}$. A multigraph $H$ is a
_submultigraph_ of a multigraph $G$ if $V(H)\subseteq V(G)$ and $E(H)\subseteq
E(G)$. Let $V^{\prime}\subseteq V(G)$. We denote the submultigraph induced by
$V^{\prime}$ by $G[V^{\prime}]$, that is, $V(G[V^{\prime}])=V^{\prime}$ and
$E(G[V^{\prime}])=\\{\\{u,v\\}\in E(G)\leavevmode\nobreak\
|\leavevmode\nobreak\ u,v\in V^{\prime}\\}$. Let $U\subseteq V(G)$. Let
$G\setminus U$ denote the subgraph $G[V(G)\setminus U]$ of $G$.

An Eulerian cycle in a multigraph $\widehat{G}$ is a cycle that visits every
edge in $E(\widehat{G})$ exactly once. A vertex cover of $G$ is
$V^{\prime}\subseteq V(G)$ such that for every $\\{u,v\\}\in E(G)$, at least
one among $u$ and $v$ is in $V^{\prime}$. The vertex cover number of $G$ is
$\mathsf{vc}(G)=\mathsf{min}\\{|V^{\prime}|\leavevmode\nobreak\
|\leavevmode\nobreak\ V^{\prime}$ is a vertex cover of $G\\}$. When $G$ is
clear from context, we refer to $\mathsf{vc}(G)$ as $\mathsf{vc}$. A path $P$
in $G$ is $(v_{0},\ldots,v_{\ell})$, where (i) for every $0\leq i\leq\ell$,
$v_{i}\in V(G)$, and (ii) for every $0\leq i\leq\ell-1$,
$\\{v_{i},v_{i+1}\\}\in E(G)$ (we allow repeating vertices). The length of a
path $P=(v_{0},\ldots,v_{\ell})$, denoted by $|P|$, is the number of edges in
$P$ (including repetitions), that is, $\ell$. The set of vertices of $P$ is
$V(P)=\\{v_{0},\ldots,v_{\ell-1}\\}$. The multiset of edges of $P$ is
$E(P)=\\{\\{v_{i},v_{i+1}\\}\leavevmode\nobreak\ |\leavevmode\nobreak\ 0\leq
i\leq\ell-1\\}$ (including repetitions). A cycle $C$ in $G$ is a path
$(v_{0},\ldots,v_{\ell})$ such that $v_{0}=v_{\ell}$. A simple cycle is a
cycle $C=(v_{0},\ldots,v_{\ell})$ such that for every $0\leq i<j\leq\ell-1$,
$v_{i}\neq v_{j}$. An isomorphism of a multigraph $G$ into a multigraph
$G^{\prime}$ is a bijection $\alpha:V(G)\rightarrow V(G^{\prime})$, such that
$\\{u,v\\}$ appears in $E(G)$ $\ell$ times if and only if
$\\{\alpha(u),\alpha(v)\\}$ appears in $E(G^{\prime})$ $\ell$ times, for an
$\ell\in\mathbb{N}$. For a multiset $A$, we denote by $2^{A}$ the power set of
$A$, that is, $2^{A}=\\{B\leavevmode\nobreak\ |\leavevmode\nobreak\ B\subseteq
A\\}$. Let $A$ and $B$ be two multisets. Let $A\setminus B$ be the multiset
$D\subseteq A$ such that every $d\in A$ appears exactly
$\mathsf{max}\\{0,d_{A}-d_{B}\\}$ times in $D$, where $d_{A}$ and $d_{B}$ are
the numbers of times $d$ appears in $A$ and $B$, respectively. A permutation
of a multiset $A$ is a bijection $\mathsf{Permut}_{A}:A\rightarrow[|A|]$.

######  Definition 2.1 ($v_{\mathsf{init}}$-Robot Cycle).

Let $G$ be a graph, let $v_{\mathsf{init}}\in V(G)$. A
$v_{\mathsf{init}}$-robot cycle is a cycle
$\mathsf{RC}=(v_{0}=v_{\mathsf{init}},v_{1},v_{2},\ldots,v_{\ell}=v_{\mathsf{init}})$
in $G$ for some $\ell$.

When $v_{\mathsf{init}}$ is clear from the context, we refer to a
$v_{\mathsf{init}}$-robot cycle as a robot cycle.

######  Definition 2.2 (Solution).

Let $G$ be a graph, $v_{\mathsf{init}}\in V(G)$ and $k\in\mathbb{N}$. A
solution for $(G,v_{\mathsf{init}},k)$ is a set of $k$
$v_{\mathsf{init}}$-robot cycles
$\\{\mathsf{RC}_{1},\ldots,\mathsf{RC}_{k}\\}$ with $E(G)\subseteq
E(\mathsf{RC}_{1})\cup E(\mathsf{RC}_{2})\cup\dots\cup E(\mathsf{RC}_{k})$.
Its value is
$\mathsf{val}(\\{\mathsf{RC}_{1},\ldots,\mathsf{RC}_{k}\\})=\mathsf{max}\\{|E(\mathsf{RC}_{1})|,|E(\mathsf{RC}_{2})|,\ldots,|E(\mathsf{RC}_{k})|\\}$
(see Figure 1(a) for an illustration).

(a)

(b)

Figure 1: (a) An illustration of a graph $G$ (drawn in black) and a solution
for $(G,v_{\mathsf{init}},k=2)$. The $2$ robot cycles are shown by red and
blue edges where the edge labels show the order in which the edges were
covered by the respective robots. (b) The Robot Cycle-Graph for the robot
cycle drawn in blue.

######  Definition 2.3 (Collective Graph Exploration with $k$ Agents).

The Collective Graph Exploration (CGE) problem with $k$ agents is: given a
connected graph $G$, $v_{\mathsf{init}}\in V(G)$ and $k\in\mathbb{N}$, find
the minimum $B$ such that there exists a solution
$\\{\mathsf{RC}_{1},\ldots,\mathsf{RC}_{k}\\}$ where
$\mathsf{val}(\\{\mathsf{RC}_{1},\ldots,\mathsf{RC}_{k}\\})$ $=B$.

######  Definition 2.4 (Collective Graph Exploration with $k$ Agents and
Budget $B$).

The Collective Graph Exploration (CGE) problem with $k$ agents and budget $B$
is: given a connected graph $G$, $v_{\mathsf{init}}\in V(G)$ and
$k,B\in\mathbb{N}$, find a solution
$\\{\mathsf{RC}_{1},\ldots,\mathsf{RC}_{k}\\}$ where
$\mathsf{val}(\\{\mathsf{RC}_{1},\ldots,\mathsf{RC}_{k}\\})\leq B$, if such a
solution exists; otherwise, return “no-instance”.

######  Definition 2.5 (Bin Packing).

The Bin Packing problem is: given a finite set $I$ of items, a size
$s(i)\in\mathbb{N}$ for each $i\in I$, a positive integer $B$ called bin
capacity and a positive integer $k$, decide whether there is a partition of
$I$ into disjoint sets $I_{1},\ldots,I_{k}$ such that for every $1\leq j\leq
k$, $\sum_{i\in I_{j}}s(i)\leq B$.

######  Definition 2.6 (Exact Bin Packing).

The Exact Bin Packing problem is: given a finite set $I$ of items, a size
$s(i)\in\mathbb{N}$ for each $i\in I$, a positive integer $B$ called bin
capacity and a positive integer $k$ such that $\sum_{i\in I}s(i)=B\cdot k$,
decide whether there is a partition of $I$ into disjoint sets
$I_{1},\ldots,I_{k}$ such that for every $1\leq j\leq k$, $\sum_{i\in
I_{j}}s(i)=B$.

######  Definition 2.7 (Integer Linear Programming).

In the Integer Linear Programming Feasibility (ILP) problem, the input
consists of $t$ variables $x_{1},x_{2},\ldots,x_{t}$ and a set of $m$
inequalities of the following form:

$\begin{array}[]{*{9}{@{}c@{}}}a_{1,1}x_{1}&+&a_{1,2}x_{1}&+&\cdots&+&a_{1,p}x_{t}&\leq&b_{1}\\\
a_{2,1}x_{1}&+&a_{2,2}x_{2}&+&\cdots&+&a_{2,p}x_{t}&\leq&b_{2}\\\
\vdots&&\vdots&&&&\vdots&&\vdots\\\
a_{m,1}x_{1}&+&a_{m,2}x_{2}&+&\cdots&+&a_{m,p}x_{t}&\leq&b_{m}\\\ \end{array}$

where all coefficients $a_{i,j}$ and $b_{i}$ are required to integers. The
task is to check whether there exist integer values for every variable $x_{i}$
so that all inequalities are satisfiable.

######  Theorem 2.8 ([14, 17, 18]).

An ILP instance of size $m$ with $t$ variables can be solved in time
$t^{\mathcal{O}(t)}\cdot m^{\mathcal{O}(1)}$.

##  3 Reinterpretation Based on Eulerian Cycles

Our approach to CGE with $k$ agents is as follows. Let $G$ be a connected
graph, let $v_{\mathsf{init}}\in V(G)$ and let $k\in\mathbb{N}$. Let
$\\{\mathsf{RC}_{1},\ldots,\mathsf{RC}_{k}\\}$ be a solution, let $1\leq i\leq
k$ and denote
$\mathsf{RC}_{i}=(v_{0}=v_{\mathsf{init}},v_{1},v_{2},\ldots,v_{\ell}=v_{\mathsf{init}})$
for some $\ell\in\mathbb{N}$. If we define a multiset
$\widehat{E}_{\mathsf{RC_{i}}}=\\{\\{v_{j},v_{j+1}\\}\leavevmode\nobreak\
|\leavevmode\nobreak\ 0\leq j\leq\ell-1\\}$, then, clearly,
$\mathsf{RC}_{i}=(v_{0}=v_{\mathsf{init}},v_{1},v_{2},\ldots,v_{\ell}=v_{\mathsf{init}})$
is an Eulerian cycle in $\mathsf{Graph}(\widehat{E}_{\mathsf{RC_{i}}})$. We
call this graph the $\mathsf{RC}_{i}$-graph (see Figure 1(b)):

######  Definition 3.1 (Robot Cycle-Graph).

Let $G$ be a graph, let $v_{\mathsf{init}}\in V(G)$ and let
$\mathsf{RC}=(v_{0}=v_{\mathsf{init}},v_{1},v_{2},\ldots,v_{\ell}=v_{\mathsf{init}})$
be a robot cycle. The $\mathsf{RC}$-graph, denoted by
$\mathsf{Graph}(\mathsf{RC})$, is the multigraph
$\mathsf{Graph}(\widehat{E}_{\mathsf{RC}})$, where
$\widehat{E}_{\mathsf{RC}}=\\{\\{v_{i},v_{i+1}\\}\leavevmode\nobreak\
|\leavevmode\nobreak\ 0\leq i\leq\ell-1\\}$ is a multiset.

Let $G$ be a graph, let $v_{\mathsf{init}}\in V(G)$ and let
$\mathsf{RC}=(v_{0}=v_{\mathsf{init}},v_{1},v_{2},\ldots,v_{\ell}=v_{\mathsf{init}})$
be a robot cycle. Then $\mathsf{RC}$ is an Eulerian cycle in
$\mathsf{Graph}(\mathsf{RC})$.

On the opposite direction, let $\widehat{E}$ be a multiset with elements from
$E(G)$, and assume that $v_{\mathsf{init}}\in V(\mathsf{Graph}(\widehat{E}))$.
Let $\mathsf{RC}=(v_{0},v_{1},v_{2},\ldots,v_{\ell}=v_{0})$ be an Eulerian
cycle in $\mathsf{Graph}(\widehat{E})$ and assume, without loss of generality,
that $v_{0}=v_{\ell}=v_{\mathsf{init}}$. It is easy to see that $\mathsf{RC}$
is a robot cycle in $G$:

Let $G$ be a graph, let $v_{\mathsf{init}}\in V(G)$, let $\widehat{E}$ be a
multiset with elements from $E(G)$ and assume that $v_{\mathsf{init}}\in
V(\mathsf{Graph}(\widehat{E}))$. Let
$\mathsf{RC}=(v_{0}=v_{\mathsf{init}},v_{1},v_{2},\ldots,v_{\ell}=v_{\mathsf{init}})$
be an Eulerian cycle in $\mathsf{Graph}(\widehat{E})$. Then, $\mathsf{RC}$ is
a robot cycle in $G$.

From Sections 3 and 3, we get that finding a solution is equal to find $k$
multisets $\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that: (i) for every
$1\leq i\leq k$, $v_{\mathsf{init}}\in V(\mathsf{Graph}(\widehat{E}_{i}))$
(ii) for every $1\leq i\leq k$, there exists an Eulerian cycle in
$\mathsf{Graph}(\widehat{E}_{i})$ and (iii)
$E(G)\subseteq\widehat{E}_{1}\cup\ldots\cup\widehat{E}_{k}$, that is, each
$e\in E$ appears at least once in at least one of
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$.

Recall that, in a multigraph $\widehat{G}$, there exists an Eulerian cycle if
and only if $\widehat{G}$ is connected and each $v\in V(\widehat{G})$ has even
degree in $\widehat{G}$ [3]. Thus, we have the following lemma:

######  Lemma 3.2.

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$ and let
$k,B\in\mathbb{N}$. Then, $(G,v_{\mathsf{init}},k,B)$ is a yes-instance of CGE
if and only if there exist $k$ multisets
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ with elements from $E(G)$, such that
the following conditions hold:

  1. 1.

For every $1\leq i\leq k$, $v_{\mathsf{init}}\in
V(\mathsf{Graph}(\widehat{E}_{i}))$.

  2. 2.

For every $1\leq i\leq k$, $\mathsf{Graph}(\widehat{E}_{i})$ is connected, and
every vertex in $\mathsf{Graph}(\widehat{E}_{i})$ has even degree.

  3. 3.

$E(G)\subseteq\widehat{E}_{1}\cup\ldots\cup\widehat{E}_{k}$.

  4. 4.

$\mathsf{max}\\{|\widehat{E}_{1}|,\ldots,|\widehat{E}_{k}|\\}\leq B$.

##  4 High-Level Overview

###  4.1 FPT Algorithm with Respect to Vertex Cover

Our algorithm is based on a reduction to the ILP problem. We aim to construct
linear equations that verify the conditions in Lemma 3.2.

####  4.1.1 Encoding $\widehat{E}_{i}$ by a Valid Pair

First, we aim to satisfy the “local” conditions of Lemma 3.2 for each robot,
that is, Conditions 1 and 2. Let us focus on the “harder” condition of the
two, that is, Condition 2. We aim to encode any potential $\widehat{E}_{i}$ by
smaller subsets whose union is $\widehat{E}_{i}$. In addition, we would like
the “reverse” direction as well: every collection of subsets that we will be
able to unite must create some valid $\widehat{E}_{i}$. Note that we have two
goals to achieve when uniting the subsets together: (i) derive a connected
graph, where (ii) each vertex has even degree. In the light of this, the most
natural encoding for the subsets are cycles, being the simplest graphs
satisfying both aforementioned goals. Indeed, every cycle is connected, and a
graph composed only of cycles is a graph where every vertex has even degree.
Here, the difficulty is to maintain the connectivity of the composed graph. On
the positive side, observe that every cycle in the input graph $G$ has a non-
empty intersection with any vertex cover $\mathsf{VC}$ of $G$. So, we deal
with the connectivity requirement as follows. We seek for a graph
$\overline{G}$ that is essentially (but not precisely) a subgraph of $G$ that
is (i) “small” enough, and (ii) for every valid $\widehat{E}_{i}$, there
exists $\mathsf{CC}\subseteq E(\overline{G})$ such that
$\mathsf{Graph}(\mathsf{CC})$ is a “submultigraph” of
$\mathsf{Graph}(\widehat{E}_{i})$, $\mathsf{Graph}(\mathsf{CC})$ is connected,
and
$V(\mathsf{Graph}(\mathsf{CC}))\cap\mathsf{VC}=V(\mathsf{Graph}(\widehat{E}_{i}))\cap\mathsf{VC}$.

Equivalence Graph $G^{*}$. A first attempt to find such a graph is as follows.
We define an equivalence relation on $V(G)\setminus\mathsf{VC}$ based on the
sets of neighbors of the vertices in $V(G)\setminus\mathsf{VC}$ (see
Definition 5.2) (see the $4$ equivalence classes of the graph $G$ in Figure
2(a)). We denote the set of equivalence classes induced by this equivalence
relation by $\mathsf{EQ}$. Then $G^{*}$ is the graph defined as follows (for
more details, see Definition 5.3).

######  Definition 4.1 (Equivalence Graph $G^{*}$).

Let $G^{*}$ be the graph that: (i) contains $\mathsf{VC}$, and the edges
having both endpoints in $\mathsf{VC}$, and (ii) where every equivalence class
$u^{*}\in\mathsf{EQ}$ is represented by a single vertex adjacent to the
neighbors of some $u\in u^{*}$ in $G$ (which belong to $\mathsf{VC}$). See
Figure 2(b).

Unfortunately, this attempt fails, as we might need to use more than one
vertex from the same $u^{*}\in\mathsf{EQ}$ in order to maintain the
connectivity. E.g., see Figure 3(b). If we delete $r_{2}$ and $y_{5}$, which
are in the same equivalence class (in $G$) as $r_{1}$ and $y_{6}$,
respectively, then the graph is no longer connected.

(a) $G$

(b) $G^{*}$

(c) $\overline{G}$

Figure 2: An illustration of a graph $G$ (in (a)), and its corresponding
graphs $G^{*}$ (in (b)) and $\overline{G}$ (in (c)). The vertex cover vertices
and their edges are shown in orange. The $4$ equivalence classes and their
vertices are shown by red, yellow, green, and blue.

The Multigraph $\overline{G}$. So, consider the following second attempt. We
use the aforementioned graph $G^{*}$, but instead of one vertex representing
each $u^{*}\in\mathsf{EQ}$, we have
$\mathsf{min}\\{|u^{*}|,2^{|\mathsf{N}_{G^{*}}({u^{*}})|}\\}$ vertices.
Observe that given a connected subgraph $G^{\prime}$ of $G$, and two vertices
$u,u^{\prime}\in u^{*}$ such that
$\mathsf{N}_{G^{\prime}}(u)=\mathsf{N}_{G^{\prime}}(u^{\prime})$, it holds
that $G\setminus\\{u^{\prime}\\}$ remains connected (e.g., see Figure 3(a) and
3(b). The connectivity is still maintained even after deleting all but one
vertex in the same equivalence class (in $G$) having same neighbourhood).
Therefore, we have enough vertices for each $u^{*}\in\mathsf{EQ}$ in the
graph, and its size is a function of $|\mathsf{VC}|$; so, we obtained the
sought graph $\overline{G}$. Now, we would like to have an additional property
for $\mathsf{CC}$, which is that every vertex in $\mathsf{Graph}(\mathsf{CC})$
has even degree in it. To this end, we add to $\overline{G}$ more vertices for
each $u^{*}\in\mathsf{EQ}$. See Figure 3(c). The vertex $g_{13}$ having the
same neighbours as $g_{11}$ in $H$ and being in the same equivalence class (in
$G$) as $g_{11}$ is added to make the degrees of $1$ and $2$ even. We have the
following definition for $\overline{G}$ (for more details, see Definition 5.4
and the discussion before this definition).

######  Definition 4.2 (The Multigraph $\overline{G}$).

Let $\overline{G}$ be the graph that: (i) contains $\mathsf{VC}$, and the
edges having both endpoints in $\mathsf{VC}$, (ii) for every equivalence class
$u^{*}\in\mathsf{EQ}$, there are exactly
$\mathsf{min}\\{|u^{*}|,2^{|\mathsf{N}_{G^{*}}({u^{*}})|}+|\mathsf{VC}|^{2}\\}$
vertices, adjacent to the neighbors of some $u\in u^{*}$ in $G$ (which belong
to $\mathsf{VC}$), (iii) each edge in $\overline{G}$ appears exactly twice in
$E(\overline{G})$ (for technical reasons). See Figure 2(c).

A Skeleton of $\widehat{E}_{i}$. We think of $\mathsf{Graph}(\mathsf{CC})$ as
a “skeleton” of a potential $\widehat{E}_{i}$. By adding cycles with a vertex
from $V(\mathsf{Graph}(\mathsf{CC}))\cap\mathsf{VC}$, we maintain the
connectivity, and since every vertex in $\mathsf{Graph}(\mathsf{CC})$ has even
degree, then by adding a cycle, this property is preserved as well. We have
the following definition for a skeleton.

(a) $\mathsf{Graph}(\widehat{E})$

(b) $H$

(c) $\mathsf{Graph}(\mathsf{CC})$

(d) $\mathsf{Graph}(\mathsf{CC}^{\prime})$

Figure 3: The graphs shown here are with respect to the graph $G$ shown in
Figure 2(a). An illustration of (a) a graph $\mathsf{Graph}(\widehat{E})$, (b)
the graph $H$ obtained by deleting all but one vertex from the same
equivalence class in $G$ and have the same neighbours in
$\mathsf{Graph}(\widehat{E})$, (c) the graph $\mathsf{Graph}(\mathsf{CC})$
where $\mathsf{CC}$ is a skeleton of $\widehat{E}$ obtained from the graph in
(b) by adding four more edges from $\mathsf{Graph}(\widehat{E})\setminus H$,
and (d) the graph $\mathsf{Graph}(\mathsf{CC}^{\prime})$ where
$\mathsf{CC}^{\prime}$ is the skeleton in $\overline{G}$ that is derived from
the skeleton $\mathsf{CC}$.

######  Definition 4.3 (A Skeleton $\mathsf{CC}$).

A skeleton of $\widehat{E}_{i}$ is $\mathsf{CC}\subseteq\widehat{E}_{i}$ such
that: (i) $\mathsf{Graph}(\mathsf{CC})$ is a “submultigraph” of
$\overline{G}$, (ii) $\mathsf{Graph}(\mathsf{CC})$ is connected,
$v_{\mathsf{init}}\in V(\mathsf{Graph}(\mathsf{CC}))$ and every vertex in
$\mathsf{Graph}(\mathsf{CC})$ has even degree, and (iii)
$V(\mathsf{Graph}(\mathsf{CC}))\cap\mathsf{VC}=V(\mathsf{Graph}(\widehat{E}_{i}))\cap\mathsf{VC}$
(See Figure 3(d)).

An $\widehat{E}_{i}$-Valid Pair. In Section 5, we prove that we might assume
that the $\widehat{E}_{i}$’s are nice multisets, that is, a multiset where
every element appears at most twice. In Lemma 5.10, we prove that every
$\widehat{E}_{i}$ (assuming $\widehat{E}_{i}$ is nice) can be encoded by a
skeleton $\mathsf{CC}$ (See Figure 3(c).) and a multiset ${\cal C}$ of cycles
(of length bounded by $2|\mathsf{VC}|$). We say that $(\mathsf{CC},{\cal C})$
is an $\widehat{E}$-valid pair (for more details, see Definition 5.9 and
Section 5.1).

######  Definition 4.4 (A Valid Pair).

A pair $(\mathsf{CC},{\cal C})$, where $\mathsf{CC}$ is a skeleton of
$\widehat{E}_{i}$ and ${\cal C}$ is a multiset of cycles in
$\mathsf{Graph}(\widehat{E}_{i})$, is an $\widehat{E}_{i}$-valid pair skeleton
$\mathsf{CC}$ if:

  1. 1.

The length of each cycle in ${\cal C}$ is bounded by $2|\mathsf{VC}|$.

  2. 2.

At most $2|\mathsf{VC}|^{2}$ cycles in ${\cal C}$ have length other than $4$.

  3. 3.

$\mathsf{CC}\cup\bigcup_{C\in{\cal C}}E(C)=\widehat{E}_{i}$ (being two
multisets).

####  4.1.2 Robot and Cycle Types

Now, obviously, the number of different cycles in $G$ (of length bounded by
$2|\mathsf{VC}|$) is potentially huge. Fortunately, it is suffices to look at
cycles in $G^{*}$ in order to preserve Condition 2 of Lemma 3.2: assume that
we have a connected $\mathsf{Graph}(\mathsf{CC})$ such that every vertex in
$\mathsf{Graph}(\mathsf{CC})$ has even degree in it, and a multiset of cycles
with a vertex from $V(\mathsf{Graph}(\mathsf{CC}))\cap\mathsf{VC}$ in $G^{*}$.
By replacing each vertex that represents $u^{*}\in\mathsf{EQ}$ by any $u\in
u^{*}$, the connectivity preserved, and the degree of each vertex is even.

Thus, each robot is associated with a robot type $\mathsf{RobTyp}$, which
includes a skeleton $\mathsf{CC}$ of the multiset $\widehat{E}_{i}$ associated
with the robot (along other information discussed later). In order to preserve
Condition 1 of Lemma 3.2, we also demand that $v_{\mathsf{init}}\in
V(\mathsf{Graph}(\mathsf{CC}))$. Generally, for each type we define, we will
have a variable that stands for the number of elements of that type. We are
now ready to present our first equation of the ILP reduction:

Equation 1: Robot Type for Each Robot. In this equation, we ensure that the
total sum of robots of the different robot types is exactly $k$, that is,
there is exactly one robot type for each robot:

1\.
$\displaystyle{\sum_{\mathsf{RobTyp}\in\mathsf{RobTypS}}x_{\mathsf{RobTyp}}=k}$.

In addition, the other “pieces” of the “puzzle”, that is, the cycles, are also
represented by types: Each cycle $C$ of length at most $2|\mathsf{VC}|$ in
$G^{*}$ is represented by a cycle type, of the form
$\mathsf{CycTyp}=(C,\mathsf{RobTyp})$ (along other information discussed
later), where $\mathsf{RobTyp}$ is a robot type that is “able to connect to
$C$”, that is, $V(\mathsf{Graph}(\mathsf{CC}))\cap\mathsf{VC}\cap
V(C)\neq\emptyset$ for $\mathsf{RobTyp}=\mathsf{CC}$. Similarly, we will have
equations for our other types.

Satisfying the Budget Restriction. Now, we aim to satisfy the budget condition
(Condition 2 of Lemma 3.2), that is, for every $i\in[k]$,
$|\widehat{E}_{i}|\leq B$. Let $i\in[k]$ and let $(\mathsf{CC},{\cal C})$ be
an $\widehat{E}$-valid pair. So,
$\widehat{E}_{i}=\mathsf{CC}\cup(\bigcup_{C\in{\cal C}}E(C))$ (being a union
of two multisets). Now, in Lemma 5.10, we prove that “most” of the cycles in
${\cal C}$ are of length $4$, that is, for every $2\leq j\leq
2|\mathsf{VC}|,j\neq 4$, the number of cycles of length $j$ in ${\cal C}$ is
bounded by $2|\mathsf{VC}|^{2}$. Therefore, we add to the definition of a
robot type also the number of cycles of length exactly $j$, encoded by a
vector
$\mathsf{NumOfCyc}=(N_{2},N_{3},N_{5},N_{6},\ldots,N_{2|\mathsf{VC}|})$. So,
for now, a robot type is $\mathsf{RobTyp}=(\mathsf{CC},\mathsf{NumOfCyc})$.
Thus, in order to satisfy the budget condition, we verify that the budget used
by all the robots of a robot type
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{NumOfCyc})$, is as expected together.
First, we ensure that the number of cycles of each length $2\leq j\leq
2|\mathsf{VC}|,j\neq 4$, is exactly as the robot type demands, times the
number of robots associated with this type, that is, $N_{j}\cdot
x_{\mathsf{RobTyp}}$. So, we have the following equation:

Equation 5: Assigning the Exact Number of Cycles of Length Other Than $4$ to
Each Robot Type. We have the following notation:
$\mathsf{CycTypS}(\mathsf{RobTyp},j)$ is the set of cycle types for cycles of
length $j$ assigned to a robot of robot type $\mathsf{RobTyp}$.

5\. For every robot type $\mathsf{RobTyp}=(\mathsf{CC},\mathsf{NumOfCyc})$ and
for every $2\leq j\leq 2|\mathsf{VC}|$, $j\neq 4$,
$\displaystyle{\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{RobTyp},j)}}x_{\mathsf{CycTyp}}=N_{j}\cdot
x_{\mathsf{RobTyp}}}$, where
$\mathsf{NumOfCyc}=(N_{2},N_{3},N_{5},N_{6},\ldots,$ $N_{2|\mathsf{VC}|})$.

Observe that once this equation is satisfied, we are able to arbitrary
allocate $N_{j}$ cycles of length $j$ to each robot of type $\mathsf{RobTyp}$.
So, in order to verify the budget limitation, we only need to deal with the
cycles of length $4$. Now, notice that the budget left for a robot of type
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{NumOfCyc})$ for the cycles of length $4$
is $B-(|\mathsf{CC}|+\sum_{2\leq j\leq 2|\mathsf{VC}|,j\neq 4}N_{j}\cdot j)$,
where $\mathsf{NumOfCyc}=(N_{2},N_{3},N_{5},N_{6},\ldots,N_{2|\mathsf{VC}|})$.
Now, the maximum number of cycles we can add to a single robot of type
$\mathsf{RobTyp}$ is the largest number which is a multiple of $4$, that is
less or equal to $B-\mathsf{Bud}(\mathsf{RobTyp})$. So, for every robot type
$\mathsf{RobTyp}$ let
$\mathsf{CycBud}(\mathsf{RobTyp})=\lfloor(B-(|\mathsf{CC}|+\sum_{2\leq j\leq
2|\mathsf{VC}|,j\neq 4}N_{j}\cdot j))\cdot\frac{1}{4}\rfloor\cdot 4$. Notice
that $\mathsf{CycBud}(\mathsf{RobTyp})$ is the budget left for the cycles of
length $4$. Thus, we have the following equation:

Equation 6: Verifying the Budget Limitation. This equation is defined as
follows.

6\. For every $\mathsf{RobTyp}\in\mathsf{RobTypS}$,
$\displaystyle{\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{RobTyp},4)}}4\cdot
x_{\mathsf{CycTyp}}\leq
x_{\mathsf{RobTyp}}\cdot\mathsf{CycBud}(\mathsf{RobTyp})}$.

By now, we have that there exist $\widehat{E}_{1},\ldots,\widehat{E}_{k}$ that
satisfy Conditions 1, 2 and 4 of Lemma 3.2 if and only if Equations 1, 5 and 6
can be satisfied.

Covering Edges with Both Endpoints in $\mathsf{VC}$. Now, we aim to satisfy
Condition 3 of Lemma 3.2, that is, we need to verify that every edge is
covered by at least one robot. First, we deal with edges with both endpoints
in $\mathsf{VC}$. Here, for every $\\{u,v\\}$ such that $u,v\in\mathsf{VC}$,
we just need to verify that at least one cycle or one of the $\mathsf{CC}$’s
contains $\\{u,v\\}$. This we can easily solve by the following equation:

Equation 4: Covering Each Edge With Both Endpoints in $\mathsf{VC}$. We have
the following notations: For every $\\{u,v\\}\in E$ such that
$u,v\in\mathsf{VC}$, (i) let $\mathsf{CycTypS}(\\{u,v\\})$ be the set of cycle
types $\mathsf{CycTyp}=(C,\mathsf{RobTyp})$ where $C$ covers $\\{u,v\\}$, and
(ii) let $\mathsf{RobTypS}(\\{u,v\\})$ be the set of robot types
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{NumOfCyc})$ where $\mathsf{CC}$ covers
$\\{u,v\\}$. In this equation, we ensure that each $\\{u,v\\}\in E(G)$ with
both endpoints in $\mathsf{VC}$ is covered at least once:

4\. For every $\\{u,v\\}\in E$ such that $u,v\in\mathsf{VC}$,

$\displaystyle{\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\\{u,v\\})}}x_{\mathsf{CycTyp}}+\sum_{{\mathsf{RobTyp}\in\mathsf{RobTypS}(\\{u,v\\})}}}$
$x_{\mathsf{RobTyp}}\geq 1$.

Let $\mathsf{RobTypS}$ be the set of the robot types, and let
$\mathsf{CycTypS}$ be the set of cycle types.

Covering Edges with an Endpoint in $V(G)\setminus\mathsf{VC}$. Now, we aim to
cover the edges from $E(G)$ with (exactly) one endpoint in
$V(G)\setminus\mathsf{VC}$. Here, we need to work harder. Let $x_{z}$, for
every $z\in\mathsf{RobTypS}\cup\mathsf{CycTypS}$, be values that satisfy
Equations 1 and 4–6. As for now, we will arbitrary allocate cycles to robots
according to their types. Then, we will replace every $u^{*}\in
V(\mathsf{Graph}(\mathsf{CC}_{i}))$ and $u^{*}\in V(C)$, for every cycle $C$
allocated to the $i$-th robot, by an arbitrary $u\in u^{*}$. Then, we will
define $\widehat{E}_{i}$ as the union of edge set of the cycles and
$\mathsf{CC}_{i}$ we obtained. We saw that due to Equations 1, 5 and 6,
Conditions 1, 2 and 4 of Lemma 3.2 are satisfied. In addition, due to
Equations 4, we ensure that each $\\{u,v\\}\in E(G)$ with both endpoints in
$\mathsf{VC}$ is covered. The change we need to do in order to cover edges
with an endpoint in $V(G)\setminus\mathsf{VC}$ is to make a smarter choices
for the replacements of $u^{*}$ vertices.

####  4.1.3 Vertex Type

Allocation of Multisets with Elements from $\mathsf{N}_{G^{*}}({u^{*}})$.
Observe that each $u^{*}_{j}\in V(\mathsf{Graph}(\mathsf{CC}_{i}))$ that is
replaced by some $u\in u^{*}$, covers the multiset of edges
$\\{\\{u,v\\}\leavevmode\nobreak\ |\leavevmode\nobreak\
v\in\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{i})}({u^{*}_{j}})\\}$.
In addition, every $u^{*}\in V(C)$ that is replaced by $u\in u^{*}$, covers
the multiset of edges $\\{\\{u,v\\},\\{u,v^{\prime}\\}\\}$, where $v$ and
$v^{\prime}$ are the vertices right before and right after $u$ in $C$,
respectively. Now, in order to cover every edge with an endpoint in
$V(G)\setminus\mathsf{VC}$, we need to cover the set
$\\{\\{u,v\\}\leavevmode\nobreak\ |\leavevmode\nobreak\
v\in\mathsf{N}_{G^{*}}({u^{*}})\\}$ for every $u\in u^{*}\in\mathsf{EQ}$.
Therefore, we would like to ensure that the union of multisets of neighbors
“allocated” for each $u$, when we replace some $u^{*}$ by $u$, contains
$\\{\\{u,v\\}\leavevmode\nobreak\ |\leavevmode\nobreak\
v\in\mathsf{N}_{G^{*}}({u^{*}})\\}$.

Figure 4: An illustration of the parts of a solution around an independent set
vertex $v$. The three colors represent the parts of the multisets
corresponding to three robots. The solid edges belong to the skeleton of the
specific robot. The dashed edges belong to a cycle, labelled in the figure, of
the multiset of the cycles corresponding to the specific robot. The vertex
type of $v$ derived from the solution shown in the figure is
$(v^{*},\\{\\{1,6,8,8\\},\\{3,4\\},\\{7,8\\},\\{2,2,5,6\\}\\})$, where $v\in
v^{*}\in\mathsf{EQ}$.

The Set $\mathsf{NeiSubsets}$ of Multisets Needed to Allocate to a Vertex.
Now, the reverse direction holds as well: let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ be multisets satisfying the
conditions of Lemma 3.2, for every $i\in[k]$, let $(\mathsf{CC}_{i},{\cal
C}_{i})$ be an $\widehat{E}_{i}$-valid pair, and let $u\in
u^{*}\in\mathsf{EQ}$. Consider the following multisets (*): (i) for every
$i\in[k]$ such that $u\in V(\mathsf{Graph}(\mathsf{CC}_{i}))$, the multiset
$\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{i})}(u)$; (ii) for every
$i\in[k]$ and $C\in{\cal C}_{i}$ and every appearance of $u$ in $C$, the
multiset $\\{v,v^{\prime}\\}$, where $v$ and $v^{\prime}$ are the vertices in
$C$ right before and right after the appearance of $u$. By Condition 3 of
Lemma 3.2, every edge appears in at least one among
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$. So, as for every $i\in[k]$,
$\widehat{E}_{i}=\mathsf{CC}_{i}\bigcup_{C\in{\cal C}_{i}}E(C)$, the union of
the multisets in (*) obviously contains $\mathsf{N}_{G^{*}}({u^{*}})$, e.g.
see Figure 4. We would like to store the information of these potential
multisets that ensures we covered $\mathsf{N}_{G^{*}}({u^{*}})$. The issue is
that there might be a lot of multisets, as $u$ might appear in many
$\widehat{E}_{i}$’s. Clearly, it is sufficient to store one copy of each such
multiset, as we only care that the union of the multisets contains
$\mathsf{N}_{G^{*}}({u^{*}})$. Now, as we assume that
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ are nice multisets, each element in
every multiset we derived appears at most twice in that multiset. In addition,
since every edge in $E(\overline{G})$ appears at most twice, for each skeleton
$\mathsf{CC}\subseteq E(\overline{G})$, each edge appears at most twice in
$E(\mathsf{Graph}(\mathsf{CC}))$. So, for each $u^{*}_{j}\in
V(\mathsf{Graph}(\mathsf{CC}))$ we replace by some $u\in u^{*}$, in the
multiset of neighbors that are covered, every element appears at most twice.
Moreover, since the degree is even, we have that the number of element in each
multiset is even.

For a set $A$ we define the multiset
$A\times\mathsf{2}=\\{a,a\leavevmode\nobreak\ |\leavevmode\nobreak\ a\in
A\\}$. That is, each element in $A$ appears exactly twice in
$A\times\mathsf{2}$. Thus, we have the following definition for a vertex type
(for more details, see Section 5.2).

######  Definition 4.5 (Vertex Type).

Let $G$ be a connected graph and let $\mathsf{VC}$ be a vertex cover of $G$.
Let $u^{*}\in\mathsf{EQ}$ and let $\mathsf{NeiSubsets}\subseteq
2^{\mathsf{N}_{G^{*}}(u^{*})\times\mathsf{2}}$. Then,
$\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})$ is a vertex type if for every
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}$, $|\mathsf{NeiSub}|$ is even, and
$\mathsf{N}_{G^{*}}(u^{*})\subseteq\bigcup\mathsf{NeiSubsets}$.

Now, given $\widehat{E}_{1},\ldots,\widehat{E}_{k}$ satisfying the conditions
of Lemma 3.2, for every $i\in[k]$, an $\widehat{E}_{i}$-valid pair
$(\mathsf{CC}_{i},{\cal C}_{i})$, and $u\in u^{*}\in\mathsf{EQ}$, we derive
the vertex type of $u$ as follows. We take the set $\mathsf{NeiSubsets}$ of
multisets as described in (*). Clearly, $(u^{*},\mathsf{NeiSubsets})$ is a
vertex type (for more details, see Definition 5.13 and Lemma 5.15).

For the reverse direction, we will use vertex type in order to cover the edges
incident to each $u\in u^{*}\in\mathsf{EQ}$. Let $\mathsf{VerTypS}$ be the set
of vertex types. We have a variable $x_{z}$ for every $z\in\mathsf{VerTypS}$.
First, each $u\in u^{*}\in\mathsf{EQ}$ is associated with exactly one vertex
type $\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})$, for some
$\mathsf{NeiSubsets}$. To achieve this, we first ensure that for every
$u^{*}\in\mathsf{EQ}$, the total sum of $x_{z}$ for
$z\in\mathsf{VerTypS}_{u^{*}}$, is exactly $|u^{*}|$, where
$\mathsf{VerTypS}_{u^{*}}=\\{(u^{*},\mathsf{NeiSubsets})\in\mathsf{VerTypS}\\}$.

Equation 2: Vertex Type for Each Vertex. This equation is defined as follows.

2\. For every $u^{*}\in\mathsf{EQ}$,
$\displaystyle{\sum_{\mathsf{VerTyp}\in\mathsf{VerTypS}_{u^{*}}}x_{\mathsf{VerTyp}}=|u^{*}|}$

Given values for the variables that satisfy the equation, we arbitrary
determine a vertex type $(u^{*},\mathsf{NeiSubsets})$ for each $u\in u^{*}$,
such that there are exactly $x_{\mathsf{VerTyp}}$ vertices of type
$\mathsf{VerTyp}$.

Allocation Functions of Multisets to Vertex Types. Now, let $u\in
u^{*}\in\mathsf{EQ}$ of a vertex type $(u^{*},\mathsf{NeiSubsets})$. We aim
that when we do the replacements of $u^{*}$’s by vertices from $u^{*}$, each
$u$ gets an allocation of at least one of any of the multisets in
$\mathsf{NeiSubsets}$. This ensures that we covered all of the edges adjacent
to $u$. Instead of doing this for each $u\in u^{*}\in\mathsf{EQ}$, we will
ensure that each $\mathsf{NeiSub}\in\mathsf{NeiSubsets}$ is allocated for
vertices of type $(u^{*},\mathsf{NeiSubsets})$ at least $x_{\mathsf{VerTyp}}$
times. To this end, we add more information for the robot types. For a robot
type with a skeleton $\mathsf{CC}$, recall that we replace each $u^{*}_{j}\in
V(\mathsf{Graph}({\mathsf{CC})})$ by some $u\in u^{*}$. The robot type also
determines what is the vertex type of $u$ that replaces $u^{*}_{j}$. In
particular, we add to the robot type an allocation for each of
$\\{(u^{*}_{j},\widehat{\mathsf{N}}_{\mathsf{Graph}({\mathsf{CC})}}(u^{*}_{j}))\leavevmode\nobreak\
|\leavevmode\nobreak\ u^{*}_{j}\in V(\mathsf{Graph}({\mathsf{CC})})\\}$, that
is, a function $\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})}$ from this set
into $\mathsf{VerTypS}$ (e.g., a robot of a robot type associated with the
skeleton illustrated by Figure 3(d), needs to allocate the pair
$(r^{*}_{1},\\{1,1\\})$, along with the other pairs shown in the figure).
Observe that $u_{j}^{*}$ is the vertex being replaced, and
$\widehat{\mathsf{N}}_{\mathsf{Graph}({\mathsf{CC})}}(u^{*}_{j})$ is the
multiset of neighbors that are covered. So, we demand that each
$(u^{*}_{j},\widehat{\mathsf{N}}_{\mathsf{Graph}({\mathsf{CC})}}(u^{*}_{j}))$
is allocated to a vertex type $(u^{*},\mathsf{NeiSubsets})$ that “wants” to
get $\widehat{\mathsf{N}}_{\mathsf{Graph}({\mathsf{CC})}}(u^{*}_{j})$, that
is,
$\widehat{\mathsf{N}}_{\mathsf{Graph}({\mathsf{CC})}}(u^{*}_{j})\in\mathsf{NeiSubsets}$
(e.g, a robot of a robot type associated with the skeleton illustrated by
Figure 3(d), might allocate $(r^{*}_{1},\\{1,1\\})$ to a vertex type
$(r^{*},\\{\\{1,1\\},\\{3,4\\}\\})$). Now, we are ready to define a robot type
as follows (for more details, see Section 5.3).

######  Definition 4.6 (Robot Type).

A robot type is
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},\mathsf{NumOfCyc})$
such that:

  1. 1.

$\mathsf{CC}\subseteq E(\overline{G})$.

  2. 2.

$\mathsf{Graph}(\mathsf{CC})$ is connected, every vertex in
$\mathsf{Graph}(\mathsf{CC})$ has even degree and
$v_{\mathsf{init}}\in V(\mathsf{Graph}(\mathsf{CC}))$.

  3. 3.

$\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})}$ is an allocation of
$\\{(u^{*}_{j},\widehat{\mathsf{N}}_{\mathsf{Graph}({\mathsf{CC})}}(u^{*}_{j}))\leavevmode\nobreak\
|\leavevmode\nobreak\ u^{*}_{j}\in V(\mathsf{Graph}({\mathsf{CC})})\\}$ to
vertex types.

  4. 4.

$\mathsf{NumOfCyc}=(N_{2},N_{3},N_{5},N_{6},\ldots,N_{2|\mathsf{VC}|})$, where
$0\leq N_{i}\leq 2|\mathsf{VC}|^{2}$ for every $2\leq i\leq 2|\mathsf{VC}|$,
$i\neq 4$.

Similarly, we add to a cycle type with a cycle $C$ in $G^{*}$ an allocation of
the multiset $\\{\\{v,v^{\prime}\\}\leavevmode\nobreak\ |\leavevmode\nobreak\
u^{*}\in V(C)$, $v$ and $v^{\prime}$ are the vertices appears right before and
right after $u^{*}\\}$ to vertex types (given by a function
$\mathsf{PaAlloc}_{C}$). Now, we are ready to define a cycle type as follows
(for more details, see Section 5.4).

######  Definition 4.7 (Cycle Type).

Let $C\in\mathsf{Cyc}_{G^{*}}$, let $\mathsf{PaAlloc}_{C}$ be an allocation of
$\\{\\{v,v^{\prime}\\}\leavevmode\nobreak\ |\leavevmode\nobreak\ u^{*}$ $\in
V(C)$, $v$ and $v^{\prime}$ are the vertices appears right before and right
after $u^{*}\\}$ to vertex types, and let
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},\mathsf{NumOfCyc})$
be a robot type. Then,
$\mathsf{CycTyp}=(C,\mathsf{PaAlloc}_{C},\mathsf{RobTyp})$ is a cycle type if
$V(\mathsf{Graph}(\mathsf{CC}))\cap V(C)\cap\mathsf{VC}\neq\emptyset$.

We have the following notations.

For every $\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})\in\mathsf{VerTypS}$,
every $\mathsf{NeiSub}=\\{v,v^{\prime}\\}\in\mathsf{NeiSubsets}$ and $1\leq
j\leq 2|\mathsf{VC}|$, $\mathsf{CycTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)$
is the set of cycle types that assign $\mathsf{NeiSub}$ to $\mathsf{VerTyp}$
exactly $j$ times. For every
$\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})\in\mathsf{VerTypS}$, every
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}$ and $1\leq j\leq
2^{|\mathsf{VC}|}+|\mathsf{VC}|^{2}$,
$\mathsf{RobTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)$ is the set of robot
types that assign $\mathsf{NeiSub}$ to $\mathsf{VerTyp}$ exactly $j$ times.
Finally, we have the following equation:

Equation 3: Assigning Enough Subsets for Each Vertex Type. The equation is
defined as follows.

3\. For every
$\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})\in\mathsf{VerTypS}$, and every
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}$,

$\displaystyle{\sum_{j=1}^{2{|\mathsf{VC}|}}\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)}}j\cdot
x_{\mathsf{CycTyp}}+}$
$\displaystyle{\sum_{j=1}^{2^{|\mathsf{VC}|}+|\mathsf{VC}|^{2}}\sum_{{\mathsf{RobTyp}\in\mathsf{RobTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)}}j\cdot
x_{\mathsf{RobTyp}}\geq x_{\mathsf{VerTyp}}}$.

####  4.1.4 The Correctness of The Reduction

We denote the ILP instance associated with Equations 1–6 by
$\mathsf{Reduction}(G,v_{\mathsf{init}},k,B)$. Now, we give a proof sketch for
the correctness of the reduction:

######  Lemma 4.8.

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$ and let
$k,B\in\mathbb{N}$. Then, $(G,v_{\mathsf{init}},k,B)$ is a yes-instance of
CGE, if and only if $\mathsf{Reduction}(G,v_{\mathsf{init}},k,B)$ is a yes-
instance of the Integer Linear Programming.

######  Proof 4.9.

Let $x_{z}$, for every
$z\in\mathsf{VerTypS}\cup\mathsf{RobTypS}\cup\mathsf{CycTypS}$, be values
satisfying Equations 1–6. For every vertex type
$\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})$ and each
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}$, let
$\mathsf{Alloc}(\mathsf{VerTyp},\mathsf{NeiSub})$ be the set of every
allocation of $\mathsf{NeiSub}$ to $\mathsf{VerTyp}$ by cycles or robots. We
arbitrary allocate each element in
$\mathsf{Alloc}(\mathsf{VerTyp},\mathsf{NeiSub})$ to a vertex in $u^{*}$, such
that every vertex $u\in u^{*}$ of type $\mathsf{VerTyp}$ gets at least one
allocation. Due to Equation 3, we ensure we can do that. Then, we replace
every $u^{*}\in V(\mathsf{Graph}(\mathsf{CC}_{i}))$ and every $u^{*}\in V(C)$
(for every $C\in{\cal C}_{i}$) by the $u\in u^{*}$ derived by the allocation.
This ensures we covered every edge adjacent to a vertex in
$V(G)\setminus\mathsf{VC}$. As seen in this overview, the other conditions of
Lemma 3.2 hold (the full proof is in Section 5.6).

For the reverse direction, let $\widehat{E}_{1},\ldots,\widehat{E}_{k}$ be
multisets satisfying the conditions of Lemma 3.2. For every $1\leq i\leq k$
let $(\mathsf{CC}_{i},{\cal C}_{i})$ be an $\widehat{E}_{i}$-valid pair. Then,
we first derive the vertex type of each $u\in V(G)\setminus\mathsf{VC}$,
according to its equivalence class in $\mathsf{EQ}$, and the set of multisets
derived from $((\mathsf{CC}_{i},{\cal C}_{i}))_{1\leq i\leq k}$ (e.g. see
Figure 4)(for more details, see Definition 5.13 and Lemma 5.15). Then, we
derive the robot type
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},\mathsf{NumOfCyc})$
for each $i\in[k]$: (i) the skeleton $\mathsf{CC}$ is determined by
$\mathsf{CC}_{i}$ (e.g., see Figure 3(d))), (ii) $\mathsf{NumOfCyc}$ is
determined by the number of cycle of each length in ${\cal C}_{i}$ and (iii)
the allocation of the multisets of $\mathsf{Graph}(\mathsf{CC}_{i})$ is
determined by the vertex types of $u\in
V(\mathsf{Graph}(\mathsf{CC}_{i}))\cap(V(G)\setminus\mathsf{VC})$ we have
already computed (for more details, see Definition 5.19 and Lemma 5.21). Then,
for every $i\in[k]$ and every $C^{\prime}\in{\cal C}_{i}$, we determine the
cycle type $\mathsf{CycTyp}=(C,\mathsf{PaAlloc}_{C},\mathsf{RobTyp})$ of
$C^{\prime}$: (i) $C$ is determined by $C^{\prime}$ (we replace each $u\in
u^{*}\in\mathsf{EQ}$ in $C^{\prime}$ by $u^{*}$), (ii) $\mathsf{RobTyp}$ is
the robot type of $i$ we have already computed, and (iii)
$\mathsf{PaAlloc}_{C}$ is determined by the vertex types of $u\in
V(C^{\prime})\cap(V(G)\setminus\mathsf{VC})$ we have already computed (for
more details, see Definition 5.24 and Lemma 5.26). Then, for every
$z\in\mathsf{VerTypS}\cup\mathsf{RobTypS}\cup\mathsf{CycTypS}$, we define
$x_{z}$ to be the number of elements of type $z$. As seen in this overview,
the values of the variables satisfy Equations 1–6 (the full proof is in
Section 5.7).

Observe that the number of variables is bounded by a function of
$|\mathsf{VC}|$, so we will get an FPT runtime with respect to $\mathsf{vc}$.
We analyze the runtime of the algorithm in Section 5.8. Thus, we conclude the
correction of Theorem 1.1.

###  4.2 Approximation Algorithm with Additive Error of
$\mathcal{O}(\mathsf{vc})$

Our algorithm is based on a greedy approach. Recall that, our new goal (from
Lemma 3.2) is to find $k$ multisets $\widehat{E}_{1},\ldots,\widehat{E}_{k}$
such that for every $1\leq i\leq k$, $v_{\mathsf{init}}\in
V(\mathsf{Graph}(\widehat{E}_{i}))$, $\mathsf{Graph}(\widehat{E}_{i})$ is
connected and each $u\in V(\mathsf{Graph}(\widehat{E}_{i}))$ has even degree
in $\mathsf{Graph}(\widehat{E}_{i})$. Now, assume that we have a vertex cover
$\mathsf{VC}$ of $G$ such that $G[\mathsf{VC}]$ is connected and
$v_{\mathsf{init}}\in\mathsf{VC}$ (e.g., see the orange vertices in Figure
5(b)), and let $I=V\setminus\mathsf{VC}$. We first make the degree of every
vertex in $I$ even in $G$, by duplicating an arbitrary edge for vertices
having odd degree (e.g., see the green edges in Figure 5(c)). Observe that,
after these operations, $G$ may be a multigraph (e.g., see the graph in Figure
5(c)).

We initialize $\widehat{E}_{1},\ldots,\widehat{E}_{k}$ with $k$ empty sets. We
partition the set of edges of $G$ with one endpoint in $I$ in the following
manner. We choose the next multiset from
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ in a round-robin fashion and put a
pair of edges, not considered so far, incident to some vertex $v\in I$, in the
multiset (e.g., see the red, blue and green edges in Figure 5(d)). This
ensures that the degree of every vertex in $I$ is even in each multiset (e.g.,
see the Figures 5(e)–5(g)). Let
$\widehat{E}^{\prime}_{1},\ldots,\widehat{E}^{\prime}_{k}$ be multisets
satisfying the conditions of Lemma 3.2. Then, due to Condition 2 of Lemma 3.2,
the degree of every vertex is even in every multiset
$\widehat{E}^{\prime}_{i}$. Thus, the total number of edges (with repetition)
incident to any vertex in
$\mathsf{Graph}(\widehat{E}^{\prime}_{1}\cup\ldots\cup\widehat{E}^{\prime}_{k})$
is even. Therefore, there must be at least one additional repetition for at
least one edge of every vertex with odd degree in $G$. So, adding an
additional edge to each vertex with odd degree is “must” and it does not
“exceed” the optimal budget. Then, we partition the edges with both endpoints
in $\mathsf{VC}$, in a balanced fashion, as follows. We choose an edge, not
considered so far, and add it to a multiset with minimum size.

Observe that, after this step, we have that: i) every edge of the input graph
belongs to at least one of the multisets $\widehat{E}_{i}$, ii) the degree of
each vertex of $I$ in each multiset is even, and iii) we have not exceeded the
optimal budget (e.g., see the Figures 6(a)–6(d)). We still need to ensure that
i) $\mathsf{Graph}(\widehat{E}_{i})$ is connected, for every $i\in[k]$, ii)
the degree of each vertex of $\mathsf{VC}$ in each multiset is even, and iii)
$v_{\mathsf{init}}\in V(\mathsf{Graph}(\widehat{E}_{i}))$ for every $i\in[k]$.
Next, we add a spanning tree of $G[\mathsf{VC}]$ to each of the
$\widehat{E}_{i}$, in order to make $\mathsf{Graph}(\widehat{E}_{i})$
connected and to ensure that $v_{\mathsf{init}}\in
V(\mathsf{Graph}(\widehat{E}_{i}))$ (e.g., see the Figures 6(f)–6(h)). Lastly,
we add at most $|\mathsf{VC}|$ edges, with both endpoints in $\mathsf{VC}$, to
every $\widehat{E}_{i}$ in order to make the degree of each $u\in\mathsf{VC}$
even in each of the multiset (e.g., see the Figures 6(i)–6(k)). Observe that
the multisets $\widehat{E}_{1},\ldots,\widehat{E}_{k}$ satisfy the conditions
of Lemma 3.2. Moreover, we added at most $\mathcal{O}(|\mathsf{VC}|)$
additional edges to each $\widehat{E}_{i}$, comparing to an optimal solution.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

Figure 5: Illustration of the execution of Lines 1–1 of Algorithm 1 on the
instance shown in Figure 5(a). The orange vertices in Figures 5(b)–5(g) are
the vertex cover vertices. (a) Running example for Algorithm 1: A graph $G$, a
vertex cover $\mathsf{VC}$ (drawn in violet) of $G$, the vertex
$v_{\mathsf{init}}=9$, and $k=3$. (b) The connected vertex cover
$\mathsf{VC}^{\prime}$ (drawn in orange) of $G$ obtained from $\mathsf{VC}$
after executing Lines 1–1 of Algorithm 1. (c) The green edges are added to
make the degree of independent set vertices even (Lines 1–1 of Algorithm 1).
(d) Balanced partition of edges incident to independent set vertices to the
three robots, shown by red, blue and green edges (Lines 1–1 of Algorithm 1).
(e-g) The graphs induced by the multiset corresponding to each of the three
robots after Line 1 of Algorithm 1.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

Figure 6: Illustration of the execution of Lines 1–1 of Algorithm 1 on the
instance shown in Figure 5(a). The orange vertices in Figures 6(b)–6(k) are
the vertex cover vertices. (a) Balanced partition of all the edges, also
including the ones incident only to vertex cover vertices to the three robots,
shown by red, blue and green edges (after Line 1 of Algorithm 1). (b-d) The
graphs induced by the multisets corresponding to each of the three robots
after Line 1 of Algorithm 1. (e) A spanning tree $T$ of the graph induced by
the vertex cover $\mathsf{VC}^{\prime}$ (Line 1 of Algorithm 1). (f-h) The
graphs induced by the multisets corresponding to each of the three robots
after adding the spanning tree $T$ (Lines 1–1 of Algorithm 1). (i-k) The
graphs induced by the multisets corresponding to each of the three robots
after making the degree of each vertex in $\mathsf{VC}^{\prime}$ even (Lines
1–1 of Algorithm 1). The yellow edges correspond to the edges added by
Algorithm 2.

##  5 FPT Algorithm with Respect to Vertex Cover

In this section, we present an FPT algorithm with respect to the vertex cover
number of the input graph $G$:

See 1.1

Our algorithm is based on a reduction to the Integer Linear Programming (ILP)
problem.

Recall that by Lemma 3.2, an instance $(G,v_{\mathsf{init}},k,B)$ of CGE is a
yes-instance if and only if there exist $k$ multisets
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ with elements from $E(G)$ such that:

  1. 1.

For every $1\leq i\leq k$, $v_{\mathsf{init}}\in
V(\mathsf{Graph}(\widehat{E}_{i}))$.

  2. 2.

For every $1\leq i\leq k$, $\mathsf{Graph}(\widehat{E}_{i})$ is connected, and
every vertex in it has even degree.

  3. 3.

$E(G)\subseteq\widehat{E}_{1}\cup\ldots\cup\widehat{E}_{k}$.

  4. 4.

$\mathsf{max}\\{|\widehat{E}_{1}|,\ldots,|\widehat{E}_{k}|\\}\leq B$.

Now, we show that it is enough to look at “simpler” multisets satisfying the
conditions of Lemma 3.2. By picking a solution that minimizes
$\sum^{k}_{i=1}|\widehat{E}_{i}|$, it holds that for every $1\leq i\leq k$ and
$\\{u,v\\}\in\widehat{E}_{i}$, $\\{u,v\\}$ appears at most twice in
$\widehat{E}_{i}$:

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$ and let
$k,B\in\mathbb{N}$. Assume that there exist
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that the conditions of Lemma 3.2
hold. Then, there exist
$\widehat{E}^{\prime}_{1},\ldots,\widehat{E}^{\prime}_{k}$ such that the
conditions of Lemma 3.2 hold and for every $1\leq i\leq k$, each
$\\{u,v\\}\in\widehat{E}^{\prime}_{i}$ appears at most twice in
$\widehat{E}^{\prime}_{i}$.

######  Proof 5.1.

Let $\widehat{E}_{1},\ldots,\widehat{E}_{k}$ be multisets satisfying the
conditions of Lemma 3.2. Assume that there exists $1\leq i\leq k$ and
$\\{u,v\\}\in\widehat{E}_{i}$ that appears more than twice in
$\widehat{E}_{i}$. Let
$\widehat{E}^{\prime}_{i}=\widehat{E}_{i}\setminus\\{\\{u,v\\},\\{u,v\\}\\}$.
Observe that since every vertex in $\mathsf{Graph}(\widehat{E}_{i})$ has even
degree, then every vertex in $\mathsf{Graph}(\widehat{E}^{\prime}_{i})$ has
even degree. Thus, it is easy to see that
$\widehat{E}_{1},\ldots,\widehat{E}_{i-1},\widehat{E}^{\prime}_{i},\widehat{E}_{i+1},\ldots\widehat{E}_{k}$
are also multisets satisfying the conditions of Lemma 3.2.

We aim to construct linear equations that verify the conditions in Lemma 3.2.
We begin with some definitions that we will use later, when we present our
reduction.

###  5.1 Encoding $\widehat{E}_{i}$ by a Valid Pair

Given $\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that conditions of
Observation 5 hold, we show how to “encode” each $\widehat{E}_{i}$ by a
different structure, which will be useful later. For this purpose, we present
some definitions. Let $G$ be a connected graph and let $\mathsf{VC}$ be a
vertex cover of $G$, given as input. We define an equivalence relation on
$V(G)\setminus\mathsf{VC}$ based on the sets of neighbors of the vertices in
$V(G)\setminus\mathsf{VC}$:

######  Definition 5.2 (Equivalence Relation for the Independent Set).

Let $G$ be a connected graph and let $\mathsf{VC}$ be a vertex cover of $G$.
Let $\mathsf{IND}=V(G)\setminus\mathsf{VC}$. For every $u,v\in\mathsf{IND}$,
$u$ is equal to $v$ if $\mathsf{N}(u)=\mathsf{N}(v)$. We denote the set of
equivalence classes induced by this equivalence relation by
$\mathsf{EQ}_{G,\mathsf{VC}}$.

When $G$ and $\mathsf{VC}$ are clear from context, we refer to
$\mathsf{EQ}_{G,\mathsf{VC}}$ as $\mathsf{EQ}$.

Next, we define the equivalence graph of $G$ and $\mathsf{VC}$, denoted by
$G^{*}$. It contains every vertex from $\mathsf{VC}$, and the edges having
both endpoints in $\mathsf{VC}$. In addition, every equivalence class
$u^{*}\in\mathsf{EQ}$ is represented by a single vertex adjacent to the
neighbors of some $u\in u^{*}$ in $G$ (which belong to $\mathsf{VC}$), e.g.
see Figure 2(b).

######  Definition 5.3 (Equivalence Graph $G^{*}$).

Let $G$ be a connected graph and let $\mathsf{VC}$ be a vertex cover of $G$.
The equivalence graph of $G$ and $\mathsf{VC}$ is
$G^{*}=\mathsf{Graph}(E^{*})$ where
$E^{*}=\\{\\{u^{*},v\\}\leavevmode\nobreak\ |\leavevmode\nobreak\
u^{*}\in\mathsf{EQ},\exists u\in V(G)$ s.t. $\\{u,v\\}\in E(G)\wedge u\in
u^{*}\\}\cup\\{\\{u,v\\}\in E(G)\leavevmode\nobreak\ |\leavevmode\nobreak\
u,v\in\mathsf{VC}\\}$.

To construct $k$ multisets $\widehat{E}_{1},\ldots,\widehat{E}_{k}$ that
satisfy the conditions of Lemma 3.2, we first deal with Condition 2: given
$1\leq i\leq k$, we need to ensure that $\mathsf{Graph}(\widehat{E}_{i})$ is
connected, and every vertex in it has even degree. For this purpose, we
“encode” $\widehat{E}_{i}$, for every $1\leq i\leq k$, as follows. First, we
construct a “small” subset $\mathsf{CC}_{i}\subseteq\widehat{E}_{i}$ such
that: (i) $\mathsf{Graph}(\mathsf{CC}_{i})$ is connected; (ii) every vertex in
$\mathsf{Graph}(\mathsf{CC}_{i})$ has even degree; and (iii)
$V(\mathsf{Graph}(\mathsf{CC}_{i}))\cap\mathsf{VC}=\mathsf{Graph}(\widehat{E}_{i})\cap\mathsf{VC}$.
In words, Condition (iii) states that every vertex from
$\mathsf{Graph}(\widehat{E}_{i})$ that belongs to $\mathsf{VC}$ also belongs
to $\mathsf{Graph}(\mathsf{CC}_{i})$. Observe that every vertex will have even
degree in $\mathsf{Graph}(\widehat{E}_{i}\setminus\mathsf{CC}_{i})$, and every
cycle in $\mathsf{Graph}(\widehat{E}_{i}\setminus\mathsf{CC}_{i})$ will
contain at least one vertex from $\mathsf{VC}$. We will later use these
properties to “encode” the edges from
$\widehat{E}_{i}\setminus\mathsf{CC}_{i}$.

Now, we turn to show how to construct $\mathsf{CC}_{i}$. For this purpose, we
define the graph $\overline{G}$. This graph is similar to $G^{*}$, but has
$\mathsf{NumVer}(u^{*})=\mathsf{min}\\{|u^{*}|,2^{|\mathsf{N}_{G^{*}}({u^{*}})|}+|\mathsf{VC}|^{2}\\}$
vertices for each $u^{*}\in\mathsf{EQ}$. In addition, each edge in
$\overline{G}$ appears exactly twice in $E(\overline{G})$, e.g. see Figure
2(c). We will see later that we can construct $\mathsf{CC}_{i}$ as a
submultigraph of $\overline{G}$.

######  Definition 5.4 (The Multigraph $\overline{G}$).

Let $G$ be a connected graph and let $\mathsf{VC}$ be a vertex cover of $G$.
For every $u^{*}\in\mathsf{EQ}$, let
$\mathsf{NumVer}(u^{*})=\mathsf{min}\\{|u^{*}|,2^{|\mathsf{N}_{G^{*}}({u^{*}})|}+|\mathsf{VC}|^{2}\\}$.
Then, $\overline{G}=\mathsf{Graph}(\overline{E})$ where
$\overline{E}=\\{\\{u^{*}_{i},v\\},\\{u^{*}_{i},v\\}\leavevmode\nobreak\
|\leavevmode\nobreak\ u^{*}\in\mathsf{EQ},\exists u\in V(G)$ s.t.
$\\{u,v\\}\in E(G)\wedge u\in u^{*},1\leq
i\leq\mathsf{NumVer}(u^{*})\\}\cup\\{\\{u,v\\},\\{u,v\\}\leavevmode\nobreak\
|\leavevmode\nobreak\ \\{u,v\\}\in E(G),u,v\in\mathsf{VC}\\}$.

Next, for a submultigraph $H$ of $G$, we define the term
$\overline{G}$-submultigraph (e.g. see Figure 3(b)):

######  Definition 5.5 ($\overline{G}$-Submultigraph).

Let $G$ be a connected graph and let $\mathsf{VC}$ be a vertex cover of $G$.
Let $\widehat{E}$ be a multiset with elements from $E(G)$ such that every
$\\{u,v\\}\in\widehat{E}$ appears at most twice in $\widehat{E}$. A
submultigraph $H$ of $\mathsf{Graph}(\widehat{E})$ is a
$\overline{G}$-submultigraph if for every $u^{*}\in\mathsf{EQ}$, $|V(H)\cap
u^{*}|\leq\mathsf{NumVer}(u^{*})$.

Given a $\overline{G}$-submultigraph $H$, we define the operation
$\overline{G}(H)$, which returns a submultigraph $\overline{H}$ of
$\overline{G}$ isomorphic to $H$ with isomorphism $\alpha:V(H)\rightarrow
V(\overline{H})$, where every vertex $u\in u^{*}\cap V(H)$ is mapped (by
$\alpha$) to a vertex in $\overline{G}$ that belongs to the same equivalence
class as $u$ (e.g., see Figure 7):

######  Definition 5.6 (The Operation $\overline{G}$).

Let $G$ be a connected graph, let $\mathsf{VC}$ be a vertex cover of $G$ and
let $H$ be a $\overline{G}$-submultigraph. Then, $\overline{G}(H)$ is a
submultigraph $\overline{H}$ of $\overline{G}$ for which there exists a
isomorphism $\alpha:V(H)\rightarrow V(\overline{H})$ satisfying the following
conditions:

  1. 1.

For every $u\in\mathsf{VC}$, $\alpha(u)=u$.

  2. 2.

For every $u\in u^{*}\in\mathsf{EQ}$, there exists
$j\in[\mathsf{NumVer}(u^{*})]$ such that $\alpha(u)=u^{*}_{j}$.

Figure 7: The graph $\overline{G}(H)$ for the graph $H$ in Figure 3(b). The
isomorphism $\alpha$ for independent vertices is defined as follows:
$\alpha(r_{1})=r^{*}_{1}$, $\alpha(r_{2})=r^{*}_{2}$,
$\alpha(y_{5})=y^{*}_{1}$, $\alpha(y_{6})=y^{*}_{2}$,
$\alpha(g_{11})=g^{*}_{1}$, and $\alpha(g_{12})=g^{*}_{2}$.

Observe that since $H$ is a $\overline{G}$-submultigraph,
$\mathsf{NumVer}(u^{*})$ and the number of appearance of each edge are large
enough to ensure that $\overline{G}(H)$ is well defined (although not uniquely
defined).

Assuming we have computed $\mathsf{CC}_{i}$ (which we will do soon in Lemma
5.10), we now explain the intuition for how to encode the edges in
$\widehat{E}_{i}\setminus\mathsf{CC}_{i}$. Recall that every vertex has even
degree in $\mathsf{Graph}(\widehat{E}_{i}\setminus\mathsf{CC}_{i})$.
Therefore, if $\mathsf{Graph}(\widehat{E}_{i}\setminus\mathsf{CC}_{i})$ is not
empty, there exists a cycle $C$ in
$\mathsf{Graph}(\widehat{E}_{i}\setminus\mathsf{CC}_{i})$, and, in particular,
a simple one, as is implied by the following observation:

Let $G$ be a non-empty multigraph. Assume that every vertex in $G$ has even
degree in it. Then, there exists a simple cycle in $G$.

Now, observe that every vertex also has even degree in
$\mathsf{Graph}(\widehat{E}_{i}\setminus(\mathsf{CC}_{i}\cup E(C)))$, as
implied by the following observation:

Let $G$ be a multigraph. Assume that every vertex in $G$ has even degree in
it. Let $C$ be a cycle in $G$. Then, every vertex in
$\mathsf{Graph}(E(G)\setminus E(C))$ has even degree in it.

So, the same reasoning can be reapplied. Therefore, we can encode
$\widehat{E}_{i}\setminus\mathsf{CC}_{i}$ by a multiset of cycles. In
particular, in the following lemma, we show that we can encode
$\widehat{E}_{i}\setminus\mathsf{CC}_{i}$ by a multiset of cycles ${\cal C}$
such that all the cycles except for “few” of them are of length $4$; in
addition, the cycles from ${\cal C}$ that are of length other than $4$ are
simple.

######  Lemma 5.7.

Let $G$ be a multigraph such that each $\\{u,v\\}\in E(G)$ appears at most
twice in $E(G)$, and let $\mathsf{VC}$ be a vertex cover of $G$. Assume that
every vertex in $G$ has even degree. Then, there exists a multiset of cycles
${\cal C}$ in $G$ such that:

  1. 1.

At most $2|\mathsf{VC}|^{2}$ cycles in ${\cal C}$ have length other than $4$.

  2. 2.

The cycles in ${\cal C}$ that have length other than $4$ are simple.

  3. 3.

$\bigcup_{C\in{\cal C}}E(C)=E(G)$ (being two multisets).

######  Proof 5.8.

First, assume that there are more than $2|\mathsf{VC}|^{2}$ edges in $E(G)$.
Let $\mathsf{IND}=V(G)\setminus\mathsf{VC}$. Every $u\in V(G)$ has even
degree, so let $2d_{u}$ be the degree of $u$ in $G$, where
$d_{u}\in\mathbb{N}$. For every $u\in\mathsf{IND}$, let
$\widehat{A}_{u}=\\{\\{\\{u,v_{i}\\},\\{u,v_{i}^{\prime}\\}\\}_{i=1}^{d_{u}}\\}$
be a partition of the edges incident to $u$ in $G$ into multisets of two
elements, and let $\widehat{A}=\bigcup_{u\in\mathsf{IND}}\widehat{A}_{u}$.
Observe that there are more than $2|\mathsf{VC}|^{2}$ edges in $G$, and the
number of edges in $G$ with both endpoints in $\mathsf{VC}$ is bounded by
$2{|\mathsf{VC}|\choose 2}\leq|\mathsf{VC}|^{2}$ (${|\mathsf{VC}|\choose 2}$
different edges, each appears at most twice). So, there are more than
$|\mathsf{VC}|^{2}$ edges with one endpoint in $\mathsf{IND}$. This implies
that we have more than $\frac{1}{2}|\mathsf{VC}|^{2}$ multisets in
$\widehat{A}$. Now, every multiset in $\widehat{A}$ consists of two edges,
each edge is incident to exactly one vertex from $\mathsf{VC}$. Notice that
the number of different options to choose two vertices from $\mathsf{VC}$ is
bounded by $\frac{1}{2}|\mathsf{VC}|^{2}$. Therefore, since there are more
than $\frac{1}{2}|\mathsf{VC}|^{2}$ multisets in $\widehat{A}$, there exist
two multisets
$\\{\\{u,v_{i}\\},\\{u,v_{i}^{\prime}\\}\\},\\{\\{\tilde{u},v_{j}\\},\\{\tilde{u},v_{j}^{\prime}\\}\\}$
such that $v_{i}=v_{j}$ and $v^{\prime}_{i}=v^{\prime}_{j}$. So,
$C=(u,v_{i},\tilde{u},v^{\prime}_{i},u)$ is a cycle of length $4$ in $G$. From
Observation 5.1, the degree of every vertex in $G$ remains even after deleting
the edges of $C$ from $G$. Then, after deleting the edges of $C$ from $G$ (and
inserting it into ${\cal C}$), we can use the same argument to find yet
another cycle.

If $G$ has $2|\mathsf{VC}|^{2}$ edges or less (and it is not empty), then
since the degree of every vertex is even, from Observation 5.1, we can find a
cycle—and, in particular, a simple one—in the multigraph and delete it (and
inserting it into ${\cal C}$).

The process ends when there are no edges in the multigraph. Clearly, by our
construction, the conditions of the lemma hold. This ends the proof.

We have the following observation, which will be useful later:

Let $G$ be a connected multigraph, let $\mathsf{VC}$ be a vertex cover of $G$
and let $C$ be a cycle in $G$. Then, $V(C)\cap\mathsf{VC}\neq\emptyset$.

Let $\widehat{E}_{1},\ldots,\widehat{E}_{k}$ satisfy the conditions of Lemma
3.2. We encode each $\widehat{E}_{i}$ as a pair $(\mathsf{CC}_{i},{\cal
C}_{i})$ where $\mathsf{CC}_{i}\cup\bigcup_{C\in{\cal
C}_{i}}E(C)=\widehat{E}_{i}$, and: (i) $\mathsf{Graph}(\mathsf{CC}_{i})$ is a
$\overline{G}$-submultigraph; (ii) $\mathsf{Graph}(\mathsf{CC}_{i})$ is
connected, $v_{\mathsf{init}}\in V(\mathsf{Graph}(\mathsf{CC}_{i}))$ and every
vertex in $\mathsf{Graph}(\mathsf{CC}_{i})$ has even degree; and (iii) ${\cal
C}_{i}$ is a multiset of cycles satisfying the conditions of Lemma 5.7. We
call such a pair an $\widehat{E}_{i}$-valid pair:

######  Definition 5.9 (Valid Pair).

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$ and let
$\mathsf{VC}$ be a vertex cover of $G$. Let $\widehat{E}$ be a multiset with
elements from $E(G)$ such that $\mathsf{Graph}(\widehat{E})$ is connected,
$v_{\mathsf{init}}\in V(\mathsf{Graph}(\widehat{E}))$, and every vertex in
$\mathsf{Graph}(\widehat{E})$ has even degree. Let
$\mathsf{CC}\subseteq\widehat{E}$, and let ${\cal C}$ be a multiset of cycles
in $\mathsf{Graph}(\widehat{E})$. Then, $(\mathsf{CC},{\cal C})$ is an
$\widehat{E}$-valid pair if the following conditions are satisfied:

  1. 1.

$\mathsf{Graph}(\mathsf{CC})$ is a $\overline{G}$-submultigraph.

  2. 2.

$\mathsf{Graph}(\mathsf{CC})$ is connected, $v_{\mathsf{init}}\in
V(\mathsf{Graph}(\mathsf{CC}))$ and every vertex in
$\mathsf{Graph}(\mathsf{CC})$ has even degree.

  3. 3.

$V(\mathsf{Graph}(\mathsf{CC}))\cap\mathsf{VC}=V(\mathsf{Graph}(\widehat{E}))\cap\mathsf{VC}$.

  4. 4.

At most $2|\mathsf{VC}|^{2}$ cycles in ${\cal C}$ have length other than $4$.

  5. 5.

The cycles in ${\cal C}$ of length other than $4$ are simple.

  6. 6.

$\mathsf{CC}\cup\bigcup_{C\in{\cal C}}E(C)=\widehat{E}$.

Next, we invoke Lemma 5.7 in order to prove the following. Let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ satisfy the conditions of Lemma 3.2,
and for every $1\leq i\leq k$ and $\\{u,v\\}\in\widehat{E}_{i}$, $\\{u,v\\}$
appears at most twice in $\widehat{E}_{i}$ (see Observation 5). Then, there
exists $(\mathsf{CC}_{i},{\cal C}_{i})$ such that $(\mathsf{CC}_{i},{\cal
C}_{i})$ is an $\widehat{E}_{i}$-valid pair:

######  Lemma 5.10.

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$ and let
$\mathsf{VC}$ be a vertex cover of $G$. Let $\widehat{E}$ be a multiset with
elements from $E(G)$. Assume that $\mathsf{Graph}(\widehat{E})$ is connected,
$v_{\mathsf{init}}\in V(\mathsf{Graph}(\widehat{E}))$, every vertex in
$\mathsf{Graph}(\widehat{E})$ has even degree and every
$\\{u,v\\}\in\widehat{E}$ appears at most twice in $\widehat{E}$. Then, there
exist $\mathsf{CC}\subseteq\widehat{E}$ and a multiset of cycles ${\cal C}$ in
$\mathsf{Graph}(\widehat{E})$ such that $(\mathsf{CC},{\cal C})$ is an
$\widehat{E}$-valid pair.

######  Proof 5.11.

First, we construct $\mathsf{CC}$. For this purpose, we obtain a multigraph
$H$ from $\mathsf{Graph}(\widehat{E})$ as follows: Starting with
$H=\mathsf{Graph}(\widehat{E})$. While there exist $u,u^{\prime}\in u^{*}\cap
V(H)$ such that $\mathsf{N}_{H}(u)=\mathsf{N}_{H}(u^{\prime})$, delete
$u^{\prime}$. Observe that, since $\mathsf{Graph}(\widehat{E})$ is connected,
then so is $H$. Also, observe that for every $u\in u^{*}\in\mathsf{EQ}$, the
number of options for $\mathsf{N}_{H}(u)$ is bounded by
$2^{|\mathsf{N}_{G^{*}}(u^{*})|}$. So, for every $u^{*}\in\mathsf{EQ}$,
$|u^{*}\cap V(H)|\leq 2^{|\mathsf{N}_{G^{*}}(u^{*})|}$. Notice that for every
$u^{*}\in\mathsf{EQ}$, we might have more than one vertex from $u^{*}$ in $H$
since vertices that have the same neighbors in $G$, might have different
neighbors in $H$. In addition, each $u\in u^{*}\in\mathsf{EQ}$ has even degree
in $H$ (being the same as its degree in $\mathsf{Graph}(\widehat{E})$), e.g.
see Figure 3(b).

Now, let $v\in\mathsf{VC}$ that has odd degree in $H$ (if one exists). Notice
that since the number of vertices with odd degree is even in every multigraph,
there exists $v^{\prime}\in\mathsf{VC}\cap V(H)$ such that $v^{\prime}\neq v$
and $v$ has odd degree in $H$. We build a path $P$ from $v$ to such a
$v^{\prime}$ in $G$ using edges in $\widehat{E}\setminus E(H)$ as follows.
Since $v$ has odd degree in $H$ and even degree in
$\mathsf{Graph}(\widehat{E})$, there exists $\\{u,v\\}\in\widehat{E}\setminus
E(H)$. We add $\\{u,v\\}$ to $P$. Now, if $u$ has odd degree in $H$, then
$u\in\mathsf{VC}$ and we finish; otherwise, $u$ has even degree in $H$, so it
has odd degree in $\mathsf{Graph}(E(H)\cup E(P))$, and so there exists
$\\{u,u^{\prime}\\}\in\widehat{E}\setminus(E(H)\cup E(P))$. This process is
finite, and ends when $P$ reaches $v^{\prime}\in\mathsf{VC}$ with odd degree
in $H$. Now, since there exists a path $P$ from $v$ to $v^{\prime}$ in
$\mathsf{Graph}(\widehat{E})$ such that $E(P)\cap E(H)=\emptyset$, there
exists a simple path $P^{\prime}$ from $v$ to $v^{\prime}$ in
$\mathsf{Graph}(\widehat{E})$, such that $E(P^{\prime})\cap E(H)=\emptyset$.
Observe that $|P^{\prime}|\leq 2|\mathsf{VC}|$, and there are at most
$|\mathsf{VC}|$ vertices in $P^{\prime}$ from $V(G)\setminus\mathsf{VC}$. We
add the edges of $P^{\prime}$ to $H$, that is,
$H\leftarrow\mathsf{Graph}(E(H)\cup E(P^{\prime}))$ (e.g. see the dashed paths
in Figure 3(c)), and continue with this process until every vertex in $H$ has
even degree. Observe that, by the end of this process, we have added at most
$|\mathsf{VC}|^{2}$ vertices from $V(G)\setminus\mathsf{VC}$ to $H$. So, in
particular, for every $u^{*}\in\mathsf{EQ}$, we have added at most
$|\mathsf{VC}|^{2}$ vertices from $(V(G)\setminus\mathsf{VC})\cap u^{*}$ to
$H$.

Overall, for every $u^{*}\in\mathsf{EQ}$, $|u^{*}\cap V(H)|\leq
2^{|\mathsf{N}_{G^{*}}(u^{*})|}+|\mathsf{VC}|^{2}$. In addition, notice that
$H$ is a submultigraph of $\mathsf{Graph}(\widehat{E})$, so each $\\{u,v\\}\in
E(H)$ appears at most twice in $E(H)$. Moreover, observe that
$V(H)\cap\mathsf{VC}=V(\mathsf{Graph}(\widehat{E}))\cap\mathsf{VC}$, and since
we assume that $v_{\mathsf{init}}\in\mathsf{VC}$, then $v_{\mathsf{init}}\in
V(H)$. We define $\mathsf{CC}=E(H)$, so Conditions 1–3 of Definition 5.9 are
satisfied. Now, observe that every vertex in
$\mathsf{Graph}(\widehat{E}\setminus\mathsf{CC})$ has even degree, and
$\mathsf{VC}\cap V(\mathsf{Graph}(\widehat{E}\setminus\mathsf{CC}))$ is a
vertex cover of $\mathsf{Graph}(\widehat{E}\setminus\mathsf{CC})$. Therefore,
from Lemma 5.7, there exists a multiset of cycles ${\cal C}$ in
$\mathsf{Graph}(\widehat{E}\setminus\mathsf{CC})$ such that Conditions 4–6 of
Definition 5.9 are satisfied. So, $(\mathsf{CC},{\cal C})$ is an
$\widehat{E}$-valid pair. This completes the proof.

###  5.2 Vertex Type

Now, to construct the equations for the ILP instance, we present the
variables. First, we have a variable for each vertex type. We begin by showing
how we derive the vertex type of a vertex from a solution, and then we define
formally the term vertex type. For this purpose, we introduce some
definitions.

An intuition for a vertex type is as follows. Let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that the conditions of Lemma 3.2
hold, and for every $1\leq i\leq k$ let $(\mathsf{CC}_{i},{\cal C}_{i})$ be an
$\widehat{E}_{i}$-valid pair. For every $u\in u^{*}\in\mathsf{EQ}$, we derive
multisets with elements from $\mathsf{N}_{G^{*}}(u^{*})$ as follows. First,
for every $1\leq i\leq k$, we derive the multiset of neighbors of $u$ in
$\mathsf{Graph}(\mathsf{CC}_{i})$, that is
$\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{i})}(u)$. Second, for every
$1\leq i\leq k$ and $C\in{\cal C}_{i}$ such that $u\in V(C)$, we derive the
multiset $\\{v,v^{\prime}\\}$, where $v$ and $v^{\prime}$ are the vertices
appear right before and right after $u$ in $C$, respectively. Now, recall that
in a solution, every edge is covered by at least one robot. So, given a vertex
$u\in u^{*}\in\mathsf{EQ}$ and an edge $\\{u,v\\}\in E(G)$, there exists
$1\leq i\leq k$ such that $\\{u,v\\}$ is covered by the $i$-th robot, that is,
$\\{u,v\\}\in\widehat{E}_{i}$. Since $\mathsf{CC}_{i}\cup\bigcup_{C\in{\cal
C}_{i}}E(C)=\widehat{E}_{i}$, either $\\{u,v\\}\in\mathsf{CC}_{i}$ or
$\\{u,v\\}\in E(C)$, for some $C\in{\cal C}_{i}$. Thus, $u$ is in at least one
multiset we derived. In the vertex types, we consider all the possible options
for such multisets.

In the next definition, for a given cycle $C$, we define the pairs of edges of
$C$, denoted $\mathsf{EdgePairs}(C)$: for each $u\in
V(G)\setminus\mathsf{VC}$, we have the pair $(\\{u,v\\},\\{u,v^{\prime}\\})$,
where $v$ and $v^{\prime}$ are the vertices appear right before and right
after $u$ in $C$. Later, we will derive for each such a pair, the multiset
$\\{v,v^{\prime}\\}$ and “allocate” it to $u$.

Let $G$ be a connected graph and let $\mathsf{VC}$ be a vertex cover of $G$.
We denote the set of cycles of length at most
$\mathsf{max}\\{4,2|\mathsf{VC}|\\}$ in $G$ by $\mathsf{Cyc}_{G}$. Let
$C=(v_{0},\ldots,v_{\ell}=v_{0})\in\mathsf{Cyc}_{G}$. We denote by
$\mathsf{EQ}(C)$ the cycle in $G^{*}$ obtained from $C$ by replacing each
$v_{i}\in V(C)\cap(V(G)\setminus\mathsf{VC})$ by $u^{*}\in\mathsf{EQ}$, where
$v_{i}\in u^{*}$, for every $1\leq i\leq\ell$.

######  Definition 5.12 (Pairs of a Cycle).

Let $G$ be a connected graph, let $\mathsf{VC}$ be a vertex cover of $G$ and
let
$C=(v_{0},\ldots,v_{\ell}=v_{0})\in\mathsf{Cyc}_{G}\cup\mathsf{Cyc}_{G^{*}}$.
Then, the pairs of edges of $C$ is the multiset
$\mathsf{EdgePairs}(C)=\\{\\{\\{v_{i-1},v_{i}\\},\\{v_{i},v_{i+1}\\}\\}\leavevmode\nobreak\
|\leavevmode\nobreak\ 1\leq
i\leq\ell-1,v_{i}\in\mathsf{IND}\cup\mathsf{EQ}\\}$.

Recall that, given a multigraph $G$ and $u\in V(G)$, the multiset of neighbors
of $u$ in $G$ is denoted by $\widehat{\mathsf{N}}_{G}(u)=\\{v\in
V\leavevmode\nobreak\ |\leavevmode\nobreak\ \\{u,v\\}\in E(G)\\}$ (with
repetition).

######  Definition 5.13 (Deriving Vertex Types From a Solution).

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$, let
$k,B\in\mathbb{N}$, let $\mathsf{VC}$ be a vertex cover of $G$ and let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that conditions of Lemma 3.2
hold. For every $1\leq i\leq k$ let $(\mathsf{CC}_{i},{\cal C}_{i})$ be an
$\widehat{E}_{i}$-valid pair. In addition, for every $1\leq i\leq k$ and $u\in
u^{*}\in\mathsf{EQ}$ such that $u\in V(\mathsf{Graph}(\widehat{E}_{i}))$, let
$\mathsf{NeiPairs}_{{\cal C}_{i}}(u)=\\{\\{v,v^{\prime}\\}\leavevmode\nobreak\
|\leavevmode\nobreak\ C\in{\cal
C}_{i},\\{\\{u,v\\},\\{u,v^{\prime}\\}\\}\in\mathsf{EdgePairs}(C)\\}$ be a
set. For every $u\in u^{*}\in\mathsf{EQ}$, let
$\mathsf{NeiSubsets}(u)=\bigcup_{1\leq i\leq
k}(\\{\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{i})}(u)\\}\cup\mathsf{NeiPairs}_{{\cal
C}_{i}}(u))$ be a set. Then, for every $u\in u^{*}\in\mathsf{EQ}$,
$\mathsf{DerVerTyp}(\\{(\mathsf{CC}_{i},{\cal C}_{i})\\}_{1\leq i\leq
k},u)=(u^{*},\mathsf{NeiSubsets}(u))$.

Whenever $\\{(\mathsf{CC}_{i},{\cal C}_{i})\\}_{1\leq i\leq k}$ is clear from
context, we refer to $\mathsf{DerVerTyp}(\\{(\mathsf{CC}_{i},{\cal
C}_{i})\\}_{1\leq i\leq k},$ $u)$ as $\mathsf{DerVerTyp}(u)$. Observe that
every element in $\mathsf{NeiPairs}_{{\cal C}_{i}}(u)$ is a multiset of two
vertices (which might be the same vertex).

Now, observe that each vertex in every multiset derived in Lemma 5.13 appears
at most twice: each edge appears at most twice in $\mathsf{CC}_{i}$, and every
multiset derived from a cycle has exactly two elements in it. In addition,
since the degree of each vertex is even in $\mathsf{Graph}(\mathsf{CC}_{i})$,
every multiset derived in Lemma 5.13 has an even number of elements. So, we
will consider only multisets with these restriction.

For a set $A$ we define the multiset
$A\times\mathsf{2}=\\{a,a\leavevmode\nobreak\ |\leavevmode\nobreak\ a\in
A\\}$. That is, each element in $A$ appears exactly twice in
$A\times\mathsf{2}$.

Now, we define the term vertex type:

######  Definition 5.14 (Vertex Type).

Let $G$ be a connected graph and let $\mathsf{VC}$ be a vertex cover of $G$.
Let $u^{*}\in\mathsf{EQ}$ and let $\mathsf{NeiSubsets}\subseteq
2^{\mathsf{N}_{G^{*}}(u^{*})\times\mathsf{2}}$. Then,
$\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})$ is a vertex type if for every
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}$, $|\mathsf{NeiSub}|$ is even, and
$\mathsf{N}_{G^{*}}(u^{*})\subseteq\bigcup\mathsf{NeiSubsets}$.

We denote the set of vertex types by $\mathsf{VerTypS}$.

In the following lemma we show the “correctness” of Definition 5.13, that is,
for every $u\in\mathsf{IND}$, $\mathsf{DerVerTyp}(u)$ is indeed a vertex type.

######  Lemma 5.15.

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$, let
$k,B\in\mathbb{N}$ and let $\mathsf{VC}$ be a vertex cover of $G$. Let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that conditions of Lemma 3.2
hold and for every $1\leq i\leq k$ let $(\mathsf{CC}_{i},{\cal C}_{i})$ be an
$\widehat{E}_{i}$-valid pair. Then, for every $u\in\mathsf{IND}$,
$\mathsf{DerVerTyp}(u)$ is a vertex type.

######  Proof 5.16.

We show that, for every $u\in u^{*}\in\mathsf{EQ}$,
$\mathsf{DerVerTyp}(u)=(u^{*},\mathsf{NeiSubsets}(u))$ is a vertex type. Let
$u\in u^{*}\in\mathsf{EQ}$. First, we show that for every
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}(u)$, $\mathsf{NeiSub}\in
2^{\mathsf{N}_{G^{*}}(u^{*})\times\mathsf{2}}$ and $|\mathsf{NeiSub}|$ is
even. For every $\mathsf{NeiSub}\in\mathsf{NeiSubsets}(u)$ there exists $1\leq
i\leq k$ such that
$\mathsf{NeiSub}\in\\{\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{i})}(u)\\}\cup\mathsf{NeiPairs}_{{\cal
C}_{i}}(u)$.

  * •

If
$\mathsf{NeiSub}=\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{i})}(u)$,
then $\mathsf{NeiSub}=\\{v\in
V(\mathsf{Graph}(\mathsf{CC}_{i}))\leavevmode\nobreak\ |\leavevmode\nobreak\
\\{u,v\\}\in\mathsf{CC}_{i}\\}$. Since $\mathsf{CC}_{i}$ is a
$\overline{G}$-submultigraph, each $\\{u,v\\}\in\mathsf{CC}_{i}$ appears at
most twice in $\mathsf{CC}_{i}$. Then, each $v\in\mathsf{NeiSub}$ appears at
most twice in $\mathsf{NeiSub}$, and so $\mathsf{NeiSub}\in
2^{\mathsf{N}_{G^{*}}(u^{*})\times\mathsf{2}}$. In addition, the degree of $u$
in $\mathsf{Graph}(\mathsf{CC}_{i})$ is even, so $|\mathsf{NeiSub}|$ is even.

  * •

Otherwise, $\mathsf{NeiSub}\in\mathsf{NeiPairs}_{{\cal C}_{i}}(u)$, and every
multiset in $\mathsf{NeiPairs}_{{\cal C}_{i}}(u)$ has exactly two vertices, so
$\mathsf{NeiSub}\in 2^{\mathsf{N}_{G^{*}}(u^{*})\times\mathsf{2}}$ and
$|\mathsf{NeiSub}|$ is even.

Now, we show that
$\mathsf{N}_{G^{*}}(u^{*})\subseteq\bigcup\mathsf{NeiSubsets}(u)$. Let
$v\in\mathsf{N}_{G^{*}}(u^{*})$. From Condition 3 of Lemma 3.2,
$E(G)\subseteq\widehat{E}_{1}\cup\ldots\cup\widehat{E}_{k}$. Then, there
exists $1\leq i\leq k$ such that $\\{u,v\\}\in\widehat{E}_{i}$. Since
$(\mathsf{CC}_{i},{\cal C}_{i})$ is an $\widehat{E}_{i}$-valid pair,
$\widehat{E}_{i}=\mathsf{CC}_{i}\cup\bigcup_{C\in{\cal C}_{i}}E(C)$. So, if
$\\{u,v\\}\in\mathsf{CC}_{i}$, then
$v\in\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{i})}(u)$; otherwise,
there exists $C\in{\cal C}_{i}$ such that $\\{u,v\\}\in E(C)$. Therefore,
there exists $v^{\prime}\in V(G)$ such that
$\\{\\{u,v\\},\\{u,v^{\prime}\\}\\}\in\mathsf{EdgePairs}(C)$, so
$\\{v,v^{\prime}\\}\in\mathsf{NeiPairs}_{{\cal C}_{i}}(u)$, thus
$v\in\bigcup\mathsf{NeiSubsets}(u)$. So, for every $u\in u^{*}\in\mathsf{EQ}$,
$\mathsf{DerVerTyp}(u)=(u^{*},\mathsf{NeiSubsets}(u))$ is a vertex type.

###  5.3 Robot Type

Now, we continue to introduce the variables we need for the ILP instance. We
have a variable for each robot type. First, we show how we derive a robot type
for each robot from a solution, and then we will present the definition of an
abstract type. An intuition for a robot type is as follows. In Definition
5.13, where we derive vertex types, we saw how we derive
$\mathsf{NeiSubsets}(u)$ for each $u\in V(G)\setminus\mathsf{VC}$. Some of the
multisets in $\mathsf{NeiSubsets}(u)$ are derived from
$\mathsf{Graph}(\mathsf{CC}_{i})$, where $(\mathsf{CC}_{i},{\cal C}_{i})$ is
an $\widehat{E}_{i}$-valid pair associated with each robot $i$. Now, we look
on the “puzzle” from the perspective of the robots. For each $u\in
V(\mathsf{Graph}(\mathsf{CC}_{i}))\setminus\mathsf{VC}$, the multiset
$\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{i})}(u)$ is “allocated” for
the vertex type of $u$. For an induced submultigraph $\overline{H}$ of
$\overline{G}$, we present two notations: the multiset
$\mathsf{NeiOfInd}(\overline{H})$, and an allocation for this multiset. When
$\overline{H}=\overline{G}(\mathsf{Graph}(\mathsf{CC}_{i}))$,
$\mathsf{NeiOfInd}(\overline{H})$ is the set of pairs
$(u^{*}_{i},\mathsf{NeiSub})$ we will later allocate to vertex types.

######  Definition 5.17 ($\mathsf{NeiOfInd}(\overline{H})$).

Let $G$ be a connected graph and let $\mathsf{VC}$ be a vertex cover of $G$.
Let $\overline{H}$ be a submultigraph of $\overline{G}$. Then,
$\mathsf{NeiOfInd}(\overline{H})=\\{(u^{*}_{i},\widehat{\mathsf{N}}_{\overline{H}}(u^{*}_{i}))\leavevmode\nobreak\
|\leavevmode\nobreak\ u^{*}_{i}\in V(\overline{H})\\}$ as a multiset.

A vertex allocation of $\mathsf{NeiOfInd}(\overline{H})$ is a function that
assigns a vertex type to each
$(u^{*}_{i},\mathsf{NeiSub})\in\mathsf{NeiOfInd}(\overline{H})$. We allocate
$(u^{*}_{i},\mathsf{NeiSub})$ to a vertex type that “expects” to get
$\mathsf{NeiSub}$, that is, a vertex type $(u^{*},\mathsf{NeiSubsets})$ where
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}$.

######  Definition 5.18 (Vertex Allocation of
$\mathsf{NeiOfInd}(\overline{H})$).

Let $G$ be a connected graph and let $\mathsf{VC}$ be a vertex cover of $G$.
Let $\overline{H}$ be a submultigraph of $\overline{G}$. A vertex allocation
of $\mathsf{NeiOfInd}(\overline{H})$ is a function
$\mathsf{Alloc}_{\overline{H}}:\mathsf{NeiOfInd}(\overline{H})\rightarrow\mathsf{VerTypeS}$
such that for every
$(u^{*}_{i},\mathsf{NeiSub})\in\mathsf{NeiOfInd}(\overline{H})$,
$\mathsf{Alloc}_{\overline{H}}(u^{*}_{i},\mathsf{NeiSub})=(u^{*},\mathsf{NeiSubsets})$
where
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}$.

In addition to the vertex allocation, the type of each robot $i$ is associated
with a vector of non-negative integers
$\mathsf{NumOfCyc}=(N_{i,2},N_{i,3},N_{i,5},N_{i,6},\ldots,N_{i,2|\mathsf{VC}|})$:
for every $2\leq j\leq 2|\mathsf{VC}|$, $j\neq 4$, $N_{i,j}$ is the number of
cycles of length exactly $j$ in ${\cal C}_{i}$, where $(\mathsf{CC}_{i},{\cal
C}_{i})$ be an $\widehat{E}_{i}$-valid pair.

######  Definition 5.19 (Deriving Robot Types From a Solution).

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$, let
$k,B\in\mathbb{N}$, let $\mathsf{VC}$ be a vertex cover of $G$ and let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that the conditions of Lemma 3.2
hold. For every $1\leq i\leq k$, let $(\mathsf{CC}_{i},{\cal C}_{i})$ be an
$\widehat{E}_{i}$-valid pair. For every $1\leq i\leq k$, let
$G^{\prime}_{i}=\overline{G}(\mathsf{Graph}(\mathsf{CC}_{i}))$ with an
isomorphism $\alpha_{i}:V(G_{i}^{\prime})\rightarrow
V(\mathsf{Graph}(\mathsf{CC}_{i}))$, and let
$\mathsf{CC}^{\prime}_{i}=E(G_{i}^{\prime})$. For every $1\leq i\leq k$ and
$(u^{*}_{j},\mathsf{NeiSub})\in\mathsf{NeiOfInd}(G^{\prime}_{i})$, let
$\mathsf{Alloc}_{G_{i}^{\prime}}((u^{*}_{j},\mathsf{NeiSub}))=\mathsf{DerVerTyp}(\alpha_{i}(u^{*}_{j}))$.
For every $1\leq i\leq k$ and $2\leq j\leq 2|\mathsf{VC}|$, $j\neq 4$, let
$N_{i,j}$ be the number of cycles of size $j$ in ${\cal C}_{i}$, and for every
$1\leq i\leq k$ let
$\mathsf{NumOfCyc}_{i}=(N_{i,2},N_{i,3},N_{i,5},N_{i,6},\ldots,N_{i,2|\mathsf{VC}|})$.
Then, for every $1\leq i\leq k$, let
$\mathsf{DerRobTyp}(\\{(\mathsf{CC}_{j},{\cal C}_{j})\\}_{1\leq j\leq
k},i)=(\mathsf{CC}^{\prime}_{i},\mathsf{Alloc}_{G_{i}^{\prime}},\mathsf{NumOfCyc}_{i})$.

Whenever $\\{(\mathsf{CC}_{i},{\cal C}_{i})\\}_{1\leq i\leq k}$ is clear from
context, we refer to $\mathsf{DerRobTyp}(\\{(\mathsf{CC}_{i},{\cal
C}_{i})\\}_{1\leq i\leq k},$ $i)$ as $\mathsf{DerRobTyp}(i)$.

Now, we define the term robot type. As mentioned, a robot type is first
associated with $\mathsf{CC}\subseteq E(\overline{G})$ and a vertex allocation
of $\mathsf{NeiOfInd}(\mathsf{Graph}(\mathsf{CC}))$. We demand that
$\mathsf{Graph}(\mathsf{CC})$ is connected, every vertex in
$\mathsf{Graph}(\mathsf{CC})$ has even degree and $v_{\mathsf{init}}\in
V(\mathsf{Graph}(\mathsf{CC}))$, similarly to Conditions 2 and 3 of Definition
5.9. This way we ensure that the multiset $\widehat{E}$ we will build for the
a robot makes $\mathsf{Graph}(\widehat{E})$ connected: we will later associate
with a robot only cycles $C$ such that $V(C)\cap
V(\mathsf{Graph}(\mathsf{CC}))\neq\emptyset$. In addition, we also ensure that
every vertex in $\mathsf{Graph}(\widehat{E})$ will have even degree in
$\mathsf{Graph}(\widehat{E})$: each such vertex has even degree in
$\mathsf{Graph}(\mathsf{CC})$, and we will add only cycles to this graph, so
the degree of each vertex will remain even. Therefore, we ensure that the
“local” properties of each robot, given by Conditions 1 and 2 of Lemma 3.2,
are preserved. The vector of non-negative integers
$\mathsf{NumOfCyc}=(N_{2},N_{3},N_{5},N_{6},\ldots,N_{2|\mathsf{VC}|})$
determines how many cycles of each length (other than $4$) we will associate
with the robot. Observe that, due to Condition 4 of Definition 5.9, each
$N_{j}$ is bounded by $2|\mathsf{VC}|^{2}$.

######  Definition 5.20 (Robot Type).

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$ and let
$\mathsf{VC}$ be a vertex cover of $G$. Then,
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},\mathsf{NumOfCyc})$
is a robot type if the following conditions are satisfied:

  1. 1.

$\mathsf{CC}\subseteq E(\overline{G})$.

  2. 2.

$\mathsf{Graph}(\mathsf{CC})$ is connected, every vertex in
$\mathsf{Graph}(\mathsf{CC})$ has even degree and
$v_{\mathsf{init}}\in V(\mathsf{Graph}(\mathsf{CC}))$.

  3. 3.

$\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})}$ is a vertex allocation of
$\mathsf{NeiOfInd}(\mathsf{Graph}(\mathsf{CC}))$.

  4. 4.

$\mathsf{NumOfCyc}=(N_{2},N_{3},N_{5},N_{6},\ldots,N_{2|\mathsf{VC}|})$, where
$0\leq N_{i}\leq 2|\mathsf{VC}|^{2}$ for every $2\leq i\leq 2|\mathsf{VC}|$,
$i\neq 4$.

We denote the set of robot types by $\mathsf{RobTypS}$.

In the following lemma we show the “correctness” of Definition 5.19, that is,
for every $1\leq i\leq k$, $\mathsf{DerRobTyp}(i)$ is indeed a robot type.

######  Lemma 5.21.

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$, let
$k,B\in\mathbb{N}$ and let $\mathsf{VC}$ be a vertex cover of $G$. Let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that conditions of Lemma 3.2
hold, and for every $1\leq i\leq k$, let $(\mathsf{CC}_{i},{\cal C}_{i})$ be
an $\widehat{E}_{i}$-valid pair. Then, for every $1\leq i\leq k$,
$\mathsf{DerVerTyp}(i)$ is a robot type.

######  Proof 5.22.

Let $1\leq i\leq k$. We show that $\mathsf{DerVerTyp}(i)$ is a robot type by
proving that the conditions of Definition 5.20 hold. Since
$(\mathsf{CC}_{i},{\cal C}_{i})$ is an $\widehat{E}_{i}$-valid pair, from
Condition 1 of Definition 5.9, $\mathsf{Graph}(\mathsf{CC}_{i})$ is a
$\overline{G}$-submultigraph. So,
$G^{\prime}_{i}=\overline{G}(\mathsf{Graph}(\mathsf{CC}_{i}))$ is a
submultigraph of $\overline{G}$, with an isomorphism
$\alpha_{i}:V(\overline{G})\rightarrow V(\mathsf{Graph}(\mathsf{CC}_{i}))$
satisfies the conditions of Definition 5.6. Thus,
$\mathsf{CC}^{\prime}_{i}=E(G_{i}^{\prime})\subseteq E(\overline{G})$, and
therefore, Condition 1 of Definition 5.20 holds.

From Condition 2 of Definition 5.9, $\mathsf{Graph}(\mathsf{CC}_{i})$ is
connected, $v_{\mathsf{init}}\in V(\mathsf{Graph}(\mathsf{CC}_{i}))$ and every
vertex in $\mathsf{Graph}(\mathsf{CC}_{i})$ has even degree. So,
$\mathsf{Graph}(\mathsf{CC}^{\prime}_{i})$ is connected, every vertex in
$\mathsf{Graph}(\mathsf{CC}^{\prime}_{i})$ has even degree and
$v_{\mathsf{init}}\in V(\mathsf{Graph}(\mathsf{CC}^{\prime}_{i}))$. Thus,
Condition 2 of Definition 5.20 holds.

Now, let $(u^{*}_{j},\mathsf{NeiSub})\in\mathsf{NeiOfInd}(G^{\prime}_{i})$.
Then,
$\mathsf{Alloc}_{G_{i}^{\prime}}((u^{*}_{j},\mathsf{NeiSub}))=\mathsf{DerVerTyp}(\alpha_{i}(u^{*}_{j}))$,
so
$\mathsf{Alloc}_{G_{i}^{\prime}}((u^{*}_{j},\mathsf{NeiSub}))=(z^{*},\mathsf{NeiSubsets}(\alpha_{i}(u^{*}_{j})))$,
where $\mathsf{NeiSubsets}(\alpha_{i}(u^{*}_{j}))=\bigcup_{1\leq t\leq k}$
$(\\{\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{t})}(\alpha_{i}(u^{*}_{j}))\\}\cup\mathsf{NeiPairs}_{{\cal
C}_{t}}(\alpha_{i}(u^{*}_{j})))$(see Definition 5.13). Observe that
$\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{i})}$
$(\alpha_{i}(u^{*}_{j}))=\mathsf{NeiSub}$, thus
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}(\alpha_{i}(u^{*}_{j}))$. In addition,
from Condition 2 of Definition 5.6, $\alpha_{i}(u^{*}_{j})\in u^{*}$, so
$z^{*}=u^{*}$. Also, from Lemma 5.15,
$\mathsf{DerVerTyp}(\alpha_{i}(u^{*}_{j}))\in\mathsf{VerTypS}$. Therefore,
$\mathsf{Alloc}_{G_{i}^{\prime}}$ is a vertex allocation of
$\mathsf{NeiOfInd}(G_{i}^{\prime})=\mathsf{NeiOfInd}(\mathsf{Graph}(\mathsf{CC}_{i}^{\prime}))$,
so Condition 3 of Definition 5.20 holds.

Now, since $(\mathsf{CC}_{i},{\cal C}_{i})$ is an $\widehat{E}_{i}$-valid
pair, from Condition 1 of Definition 5.9, at most $2|\mathsf{VC}|^{2}$ cycles
in ${\cal C}_{i}$ have length other than $4$. Therefore, for every $2\leq
j\leq 2|\mathsf{VC}|$, $0\leq N_{j}\leq 2|\mathsf{VC}|^{2}$. So, Condition 4
of Definition 5.20 holds.

We proved that all of the conditions of Definition 5.20 hold, so
$\mathsf{DerVerTyp}(i)$ is a robot type. This ends the proof.

###  5.4 Cycle Type

Lastly, we have a variable for each cycle type. For every $1\leq i\leq k$, let
$(\mathsf{CC}_{i},{\cal C}_{i})$ be an $\widehat{E}_{i}$-valid pair. First, we
show how we derive a cycle type for each $C\in{\cal C}_{i}$, for every $1\leq
i\leq k$, and then we will present the definition. An intuition for a cycle
type is as follows. In Lemma 5.13, where we derive vertex types, we saw how we
derive $\mathsf{NeiSubsets}(u)$ for each $u\in V(G)\setminus\mathsf{VC}$. Some
of the multisets in $\mathsf{NeiSubsets}(u)$ are derived from cycles in
$\mathsf{CC}_{i}$, for some $1\leq i\leq k$. Now, we look on the “puzzle” from
the perspective of the cycles. For each
$\\{\\{u,v\\},\\{u,v^{\prime}\\}\\}\in\mathsf{EdgePairs}(C)$, the multiset
$\\{v,v^{\prime}\\}$ is “allocated” for the vertex type of $u$.

Similarly to the definition of a vertex allocation of
$\mathsf{NeiOfInd}(G^{\prime})$ (Definition 5.18), we have the following
definition, for allocation of $\mathsf{EdgePairs}(C)$:

######  Definition 5.23 (Vertex Allocation of $\mathsf{EdgePairs}(C)$).

Let $G$ be a connected graph, let $\mathsf{VC}$ be a vertex cover of $G$ and
let $C\in\mathsf{Cyc}_{G}\cup\mathsf{Cyc}_{G^{*}}$. A vertex allocation of
$\mathsf{EdgePairs}(C)$ is a function
$\mathsf{PaAlloc}_{C}:\mathsf{EdgePairs}(C)\rightarrow\mathsf{VerType}$, such
that for every
$\\{\\{v_{i-1},v_{i}\\},\\{v_{i},v_{i+1}\\}\\}\in\mathsf{EdgePairs}(C)$,
$\\{v_{i-1},v_{i+1}\\}\in\mathsf{NeiSubsets}$ and $v_{i}\in u^{*}$ or
$v_{i}=u^{*}$, where $\mathsf{PaAlloc}_{C}(\\{\\{v_{i-1},v_{i}\\},$
$\\{v_{i},v_{i+1}\\}\\})=(u^{*},\mathsf{NeiSubsets})$.

Let $C=(v_{0},\ldots,v_{\ell}=v_{0})\in\mathsf{Cyc}_{G}$. Recall that we
denote by $\mathsf{EQ}(C)$ the cycle in $G^{*}$ obtained from $C$ by replacing
each $v_{i}\in V(C)\cap(V(G)\setminus\mathsf{VC})$ by $u^{*}\in\mathsf{EQ}$,
where $v_{i}\in u^{*}$, for every $1\leq i\leq\ell$. Similarly, let
$\mathsf{PaAlloc}_{C}$ be a vertex allocation of $\mathsf{EdgePairs}(C)$. We
denote by $\mathsf{EQ}(\mathsf{PaAlloc}_{C})$ the function
$\mathsf{EQ}(\mathsf{PaAlloc}_{C}):\mathsf{EdgePairs}(\mathsf{EQ}(C))\rightarrow\mathsf{VerType}$
defined as follows: for every
$\\{\\{v_{i-1},u^{*}\\},\\{u^{*},v_{i+1}\\}\\}\in\mathsf{EdgePairs}(\mathsf{EQ}(C))$,
$\mathsf{EQ}(\mathsf{PaAlloc}_{C})(\\{\\{v_{i-1},u^{*}\\},\\{u^{*},v_{i+1}\\}$
$\\})=\mathsf{Alloc}_{C}(\\{\\{v_{i-1},v_{i}\\},\\{v_{i},v_{i+1}\\}\\})$.
Observe that $\mathsf{EQ}(\mathsf{PaAlloc}_{C})$ is a vertex allocation of
$\mathsf{EdgePairs}(\mathsf{EQ}(C))$:

Let $C\in\mathsf{Cyc}_{G}$ and let $\mathsf{PaAlloc}_{C}$ be a vertex
allocation of $\mathsf{EdgePairs}(C)$. Then,
$\mathsf{EQ}(\mathsf{PaAlloc}_{C})$ is a vertex allocation of
$\mathsf{EdgePairs}(\mathsf{EQ}(C))$.

######  Definition 5.24 (Deriving Cycle Types From a Solution).

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$, let
$k,B\in\mathbb{N}$, let $\mathsf{VC}$ be a vertex cover of $G$ and let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that conditions of Lemma 3.2
hold. For every $1\leq i\leq k$, let $(\mathsf{CC}_{i},{\cal C}_{i})$ be an
$\widehat{E}_{i}$-valid pair. For every $1\leq i\leq k$, $C\in{\cal C}_{i}$
and $\\{\\{u,v\\},\\{u,v^{\prime}\\}\\}\in\mathsf{EdgePairs}(C)$, let
$\mathsf{PaAlloc}_{i,C}(\\{\\{v,u\\},\\{u,v^{\prime}\\}\\})=\mathsf{DerVerTyp}(u)$.
Then, for every $1\leq i\leq k$ and $C\in{\cal C}_{i}$, let

$\mathsf{DerCycTyp}(\\{(\mathsf{CC}_{j},{\cal C}_{j})\\}_{1\leq j\leq
k},i,C)=(\mathsf{EQ}(C),\mathsf{EQ}(\mathsf{PaAlloc}_{i,C}),\mathsf{DerRobTyp}(i))$.

Whenever $\\{(\mathsf{CC}_{i},{\cal C}_{i})\\}_{1\leq i\leq k}$ is clear from
context, we refer to $\mathsf{DerCycTyp}(\\{(\mathsf{CC}_{j},{\cal
C}_{j})\\}_{1\leq j\leq k},$ $i,C)$ as $\mathsf{DerCycTyp}(i,C)$.

Now, we define the term cycle type. In addition to the vertex allocation of
$\mathsf{EdgePairs}(C)$, we have the robot type
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},\mathsf{NumOfCyc})$
associated with the cycle type. In order to maintain the connectivity of
$\mathsf{Graph}(\widehat{E})$, we demand that
$V(\mathsf{Graph}(\mathsf{CC}))\cap V(C)\cap\mathsf{VC}\neq\emptyset$ (see the
discussion before Definition 5.20).

######  Definition 5.25 (Cycle Type).

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$ and let
$\mathsf{VC}$ be a vertex cover of $G$. Let $C\in\mathsf{Cyc}_{G^{*}}$, let
$\mathsf{PaAlloc}_{C}$ be a vertex allocation of $\mathsf{EdgePairs}(C)$ and
let
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},\mathsf{NumOfCyc})$
be a robot type. Then,
$\mathsf{CycTyp}=(C,\mathsf{PaAlloc}_{C},\mathsf{RobTyp})$ is a cycle type if
$V(\mathsf{Graph}(\mathsf{CC}))\cap V(C)\cap\mathsf{VC}\neq\emptyset$.

We denote the set of cycle types by $\mathsf{CycTypS}$.

In the following lemma we show the “correctness” of Definition 5.24, that is,
for every $1\leq i\leq k$, $C\in{\cal C}_{i}$, $\mathsf{DerCycTyp}(i,C)$ is
indeed a cycle type.

######  Lemma 5.26.

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$, let
$k,B\in\mathbb{N}$ and let $\mathsf{VC}$ be a vertex cover of $G$. Let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that conditions of Lemma 3.2
hold and for every $1\leq i\leq k$ let $(\mathsf{CC}_{i},{\cal C}_{i})$ be an
$\widehat{E}_{i}$-valid pair. Then, for every $1\leq i\leq k$, $C\in{\cal
C}_{i}$, $\mathsf{DerCycTyp}(i,C)$ is a cycle type.

######  Proof 5.27.

Let $1\leq i\leq k$ and $C\in{\cal C}_{i}$. We show that
$\mathsf{DerCycTyp}(i,C)$ is a cycle type. First, from Condition 4 of
Definition 5.9, every cycle in ${\cal C}_{i}$ of length other than $4$ is
simple. So, the length of $C$ is at most $\mathsf{max}\\{4,2|\mathsf{VC}|\\}$,
and thus, $\mathsf{EQ}(C)\in\mathsf{Cyc}_{G^{*}}$.

Second, we show that $\mathsf{PaAlloc}_{i,C}$, defined in Definition 5.24, is
a vertex allocation of $\mathsf{EdgePairs}(C)$. Let
$\\{\\{u,v\\},\\{u,v^{\prime}\\}\\}\in\mathsf{EdgePairs}(C)$. Then,
$\mathsf{PaAlloc}_{i,C}(\\{\\{v,u\\},\\{u,v^{\prime}\\}\\})=\mathsf{DerVerTyp}(u)$.
First, from Lemma 5.15, $\mathsf{DerVerTyp}(u)$ is a vertex type. Now, by
Definition 5.13, $\mathsf{DerVerTyp}(u)=(u^{*},\mathsf{NeiSubsets}(u))$, where
$u\in u^{*}$, $\mathsf{NeiSubsets}(u)=\bigcup_{1\leq j\leq k}($
$\\{\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{j})}(u)\\}\cup\mathsf{NeiPairs}_{{\cal
C}_{j}}(u))$ and $\mathsf{NeiPairs}_{{\cal
C}_{j}}(u)=\\{\\{v,v^{\prime}\\}\leavevmode\nobreak\ |\leavevmode\nobreak\
C\in{\cal
C}_{j},\\{\\{u,v\\},\\{u,v^{\prime}\\}\\}\in\mathsf{EdgePairs}(C)\\}$. So,
since $\\{\\{u,v\\},\\{u,v^{\prime}\\}\\}\in\mathsf{EdgePairs}(C)$, then
$\\{v,v^{\prime}\\}\in\mathsf{NeiPairs}_{{\cal
C}_{i}}(u)\subseteq\mathsf{NeiSubsets}(u)$. Therefore,
$\mathsf{PaAlloc}_{i,C}$ is a vertex allocation of $\mathsf{EdgePairs}(C)$,
and from Observation 5.4, $\mathsf{EQ}(\mathsf{PaAlloc}_{i,C})$ is a vertex
allocation of $\mathsf{EdgePairs}(\mathsf{EQ}(C))$.

Now, since $(\mathsf{CC}_{i},{\cal C}_{i})$ is an $\widehat{E}_{i}$-valid
pair, from Condition 3 of Definition 5.9, $V(\mathsf{Graph}(\mathsf{CC}_{i}))$
$\cap\mathsf{VC}=V(\mathsf{Graph}(\widehat{E}_{i}))\cap\mathsf{VC}$. From
Definition 5.19,
$\mathsf{DerRobTyp}(i)=((\mathsf{CC}^{\prime}_{i}),\mathsf{Alloc}_{G_{i}^{\prime}},$
$\mathsf{NumOfCyc}_{i})$, where $\mathsf{CC}^{\prime}_{i}=E(G_{i}^{\prime})$
and $G^{\prime}_{i}=\overline{G}(\mathsf{Graph}(\mathsf{CC}_{i}))$. Now,
Condition 1 of Definition 5.6 implies that
$V(G^{\prime}_{i})\cap\mathsf{VC}=V(\mathsf{Graph}(\widehat{E}_{i}))\cap\mathsf{VC}$,
so
$V(\mathsf{Graph}(\mathsf{CC}^{\prime}))\cap\mathsf{VC}=V(\mathsf{Graph}(\widehat{E}_{i}))$
$\cap\mathsf{VC}$. From Observation 5.1,
$V(\mathsf{Graph}(\widehat{E}_{i}))\cap\mathsf{VC}\cap V(C)\neq\emptyset$,
thus $V(\mathsf{Graph}(\mathsf{CC}^{\prime}))\cap\mathsf{VC}\cap
V(C)\neq\emptyset$. In addition, from Lemma 5.21, $\mathsf{DerRobTyp}(i)$ is a
robot type. Overall, $\mathsf{DerCycTyp}(i,C)$ is a cycle type.

###  5.5 The Instance $\mathsf{Reduction}(G,v_{\mathsf{init}},k,B)$ of the ILP
Problem

Now, we are ready to present our reduction to the ILP problem. We have the
following variables:

  * •

For every $\mathsf{VerTyp}\in\mathsf{VerTypS}$, we have the variable
$x_{\mathsf{VerTyp}}$.

  * •

For every $\mathsf{RobTyp}\in\mathsf{RobTypS}$, we have the variable
$x_{\mathsf{RobTyp}}$.

  * •

For every $\mathsf{CycTyp}\in\mathsf{CycTypS}$, we have the variable
$x_{\mathsf{CycTyp}}$.

Each variable stands for the number of elements of each type. We give
intuition for each of the following equations:

Equation 1: Robot Type for Each Robot. In this equation, we make sure that the
total sum of robot types is exactly $k$, that is, there is exactly one robot
type for each robot:

1\.
$\displaystyle{\sum_{\mathsf{RobTyp}\in\mathsf{RobTypS}}x_{\mathsf{RobTyp}}=k}$.

Equation 2: Vertex Type for Each Vertex. For every $u^{*}\in\mathsf{EQ}$, we
denote the set of
$\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})\in\mathsf{VerTypS}$ by
$\mathsf{VerTypS}_{u^{*}}$. In this equation, we make sure, for every
$u^{*}\in\mathsf{EQ}$, that the total sum of vertex types in
$\mathsf{VerTypS}_{u^{*}}$ is exactly $|u^{*}|$. That is, there is exactly one
vertex type $\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})$ for each $u\in
u^{*}$:

2\. For every $u^{*}\in\mathsf{EQ}$,
$\displaystyle{\sum_{\mathsf{VerTyp}\in\mathsf{VerTypS}_{u^{*}}}x_{\mathsf{VerTyp}}=|u^{*}|}$

Equation 3: Assigning Enough Subsets to Each Vertex Type. We have the
following notations:

  * •

For every $\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})\in\mathsf{VerTypS}$,
every $\mathsf{NeiSub}=\\{v,v^{\prime}\\}\in\mathsf{NeiSubsets}$ and $1\leq
j\leq 2|\mathsf{VC}|$, we denote

$\mathsf{CycTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)=\\{\mathsf{CycTyp}=(C,\mathsf{PaAlloc}_{C},\mathsf{RobTyp})\in\mathsf{CycTypS}\leavevmode\nobreak\
|\leavevmode\nobreak\ $

$|\\{\\{\\{u^{*},v\\},\\{u^{*},v^{\prime}\\}\\}\in\mathsf{EdgePairs}(C)\leavevmode\nobreak\
|\leavevmode\nobreak\ $
$\mathsf{PaAlloc}_{C}(\\{\\{u^{*},v\\},\\{u^{*},v^{\prime}\\}\\})=\mathsf{VerTyp}\\}|=j\\}$.
That is, $\mathsf{CycTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)$ is the set of
cycle types that assign $\mathsf{NeiSub}$ to $\mathsf{VerTyp}$ exactly $j$
times.

  * •

For every $\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})\in\mathsf{VerTypS}$,
every $\mathsf{NeiSub}\in\mathsf{NeiSubsets}$ and $1\leq j\leq
2^{|\mathsf{VC}|}+|\mathsf{VC}|^{2}$,

$\mathsf{RobTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)=\\{\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},\mathsf{NumOfCyc})\in\mathsf{RobTypS}\leavevmode\nobreak\
|\leavevmode\nobreak\ $

$|\\{(u^{*}_{i},\mathsf{NeiSub})\in\mathsf{NeiOfInd}(\mathsf{Graph}(\mathsf{CC}))\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})}((u^{*}_{i},\mathsf{NeiSub}))=\mathsf{VerTyp}\\}|=j\\}$.
That is, $\mathsf{RobTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)$ is the set of
robot types that assign $\mathsf{NeiSub}$ to $\mathsf{VerTyp}$ exactly $j$
times.

Recall that, for a vertex $u\in u^{*}\in\mathsf{EQ}$ of vertex type
$\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})$, $\mathsf{NeiSubsets}$ encodes
“how” the edges incident to $u$ are covered. That is, for every
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}$, there exists a robot $i\in[k]$ which
covers the multiset of edges with one endpoint in $u$ and the other being a
vertex in $\mathsf{NeiSub}$. A robot is able to cover this exact multiset of
edges if
$(u^{*}_{i},\mathsf{NeiSub})\in\mathsf{NeiOfInd}(\mathsf{Graph}(\mathsf{CC}_{i})$
or $\mathsf{NeiSub}=\\{v,v^{\prime}\\}$ and
$\\{\\{u^{*},v\\},\\{u^{*},v^{\prime}\\}\\}\in\mathsf{EdgePairs}(C)$ for
$C\in{\cal C}_{i}$, where $\mathsf{CC}_{i}$ and ${\cal C}_{i}$ satisfy the
conditions of Lemma 5.10. Therefore, for every
$\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})\in\mathsf{VerTypS}$ and every
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}$, we ensure we have at least one
$\mathsf{NeiSub}$ assigned to each vertex of $\mathsf{VerTyp}$:

3\. For every
$\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})\in\mathsf{VerTypS}$, and every
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}$,

$\displaystyle{\sum_{j=1}^{2{|\mathsf{VC}|}}\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)}}j\cdot
x_{\mathsf{CycTyp}}+}$
$\displaystyle{\sum_{j=1}^{2^{|\mathsf{VC}|}+|\mathsf{VC}|^{2}}\sum_{{\mathsf{RobTyp}\in\mathsf{RobTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)}}j\cdot
x_{\mathsf{RobTyp}}\geq x_{\mathsf{VerTyp}}}$.

Observe that Equations 1–3 ensure that every edge with one endpoint in
$V\setminus\mathsf{VC}$ is covered.

Equation 4: Covering Each Edge with Both Endpoints in $\mathsf{VC}$. We have
the following notations:

  * •

For every $\\{u,v\\}\in E$ such that $u,v\in\mathsf{VC}$,

$\mathsf{CycTypS}(\\{u,v\\})=\\{\mathsf{CycTyp}=(C,\mathsf{PaAlloc}_{C},\mathsf{RobTyp})\in\mathsf{CycTypS}\leavevmode\nobreak\
|\leavevmode\nobreak\ \\{u,v\\}\in E(C)\\}$. That is,
$\mathsf{CycTypS}(\\{u,v\\})$ is the set of cycle types
$\mathsf{CycTyp}=(C,\mathsf{PaAlloc}_{C},\mathsf{RobTyp})$ where $C$ covers
$\\{u,v\\}$.

  * •

For every $\\{u,v\\}\in E$ such that $u,v\in\mathsf{VC}$,

$\mathsf{RobTypS}(\\{u,v\\})=\\{\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},$
$\mathsf{NumOfCyc})\in\mathsf{RobTypS}\leavevmode\nobreak\
|\leavevmode\nobreak\ \\{u,v\\}\in\mathsf{CC}\\}$. That is,
$\mathsf{RobTypS}(\\{u,v\\})$ is the set of robot types
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})})$
where $\mathsf{CC}$ covers $\\{u,v\\}$.

In this equation we ensure that each $\\{u,v\\}\in E$ with both endpoints in
$\mathsf{VC}$ is covered at least once:

4\. For every $\\{u,v\\}\in E$ such that $u,v\in\mathsf{VC}$,

$\displaystyle{\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\\{u,v\\})}}x_{\mathsf{CycTyp}}+\sum_{{\mathsf{RobTyp}\in\mathsf{RobTypS}(\\{u,v\\})}}x_{\mathsf{RobTyp}}\geq
1}$.

Observe that Equations 1–4 ensure that every edge in $G$ is covered.

Equation 5: Assigning the Exact Amount of Cycles with Length Other Than $4$ to
Each Robot Type. We have the following notation:

  * •

For every $\mathsf{RobTyp}\in\mathsf{RobTypS}$ and for every $2\leq j\leq
2|\mathsf{VC}|$,

$\mathsf{CycTypS}(\mathsf{RobTyp},j)=\\{\mathsf{CycTyp}=(C,\mathsf{PaAlloc}_{C},\mathsf{RobTyp})\in\mathsf{CycTypS}\leavevmode\nobreak\
|\leavevmode\nobreak\ |C|=j\\}$. That is,
$\mathsf{CycTypS}(\mathsf{RobTyp},j)$ is the set of cycle types, stand for a
cycle of length $j$ and assigned to a robot with robot type $\mathsf{RobTyp}$.

Let
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},\mathsf{NumOfCyc})\in\mathsf{RobTypS}$
be a robot type. In this equation, we verify that the number of cycles of
length other than $4$ assigned to robots with robot type $\mathsf{RobTyp}$ is
exactly as determined in $\mathsf{NumOfCyc}$:

5\. For every
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},\mathsf{NumOfCyc})\in\mathsf{RobTypS}$
and for every

$2\leq j\leq 2|\mathsf{VC}|$, $j\neq 4$,
$\displaystyle{\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{RobTyp},j)}}x_{\mathsf{CycTyp}}=N_{j}\cdot
x_{\mathsf{RobTyp}}}$,

where $\mathsf{NumOfCyc}=(N_{2},N_{3},N_{5},N_{6},\ldots,N_{2|\mathsf{VC}|})$.

Equation 6: Verifying the Budget Limit. Let
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},\mathsf{NumOfCyc})$
$\in\mathsf{RobTypS}$ be a robot type, and let $i\in[k]$ be robot with robot
type $\mathsf{RobTyp}$. From Lemma 5.10, there exist
$\mathsf{CC}_{i}\subseteq\widehat{E}_{i}$ and a multiset of cycles ${\cal
C}_{i}$ in $\mathsf{Graph}(\widehat{E}_{i})$, such that
$\mathsf{CC}_{i}\cup\bigcup_{C\in{\cal C}_{i}}E(C)=\widehat{E}_{i}$. Now, as
we determine the robot type of the $i$-th robot to be $\mathsf{RobTyp}$,
$|\mathsf{CC}_{i}|=|\mathsf{CC}|$, and the number of cycles in ${\cal C}_{i}$
of length other than $4$ is fixed by $\mathsf{NumOfCyc}$. We have the
following notation:

  * •

$\displaystyle{\mathsf{Bud}(\mathsf{RobTyp})=|\mathsf{CC}|+\sum_{2\leq j\leq
2|\mathsf{VC}|,j\neq 4}N_{j}\cdot j}$, where
$\mathsf{NumOfCyc}=(N_{2},N_{3},N_{5},N_{6},\ldots,$
$N_{2|\mathsf{VC}|})$.

That is, $\mathsf{Bud}(\mathsf{RobTyp})$ is the number of edges in
$\mathsf{CC}_{i}\cup\bigcup_{C\in{\cal C}_{i}}E(C)$ excluding the number of
edges in cycles of length $4$ in ${\cal C}_{i}$. Therefore,
$B-\mathsf{Bud}(\mathsf{RobTyp})$ is the budget left for the robot for the
cycles in ${\cal C}_{i}$ of length $4$. Now, we take the largest number which
is a multiple of $4$ and less or equal to $B-\mathsf{Bud}(\mathsf{RobTyp})$,
to be the budget left for cycles of length $4$. So, we have the following
notation:

  * •

For every $\mathsf{RobTyp}\in\mathsf{RobTypS}$,
$\mathsf{CycBud}(\mathsf{RobTyp})=\lfloor(B-\mathsf{Bud}(\mathsf{RobTyp}))\cdot\frac{1}{4}\rfloor\cdot
4$.

6\. For every $\mathsf{RobTyp}\in\mathsf{RobTypS}$,
$\displaystyle{\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{RobTyp},4)}}4\cdot
x_{\mathsf{CycTyp}}\leq
x_{\mathsf{RobTyp}}\cdot\mathsf{CycBud}(\mathsf{RobTyp})}$.

Summary of Equations. In conclusion, given an instance
$(G,v_{\mathsf{init}},k,B)$ of CGE problem,
$\mathsf{Reduction}(G,v_{\mathsf{init}},k,B)$ is the instance of the ILP
problem described by the following equations:

  1. 1.

$\displaystyle{\sum_{\mathsf{RobTyp}\in\mathsf{RobTypS}}x_{\mathsf{RobTyp}}=k}$.

  2. 2.

For every $u^{*}\in\mathsf{EQ}$,
$\displaystyle{\sum_{\mathsf{VerTyp}\in\mathsf{VerTypS}_{u^{*}}}x_{\mathsf{VerTyp}}=|u^{*}|}$.

  3. 3.

For every $\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})\in\mathsf{VerTypS}$,
and every $\mathsf{NeiSub}\in\mathsf{NeiSubsets}$,

$\displaystyle{\sum_{j=1}^{2{|\mathsf{VC}|}}\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)}}j\cdot
x_{\mathsf{CycTyp}}+}$
$\displaystyle{\sum_{j=1}^{2^{|\mathsf{VC}|}+|\mathsf{VC}|^{2}}\sum_{{\mathsf{RobTyp}\in\mathsf{RobTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)}}j\cdot
x_{\mathsf{RobTyp}}\geq x_{\mathsf{VerTyp}}}$.

  4. 4.

For every $\\{u,v\\}\in E$ such that $u,v\in\mathsf{VC}$,
$\displaystyle{\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\\{u,v\\})}}x_{\mathsf{CycTyp}}+\sum_{{\mathsf{RobTyp}\in\mathsf{RobTypS}(\\{u,v\\})}}x_{\mathsf{RobTyp}}\geq
1}$.

  5. 5.

For every
$\mathsf{RobTyp}=(\mathsf{CC},\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC})},\mathsf{NumOfCyc})\in\mathsf{RobTypS}$
and for every

$2\leq j\leq 2|\mathsf{VC}|$, $j\neq 4$,
$\displaystyle{\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{RobTyp},j)}}x_{\mathsf{CycTyp}}=N_{j}\cdot
x_{\mathsf{RobTyp}}}$,

where $\mathsf{NumOfCyc}=(N_{2},N_{3},N_{5},N_{6},\ldots,N_{2|\mathsf{VC}|})$.

  6. 6.

For every $\mathsf{RobTyp}\in\mathsf{RobTypS}$,
$\displaystyle{\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{RobTyp},4)}}4\cdot
x_{\mathsf{CycTyp}}\leq
x_{\mathsf{RobTyp}}\cdot\mathsf{CycBud}(\mathsf{RobTyp})}$.

###  5.6 Correctness: Forward Direction

Now, we turn to prove the correctness of the reduction. In particular, we have
the following lemma:

######  Lemma 5.28.

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$ and let
$k,B\in\mathbb{N}$. Then, $(G,v_{\mathsf{init}},k,B)$ is a yes-instance of the
CGE, if and only if $\mathsf{Reduction}(G,v_{\mathsf{init}},k,B)$ is a yes-
instance of the Integer Linear Programming.

We split the proof of the correctness of Lemma 5.28 to two lemmas. We begin
with the proof of the first direction:

######  Lemma 5.29.

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$ and let
$k,B\in\mathbb{N}$. If $(G,v_{\mathsf{init}},k,B)$ is a yes-instance of the
CGE problem, then $\mathsf{Reduction}(G,v_{\mathsf{init}},k,B)$ is a yes-
instance of the Integer Linear Programming.

Towards the proof of Lemma 5.29, we present the function
$\mathsf{RobExpToILP}$. This function gets as input, for every $1\leq i\leq
k$, $(\mathsf{CC}_{i},{\cal C}_{i})$ that is an $\widehat{E}_{i}$-valid pair.
Then, for every
$z\in\mathsf{VerTypS}\cup\mathsf{RobTypS}\cup\mathsf{CycTypS}$,
$\mathsf{RobExpToILP}(z)$ is the number of elements of type $z$ derived by
Definitions 5.13, 5.19 and 5.24:

######  Definition 5.30 ($\mathsf{RobExpToILP}$).

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$, let
$\mathsf{VC}$ be a vertex cover of $G$ and let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that conditions of Lemma 3.2
hold. For every $1\leq i\leq k$, let $(\mathsf{CC}_{i},{\cal C}_{i})$ be an
$\widehat{E}_{i}$-valid pair. Then:

  1. 1.

For every $\mathsf{VerTyp}\in\mathsf{VerTypS}$,
$\mathsf{RobExpToILP}(\\{(\mathsf{CC}_{j},{\cal C}_{j})\\}_{1\leq j\leq
k},\mathsf{VerTyp})=|\\{u\in V(G)\setminus\mathsf{VC}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathsf{DerVerTyp}(u)=\mathsf{VerTyp}\\}|$.

  2. 2.

For every $\mathsf{RobTyp}\in\mathsf{RobTypS}$,
$\mathsf{RobExpToILP}(\\{(\mathsf{CC}_{j},{\cal C}_{j})\\}_{1\leq j\leq
k},\mathsf{RobTyp})=|\\{1\leq i\leq k\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathsf{DerRobTyp}(i)=\mathsf{RobTyp}\\}|$.

  3. 3.

For every $\mathsf{CycTyp}\in\mathsf{CycTypS}$,
$\mathsf{RobExpToILP}(\\{(\mathsf{CC}_{j},{\cal C}_{j})\\}_{1\leq j\leq
k},\mathsf{CycTyp})=|\\{(i,C)\leavevmode\nobreak\ |\leavevmode\nobreak\ 1\leq
i\leq k,C\in{\cal C}_{i},\mathsf{DerCycTyp}(i,C)=\mathsf{CycTyp}\\}|$.

Whenever $\\{(\mathsf{CC}_{i},{\cal C}_{i})\\}_{1\leq i\leq k}$ is clear from
context, we refer to
$\mathsf{RobExpToILP}(\\{(\mathsf{CC}_{j},{\cal C}_{j})\\}_{1\leq j\leq
k},\mathsf{VerTyp})$, $\mathsf{RobExpToILP}(\\{(\mathsf{CC}_{j},{\cal
C}_{j})\\}_{1\leq j\leq k},\mathsf{RobTyp})$ and
$\mathsf{RobExpToILP}(\\{(\mathsf{CC}_{j},{\cal C}_{j})\\}_{1\leq j\leq
k},\mathsf{CycTyp})$ as $\mathsf{RobExpToILP}(\mathsf{VerTyp})$,
$\mathsf{RobExpToILP}(\mathsf{RobTyp})$
and $\mathsf{RobExpToILP}(\mathsf{CycTyp})$, respectively.

In the next lemma, we prove that the values given by Definition 5.30 satisfy
the inequalities of $\mathsf{Reduction}(G,v_{\mathsf{init}},k,B)$:

######  Lemma 5.31.

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$, let
$\mathsf{VC}$ be a vertex cover of $G$ and let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that conditions of Lemma 3.2
hold. For every $1\leq i\leq k$, let $(\mathsf{CC}_{i},{\cal C}_{i})$ be an
$\widehat{E}_{i}$-valid pair. Then, the values
$x_{z}=\mathsf{RobExpToILP}(z)$, for every
$z\in\mathsf{VerTypS}\cup\mathsf{RobTypS}\cup\mathsf{CycTypS}$, satisfy the
inequalities of $\mathsf{Reduction}(G,v_{\mathsf{init}},k,B)$.

For the sake of readability, we split Lemma 5.31 and its proof into two
lemmas: In Lemma 5.32 we prove that the values
$x_{z}=\mathsf{RobExpToILP}(z)$, for every
$z\in\mathsf{VerTypS}\cup\mathsf{RobTypS}\cup\mathsf{CycTypS}$, satisfy
inequalities 1–3 of $\mathsf{Reduction}(G,v_{\mathsf{init}},k,B)$, and in
Lemma 5.34 we prove that these values satisfy inequalities 4–6.

######  Lemma 5.32.

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$, let
$\mathsf{VC}$ be a vertex cover of $G$ and let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that conditions of Lemma 3.2
hold. For every $1\leq i\leq k$, let $(\mathsf{CC}_{i},{\cal C}_{i})$ be an
$\widehat{E}_{i}$-valid pair. Then, the values
$x_{z}=\mathsf{RobExpToILP}(z)$, for every
$z\in\mathsf{VerTypS}\cup\mathsf{RobTypS}\cup\mathsf{CycTypS}$, satisfy
inequalities 1–3 of $\mathsf{Reduction}(G,v_{\mathsf{init}},k,B)$.

######  Proof 5.33.

By Lemma 5.21, for every $1\leq i\leq k$, $\mathsf{DerVerTyp}(i)$ is a robot
type, and thus, Equation 1 is satisfied.

Similarly, from Lemma 5.15, for every $u\in u^{*}\in\mathsf{EQ}$,
$\mathsf{DerVerTyp}(u)$ is a vertex type, where
$\mathsf{DerVerTyp}(u)=(u^{*},\mathsf{NeiSubsets})$, for some
$\mathsf{NeiSubsets}\subseteq 2^{\mathsf{N}_{G^{*}}(u^{*})\times\mathsf{2}}$.
Therefore, Equations 2 are satisfied.

Now, let $\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})\in\mathsf{VerTypS}$, let
$u\in u^{*}$ such that $\mathsf{DerVerTyp}(u)=\mathsf{VerTyp}$, and let
$\mathsf{NeiSub}\in\mathsf{NeiSubsets}$. So, by Definition 5.13,
$\mathsf{NeiSubsets}=\mathsf{NeiSubsets}(u)=\bigcup_{1\leq i\leq
k}(\\{\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{i})}(u)\\}\cup\mathsf{NeiPairs}_{{\cal
C}_{i}}(u))$, where $\mathsf{NeiPairs}_{{\cal
C}_{i}}(u)=\\{\\{v,v^{\prime}\\}\leavevmode\nobreak\ |\leavevmode\nobreak\
C\in{\cal C}_{i},\\{\\{u,v\\},$
$\\{u,v^{\prime}\\}\\}\in\mathsf{EdgePairs}(C)\\}$. Thus, there exists $1\leq
i\leq k$ such that at least one among the following conditions holds:

  1. 1.

$\mathsf{NeiSub}\in\mathsf{NeiPairs}_{{\cal C}_{i}}(u)$. Therefore, there
exists $C\in{\cal C}_{i}$ such that $\\{\\{u,v\\},\\{u,v^{\prime}\\}\\}\in$
$\mathsf{EdgePairs}(C)$ and $\mathsf{NeiSub}=\\{v,v^{\prime}\\}$. Thus, by
Definition 5.24,
$\mathsf{DerCycTyp}(i,C)=(\mathsf{EQ}(C),\mathsf{EQ}(\mathsf{PaAlloc}_{i,C})$,
$\mathsf{DerRobTyp}(i))$, where $\mathsf{PaAlloc}_{i,C}$ is a vertex
allocation of
$\mathsf{EdgePairs}(C)$, and
$\mathsf{PaAlloc}_{i,C}(\\{\\{v,u\\},\\{u,v^{\prime}\\}\\})=\mathsf{DerVerTyp}(u)=\mathsf{VerTyp}$.
So, $u$ contributes at least one to
$|\\{\\{\\{u,v\\},\\{u,v^{\prime}\\}\\}\in\mathsf{EdgePairs}(C)\leavevmode\nobreak\
|\leavevmode\nobreak\ $
$\mathsf{PaAlloc}_{i,C}(\\{\\{u,v\\},\\{u,v^{\prime}\\}\\})=\mathsf{VerTyp}\\}|$,
thus, $u$ contributes at least one to
$|\\{\\{\\{u^{*},v\\},\\{u^{*},v^{\prime}\\}\\}\in\mathsf{EdgePairs}(\mathsf{EQ}(C))\leavevmode\nobreak\
|\leavevmode\nobreak\ $
$\mathsf{EQ}(\mathsf{PaAlloc}_{i,C})(\\{\\{u^{*},v\\},\\{u^{*},v^{\prime}\\}\\})=\mathsf{VerTyp}\\}|$.
Now, since $C\in\mathsf{Cyc}_{G}$, $\mathsf{EQ}(C)\in\mathsf{Cyc}_{G^{*}}$, so
the length of $\mathsf{EQ}(C)$ is bounded by
$\mathsf{max}\\{4,2|\mathsf{VC}|\\}$, and thus,
$|\mathsf{EdgePairs}(\mathsf{EQ}(C))|\leq 2|\mathsf{VC}|$. In addition, by
Lemma 5.26, $\mathsf{DerCycTyp}(i,C)=\mathsf{CycTyp}$ is a cycle type.
Therefore, there exists $1\leq t\leq 2|\mathsf{VC}|$ such that
$\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{VerTyp},\mathsf{NeiSub},t)$. Thus,
$u$ contributes at least one to
$\displaystyle{\sum_{r=1}^{2{|\mathsf{VC}|}}\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{VerTyp},\mathsf{NeiSub},r)}}r\cdot
x_{\mathsf{CycTyp}}}$.

  2. 2.

$\mathsf{NeiSub}\in\widehat{\mathsf{N}}_{\mathsf{Graph}(\mathsf{CC}_{i})}(u)$.
By Definition 5.19,
$\mathsf{DerCycTyp}(i)=(\mathsf{CC}^{\prime}_{i},\mathsf{Alloc}_{G_{i}^{\prime}},\mathsf{NumOfCyc}_{i})$,
where (i) $\mathsf{CC}^{\prime}_{i}=E(G_{i}^{\prime})$, (ii)
$G^{\prime}_{i}=\overline{G}(\mathsf{Graph}(\mathsf{CC}_{i}))$ with an
isomorphism $\alpha_{i}:V(G_{i}^{\prime})\rightarrow
V(\mathsf{Graph}(\mathsf{CC}_{i}))$ and (iii) for every
$(u^{*}_{j},\mathsf{NeiSub})\in\mathsf{NeiOfInd}(G^{\prime}_{i})$,
$\mathsf{Alloc}_{G_{i}^{\prime}}((u^{*}_{j},\mathsf{NeiSub}))=\mathsf{DerVerTyp}(\alpha_{i}(u^{*}_{j}))$.
Let $j\in\mathbb{N}$ such that $\alpha_{i}(u^{*}_{j})=u$, so
$\mathsf{Alloc}_{G_{i}^{\prime}}((u^{*}_{j},\mathsf{NeiSub}))=\mathsf{DerVerTyp}(\alpha_{i}(u^{*}_{j}))=\mathsf{VerTyp}$.
Therefore, $u$ contributes at least one to
$|\\{(u^{*}_{t},\mathsf{NeiSub})\in\mathsf{NeiOfInd}(\mathsf{Graph}(\mathsf{CC}_{i}))\leavevmode\nobreak\
|\leavevmode\nobreak\ $
$\mathsf{Alloc}_{\mathsf{Graph}(\mathsf{CC}_{i})}((u^{*}_{t},\mathsf{NeiSub}))=\mathsf{VerTyp}\\}|$.
In addition, by Lemma 5.21, $\mathsf{DerRobTyp}(i)=\mathsf{RobTyp}$ is a robot
type. Now, since $\mathsf{Graph}(\mathsf{CC}_{i})$ is a
$\overline{G}$-submultigraph (see Definition 5.4),
$|V(\mathsf{Graph}(\mathsf{CC}_{i}))\cap u^{*}|\leq
2^{|\mathsf{N}_{G^{*}}({u^{*}})|}+|\mathsf{VC}|^{2}\leq
2^{|\mathsf{VC}|}+|\mathsf{VC}|^{2}$, so
$|\\{(u^{*}_{t},\mathsf{NeiSub})\in\mathsf{NeiOfInd}(\mathsf{Graph}(\mathsf{CC}_{i}))|\leq
2^{|\mathsf{VC}|}+|\mathsf{VC}|^{2}$. Therefore, there exists $1\leq t\leq
2^{|\mathsf{VC}|}+|\mathsf{VC}|^{2}$ such that
$\mathsf{RobTyp}\in\mathsf{RobTypS}(\mathsf{VerTyp},\mathsf{NeiSub},t)$. Thus,
$u$ contributes at least one to
$\displaystyle{\sum_{r=1}^{2^{|\mathsf{VC}|}+|\mathsf{VC}|^{2}}\sum_{{\mathsf{RobTyp}\in\mathsf{RobTypS}(\mathsf{VerTyp},\mathsf{NeiSub},r)}}r\cdot
x_{\mathsf{RobTyp}}}$.

Therefore, each $u\in V(G)\setminus\mathsf{VC}$ such that
$\mathsf{DerVerTyp}(u)=\mathsf{VerTyp}=(u^{*},\mathsf{NeiSubsets})$,
contributes at least one to

$\displaystyle{\sum_{j=1}^{2{|\mathsf{VC}|}}\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)}}j\cdot
x_{\mathsf{CycTyp}}+\sum_{j=1}^{2^{|\mathsf{VC}|}+|\mathsf{VC}|^{2}}}$
$\displaystyle{\sum_{{\mathsf{RobTyp}\in\mathsf{RobTypS}(\mathsf{VerTyp},\mathsf{NeiSub},j)}}j\cdot
x_{\mathsf{RobTyp}}}$.

Thus, since $\mathsf{RobExpToILP}(\mathsf{VerTyp})=|\\{u\in
V(G)\setminus\mathsf{VC}\leavevmode\nobreak\ |\leavevmode\nobreak\
\mathsf{DerVerTyp}(u)=\mathsf{VerTyp}\\}|$ and
$x_{\mathsf{VerTyp}}=\mathsf{RobExpToILP}(\mathsf{VerTyp})$, we get that
Equations 3 are satisfied.

######  Lemma 5.34.

Let $G$ be a connected graph, let $v_{\mathsf{init}}\in V(G)$, let
$\mathsf{VC}$ be a vertex cover of $G$ and let
$\widehat{E}_{1},\ldots,\widehat{E}_{k}$ such that conditions of Lemma 3.2
hold. For every $1\leq i\leq k$, let $(\mathsf{CC}_{i},{\cal C}_{i})$ be an
$\widehat{E}_{i}$-valid pair. Then, the values
$x_{z}=\mathsf{RobExpToILP}(z)$, for every
$z\in\mathsf{VerTypS}\cup\mathsf{RobTypS}\cup\mathsf{CycTypS}$, satisfy
inequalities 4–6 of $\mathsf{Reduction}(G,v_{\mathsf{init}},k,B)$.

######  Proof 5.35.

Let $\\{u,v\\}\in E$ such that $u,v\in\mathsf{VC}$. By Condition 3 of Lemma
3.2, $E(G)\subseteq\widehat{E}_{1}\cup\ldots\cup\widehat{E}_{k}$. So, there
exists $1\leq i\leq k$ such that $\\{u,v\\}\in\widehat{E}_{i}$. Since
$(\mathsf{CC}_{i},{\cal C}_{i})$ is an $\widehat{E}_{i}$-valid pair, by
Condition 6 of Definition 5.9, $\mathsf{CC}_{i}\cup\bigcup_{C\in{\cal
C}_{i}}E(C)=\widehat{E}_{i}$. So, at least one among the following two cases
holds:

  1. 1.

$\\{u,v\\}\in\mathsf{CC}_{i}$. By Definition 5.19,
$\mathsf{DerRobTyp}(i)=(\mathsf{CC}^{\prime}_{i},\mathsf{Alloc}_{G_{i}^{\prime}},\mathsf{NumOfCyc}_{i})$,
where $\mathsf{CC}^{\prime}_{i}=E(G_{i}^{\prime})$ and
$G^{\prime}_{i}=\overline{G}(\mathsf{Graph}(\mathsf{CC}_{i}))$. So,
$\\{u,v\\}\in\mathsf{CC}^{\prime}_{i}$. Now, by Lemma 5.21,
$\mathsf{DerRobTyp}(i)=\mathsf{RobTyp}$ is a robot type. Therefore,
$\mathsf{RobTyp}\in\mathsf{RobTypS}(\\{u,v\\})$, thus
$\displaystyle{\sum_{{\mathsf{RobTyp}\in\mathsf{RobTypS}(\\{u,v\\})}}x_{\mathsf{RobTyp}}\geq
1}$.

  2. 2.

There exists $C\in{\cal C}_{i}$ such that $\\{u,v\\}\in E(C)$. By Definition
5.24,
$\mathsf{DerCycTyp}(i,C)=(\mathsf{EQ}(C),\mathsf{EQ}(\mathsf{PaAlloc}_{i,C})$,
and observe that $\\{u,v\\}\in\mathsf{EQ}(C)$. In addition, by Lemma 5.26,
$\mathsf{DerCycTyp}(i,C)=\mathsf{CycTyp}$ is a cycle type. Therefore,
$\mathsf{CycTyp}\in\mathsf{CycTypS}(\\{u,v\\})$, so
$\displaystyle{\sum_{{\mathsf{CycTyp}\in\mathsf{CycTypS}(\\{u,v\\})}}x_{\mathsf{CycTyp}}\geq
1}$.

Either way, we get that