# On chromatic vertex stability of 3-chromatic graphs with maximum degree 4

Martin Knor1, Mirko Petruševski2, Riste Škrekovski3,4
1 Slovak University of Technology in Bratislava, Bratislava, Slovakia
2 University Ss Cyril and Methodius, MFS, 1000 Skopje, Macedonia
3 University of Ljubljana, FMF, 1000 Ljubljana, Slovenia
4 Faculty of Information Studies, 8000 Novo Mesto, Slovenia

###### Abstract

The (independent) chromatic vertex stability (${\rm ivs_{\chi}}(G)$) ${\rm
vs_{\chi}}(G)$ is the minimum size of (independent) set $S\subseteq V(G)$ such
that $\chi(G-S)=\chi(G)-1$. In this paper we construct infinitely many graphs
$G$ with $\Delta(G)=4$, $\chi(G)=3$, ${\rm ivs_{\chi}}(G)=3$ and ${\rm
vs_{\chi}}(G)=2$, which gives a partial negative answer to a problem posed in
[3].

##  1 Introduction

Let $G$ be a graph. Its edge stability number, $\rm{es}_{\chi}(G)$, is the
minimum number of edges whose deletion results in a graph $H$ with
$\chi(H)=\chi(G)-1$. Edge stability number was introduced in 1980 by Staton
[8], and rediscoverd in 2008 by Arumugam, Sahul Hamid and Muthukamatchi [4].
For recent results on this invariant see e.g. [1, 2, 6, 7].

General concept of stability number appeared in [5], but the first paper on
chromatic vertex stability number was written by Akbari, Beikmohammadi,
Klavžar and Movarraei in 2021, see [3]. The chromatic vertex stability ${\rm
vs_{\chi}}(G)$ of $G$ is the minimum number of vertices of $G$ such that their
deletion results in a graph $H$ with $\chi(H)=\chi(G)-1$. Analogously, the
independent chromatic vertex stability ${\rm ivs_{\chi}}(G)$ of $G$ is the
minimum number of independent vertices of $G$ such that their deletion results
in a graph $H$ with $\chi(H)=\chi(G)-1$. Obviously, ${\rm
vs_{\chi}}(G)\leq{\rm ivs_{\chi}}(G)$. The main result of [3] is the
following.

######  Theorem 1.

If $G$ is a graph with $\chi(G)\in\\{\Delta(G),\Delta(G)+1\\}$ then ${\rm
vs_{\chi}}(G)={\rm ivs_{\chi}}(G)$.

The authors showed that as soon as $\chi(G)\leq\frac{\Delta(G)+1}{2}$ the
equality ${\rm vs_{\chi}}(G)={\rm ivs_{\chi}}(G)$ need no longer be true.
Whether ${\rm vs_{\chi}}(G)={\rm ivs_{\chi}}(G)$ always holds if
$\frac{\Delta(G)}{2}+1\leq\chi(G)\leq\Delta(G)-1$ was left unanswered, so they
asked the following question (see Problem 3.2 in [3]).

######  Problem 2.

Is it true that if $G$ is a graph with $\chi(G)\geq\frac{\Delta(G)}{2}+1$,
then ${\rm vs_{\chi}}(G)={\rm ivs_{\chi}}(G)$?

In this paper we prove that Problem 2 answers in the negative for $\chi(G)=3$
and $\Delta(G)=4$. A simple ‘ladder-like’ counterexample on $9$ vertices is
depicted in Figure 1. Notice that the ladder part of the counterexample can be
of any length $4k$ for $k\geq 2$.

Figure 1: A graph $G$ with $\Delta(G)=4$ and $\chi(G)=3$. The blue independent
$3$-set realizes ${\rm ivs_{\chi}}(G)=3$ and the yellow $2$-set realizes ${\rm
vs_{\chi}}(G)=2$.

Our main result is the following.

######  Theorem 3.

For each $n\geq 9$ there are at least
$\max\\{1,2^{\lfloor\frac{n-11}{2}\rfloor}\\}$ planar graphs with $\chi(G)=3$,
$\Delta(G)=4$, ${\rm ivs_{\chi}}(G)=3$ and ${\rm vs_{\chi}}(G)=2$.

Observe that if $\chi(G)=3$ and $\Delta(G)=4$, then
$\chi(G)=\frac{\Delta(G)}{2}+1=\Delta(G)-1$. Hence, the bound on $\chi(G)$ in
Theorem 1 cannot be relaxed when $\chi(G)=3$.

##  2 Proofs

We start with a pair of simple observations followed by a couple of lemmas.

######  Observation 4.

For every graph $G$, ${\rm ivs_{\chi}}(G)$ equals the minimum size of a colour
class over all proper $\chi(G)$-colourings of $G$. Hence $|V(G)|\geq{\rm
ivs_{\chi}}(G)\cdot\chi(G)$.

###### Proof.

Let us first notice that there exists a proper $\chi(G)$-colouring of $G$ with
a colour class of size ${\rm ivs_{\chi}}(G)$. Indeed, take $S\subseteq V(G)$
to be an independent set of size $|S|={\rm ivs_{\chi}}(G)$ such that
$\chi(G-S)=\chi(G)-1$. Use a proper $(\chi(G)-1)$-colouring of $G-S$ and
assign to vertices of $S$ a new colour. So ${\rm ivs_{\chi}}(G)$ is not less
than the minimum size of a colour class over all proper $\chi(G)$-colourings
of $G$.

Contrarily, consider a proper $\chi(G)$-colouring of $G$ which minimizes the
size of a colour class, and let $S$ be such a minimum colour class. Then $S$
is an independent subset of $V(G)$ and $\chi(G-S)\leq\chi(G)-1$. In fact, we
must have equality here for otherwise $G$ would admit a proper
$(\chi(G)-1)$-colouring. So ${\rm ivs_{\chi}}(G)$ is also not more than the
minimum size of a colour class over all proper $\chi(G)$-colourings of $G$,
which proves our point.

The inequality $|V(G)|\geq{\rm ivs_{\chi}}(G)\cdot\chi(G)$ is now an immediate
consequence. ∎

######  Observation 5.

If $\Delta(G)\leq 2$ then ${\rm vs_{\chi}}(G)={\rm ivs_{\chi}}(G)$.

###### Proof.

We may assume that ${\rm vs_{\chi}}(G)\geq 2$. Indeed, if ${\rm
vs_{\chi}}(G)=1$ then obviously ${\rm ivs_{\chi}}(G)=1$ as well. We may also
assume that $G$ is connected. Then $G$ is either a path or an even cycle. In
either case ${\rm vs_{\chi}}(G)={\rm
ivs_{\chi}}(G)=\lfloor\frac{|V(G)|}{2}\rfloor$. ∎

As already mentioned, we are interested in finding graphs $G$ for which
$\chi(G)\geq\frac{\Delta(G)}{2}+1$ and ${\rm ivs_{\chi}}(G)>{\rm
vs_{\chi}}(G)$. Our first lemma establishes some implications for the order
and the considered stability parameters.

######  Lemma 6.

If ${\rm ivs_{\chi}}(G)>{\rm vs_{\chi}}(G)$ and
$\chi(G)\geq\frac{\Delta(G)}{2}+1$ then $|V(G)|\geq 9$, ${\rm
ivs_{\chi}}(G)\geq 3$, ${\rm vs_{\chi}}(G)\geq 2$ and $\chi(G)\geq 3$.
Moreover, if $|V(G)|=9$ then ${\rm ivs_{\chi}}(G)=3$, ${\rm vs_{\chi}}(G)=2$
and $\chi(G)=3$.

###### Proof.

Since ${\rm ivs_{\chi}}(G)>{\rm vs_{\chi}}(G)$, we must have ${\rm
vs_{\chi}}(G)\geq 2$ and consequently ${\rm ivs_{\chi}}(G)\geq 3$.

If $\chi(G)\leq 2$ then from $\chi(G)\geq\frac{\Delta(G)}{2}+1$ we get
$\Delta(G)\leq 2(\chi(G)-1)\leq 2$, which in view of Observation 5 contradicts
${\rm ivs_{\chi}}(G)>{\rm vs_{\chi}}(G)$. Hence $\chi(G)\geq 3$.

From the inequality stated in Observation 4, it follows that $|V(G)|\geq{\rm
ivs_{\chi}}(G)\cdot\chi(G)\geq 3\cdot 3$, that is, $|V(G)|\geq 9$. And if
$|V(G)|=9$ then $\chi(G)={\rm ivs_{\chi}}(G)=3$ and ${\rm vs_{\chi}}(G)=2$. ∎

Figure 2 depicts two graphs, respectively denoted by $G_{9}$ and $G_{10}$ in
regard to their orders. The former one can be obtained from the 1-skeleton of
a regular octagon by subdividing the edges of a triangle. It has
$\Delta(G_{9})=4$, $\chi(G_{9})={\rm ivs_{\chi}}(G_{9})=3$ and ${\rm
vs_{\chi}}(G_{9})=2$. Observe that $\chi(G_{9}-\\{x,y\\})=2$ if and only if
$\\{x,y\\}=\\{v_{i},v_{j}\\}$, where $1\leq i<j\leq 3$, and for an independent
set of vertices $\\{x,y,z\\}$ we have $\chi(G_{9}-\\{x,y,z\\})=2$ if and only
if $\\{x,y,z\\}=\\{u_{i},v_{i},w_{i}\\}$, where $1\leq i\leq 3$. The graph
$G_{10}$ is obtained from $G_{9}$ by adding the vertex $q$ and connecting it
to $w_{2}$ and $w_{3}$. It also has $\Delta(G_{10})=4$, $\chi(G_{10})={\rm
ivs_{\chi}}(G_{10})=3$ and ${\rm vs_{\chi}}(G_{10})=2$. Again
$\chi(G_{10}-\\{x,y\\})=2$ if and only if $\\{x,y\\}=\\{v_{i},v_{j}\\}$, where
$1\leq i<j\leq 3$, and for an independent set of vertices $\\{x,y,z\\}$ we
have $\chi(G_{10}-\\{x,y,z\\})=2$ if and only if
$\\{x,y,z\\}=\\{u_{i},v_{i},w_{i}\\}$ where $2\leq i\leq 3$.

Figure 2: The graph $G_{9}$ (left) and the graph $G_{10}$ (right).

Our second lemma concerns the case $\chi(G)={\rm ivs_{\chi}}(G)=3$ and ${\rm
vs_{\chi}}(G)=2$. Under the assumption $\chi(G)\geq\frac{\Delta(G)}{2}+1$ we
establish the maximum degree of $G$ and the vertex degrees of every $2$-set
which realizes ${\rm vs_{\chi}}(G)$.

######  Lemma 7.

Let $G$ be a graph with $\chi(G)={\rm ivs_{\chi}}(G)=3$, ${\rm
vs_{\chi}}(G)=2$ and $\chi(G)\geq\frac{\Delta(G)}{2}+1$. Then $\Delta(G)=4$
and for every $v_{1},v_{2}\in V(G)$ such that $\chi(G-\\{v_{1},v_{2}\\})=2$ we
have $\deg_{G}(v_{1})=\deg_{G}(v_{2})=4$.

###### Proof.

Let $G$ satisfy the assumptions of the lemma and let $v_{1},v_{2}\in V(G)$
such that $\chi(G-\\{v_{1},v_{2}\\})=2$. Then $\Delta(G)\leq 2(\chi(G)-1)=4$.
By way of contradiction, suppose that $\deg_{G}(v_{1})\leq 3$. Since ${\rm
ivs_{\chi}}(G)=3>2$, we have $v_{1}v_{2}\in E(G)$. Further, since
$\chi(G-v_{2})=3$, there must be an odd cycle in $G-v_{2}$; moreover, every
such cycle passes through $v_{1}$ as $G-\\{v_{1},v_{2}\\}$ is bipartite.
Consequently $\deg_{G}(v_{1})=3$.

Let $u_{1},u_{2}$ be neighbours of $v_{1}$ in $G-v_{2}$. Since every odd cycle
in $G-v_{2}$ passes through both $u_{1},u_{2}$, we conclude that
$G-\\{u_{i},v_{2}\\}$ is bipartite as well, $i\in\\{1,2\\}$. From ${\rm
ivs_{\chi}}(G)=3>2$ it follows that $u_{1}v_{2},u_{2}v_{2}\in E(G)$. Moreover,
$u_{1}u_{2}\notin E(G)$, for otherwise $v_{1},v_{2},u_{1},u_{2}$ induces
$K_{4}$, implying $\chi(G)\geq 4$.

Since ${\rm ivs_{\chi}}(G)\geq 3$, there must be an odd cycle in
$G-\\{u_{1},u_{2}\\}$. This cycle cannot pass through $v_{1}$ since
$\deg_{G-\\{u_{1},u_{2}\\}}(v_{1})=1$. If this cycle does not pass through
$v_{2}$ as well then it is in $G-\\{v_{1},v_{2}\\}$ which means that
$\chi(G-\\{v_{1},v_{2}\\})\geq 3$, a contradiction. Hence, there is an odd
cycle passing through $v_{2}$ in $G-\\{u_{1},u_{2},v_{1}\\}$, which means that
$\deg_{G}(v_{2})\geq 5$. This contradiction settles the lemma. ∎

A computer search shows that there are precisely $30$ graphs $G$ of order $9$
and having $\Delta(G)=4$, $\chi(G)=3$, ${\rm ivs_{\chi}}(G)=3$ and ${\rm
vs_{\chi}}(G)=2$. Several of them (including $G_{9}$) are planar and four are
obtained by adding an edge to another graph from the same collection.

For every $n\geq 9$ let $S_{n}$ be the set of graphs $G$ on $n$ vertices such
that $\Delta(G)=4$, $\chi(G)=3$, ${\rm ivs_{\chi}}(G)=3$ and ${\rm
vs_{\chi}}(G)=2$. Thus $G_{9}\in S_{9}$ and $G_{10}\in S_{10}$. By
${C_{\chi}}(G)$ we denote the set of vertices $x\in V(G)$ such that there is
$y\in V(G)$ for which $\chi(G-\\{x,y\\})=2$; note in passing that every such
$y$ is a neighbour of $x$. For example,
${C_{\chi}}(G_{9})={C_{\chi}}(G_{10})=\\{v_{1},v_{2},v_{3}\\}$. In view of our
next result, for every $n\geq 9$ there is a planar graph in $S_{n}$ which is
topologically equivalent to $G_{9}$ or $G_{10}$.

######  Proposition 8.

Let $G\in S_{n}$ and $e_{1},e_{2},\dots,e_{t}\in E(G)\backslash
E([{C_{\chi}}(G)])$, i.e., each $e_{i}$ has at most one endvertex in
${C_{\chi}}(G)$. Let $n_{1},n_{2},\dots,n_{t}$ be positive even integers. For
every $i$, $1\leq i\leq t$, subdivide $e_{i}$ with $n_{i}$ new vertices, and
denote the resulting graph by $H$. Then $\Delta(H)=4$, $\chi(H)=3$, ${\rm
ivs_{\chi}}(H)=3$ and ${\rm vs_{\chi}}(H)=2$. In other words, $H\in
S_{n+(n_{1}+\cdots+n_{t})}$.

###### Proof.

Obviously $\Delta(H)=\Delta(G)=4$. As $\chi(G)=3$, the graph $G$ has an odd
cycle. Since to any edge of this cycle we added an even number (possibly zero)
of vertices, $H$ also has an odd cycle; thus $\chi(H)\geq 3$. Moreover, if
$S\subseteq V(G)$ is such that $G-S$ is bipartite then $H-S$ is bipartite as
well. Hence, $\chi(H)=3$, ${\rm ivs_{\chi}}(H)\leq 3$ and ${\rm
vs_{\chi}}(H)\leq 2$.

If there is $v\in V(H)$ such that $\chi(H-v)=2$, then $v\notin V(G)$. So $v$
is obtained by subdividing an edge, say $xy$, of $G$. However, as $H-v$ is
bipartite, both $G-x$ and $G-y$ are bipartite, a contradiction. Hence, ${\rm
vs_{\chi}}(H)=2$.

Finally, let us show that ${\rm ivs_{\chi}}(H)=3$. Supposing the opposite,
there are $u,v\in V(H)$ such that $\chi(H-\\{u,v\\})=2$ and $uv\notin E(H)$.
It cannot be that both $u$ and $v$ are in $V(G)$, because we did not subdivide
edges connecting vertices of ${C_{\chi}}(G)$. So we may assume that $v$ is
obtained by subdividing an edge $xy$ of $G$, where $y\notin{C_{\chi}}(G)$.
Since $H-\\{u,v\\}$ is bipartite, so is $H-\\{u,y\\}$. But then $u$ cannot be
a vertex of $G$ as well. Hence, $u$ is obtained by subdividing an edge $wz$ of
$G$. As $H-\\{u,y\\}$ is bipartite, so is $H-\\{z,y\\}$. However, this
contradicts the fact that $y\notin{C_{\chi}}(G)$. ∎

From Proposition 8 we deduce that $S_{n}\neq\emptyset$ for every $n\geq 9$.
Indeed, if $n$ is odd then take $G_{9}$, subdivide the edge $u_{2}w_{1}$ with
$n-9$ new vertices and denote the resulting graph by $G_{n}$. Analogously if
$n$ is even then take $G_{10}$, subdivide the edge $u_{2}w_{1}$ with $n-10$
new vertices and denote the resulting graph by $G_{n}$. Then $G_{n}$ is a
connected planar graph and $G_{n}\in S_{n}$, by Proposition 8.

Our next result shows that $S_{n}$ contains exponentially many planar graphs.
Its proof relies on the following construction. We pair up several new
vertices of $H$, i.e., vertices belonging in $V(H)\backslash V(G)$ to obtain a
graph $F$ such that both $F-\\{v_{1},v_{2}\\}$ and $F-\\{u_{1},u_{2},u_{3}\\}$
are bipartite. Then $F\in S_{n^{\prime}}$ for some $n^{\prime}$.

######  Theorem 9.

For each $n\geq 11$ there are at least $2^{\lfloor\frac{n-11}{2}\rfloor}$
2-connected planar graphs in $S_{n}$.

###### Proof.

In view of $G_{11}$ and $G_{12}$, we assume $n\geq 13$. Take $G_{n}$ and
relabel the vertices of the $u_{2}-u_{3}$ path that passes through $w_{1}$ by
$u_{2}=a_{0},a_{1},a_{2},\dots,a_{\ell-1}=w_{1},a_{\ell}=u_{3}$; here
$\ell=n-7$ if $n$ is odd and $\ell=n-8$ if $n$ is even. Let
$E_{n}=\\{a_{1}a_{\ell-2},a_{2}a_{\ell-3},\dots,a_{\ell/2-2}a_{\ell/2+1}\\}$.
For every $E^{\prime}\subseteq E_{n}$, denote by $H_{n,E^{\prime}}$ the graph
obtained from $G_{n}$ by adding the edges of $E^{\prime}$. Obviously
$H_{n,E^{\prime}}$ is planar, $\Delta(H_{n,E^{\prime}})=4$ and
$\chi(H_{n,E^{\prime}})=3$. Moreover, $H_{n,E^{\prime}}-\\{x,y\\}$ is
bipartite if $\\{x,y\\}=\\{v_{i},v_{j}\\}$ where $1\leq i<j\leq 3$, which
implies that ${\rm vs_{\chi}}(H_{n,E^{\prime}})=2$. Also,
$H_{n,E^{\prime}}-\\{u_{2},v_{2},w_{2}\\}$ is bipartite which gives ${\rm
ivs_{\chi}}(H_{n,E^{\prime}})\leq 3$. On the other hand, since $G_{n}$ is a
subgraph of $H_{n,E^{\prime}}$ and ${\rm ivs_{\chi}}(G_{n})=3$, we have ${\rm
ivs_{\chi}}(H_{n,E^{\prime}})=3$ as well. Thus $H_{n,E^{\prime}}\in S_{n}$.

Figure 3: The graph $H_{18,E_{18}}$.

Let $E^{\prime},E^{*}\subseteq E_{n}$, where $E^{\prime}\neq E^{*}$. We show
that the graphs $H_{n,E^{\prime}}$ and $H_{n,E^{*}}$ are not isomorphic. This
is obvious if $|E^{\prime}|\neq|E^{*}|$. So assume that
$|E^{\prime}|=|E^{*}|\geq 1$. We show that ${\rm Aut}(H_{n,E^{\prime}})$, the
group of automorphisms of $H_{n,E^{\prime}}$, (and also ${\rm
Aut}(H_{n,E^{*}})$) is trivial. That is, every automorphism of
$H_{n,E^{\prime}}$ fixes all the vertices of $H_{n,E^{\prime}}$.

There are exactly $6$ vertices of degree $4$ in $H_{n,E^{\prime}}$, namely
$u_{1},u_{2},u_{3},v_{1},v_{2},v_{3}$. Since each of $u_{1},u_{2},u_{3}$ is in
only one triangle in $H_{n,E^{\prime}}$ whereas each of $v_{1},v_{2},v_{3}$ is
in three such triangles, every automorphism must preserve the sets
$\\{u_{1},u_{2},u_{3}\\}$ and $\\{v_{1},v_{2},v_{3}\\}$. The vertices $u_{1}$
and $u_{2}$ are both adjacent to a vertex of
$H_{n,E^{\prime}}-\\{v_{1},v_{2},v_{3}\\}$. Also the vertices $u_{1}$ and
$u_{3}$ are both adjacent to a vertex of
$H_{n,E^{\prime}}-\\{v_{1},v_{2},v_{3}\\}$. But $u_{2}$ and $u_{3}$ are not
adjacent to a vertex of $H_{n,E^{\prime}}-\\{v_{1},v_{2},v_{3}\\}$, because
$n\geq 13$. Consequently, every automorphism of $H_{n,E^{\prime}}$ fixes
$u_{1}$.

In view of $a_{\ell-1}(=w_{1})$, the vertex $u_{3}$ has a neighbour of degree
$2$ which is not connected to $u_{1}$. If $u_{2}$ does not have such a
neighbour, then every automorphism of $H_{n,E^{\prime}}$ fixes also $u_{2}$
and $u_{3}$. So assume that also $u_{2}$ has a neighbour of degree $2$ which
is not connected to $u_{1}$. Now start at $u_{2}$, proceed with the above
mentioned neighbour of $u_{2}$ and construct a longest path $P_{2}$, interior
vertices of which have all degree 2. Analogously start at $u_{3}$, proceed
with the above mentioned neighbour of $u_{3}$ and construct a longest path
$P_{3}$, interior vertices of which have all degree 2. Finally, let $i$ be the
smallest index such that $a_{i}a_{\ell-1-i}\in E^{\prime}$. Then $P_{2}$ has
length $i$ while $P_{3}$ has length $i+1$. Hence, every automorphism of
$H_{n,E^{\prime}}$ must fix also $u_{2}$ and $u_{3}$. Consequently, every
automorphism of $H_{n,E^{\prime}}$ fixes all the vertices of
$H_{n,E^{\prime}}$, and so $H_{n,E^{\prime}}$ and $H_{n,E^{*}}$ are not
isomorphic graphs.

Since $E_{n}$ has
$\frac{\ell}{2}-2=\lfloor\frac{n-7}{2}\rfloor-2=\lfloor\frac{n-11}{2}\rfloor$
edges and every subset gives different graph, there are exactly
$2^{\lfloor\frac{n-11}{2}\rfloor}$ nonisomorphic graphs $H_{n,E^{\prime}}$. ∎

We conclude the paper by presenting another, more general, construction of
graphs $G$ with $\Delta(G)=4$, $\chi(G)=3$, ${\rm ivs_{\chi}}(G)=3$ and ${\rm
vs_{\chi}}(G)=2$. Let $H$ be a bipartite graph with $\Delta(H)\leq 4$ such
that there exists a cycle $C_{2k}\subseteq H$ with $k\geq 3$ and a pair
$a,b\in V(C_{2k})$ of non-adjacent vertices in $H$ on odd distance
$d_{H}(a,b)$ and having $\deg_{H}(a)=\deg_{H}(b)=2$. Take the union of $H$
with a disjoint triangle $K_{3}=uvw$ and add the edges $av,bv,aw,bw$. Denote
the resulting graph by $G$ (see Figure 4).

Figure 4: The graph $G$ if $H=C_{6}$.

######  Proposition 10.

If $H$ is of order $m$ then $G\in S_{m+3}$. Moreover, if $H$ is 2-connected
(resp. planar) then $G$ has the same feature.

###### Proof.

Clearly, the order of $G$ is $m+3$. As $\Delta(H)\leq 4$ and
$\deg_{H}(a)=\deg_{H}(b)=2$ we have $\Delta(G)=4$. In view of the triangle
$uvw$, the graph $G$ is not bipartite. In order to show $\chi(G)=3$, note that
$G-\\{u,v,w\\}$ is bipartite. Take a proper $2$-colouring $\varphi$ of
$G-\\{u,v,w\\}$ with colours $1$ and $3$, say $\varphi(a)=1$ and
$\varphi(b)=3$ (here we use that $d(a,b)$ is odd). Now change the colour of
$b$ to $1$ and the colour of every $c\in N_{G-\\{u,v,w\\}}(b)$ to $2$. Note
that by assigning the colour $1$ to $u$, the colour $2$ to $v$ and the colour
$3$ to $w$ we obtain a proper $3$-colouring of $G$.

Let us show next that ${\rm ivs_{\chi}}(G)=3$. Since $G-\\{a,b,u\\}$ is
bipartite, we have ${\rm ivs_{\chi}}(G)\leq 3$. Suppose there are non-adjacent
vertices $x,y$ such that $G-\\{x,y\\}$ is bipartite. In view of the triangle
$uvw$, the intersection $\\{x,y\\}\cap\\{u,v,w\\}$ is a singleton. We argue
that this intersection is not the vertex $u$ due to the triangles $avw$ and
$bvw$. Let $P$ and $Q$ be the two $a-b$ paths in $C_{2k}$, and recall that
both these paths are of odd lengths. Consequently, each of the cycles
$C^{\prime}=P\cup avb$, $C^{\prime\prime}=P\cup awb$,
$C^{\prime\prime\prime}=Q\cup avb$, and $C^{\prime\prime\prime\prime}=Q\cup
awb$ is odd. Hence $\\{x,y\\}\cap\\{v,w\\}\neq\emptyset$, which further
implies that $\\{x,y\\}\cap\\{a,b\\}=\emptyset$. However, then at least one of
the cycles
$C^{\prime},C^{\prime\prime},C^{\prime\prime\prime},C^{\prime\prime\prime\prime}$
appears in $G-\\{x,y\\}$. The obtained contradiction shows ${\rm
ivs_{\chi}}(G)=3$.

Finally, we prove that ${\rm vs_{\chi}}(G)=2$. Clearly ${\rm vs_{\chi}}(G)\leq
2$, because $G-\\{v,w\\}$ is bipartite. And since ${\rm vs_{\chi}}(G)=1$
implies ${\rm ivs_{\chi}}(G)=1$, we have ${\rm vs_{\chi}}(G)=2$. ∎

Note in passing that the order of the bound $|S_{n}|\geq
2^{\lfloor\frac{n-11}{2}\rfloor}$ obtained in Theorem 9 is far from
(asymptotically) optimal. Propositions 8 and 10 enable one to construct
connected planar graphs within $S_{n}$ with considerable ease. However,
establishing a more precise asymptotic estimate of $|S_{n}|$ was not the focus
of this short article; instead, the aim was simply to point out to the
existence of exponentially many graphs in $S_{n}$.

Acknowledgments. The first author acknowledges partial support by Slovak
research grants VEGA 1/0567/22, VEGA 1/0206/20, APVV–19–0308, APVV–17–0428.
All authors acknowledge partial support of the Slovenian research agency ARRS
program P1-0383 and ARRS project J1-3002.

## References

  * [1] S. Akbari, A. Beikmohammadi, B. Brešar, T. Dravec, M. Mahdi Habibollahi, N. Movarraei, On the chromatic edge stability index of graphs, arXiv:2018.10657 [math.CO]; also European J. Combin., to appear.
  * [2] S. Akbari, S. Klavžar, N. Movarraei, M. Nahvi, Nordhaus-Gaddum and other bounds for the chromatic edge-stability number, European J. Combin. 84 (2020), 103042, 8pp.
  * [3] S. Akbari, A. Beikmohammadi, S. Klavžar, N. Movarraei, On the chromatic vertex stability number of graphs, European J. Combin. 102 (2022), 103504, 10pp.
  * [4] S. Arumugam, I. Sahul Hamid, A. Muthukamatchi, Independent domination and graph colorinds, Discrete Mathematics, 195-203, Ramanujan Math. Soc. Lect. Notes Ser., 7, Ramanujan Math. Soc., Mysore, 2008.
  * [5] D. Bauer, F. Harary, J. Nieminen, C.L. Suffel, Domination alteration sets in graphs, Discrete Math. 47 (1993), 153–161.
  * [6] B. Brešar, S. Klavžar, N. Movarraei, Critical graphs for the chromatic edge-stability number, Discrete Math. 343 (2020), 111845, 7 pp.
  * [7] A. Kemnitz, M. Marangio, N. Movarraei, On the chromatic edge stability number of graphs, Graphs & Combin. 34 (2018), 1539–1551.
  * [8] W. Staton, Edge deletions and the chromatic number, Ars Combin. 10 (1990), 103–106.


# Virtual Network Embedding
without Explicit Virtual Network Specification

Jiangnan Cheng, Yingjie Bi, and Ao Tang  School of Electrical and Computer
Engineering, Cornell University
Ithaca, NY, USA
{jc3377, yb236<EMAIL_ADDRESS>
###### Abstract

Network virtualization enables Internet service providers to run multiple
heterogeneous and dedicated network architectures for different customers on a
shared substrate. In existing works on virtual network embedding (VNE), each
customer formulates a virtual network request (VNR) where a virtual network
(VN) is required. Motivated by a concrete example where VN is not a proper VNR
formulation to reflect the traffic demand of a customer, we propose a new VNR
formulation described by the traffic demand between several access node pairs
to complement the existing VNR formulation. Moreover, three different groups
of VNE variants are systematically examined. Simulations demonstrate that
shared channel embedding, as a new embedding variant under the proposed VNR
formulation, improves the acceptance rate and reduces cost and link utility
compared to traditional independent channel embedding.

###### Index Terms:

Network virtualization; Virtual network embedding; Traffic demand.

##  I Introduction

The emergence of various new Internet applications demands a flexible and
fast-moving network infrastructure that can handle increasingly larger range
of traffic dynamics, satisfy the diverse real-time characteristics and rapidly
deliver novel network service to customers. On the other hand, technology
development at the side of Internet service providers (ISPs) usually has a
slow pace, with long verification phase and dedicated hardware to guarantee
reliance and stability [1, 2]. To address this challenge, network
virtualization [3] is proposed to move network resources from dedicated
hardware to virtualized overlays, making it possible for ISPs to develop
technologies in fast cycle and run multiple heterogeneous and dedicated
network architectures for different customers on a shared substrate in the
meantime.

In existing works on network virtualization [4, 5, 6, 7, 8, 9, 10, 11, 12,
13], each customer formulates its traffic demand as a virtual network (VN)
with a given topology and link capacities. The request of each customer is
referred to as virtual network request (VNR). ISP therefore considers a
virtual network embedding (VNE) problem which allocates a subset of the shared
substrate network (SN) to a VN. When the SN can no longer support a VN, a fail
signal should be returned to the customer.

Figure 1: A motivating example which illustrates the limitation of specifying
VN in a VNR. VNR 1 cannot be embedded on SN 2, because each node pair can send
traffic with a throughput of 150 units simultaneously in VNR 1 but not in SN
2; VNR 2 cannot be embedded on SN 1, because node A and D are connected in VNR
2 but not in SN 1. Node $e$ and $f$ in VNR 2 are virtual nodes and can be
mapped to arbitrary SN nodes.

Obviously, the most economical way to formulate VNR is to specify a minimum VN
which has enough link capacities to satisfy a customer’s traffic demand.
However, there are maybe more than one economical VNR formulations and each
has its own specific limitation. For example, in Fig. 1, VNR 1 and VNR 2 are
two economical VNR formulations for a customer whose traffic demand for either
access node pair (A,C) or (B,D) is no more than 150 units, and joint traffic
demand for these two node pairs is no more than 200 units. Intuitively, VNR 2
is more economical than VNR 1 since the former one characterizes the joint
traffic demand through a VN link (e,f) while the latter one does not. As a
result, VNR 2 can be embedded on SN 2 while VNR 1 cannot. However, as a
sacrifice, VNR 2 has to have an unnecessarily connection of node pair (A, D),
preventing it to be embedded on SN 1, which on the other hand admits VNR 1.
Hence, specifying VN in a VNR may not be a proper way to reflect the
customer’s traffic demand in some cases.

Therefore, in this paper, we propose a VNR formulation which directly
characterizes the customer’s traffic demand for a group of access node pairs,
without specifying a particular virtual network. Moreover, under the new VNR
formulation, we are able to consider three different groups of VNE variants,
including single-path vs multi-path, channel vs shared channel, and oblivious
routing vs adaptive routing (both belong to shared channel). Among them,
independent channel embedding can be reduced to existing VNE problems in
previous works [5, 6, 7, 8, 9, 10, 11, 12, 13]. Starting from the well-known
approaches for independent channel embedding, we propose new algorithms to
address shared channel embedding.

The rest of the paper is organized as follows. In Section II, we formulate the
basic problem of VNE, and then discuss three different groups of VNE variants.
In Section III and Section IV, we present algorithms for single-path embedding
and multi-path embedding, respectively. The performances of different
embedding algorithms are compared in Section V. Section VI discusses the
scenarios where node constraints and delay constraints are considered and link
cost is a piecewise linear or quadratic function of link bandwidth, and
Section VII concludes the paper.

##  II Problem Formulation

In this section, we first describe the basic VNE problem where VNR directly
characterizes the customer’s traffic demand. We then introduce three different
groups of VNE variants.

###  II-A Basic VNE Problem

In most VNE researches, each virtual node is allowed to be mapped to different
real nodes of SN, and therefore corresponding VNE is decomposed into two
phases: node mapping and link mapping. However, here we only consider the most
basic VNE problem where each node appeared in VNR are real nodes of SN. This
is equivalent to the scenario where virtual node locations are predetermined,
and we adopt this configuration since our main focus is formulate the joint
traffic demand constraints in the VNE, which only modifies the link bandwidth
constraints and thus mainly affects link mapping. The discussion of node
constraints, as an independent topic, is postponed to Section VI.

SN. Suppose the SN is represented by a weighted undirected graph
$G^{s}=(V^{s},E^{s})$, where $V^{s}$ and $E^{s}$ denote the set of nodes and
links, respectively. The link that connects node $i$ and $j$ (both $\in
V^{s}$) is denoted by a two-field tuple $(i,j)$. The available bandwidth and
unit price of each link $e^{s}\in E^{s}$ are denoted by $c^{s}(e^{s})$ and
$p^{s}(e^{s})$, respectively.

VNR. Each VNR requires an SN subset that has the ability to deliver traffic
between $N$ access node pairs given by node pair vector
$\mathbf{e}^{v}=((s_{1},t_{1}),(s_{2},t_{2}),\cdots,(s_{N},t_{N}))^{\top}$,
where $s_{n},t_{n}\in V^{s}$, $\forall n\in\\{1,2,\cdots,N\\}$. The $n$-th
element of $\mathbf{e}^{v}$ is denoted by $\mathbf{e}^{v}(n)$. The associated
traffic demand of $\mathbf{e}^{v}$ is denoted by traffic demand vector
$\mathbf{d}^{v}\in\mathbb{R}^{N\times 1}$, the $n$-th element of whom, denoted
by $\mathbf{d}^{v}(n)$, represents the traffic demand for $\mathbf{e}^{v}(n)$.
Suppose the upper bound of $\mathbf{d}^{v}$ is described by matrix inequality
$\mathbf{A}^{v}\mathbf{d}^{v}\leq\mathbf{b}^{v}$, where
$\mathbf{A}^{v}\in\mathbb{R}^{M^{v}\times N}_{\geq 0}$ and
$\mathbf{b}^{v}\in\mathbb{R}^{M^{v}\times 1}_{+}$; and the lower bound of
$\mathbf{d}^{v}$ is described by $\mathbf{d}^{v}\geq\mathbf{0}$. For
convenience we denote
$\\{\mathbf{d}^{v}|\mathbf{A}^{v}\mathbf{d}^{v}\leq\mathbf{b}^{v},\mathbf{d}^{v}\geq\mathbf{0}\\}$,
the feasible region of $\mathbf{d}^{v}$ with respect to this VNR, by $D^{v}$;
and we also define
$\mathbf{d}^{v}_{\text{max}}(n)=\max\\{\mathbf{d}^{v}(n)|\mathbf{d}^{v}\in
D^{v}\\}$, which represents the maximum possible traffic demand for
$\mathbf{e}^{v}(n)$ with respect to this VNR. The VNR can therefore be denoted
by a three-field tuple $R^{v}=(\mathbf{e}^{v},\mathbf{A}^{v},\mathbf{b}^{v})$.

The key advantage of such VNR formulation is its ability to properly
characterize the joint traffic demand upper bounds. For example, the VNR
described in Section I can be formulated as

$\displaystyle\mathbf{e}^{v}$
$\displaystyle=((\text{A},\text{C}),(\text{B},\text{D}))^{\top},$ (1)
$\displaystyle\mathbf{A}^{v}$ $\displaystyle=\begin{bmatrix}1&0&1\\\
0&1&1\end{bmatrix}^{\top},$ (2) $\displaystyle\mathbf{b}^{v}$
$\displaystyle=[150,150,200]^{\top}.$ (3)

VNE. For a given VNR $R^{v}$, VNE allocates a subset of SN that can satisfy
any valid traffic demand of $R^{v}$ (a fail signal is returned if there’s no
feasible allocation). The topology of the subset is denoted by
$G^{v}=(V^{v},E^{v})$, and the allocated bandwidth for each link $e^{v}\in
E^{v}$ is $c^{v}(e^{v})$. For convenience of computation, in the rest of the
paper, we let $V^{v}=V^{s}$ and $E^{v}=E^{s}$, and allow $c^{v}(e^{s})$ to be
zero for some link $e^{s}\in E^{s}$.

Objective. The objective of VNE is to find the bandwidth allocation $c^{v}$
that minimizes the cost:

$\displaystyle\min_{c^{v}(e^{s})}\quad\sum_{e^{s}\in
E^{s}}p^{s}(e^{s})c^{v}(e^{s}).$ (4)

###  II-B VNE Variants

(a) SN 3 (b) Single-path, independent channel (c) Single-path, oblivious
routing (d) Single-path, adaptive routing

(e) SN 4 (f) Multi-path, independent channel (g) Multi-path, oblivious routing
(h) Multi-path, adaptive routing

Figure 2: VNE with different requirements

VNE can have different variants that impose additional constraints on the
allocation. In this paper, we consider three groups of VNE variants as
follows, which together can form six different embedding settings.

Single-path VS Multi-path. Single-path embedding requires the traffic of each
node pair to be routed on only one path, while for multi-path embedding the
traffic of each node pair can be routed on multiple paths simultaneously.
Multi-path embedding is more flexible, but it can lead to out-of-order
delivery problem of data packets [5].

Independent Channel VS Shared Channel. In independent channel embedding, an
independent channel (either single-path or multi-path) with end-to-end
bandwidth $\mathbf{d}^{v}_{\text{max}}(n)$ has to be offered to node pair $n$,
$\forall n$. So in VNR, $\mathbf{A}^{v}$ and $\mathbf{b}^{v}$ can be
equivalently replaced by $I_{n}$ (i.e., $n\times n$ identity matrix) and
$\mathbf{d}^{v}_{\text{max}}$, respectively. Hence independent channel
embedding can be reduced to those VNE problems in previous works [5, 6, 7, 8,
9, 10, 11, 12, 13] by constructing a VN where link $\mathbf{e}^{v}(n)$ has
bandwidth $\mathbf{d}^{v}_{\text{max}}(n)$, $\forall n$. On the other hand, in
shared channel embedding, different node pairs are allowed to share the
bandwidth of a common link, which generally results in a cheaper allocation by
considering the joint traffic demand upper bounds.

Oblivious Routing VS Adaptive Routing. There are two different routing
strategies in shared channel embedding: oblivious routing and adaptive routing
[14, 15]. In oblivious routing, the traffic between a node pair is routed on
one or more predefined paths with predefined path splitting ratios. On the
other hand, in adaptive routing, the paths and the associated path splitting
ratios for the traffic between a node pair are dynamically adjusted according
to real-time network congestion. Adaptive routing generally results in a
cheaper allocation by offering more flexibility, yet the performance is
affected by routing speed and complexity [15], so it may not be able to
accommodate a drastically changing traffic demand.

Two examples that demonstrate the differences of VNE variants ares shown in
Fig. 2. In these two examples, we consider the same VNR described in Equation
(1)-(3).

In the first example, we consider single-path embedding. Fig. 2(a) shows the
SN topology. Fig. 2(b), Fig. 2(c) and Fig. 2(d) show feasible $G^{v}$ examples
for independent channel, oblivious routing and adaptive routing embedding,
respectively. It is obvious that the $G^{v}$’s in Fig. 2(b) and Fig. 2(c) can
satisfy any valid traffic demand in their corresponding ways. And in Fig.
2(d), we always route the smaller and larger one among $\mathbf{d}^{v}(1)$ and
$\mathbf{d}^{v}(2)$ on the upper and lower link between E and F, respectively.
When the smaller and larger one among $\mathbf{d}^{v}(1)$ and
$\mathbf{d}^{v}(2)$ exchange, the path for each node pair will switch with
each other, but remain to be a single path.

In the second example, we consider multi-path embedding. Fig. 2(e) shows the
SN topology. Fig. 2(f), Fig. 2(g) and Fig. 2(h) show feasible $G^{v}$ examples
for independent channel, oblivious routing and adaptive routing embedding,
respectively. It is obvious that the $G^{v}$’s in Fig. 2(f) and Fig. 2(g) can
satisfy any valid traffic demand in their corresponding ways. And in Fig.
2(h), for each node pair we route the its traffic on the link that directly
connects it first. When the amount of its traffic is larger than 100 units,
the exceeding part is routed through the other two nodes.

Since single-path adaptive routing has the problem of shifting paths back and
forth under small disturbance, we don’t consider it in the following sections.

##  III Single-Path VNE Algorithm

Single-path independent channel (SPIC) embedding problem can be reduced to
Unsplittable Flow Problem (UFP), which is NP-hard [16]. Since independent
channel embedding can be viewed as a special case of shared channel embedding
with $\mathbf{A}^{v}=I_{n}$, single-path oblivious routing (SPOR) embedding
problem is also NP-hard. Therefore, approximation approaches are generally
adopted to solve single-path embedding problems. In this section, we present
the approximation algorithms for solving SPIC and SPOR embedding problem in
Section III-A and III-B, respectively.

###  III-A Single-path Independent Channel (SPIC)

Algorithm 1 SPIC algorithm

1: Initialize $c^{v}(e^{s})=0$, $\forall e^{s}\in E^{s}$

2: Compute $\mathbf{d}^{v}_{\text{max}}$ through LP

3: for each $n\in\\{1,2,\cdots,N\\}$ do

4: Search the $K$-least cost paths on the SN between node pair
$\mathbf{e}^{v}(n)$

5: for $k\in\\{1,2,\cdots,K\\}$ do

6: for each link $e^{s}$ along path $k$ do

7: Assume node pair $\mathbf{e}^{v}(n)$ uses path $k$, and compute the target
bandwidth allocation for link $e^{s}$
$\displaystyle\hat{c}^{v}(e^{s}):=c^{v}(e^{s})+\mathbf{d}^{v}_{\text{max}}(n)$
(5)

8: If $\hat{c}^{v}(e^{s})>c^{s}(e^{s})$, break

9: end for

10: If $\hat{c}^{v}(e^{s})\leq c^{s}(e^{s})$ for each link $e^{s}$ along path
$k$, update $c^{v}(e^{s})\leftarrow\hat{c}^{v}(e^{s})$, set path $k$ as the
path for node pair $\mathbf{e}^{v}(n)$, and break; or else continue

11: end for

12: If no path is set for node pair $\mathbf{e}^{v}(n)$, return fail signal

13: end for

14: Embedding succeeds, return the allocation $c^{v}$

The algorithm for SPIC embedding is shown in Algorithm 1, which was proposed
in [5]. In line 1, we first initialize $c^{v}(e^{s})=0$, $\forall e^{s}\in
E^{s}$. In line 2, we then compute $\mathbf{d}^{v}_{\text{max}}$. This can be
done by solving $N$ linear programming (LP) problems, which takes polynomial
time. Next, in line 3-13, for each $n\in\\{1,2,\cdots,N\\}$, we search the
$K$-least unit cost paths on the SN between node pair $\mathbf{e}^{v}(n)$ for
a fixed $K$, which can be done in $O(|E^{v}|+|V^{v}|\log|V^{v}|+K)$ time [17].
For each potential path $k$, we assume it is used by node pair
$\mathbf{e}^{v}(n)$ and check whether we can allocate enough bandwidths for
all the links along it. For each link $e^{s}$ along path $k$, its target
bandwidth allocation, denoted by $\hat{c}^{v}(e^{s})$, is given by Equation
(5). Once we have $\hat{c}^{v}(e^{s})\leq c^{s}(e^{s})$ for each link $e^{s}$
along path $k$, we set path $k$ as the path for pair $\mathbf{e}^{v}(n)$. If
no path is set, a fail signal indicating the failure of VNE should be
returned. In the end, in line 14, if for each node pair we successfully set a
path, the embedding succeeds and the resulted allocation $c^{v}$ is returned.

###  III-B Single-path Oblivious Routing (SPOR)

Our algorithm for SPOR embedding differs from Algorithm 1 by replacing
Equation (5) with

$\displaystyle\hat{c}^{v}(e^{s}):=\begin{bmatrix}\underset{\mathbf{d}^{v}}{\text{max}}\quad&\underset{n^{\prime}\leq
n:\;\text{pair }n^{\prime}\text{ uses
}e^{s}}{\sum}\mathbf{d}^{v}(n^{\prime})\\\
s.t.\quad&\mathbf{A}^{v}\mathbf{d}^{v}\leq\mathbf{b}^{v},\mathbf{d}^{v}\geq\mathbf{0}\end{bmatrix}$
(6)

and removing line 2 of Algorithm 1. Equation (6) dictates that the target
bandwidth allocation $\hat{c}^{v}(e^{s})$ should be the maximum of the sum of
$\mathbf{d}^{v}(n^{\prime})$’s, where $n^{\prime}$ can be the index of any
node pair that uses $e^{s}$ to deliver traffic, i.e., $e^{s}$ is on its path.
Such $\hat{c}^{v}(e^{s})$ can be computed through LP. It is no larger than
$c^{v}(e^{s})+\mathbf{d}^{v}_{\text{max}}(n)$ and can be potentially smaller,
because node pair $\mathbf{e}^{v}(n)$ may share $e^{s}$ with other node pairs
and they may have a joint traffic demand upper bound smaller than the sum of
their individual traffic demand upper bounds. Therefore, our SPOR algorithm
generally outperforms Algorithm 1.

##  IV Multi-Path VNE Algorithm

Multi-path independent channel embedding (MPIC) problem can be reduced to
Multi-commodity Flow Problem (MFP) [18], which is solvable in polynomial time.
On the other hand, multi-path shared channel embedding problem may not
necessarily be polynomial. In this paper, we find a polynomial time algorithm
to solve multi-path oblivious routing (MPOR) embedding problem, while the
complexity of multi-path adaptive routing (MPAR) embedding problem remains
unclear.

In this section, we present the algorithms for solving MPIC, MPOR and MPAR
embedding problem in Section IV-A, IV-B and IV-C, respectively.

###  IV-A Multi-path Independent Channel (MPIC)

MPIC embedding problem can be reduced to MFP and it is solvable in polynomial
time. Similar to SPIC embedding in Section III-A, we first compute
$\mathbf{d}^{v}_{\text{max}}$ in polynomial time. Next, $\forall
n\in\\{1,2,\cdots,N\\},\forall e^{s}\in E^{s}$, we define two flow variables
$f^{v}_{n}(e^{s}_{+})$ and $f^{v}_{n}(e^{s}_{-})$, which correspond to the
portion of $\mathbf{d}^{v}(n)$ send on edge $e^{s}$ in two different
directions. Then we can formulate the corresponding MFP in the form of LP with
objective function in Equation (4) and following constraints:

1) Flow conservation

$\displaystyle\forall i\in V^{s},\forall n\in\\{1,2,\cdots,N\\}:$
$\displaystyle\quad\sum_{e^{s}:\exists j\text{ s.t.
}e^{s}=(i,j)}f^{v}_{n}(e^{s}_{+})-\sum_{e^{s}:\exists j\text{ s.t.
}e^{s}=(j,i)}f^{v}_{n}(e^{s}_{-})$
$\displaystyle\quad=\left\\{\begin{array}[]{ll}1&i=s_{n}\\\ -1&i=t_{n}\\\
0&\text{o.w.}\end{array}\right.$ (10)

2) Flow non-negativity

$\displaystyle\forall n\in\\{1,2,\cdots,N\\},\forall e^{s}\in E^{s}:\quad
f^{v}_{n}(e^{s}_{+}),f^{v}_{n}(e^{s}_{-})\geq 0$ (11)

3) SN link bandwidth

$\displaystyle\forall e^{s}\in E^{s}:\quad c^{v}(e^{s})\leq c^{s}(e^{s})$ (12)

4) Traffic demand

$\displaystyle\forall e^{s}\in
E^{s}:\;({\mathbf{d}^{v}_{\text{max}}})^{\top}\mathbf{f}^{v}(e^{s})\leq
c^{v}(e^{s})$ (13)

where
$\mathbf{f}^{v}(e^{s})\triangleq[f^{v}_{1}(e^{s}_{+})+f^{v}_{1}(e^{s}_{-}),\cdots,f^{v}_{N}(e^{s}_{+})+f^{v}_{N}(e^{s}_{-})]^{\top}$.
Here $f^{v}_{n}(e^{s}_{+})+f^{v}_{n}(e^{s}_{-})$ represents the sum of path
splitting ratios for paths of node pair $\mathbf{e}^{v}(n)$ passing through
link $e^{s}$.

###  IV-B Multi-path Oblivious Routing (MPOR)

MPOR embedding problem is also solvable in polynomial time. We first formulate
the problem as a robust optimization problem by replacing Equation (13) with
the following constraint in MFP in Section IV-A:

$\displaystyle\forall e^{s}\in
E^{s}:\quad\begin{bmatrix}\underset{\mathbf{d}^{v}}{\text{max}}\quad&({\mathbf{d}^{v}})^{\top}\mathbf{f}^{v}(e^{s})\\\
s.t.\quad&\mathbf{A}^{v}\mathbf{d}^{v}\leq\mathbf{b}^{v},\mathbf{d}^{v}\geq\mathbf{0}\end{bmatrix}\leq
c^{v}(e^{s})$ (14)

which indicates that $c^{v}(e^{s})$ should be no less than the maximum amount
of traffic that sends on link $e^{s}$ when $\mathbf{d}^{v}\in D^{v}$.

The dual problem of the inner LP of Equation (14) is a minimization problem:

$\displaystyle\underset{\mathbf{q}^{v}(e^{s})}{\text{min}}\quad$
$\displaystyle(\mathbf{b}^{v})^{\top}\mathbf{q}^{v}(e^{s})$ (15)
$\displaystyle s.t.\quad$
$\displaystyle(\mathbf{A}^{v})^{\top}\mathbf{q}^{v}(e^{s})\geq\mathbf{f}^{v}(e^{s}),$
(16) $\displaystyle\mathbf{q}^{v}(e^{s})\geq\mathbf{0}.$ (17)

where we define dual vector $\mathbf{q}^{v}(e^{s})\in\mathbb{R}^{M^{v}\times
1}$ for each link $e^{s}\in E^{s}$. Therefore, Equation (14) can be
transformed to:

$\displaystyle\forall e^{s}\in E^{s}:\quad$
$\displaystyle(\mathbf{b}^{v})^{\top}\mathbf{q}^{v}(e^{s})\leq c^{v}(e^{s}),$
(18)
$\displaystyle(\mathbf{A}^{v})^{\top}\mathbf{q}^{v}(e^{s})\geq\mathbf{f}^{v}(e^{s}),$
(19) $\displaystyle\mathbf{q}^{v}(e^{s})\geq\mathbf{0}.$ (20)

Thus the oblivious routing problem is formulated as an LP problem with
objective function in Equation (4), and with constraints in Equation (10)-(12)
and (18)-(20).

TABLE I: Comparison of LP input complexity | Number of | Number of
---|---|---
VNE | decision variables | constraints
MPIC | $O(N|E^{s}|)$ | $O(N|V^{s}|+N|E^{s}|)$
MPOR | $O((N+M^{v})|E^{s}|)$ | $O(N|V^{s}|+(N+M^{v})|E^{s}|)$
MPAR | $O(QN|E^{s}|)$ | $O(QN|V^{s}|+QN|E^{s}|)$
Algorithm 2 MPOR-Fast Algorithm

1: Solve MPAR embedding problem

2: if MPAR fails then

3: return fail signal

4: else

5: get the allocation $c^{v}$ from MPAR, and fix the corresponding path
splitting ratios $\mathbf{f}^{v}(e^{s})$

6: for each $e^{s}\in E^{s}$ such that $c^{v}(e^{s})>0$ do

7: Update $c^{v}(e^{s})$ through inner LP in Equation (14)

8: end for

9: end if

10: Embedding succeeds, return the allocation $c^{v}$

From Table I, we can compare the LP input complexity for MPIC and MPOR. MPOR
introduces $O(M^{v}|E^{s}|)$ more decision variables and $O(M^{v}|E^{s}|)$
more constraints. which may significantly increase the running time of LP.
Therefore, we can formulate an approximation algorithm as shown in Algorithm
2, which we call MPOR-Fast, as an alternative to reduce the running time. In
MPOR-Fast, we first solve the MPIC problem. If the embedding succeeds, we get
the allocation $c^{v}$ and fix the corresponding path splitting ratios
$\mathbf{f}^{v}(e^{s})$. Next, $\forall e^{s}\in E^{s}$ such that
$c^{v}(e^{s})>0$, we update $c^{v}(e^{s})$ through LP in Equation (14), which
has only $O(N)$ decision variables and $O(M^{v}+N)$ constraints. This helps us
save running time by solving no more than $|E^{s}|$ additional small LP
problems, instead of enlarging the LP problem for MPIC.

###  IV-C Multi-path Adaptive Routing (MPAR)

For MPAR problem, its complexity remains unclear and it might be NP-hard.
Suppose the feasible region of $\mathbf{d}^{v}$ with respect to the SN
(including $G^{s}$ and $c^{s}$) is denoted by $D^{s}$, which is a polytope.
Then the polytope containment problem of whether $D^{v}\subseteq D^{s}$ is
equivalent to whether an MPAR algorithm will return a feasible $G^{v}$. It has
been known that many forms of the polytope containment problem are polynomial
[19, 20], e.g., the two polytopes both have $\mathcal{H}$-descriptions
(intersection of a finite set of half-spaces) or $\mathcal{V}$-descriptions
(convex hull of a finite set of vertices). However, in our problem, either the
$\mathcal{H}$-description or $\mathcal{V}$-description of $D^{s}$ can be
exponential in the description of the SN. For example, for the SN shown in
Fig. 3 on which we specify $N$ node pairs
$(s_{1},t),(s_{2},t),\cdots,(s_{N},t)$, the associated half-spaces of $D^{s}$
are as follows:

$\displaystyle\forall n\in\\{1,2,\cdots,N\\}:\quad 0\leq\mathbf{d}^{v}(n)\leq
1+\frac{1}{N},$ (21) $\displaystyle\forall
H\subseteq\\{1,2,\cdots,N\\}\;s.t.\;|H|>\lfloor N/2\rfloor:$
$\displaystyle\quad\sum_{n\in H}\mathbf{d}^{v}(n)\leq|H|+\frac{N-|H|}{N}.$
(22)

In Equation (22), for $H$’s such that $|H|=\lfloor N/2\rfloor+1$ only, the
number of half-spaces is $\binom{N}{\lfloor N/2\rfloor+1}$, which is
exponential in $N$. It can be similarly verified that the number of vertices
of $D^{s}$ is also exponential in $N$. This means MPAR cannot be reduced to
polytope containment problem efficiently. Moreover, reference [19] has proved
that the problem of whether a polytope with $\mathcal{H}$-description is
contained in a polytope with $\mathcal{V}$-description is co-NP-complete.
Therefore, even if we focus on a subset of the MPAR problem where the
$\mathcal{V}$-description of $D^{s}$ is polynomial in the description of the
SN (remember $D^{v}$ has $\mathcal{H}$-description in our problem
formulation), it is still unclear whether this subset is polynomial or not.

Figure 3: An example of SN such that the $\mathcal{H}$-description and
$\mathcal{V}$-description of $D^{s}$ are exponential in the description of SN.

If the scale of the considered MPAR problem is relatively small, we can
formulate an LP problem with exponential number of constraints that is
solvable in reasonable time. We first enumerate all the vertices of $D^{v}$,
which takes $O(PNM^{v})$ time [21] where $P$ is the number of the vertices. We
denote the vertices by
$\mathbf{d}^{v}_{1},\mathbf{d}^{v}_{2},\cdots,\mathbf{d}^{v}_{P}$. Then we
exclude those vertices dominated by at least one other vertex, where we say
$\mathbf{d}^{v}_{p}$ is dominated by
$\mathbf{d}^{v}_{p^{\prime}}\neq\mathbf{d}^{v}_{p}$ if and only if
$\mathbf{d}^{v}_{p^{\prime}}-\mathbf{d}^{v}_{p}\geq\mathbf{0}$. This can be
done in $O(P^{2}N)$ time through brute-force method, and without loss of
generality we assume the remaining vertices are the first $Q$ vertices. Next,
for each vertex, we define a set of flow variables through the same way in
Section IV-A. However, since now we consider $Q$ vertices, while in Section
IV-A we only consider one vertex $\mathbf{d}^{v}_{\text{max}}$, we need to
make a slight modification of the notations: $\forall
n\in\\{1,2,\cdots,N\\},\forall e^{s}\in E^{s}$, instead of defining flow
variables $f^{v}_{n}(e^{s}_{+})$ and $f^{v}_{n}(e^{s}_{-})$, we define
$f^{v}_{n,q}(e^{s}_{+})$ and $f^{v}_{n,q}(e^{s}_{-})$ for each vertex
$\mathbf{d}^{v}_{q}$, $q\in\\{1,2,\cdots,Q\\}$. Hence, the final LP would have
an objective function in Equation (4), a set of SN link bandwidth constraints
in Equation (12), and a set of flow conservation, flow non-negativity and
traffic demand constraints in Equation (10), (11) and (13) for each vertex
$\mathbf{d}^{v}_{q}$.

##  V Evaluation

In this section, we evaluate the performance of different VNE algorithms
through simulation. We first describe the settings of our simulation in
Section V-A, and then present the results of in Section V-B.

###  V-A Settings

Simulation Environment. We run VNE simulation on a laptop with 2.7 GHz Intel
Core I5 processor and 8-GB 1867 MHz DDR3 memory. The simulator is implemented
in MATLAB, and IBM ILOG CPLEX Optimization Studio [22] is used for solving LP.

Figure 4: B4 topology

$25$$50$$75$$100$$125$$150$$0.4$$0.6$$0.8$$1$Link bandwidthAcceptance rate (a)

$25$$50$$75$$100$$125$$150$$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$Link
bandwidthAverage link utility (b)

$25$$50$$75$$100$$125$$150$$0.2$$0.4$$0.6$$0.8$$1$$\cdot 10^{4}$Link
bandwidthAverage cost for all VNRs (c)

$25$$50$$75$$100$$125$$150$$1{,}500$$2{,}000$$2{,}500$Link bandwidthAverage
cost for small VNRs (d)

$200$$400$$600$$800$$1{,}000$$1{,}200$$0.4$$0.6$$0.8$$1$Link
bandwidthAcceptance rate (e)

$200$$400$$600$$800$$1{,}000$$1{,}200$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$Link
bandwidthAverage link utility (f)

$200$$400$$600$$800$$1{,}000$$1{,}200$$4{,}000$$6{,}000$$8{,}000$Link
bandwidthAverage cost for all VNRs (g)

$200$$400$$600$$800$$1{,}000$$1{,}200$$1{,}800$$1{,}900$$2{,}000$$2{,}100$Link
bandwidthAverage cost for small VNRs (h)

Figure 5: Embedding results for GT-ITM topology (top) and B4 topology
(bottom). $25$$50$$75$$100$$125$$150$$0$$0.5$$1$$1.5$$\cdot 10^{4}$Link
bandwidthAlgorithm Running Time (s) Figure 6: Algorithm running time for GT-
ITM topology.

SN. We run VNE simulation on two different SN topologies: 1) GT-ITM topology,
a topology generated by GT-ITM tool [23]. In our simulation, the GT-ITM
topology is configured to have 100 nodes which are randomly placed on a 100
$\times$ 100 grid, and each node pair is randomly connected with probability
0.1. So there are around 500 links in total. 2) B4 topology, the topology of
Google’s private inter-datacenter WAN [24, 25, 26]. Fig. 4 shows the B4
topology used in our simulation, which has 14 nodes and 25 links. For each
topology, the unit price of each link is proportional to the geographical
distance between the two nodes at its two ends; the bandwidths of all the
links are the same and we run simulation with six different link bandwidth
values.

VNR. In each VNR, the number of access nodes follows a uniform distribution
between 2 and 10. Each pair of access nodes is factored into the node pair
vector $\mathbf{e}^{v}$ with probability 0.5. For each pair in
$\mathbf{e}^{v}$, we specify a traffic demand upper bound that follows a
uniform distribution between 1 and 20. Besides, we also add $N$ random joint
traffic demand upper bound constraints, where each constraint specifies a
joint traffic demand upper bound for two or more pairs of nodes which is
smaller than the sum of their individual traffic demand upper bounds.

Time Dimension. The arrival of VNRs follows a Poisson process with an average
rate of 5 VNRs per time unit, and the duration of each VNR follows an
exponential distribution with an average of 10 time units. Each simulation
lasts for 500 time units, which corresponds to around 2500 VNRs.

VNE Algorithms. We compare six VNE algorithms: SPIC, SPOR, MPIC, MPOR, MPOR-
Fast, and MPAR+MPOR. In particular, for MPAR+MPOR, we run MPAR on small VNRs
with $N\leq 5$ and MPOR otherwise, due to the time complexity of MPAR.

###  V-B Results

The embedding results for GT-ITM topology and B4 topology are shown in Fig. 5.
The acceptance rate, average link utility, and average cost for all accepted
VNRs and all accepted small VNRs of using different VNE algorithms are
measured for both two topologies. Besides, we also present the algorithm
running time of different algorithms for GT-ITM topology in Fig. 6, since the
scale of GT-ITM topology is large enough to make algorithm running time
difference obvious. The key observations are summarized as follows.

Multi-path embedding and shared channel embedding improve the acceptance rate
when link bandwidth is limited. Fig. 5(a) and Fig. 5(e) show the acceptance
rate for GT-ITM topology and B4 topology, respectively. In both two figures,
the performance of MPIC is always better than SPIC, and the performance of
MPOR/MPOR-Fast is always better than SPOR, which indicates multi-path
embedding improves acceptance rate. Moreover, the performance of SPOR is
always better than SPIC, and when link bandwidth is smaller than 75 for GT-ITM
and 1000 for B4 (i.e., when link bandwidth is limited for MPIC), the
performance of MPOR/MPOR-Fast/MPAR+MPOR is better than MPIC, which indicates
shared channel embedding improves acceptance rate. The reason is multi-path
embedding and shared channel embedding require a cheaper allocation and thus
lead to higher acceptance rate.

Shared channel embedding reduces link utility and cost when accepted VNRs are
the same. When link bandwidth is no less than 75 for GT-ITM and 1000 for B4,
all the VNRs are accepted for MPIC, MPOR, MPOR-Fast, and MPAR+MPOR. Therefore,
the corresponding link utility and cost are comparable. In Fig. 5(b)/Fig. 5(f)
and Fig. 5(c)/Fig. 5(g), in terms of average link utility and cost, we have
MPAR+MPOR $<$ MPOR $<$ MPOR-Fast $<$ MPIC. The savings on cost for MPOR, MPOR-
Fast, and MPAR+MPOR with respect to MPIC are $24.6\%$, $4.9\%$, and $25.1\%$
respectively for GT-ITM when link bandwidth is 150, and $30.3\%$, $16.4\%$,
and $30.4\%$ respectively for B4 when link bandwidth is 1200. The reason is
shared channel embedding requires a cheaper allocation which reduces link
utility and cost.

For single-path embedding, the advantage of shared channel embedding is more
significant in a smaller SN. The advantage of SPOR, including acceptance rate,
average link utility and average cost, is nearly negligible compared to SPIC
for GT-ITM. However, for B4, we can see significant advantage of SPOR against
SPIC in terms of acceptance rate and average cost. The main reason is the
scale of B4 is relatively small, and therefore different node pairs have
higher chances to use a common link.

Compared to oblivious routing, adaptive routing has limited savings on cost
for small VNRs. Within all the VNRs, there are around 40% small VNRs with
$N\leq 5$. Fig. 5(d) and Fig. 5(h) show the average cost of these small VNRs
for MPOR and MPAR (in MPAR+MPOR only MPAR is called for small VNRs). The
saving on cost for MPAR with respect to MPOR is only $4.6\%$ for GT-ITM when
link bandwidth is 150, and $1.0\%$ for B4 when link bandwidth is 1200. This
implies that though adaptive routing tries to reduce the cost by offering more
flexibilities, the associated advantage reflected on cost tends to be small.

Shared channel embedding requires longer algorithm running time. For GT-ITM
topology, Fig. 6 indicates that shared channel embedding algorithms generally
have longer algorithm running time. However, the additional running time seems
to be trivial for SPOR (compared to SPIC) and MPOR-Fast (compared to MPIC),
while MPOR and MPAR+MPOR require $3.6\times$ and $7.4\times$ running time of
MPIC when link bandwidth is 150, respectively. So it is also a tradeoff
between algorithm running time and VNE acceptance rate when link bandwidth is
limited, or between algorithm running time and VNE cost/link utility when link
bandwidth is adequate.

##  VI Discussion

In previous sections we have studied VNE algorithms under the most basic
configuration, where only traffic demand constraints are considered and each
link has a fixed unit price. In this section, we briefly discuss the scenarios
where node constraints and delay constraints are considered and link cost is a
piecewise linear or quadratic function of link bandwidth.

###  VI-A Node Constraints

Node constraints generally include CPU capacity constraints and node location
constraints. CPU capacity constraints dictate the CPU requirement for each
virtual node, and node location constraints dictate the potential SN nodes
that each virtual node can be mapped to.

When node constraints are introduced, a node mapping step is needed to map
each virtual node to a fixed SN node, and then the aforementioned algorithms
can be used to determine the final SN subset. The node mapping algorithm
doesn’t have to take traffic demand constraints into consideration. For
example, the greedy node mapping algorithm in [5] only considers the remaining
CPU capacity and outgoing link bandwidths for a potential SN node during node
mapping, so in this case our description of traffic demand will not affect the
node mapping at all. Even for those node mapping algorithms which do consider
traffic demand constraints, we can only consider independent traffic demand
constraints in this phase.

###  VI-B Delay Constraints

Delay constraints dictate that maximum acceptable delay for routing traffic of
each node pair. When they are introduced, the latency of each SN link is also
given and we need to consider the delay of one or more paths selected for each
node pair.

Suppose the latency of SN link $e^{s}$ is $\delta(e^{s})$, and the maximum
acceptable delay for node pair $\mathbf{e}^{v}(n)$ is
$\Delta(\mathbf{e}^{v}(n))$. Then for single-path embedding, we only need to
add one check after line 7 of Algorithm 1: if the sum of $\delta(e^{s})$’s for
those $e^{s}$’s belong to path $k$ is greater than
$\Delta(\mathbf{e}^{v}(n))$, we shouldn’t use this path. For multi-path
embedding, if we only care about the average latency of all the selected
paths, then we can simply add the following constraint to the LP given in
Section IV-A:

$\displaystyle\forall n\in\\{1,2,\cdots,N\\}:$
$\displaystyle\quad\sum_{e^{s}}[f^{v}_{n}(e^{s}_{+})+f^{v}_{n}(e^{s}_{-})]\cdot\delta(e^{s})\leq\Delta(\mathbf{e}^{v}(n))$
(23)

However, if the delay of each selected path is required to be bounded by
$\Delta(\mathbf{e}^{v}(n))$, then binary variables have to be introduced into
the optimization, making it become an NP-time algorithm. Alternatively, we can
use approximation algorithms in this scenario, but it is out of the scope of
this paper so we stop our discussion here.

###  VI-C Piecewise Linear or Quadratic Link Cost

In the basic problem, we assume each link $e^{s}$ has a fixed unit price
$p^{s}(e^{s})$, i.e., link cost is a linear function of the its available
bandwidth on the resulted SN subset. Link cost can also be modeled as a
piecewise linear or quadratic function of its available bandwidth. In this
case, for single-path embedding, Algorithm 1 remains unchanged: we only need
to use the piecewise linear or quadratic function to compute link cost, and we
still use the same way to search the $K$-least cost paths in line 4. For
multi-path embedding, the LP given in Section IV-A changes to mixed-integer
linear programming (MILP) or quadratic programming (QP) when link cost is a
piecewise linear or quadratic function, respectively. For piecewise linear
link cost, which has multiple intervals, we need to introduce binary variables
to determine which interval is link bandwidth located in; and for quadratic
link cost, we can simply change the objective function in Equation (4) to a
sum of quadratic link cost functions.

##  VII Conclusion

In this paper, we presented a VNE problem where each VNR is directly described
by the traffic demand between different access node pairs, without specifying
a particular virtual network topology. This VNR formulation makes it possible
for the customer to specify joint traffic demand constraints, which can
possibly lead to a smaller and hence cheaper SN subset. Moreover, three
different groups of VNE variants were considered. Simulations showed that
shared channel embedding, as a new embedding variant under the proposed VNR
formulation, improves the acceptance rate and reduces cost and link utility
compared to traditional independent channel embedding.

There are several directions along which we can extend this study. First, the
complexity of the MPAR embedding problem remains unclear and is therefore
worthwhile to be studied. Another direction is to consider the constraints of
dynamics of adaptive routing embedding, which imposes limitations on the real-
time updates of routing and is a quite realistic concern. Finally, the joint
traffic demand constraints can be factored into the phase of node mapping,
which would further increase the search space for valid SN subset and possibly
lead to a better result.

## References

  * [1] R. Mijumbi, J. Serrat, J.-L. Gorricho, N. Bouten, F. De Turck, and R. Boutaba, “Network function virtualization: State-of-the-art and research challenges,” _IEEE Communications surveys & tutorials_, vol. 18, no. 1, pp. 236–262, 2015.
  * [2] B. Han, V. Gopalakrishnan, L. Ji, and S. Lee, “Network function virtualization: Challenges and opportunities for innovations,” _IEEE Communications Magazine_ , vol. 53, no. 2, pp. 90–97, 2015.
  * [3] T. Anderson, L. Peterson, S. Shenker, and J. Turner, “Overcoming the internet impasse through virtualization,” _Computer_ , vol. 38, no. 4, pp. 34–41, 2005.
  * [4] A. Fischer, J. F. Botero, M. T. Beck, H. De Meer, and X. Hesselbach, “Virtual network embedding: A survey,” _IEEE Communications Surveys & Tutorials_, vol. 15, no. 4, pp. 1888–1906, 2013.
  * [5] M. Yu, Y. Yi, J. Rexford, and M. Chiang, “Rethinking virtual network embedding: substrate support for path splitting and migration,” _ACM SIGCOMM Computer Communication Review_ , vol. 38, no. 2, pp. 17–29, 2008.
  * [6] N. M. K. Chowdhury, M. R. Rahman, and R. Boutaba, “Virtual network embedding with coordinated node and link mapping,” in _IEEE INFOCOM 2009_. IEEE, 2009, pp. 783–791.
  * [7] M. Chowdhury, M. R. Rahman, and R. Boutaba, “Vineyard: Virtual network embedding algorithms with coordinated node and link mapping,” _IEEE/ACM Transactions on networking_ , vol. 20, no. 1, pp. 206–219, 2011.
  * [8] X. Cheng, S. Su, Z. Zhang, H. Wang, F. Yang, Y. Luo, and J. Wang, “Virtual network embedding through topology-aware node ranking,” _ACM SIGCOMM Computer Communication Review_ , vol. 41, no. 2, pp. 38–47, 2011.
  * [9] M. R. Rahman and R. Boutaba, “Svne: Survivable virtual network embedding algorithms for network virtualization,” _IEEE Transactions on Network and Service Management_ , vol. 10, no. 2, pp. 105–118, 2013.
  * [10] J. Lu and J. Turner, “Efficient mapping of virtual networks onto a shared substrate,” 2006.
  * [11] H. Yao, X. Chen, M. Li, P. Zhang, and L. Wang, “A novel reinforcement learning algorithm for virtual network embedding,” _Neurocomputing_ , vol. 284, pp. 1–9, 2018.
  * [12] Z. Yan, J. Ge, Y. Wu, L. Li, and T. Li, “Automatic virtual network embedding: A deep reinforcement learning approach with graph convolutional networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 38, no. 6, pp. 1040–1057, 2020.
  * [13] P. Zhang, N. Chen, S. Li, K.-K. R. Choo, C. Jiang, and S. Wu, “Multi-domain virtual network embedding algorithm based on horizontal federated learning,” _IEEE Transactions on Information Forensics and Security_ , 2023.
  * [14] Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Räcke, “Optimal oblivious routing in polynomial time,” _Journal of Computer and System Sciences_ , vol. 69, no. 3, pp. 383–394, 2004.
  * [15] M. A. Kinsy, M. H. Cho, T. Wen, E. Suh, M. Van Dijk, and S. Devadas, “Application-aware deadlock-free oblivious routing,” in _Proceedings of the 36th annual international symposium on Computer architecture_ , 2009, pp. 208–219.
  * [16] J. M. Kleinberg, “Approximation algorithms for disjoint paths problems,” Ph.D. dissertation, Massachusetts Institute of Technology, 1996.
  * [17] D. Eppstein, “Finding the k shortest paths,” _SIAM Journal on computing_ , vol. 28, no. 2, pp. 652–673, 1998.
  * [18] A. A. Assad, “Multicommodity network flows-a survey,” _Networks_ , vol. 8, no. 1, pp. 37–91, 1978.
  * [19] R. M. Freund and J. B. Orlin, “On the complexity of four polyhedral set containment problems,” _Mathematical programming_ , vol. 33, no. 2, pp. 139–145, 1985.
  * [20] V. Kaibel and M. E. Pfetsch, “Some algorithmic problems in polytope theory,” in _Algebra, geometry and software systems_. Springer, 2003, pp. 23–47.
  * [21] D. Avis and K. Fukuda, “A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra,” _Discrete & Computational Geometry_, vol. 8, no. 3, pp. 295–313, 1992.
  * [22] “Ibm ilog cplex optimization studio,” 2020. [Online]. Available: https://www.ibm.com/products/ilog-cplex-optimization-studio
  * [23] E. W. Zegura, K. L. Calvert, and S. Bhattacharjee, “How to model an internetwork,” in _Proceedings of IEEE INFOCOM’96. Conference on Computer Communications_ , vol. 2. IEEE, 1996, pp. 594–602.
  * [24] S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski, A. Singh, S. Venkata, J. Wanderer, J. Zhou, M. Zhu _et al._ , “B4: Experience with a globally-deployed software defined wan,” in _ACM SIGCOMM Computer Communication Review_ , vol. 43, no. 4. ACM, 2013, pp. 3–14.
  * [25] C.-Y. Hong, S. Mandal, M. Al-Fares, M. Zhu, R. Alimi, C. Bhagat, S. Jain, J. Kaimal, S. Liang, K. Mendelev _et al._ , “B4 and after: managing hierarchy, partitioning, and asymmetry for availability and scale in google’s software-defined wan,” in _Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication_. ACM, 2018, pp. 74–87.
  * [26] “Google data centers,” 2020. [Online]. Available: https://www.google.com/about/datacenters/locations/