=Paper=
{{Paper
|id=Vol-3010/PAPER_05
|storemode=property
|title=Two Applications of Graph Minor Reduction
|pdfUrl=https://ceur-ws.org/Vol-3010/PAPER_05.pdf
|volume=Vol-3010
|authors=Ghurumuruhan Ganesan
}}
==Two Applications of Graph Minor Reduction==
https://ceur-ws.org/Vol-3010/PAPER_05.pdf
Two Applications of Graph Minor Reduction
Ghurumuruhan Ganesan1
1
Institute of Mathematical Sciences, HBNI, Chennai
Abstract
In this paper, we study two applications of graph minor reduction. In the first part of the paper, we
introduce a variant of the boxicity, called strong boxicity, where the rectangular representation satisfies
an additional condition that each rectangle contains at least one point not present in any other rectangle.
We show how the strong boxicity of a graph πΊ can be estimated in terms of the strong boxicity of a
minor π» and the number of edit operations needed to obtain π» from πΊ. In the second part of the paper,
we consider false data injection (attack) in a flow graph πΊ and quantify the subsequent effect on the
state of edges of πΊ via the edge variation factor π. We use minor reduction techniques to obtain bounds
on π in terms of the connectivity parameters of πΊ, when the attacker has complete knowledge of πΊ and
also discuss stealthy attacks with partial knowledge of the flow graph.
Keywords
Strong boxicity, Minor reduction, Flow graphs, Stealthy attacks, Edge variation factor,
1. Introduction
Graph minor reduction is an important problem from both theoretical and application perspec-
tives. In particular, graph minor reduction algorithms are extensively used in computer science
to solve a variety of problems related to network routing and design. For a detailed survey of
algorithmic aspects of graph minor reduction, we refer to the survey [2].
In this paper, we study two theoretical applications of graph minor reduction in estimating
the strong boxicity of an arbitrary graph and determining conditions for stealthy attacks on
flow graphs. Below we discuss these two issues in that order.
Strong Boxicity
The boxicity of a graph πΊ [12] is the smallest integer π such that πΊ admits a rectangular
representation in Rπ , where R denotes the real line. Boxicity as defined above is finite and
is no more than the total number of vertices in πΊ. Since then many bounds for boxicity has
been obtained in terms of various graph parameters including treewidth [4] and maximum
degree [5, 6] and also in terms of poset dimension [1, 13].
In the first part of the paper, we define a variant of boxicity which we call strong boxicity
where we impose the additional condition that no rectangle corresponding to a particular vertex
is covered by the rectangles corresponding to the other vertices. We find bounds for strong
Algorithms, Computing and Mathematics Conference (ACM 2021), Chennai, India
" gganesan82@gmail.com (G. Ganesan) ORCID: 0000-0001-5857-5411 (G. Ganesan)
Β© 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
66
boxicity in terms of boxicity and estimate the strong boxicity of a general graph in terms of the
strong boxicity of a minor and the number of edit operations needed to obtain the minor.
Stealthy Attacks in Flow Graphs
Flow graphs are expected to play an important role in the future as more and more systems
are being automated through software. This also leads to potential vulnerabilities as software
defined networks are themselves prone to attack and therefore it is important to study malicious
data attacks on such automated flow networks. A typical example is that of a power grid where
power flow through transmission lines is often subject to stealthy attacks (see for example, [9]).
The survey by [8] also describes various aspects of cyber-physical attacks and defence strategies
on the smart grid, from a network layer perspective.
Flow graphs also frequently arise in the analysis of control systems [10, 7] where the node
variables could be either electrical (like for example voltages, currents etc,) or mechanical
(like position, angle etc.) in nature. Detection of false data injection (either unintentional or
intentional) is crucial here as well and steps must be taken to ensure that the measurements are
as authentic as possible.
In the second part of the paper, we are interested in studying how stealthy attacks affect the
state of edges in a general flow graph. Different edges are affected differently and we quantify
this effect via the edge variation factor. In our main result Theorem 2 below, we estimate the
maximum possible edge variation factor in terms of connectivity parameters of the flow graph,
when the attacker has complete knowledge of the flow graph. In Section 5, we also discuss
possibility of attacks with partial flow graph knowledge.
The paper is organized as follows. In Section 2, we define the concept of strong boxicity and
determine bounds for strong boxicity in terms of boxicity and also given examples of graphs
with strong boxicity exactly equal to 2. Next in Section 3, we show how strong boxicity of
a graph can be estimated in terms of the strong boxicity of a minor and the number of edit
operations needed to obtain the corresponding minor. In Section 4, we state and prove our main
result Theorem 2 regarding existence of stealthy attacks in general flow graphs and in Section 5,
we discuss stealthy attacks in the presence of partial information.
2. Strong boxicity
Let R denote
βοΈπ the real line and for integer π β₯ 1 define a rectangle π΄ β Rπ to beβοΈa closed set of
the form π=1 [ππ , ππ ] β R , where ππ β€ ππ are real numbers. We define π΄0 := ππ=1 (ππ , ππ ) to
π
be the interior of the rectangle π΄ where (ππ , ππ ) denotes the open interval with endpoints ππ
and ππ and Set ππ΄ := π΄ β π΄0 to be the boundary of the rectangle π΄. Also for π¦ > 0, π₯ β Rπ ,
]οΈπ
we let π΅π (π₯, π¦) := π₯ + β π¦2 , π¦2 be the πβdimensional square of side length π¦ centred at π₯.
[οΈ
Let πΊ = (π, πΈ) be a graph with vertex set π = {1, 2, . . . , π} and define (π, π) β πΈ to be the
edge with endvertices π and π.
Definition 1. We say that a set of rectangles {πΌπ }1β€πβ€π in Rπ , π β₯ 1 is a strong rectangular
representation of πΊ if the following two conditions hold:
67
(a) (b)
Figure 1: (π) The condition (π2) ensures that each rectangle has an exclusive boundary point and a
small surrounding neighbourhood. (π) Strong rectangular representation of the graph π» with vertex
set {1, 2, 3} and edge set {(1, 2), (2, 3)}.
(π1) For any 1 β€ π ΜΈ= π β€ π, the rectangles
πΌπ β© πΌπ ΜΈ= β
if and only if (π, π) β πΈ. (2.1)
(π2) For every 1 β€ π£ β€ π, there exists a point π₯π£ β ππΌπ£ and a number ππ£ > 0 such that
β βπ
βοΈ
π΅π (π₯π£ , ππ£ ) β β πΌπ’ β . (2.2)
1β€π’ΜΈ=π£β€π
In other words, we prefer that no rectangle has its boundary covered completely by the
remaining rectangles. The strong boxicity of πΊ denoted by π (πΊ) is defined to be the smallest
integer π such that both the conditions (π1) β (π2) hold. In Figure 1, we illustrate condition (π2)
with a example involving a strong rectangular representation in R2 . The solid rectangle π΄π΅πΆπ·
is πΌπ£ , the point π = π₯π£ and the dotted rectangle corresponds to π΅π (π₯π£ , ππ£ ).
We recall that the boxicity πΊ denoted by π(πΊ) is defined to be smallest integer π such that
condition (π1) alone holds [12]. By definition we therefore have π(πΊ) β€ π (πΊ). To see that
strong boxicity is not always equal to boxicity, we consider the graph π» with vertex set {1, 2, 3}
and edge set {(1, 2), (2, 3)}. Setting π½1 = [0, 2], π½2 = [1, 4] and π½3 = [2, 5], we see that
condition (π1) in definition 1 holds and so π(π») = 1. However, condition (π2) does not hold
and so π (π») β₯ 2. Considering π½1 , π½2 and π½3 to be squares such that π½1 and π½3 are disjoint
and π½2 intersects both π½1 and π½3 partially, as shown in Figure 1(π), we get that π (π») = 2.
From the discussion in the above paragraph, we deduce that any connected graph containing
at least two edges must have strong boxicity at least two. In the following result, we give
examples of graphs whose strong boxicity is exactly 2 and also obtain bounds for the strong
68
boxicity in terms of the boxicity. We begin with some definitions. A tree is a connected graph
containing π vertices and π β 1 edges for some π β₯ 2. A clique in a graph πΊ is a complete
subgraph of πΊ. We say that β is a stable set in πΊ if no two vertices are adjacent in πΊ. The
graph πΊ with vertex set {1, 2, . . . , π+π} is called a threshold graph [11] if πΊ contains a clique πΎ
with vertex set {1, 2, . . . , π} and a stable set πΌ = {π + 1, . . . , π + π} satisfying the following
nested neighbourhood property: If π© (π£) is the set of all neighbours of π£ in the graph πΊ, then
π© (π + 1) β π© (π + 2) β . . . β π© (π + π). (2.3)
Proposition 1. If πΊ is a tree or a threshold graph containing at least three vertices, then the strong
boxicity π (πΊ) = 2. In general, for any graph πΊ we have that
π(πΊ) β€ π (πΊ) β€ π(πΊ) + 2. (2.4)
From (2.4), we see that any bound for boxicity can also be used to estimate the strong boxicity.
Therefore using π(πΊ) β€ min(π, π) where π is the number of edges of πΊ [12], we get from (2.4)
that π (πΊ) β€ min(π, π) + 2.
Proof of Proposition 1: First, we see that any tree or threshold graph containing at least three
vertices has strong boxicity of exactly two.
Trees: We prove by induction on π, the number of vertices in the tree. For π = 3 the tree π3
contains two edges, say (1, 2) and (2, 3). To see that π (π3 ) = 2, we define π½1 , π½2 and π½3 to be
squares such that π½1 and π½3 are disjoint and π½2 intersects both π½1 and π½3 partially, as shown in
Figure 1(π).
Now, let ππ+1 be a tree with vertex set {1, 2, . . . , π + 1} and suppose the vertex π + 1 is a
leaf attached to the vertex π£ β ππ := ππ+1 β {π + 1}. The tree ππ has strong boxicity two by
induction assumption and so there exists a strong rectangular representation {π½π }1β€πβ€π β R2
of ππ . Moreover,(οΈthere exists a vertex π₯π£ β π½π£ and a real number ππ£ > 0 satisfying (2.2). Set-
ting π½π+1 := π΅2 π₯π£ , π2π£ , we get that {π½π }1β€πβ€π+1 forms a strong rectangular representation
)οΈ
of ππ+1 .
This is illustrated in Figure 1(π), where π½π£ = πΈπΉ πΊπ» intersects other rectangles in the
rectangular representation. However, the point π = π₯π£ and a small surrounding neighbourhood
is unique to π½π£ . The rectangle π½π+1 = π΄π΅πΆπ· intersecting only π½π£ is shown in dotted lines.
Threshold graphs: Let πΊ = (πΎ, πΌ) be any threshold graph with
πΎ = {1, 2, . . . , π} being a clique of size π and πΌ = {π + 1, . . . , π + π} being a stable set.
Because of the nested neighbourhood property (2.3), we assume that π (π + π) = {1, 2, . . . , ππ }
for some π β₯ π1 β₯ π2 β₯ . . . β₯ ππ β₯ 1.
For 1 β€ π β€ π, let π½π be the 1π Γ π rectangle in R2 centred at the origin. The rectan-
gles {π½π }1β€πβ€π form a strong representation of πΎ. We then let π½π+1 , . . . , π½π+π be small dis-
joint rectangles with the property that π½π+π intersects only the rectangles π½1 , . . . , π½ππ and no
other rectangle; this is illustrated in Figure 2 for the case πΎ = {1, 2, 3, 4} and πΌ = {5, 6}
having neighbourhoods π© (5) = {1, 2, 3} and π© (6) = {1, 2}. The rectangles with corners
labelled π, 1 β€ π β€ 4 form the strong rectangular representation of πΎ. The rectangles labelled 5
and 6 are π½5 and π½6 , respectively. This completes the proof that any threshold graph containing
at least three vertices has a strong boxicity of exactly two.
69
Figure 2: Strong rectangular representation of a threshold graph.
In the rest of the proof we
βοΈπprove (2.4). Weπ use the following boundary relation throughout.
For integer π β₯ 1 let ππ = π=1 [ππ , ππ ] β R be any rectangle and let πππ be its boundary. We
then have that
πππ β πππβ1 Γ [ππ , ππ ]. (2.5)
Indeed, writing πππ = ππ β ππ0 = ππβ1 Γ [ππ , ππ ] β ππβ1
0 Γ (ππ , ππ ) and using
0
(οΈ )οΈ
ππβ1 Γ [ππ , ππ ] = ππβ1 βͺ πππβ1 Γ [ππ , ππ ]
βοΈ
0
β ππβ1 Γ (ππ , ππ ) πππβ1 Γ [ππ , ππ ],
we get (2.5).
To prove (2.4), we let {πΌπ }1β€πβ€π β Rπ , π = π(πΊ) be a rectangular representation of πΊ. For 1 β€
π β€ π, we define the rectangle π½π := πΌπ Γ [0, π] Γ [π, π] and show first that {π½π }1β€πβ€π β Rπ+2
forms a rectangular representation of πΊ. Indeed if (π, π) is an edge in πΊ then πΌπ β© πΌπ ΜΈ= β
and so
π½π β© π½π = (πΌπ β© πΌπ ) Γ [0, min(π, π)] Γ [max(π, π), π] ΜΈ= β
.
To see that the rectangles {π½π } form a strong rectangular representation of the graph πΊ, we
let π£ β πΊ be any vertex and let π₯π£ β ππΌπ£ be any point in the boundary of πΌπ£ . Setting π¦π£ :=
(π₯π£ , π£, π£) we have from (2.5) that π¦π£ β ππ½π£ . AlsoβοΈπ¦π£ β
/ π½π’ for any π’ ΜΈ= π£. Letting ππ£ := 14 , we
also get that no point of π΅π+2 (π¦π£ , ππ£ ) belongs to 1β€πΜΈ=π£β€π π½π . Therefore π (πΊ) β€ π(πΊ) + 2 and
this proves (2.4).
3. Minor Reduction
In this subsection, we estimate the strong boxicity of a graph πΊ by βconverting" πΊ into a
graph π» with small strong boxicity through appropriate edit operations. Formally, a deletion
70
operation on πΊ is either a vertex deletion or edge deletion and a contraction operation is defined
as follows. Let π = (π’, π) be an edge in πΊ for some 1 β€ π’ β€ π β 1. The graph π» obtained by
contracting the edge π has vertex set {1, 2, . . . , π β 1} and still has all edges not containing π
as an endvertex. In addition, in the graph π», the vertex π’ is now adjacent to every vertex
of ππΊ (π) β {π’}. Henceforth, we denote a deletion operation or a contraction as an edit operation.
The graph π» obtained from an edit operation on πΊ as described above, is called a minor
of πΊ. We say that a minor π» is obtained from πΊ after π1 vertex deletions, π2 edge deletions
and π3 contractions if there are graphs
πΊ = π»0 , π»1 , π»2 , . . . , π»π = π», π = π1 + π2 + π3 such that π»π is obtained by either a vertex
deletion, edge deletion or contraction of π»πβ1 and the total number of vertex deletions is π1
and the total number of edge deletions is π2 . We have the following result regarding the strong
boxicity.
Theorem 1. If π» is a minor that is obtained from πΊ after πΌπ£ vertex deletions and πΌπ edge deletions,
then
π (π») β πΌπ β€ π (πΊ) β€ π (π») + πΌπ£ + πΌπ . (3.1)
If πΉ is a minor that is obtained from πΊ after π½π£ vertex deletions, π½π edge deletions and π½π
contractions, then
π (πΊ) β€ π (πΉ ) + π½π£ + π½π + 2π½π . (3.2)
Moreover both (3.1) and (3.2) hold with strong boxicity π (.) replaced by boxicity π(.).
In practice, we choose π» to be a known graph with low strong boxicity. As an example,
suppose πΊ is a connected graph on π vertices having π + π edges. We pick and remove π + 1
edges from πΊ to get a tree π», whose strong boxicity is two by proposition 1. From relation (3.1)
in theorem 1, we therefore get that π (πΊ) β€ π + 3.
It suffices to prove Theorem 1 for a single edit operation and we consider the three cases
vertex deletion, edge deletion and edge contraction separately below. Also we prove for strong
boxicity throughout and an analogous analysis holds for boxicity.
Vertex deletion: We show that for any vertex π£ β πΊ, the strong boxicity
π (πΉπ£ ) β€ π (πΊ) β€ π (πΉπ£ ) + 1, (3.3)
where πΉπ£ = πΊ β {π£} is the graph obtained by removing the vertex π£ β πΊ. We prove for π£ = π
and an analogous analysis holds for every other vertex. If β = {πΌπ }1β€πβ€π β Rπ , π = π (πΊ) is a
strong rectangular representation of πΊ satisfying (2.1), then β β {πΌπ } is a strong rectangular
representation of πΊ β {π} and so the first inequality in (3.3) is true.
For the second inequality, we let π (π) be the neighbours of π in πΊ and βοΈlet {π½π }1β€πβ€πβ1 β
Rπ , π = π (πΉπ ) be a strong rectangular representation of πΉπ with π½π = ππ=1 [ππ,π , ππ,π ]. Set-
ting ππ’π := maxπ,π ππ,π and ππππ€ = minπ,π ππ,π we define the rectangles {πΌπ€ }1β€π€β€π β Rπ+1
as
for π€ β
β§
β¨ π½π€ Γ [0, 3] / {π} βͺ π (π)
πΌπ€ := π½π€ Γ [2, 5] for π€ β π (π) (3.4)
π
[ππππ€ , 3ππ’π ] Γ [4, 6] for π€ = π.
β©
71
By construction, the rectangles {πΌπ }1β€πβ€π form a rectangular representation of πΊ. We now
use (2.5) to see that {πΌπ } also form a strong rectangular representation of πΊ. Indeed for π€ β/
{π} βͺ π (π), we let π₯π€ β ππ½π€ and ππ€ > 0 be such that
β βπ
βοΈ
π΅π (π₯π€ , ππ€ ) β β π½π’ β . (3.5)
1β€π’ΜΈ=π€β€π
From the first line in (3.4) and (2.5) we get that π¦π€ := (π₯π€ , 0) β ππΌπ€ and from (3.5) and the
second and third lines in (3.4) we further get
β βπ
βοΈ
π¦π€ + π΅π (0, ππ€ ) Γ [β1, 1] β β πΌπ’ β . (3.6)
1β€π’ΜΈ=π€β€π
Therefore choosing ππ€ smaller if necessary we get
β βπ
βοΈ
π΅π+1 (π¦π€ , ππ€ ) β β πΌπ’ β . (3.7)
1β€π’ΜΈ=π€β€π
If π€ β π (π) then letting π₯π€ be as in (3.5), we choose π¦π€ = (π₯π€ , 2). Arguing as before and
choosing ππ€ smaller if necessary, we get (3.7). Finally, if π€ = π, then we choose π¦π€ to be
the (π + 1)-tuple (3ππ’π , . . . , 3ππ’π , 6) so that π¦π€ β ππΌπ€ . Setting ππ€ = ππ’π and using the
definition of ππ’π we again get (3.7). Thus the strong boxicity π (πΊ) β€ π + 1.
Edge deletion: For any edge π = (π’, π£) β πΊ we show that
π (π»π ) β 1 β€ π (πΊ) β€ π (π»π ) + 1, (3.8)
where π»π = πΊ β {π} is the graph obtained by removing the edge π.
To prove the lower bound in (3.8), we let {πΌπ }1β€πβ€π β Rπ , π = π (πΊ) be a strong rectangular
representation of πΊ. We define the rectangles {π΄π }1β€πβ€π β Rπ +1 as follows:
β¨ πΌπ Γ [0, 4] for π ΜΈ= π’, π£
β§
π΄π := πΌπ Γ [1, 2] for π = π’
πΌπ Γ [3, 5] for π = π£.
β©
Arguing as in the vertex deletion case, we get that the rectangles {π΄π }1β€πβ€π form a strong
rectangular representation of π»π and so the strong boxicity π (π»π ) β€ π + 1.
For the upper bound in (3.8), we use the fact that the graph π»π has π vertices and let
βοΈππΏ1 , . . . , πΏπ β
R , π = π (π»π ) be a strong rectangular representation of π»π . As before if πΏπ = π=1 [ππ,π , ππ,π ]
π
then we set ππ’π := maxπ,π ππ,π and ππππ€ := minπ,π ππ,π .
Letting ππ (π£) be the neighbours of π£ in π»π , we now define the rectangles {π
π }1β€πβ€π β Rπ+1
as follows:
for π β
β§
β¨ πΏπ Γ [0, 3] / {π’, π£} βͺ ππ (π£)
π
π := πΏπ Γ [2, 5] for π β {π’} βͺ ππ (π£)
[ππππ€ , 3ππ’π ]π Γ [4, 6] for π = π£.
β©
72
Arguing as in the vertex deletion case, we get that the rectangles {π
π }1β€πβ€π form a strong
rectangular representation of πΊ and so the strong boxicity π (πΊ) β€ π + 1.
Edge contraction: We now consider the remaining case where πΊπ is the graph obtained by
the contracting the edge π = (π’, π) β πΊ to the vertex π’ β πΊπ and show that
π (πΊ) β€ π (πΊπ ) + 2. (3.9)
The graph πΊπ has π β 1 vertices and we let {ππ }1β€πβ€πβ1 β Rπ , π = π (πΊπ ), be a strong
rectangular representation of πΊπ . If π (π’) and π (π) are the neighbours of π’ and π respectively
in πΊ, then π β π (π’) and π’ β π (π) and we define the rectangles {ππ }1β€πβ€π β Rπ+2 as follows:
for π = π’
β§
βͺ ππ’ Γ [0, 6] Γ [3, 7]
for π = π
βͺ
β¨ ππ’ Γ [4, 10] Γ [6, 10]
βͺ
βͺ
ππ := ππ Γ [0, 10] Γ [0, 5] for π β π (π’) β ({π} βͺ π (π)) (3.10)
π Γ [8, 10] Γ [0, 10] for π β π (π) β ({π’} βͺ π (π’))
βͺ
π
βͺ
βͺ
βͺ
ππ Γ [0, 10] Γ [0, 10] otherwise .
β©
We first argue that the rectangles {ππ }1β€πβ€π form a rectangular representation of πΊ. Let (π, π)
be an edge not in πΊ. If (π, π) is not of the form π = π’, π β π (π)βπ (π’) or π = π, π β π (π’)βπ (π),
then the edge (π, π) is not present in πΊπ as well and so ππ β© ππ = β
. Consequently ππ β© ππ = β
.
If π = π’ and π β π (π) β π (π’), then by definition of contraction we have that (π’, π) β πΊπ
and so ππ’ β© ππ ΜΈ= β
. But from the first and fourth lines in (3.10), we get that ππ’ β© ππ = β
.
Similarly if π = π and π β π (π’) β π (π), then ππ β© ππ = ππ’ β© ππ ΜΈ= β
. But from the second and
third lines in (3.10) we get that ππ β© ππ = β
.
Next let (π, π) be an edge present in πΊ. If π, π ΜΈ= π’ or π, then (π, π) β πΊπ and so ππ β© ππ ΜΈ= β
.
From the last three lines of (3.10) we then get that
ππ β© ππ β (ππ β© ππ ) Γ [8, 10] Γ [0, 5] ΜΈ= β
.
If π = π’ and π = π β π (π’), then from the first two lines of (3.10) we get that
ππ’ β© ππ = ππ’ Γ [4, 6] Γ [6, 7] ΜΈ= β
. (3.11)
If π = π’ and π β π (π’) β ({π} βͺ π (π)) then ππ’ β© ππ ΜΈ= β
and so from the first and third lines
in (3.10), we get that
ππ’ β© ππ = (ππ’ β© ππ ) Γ [0, 6] Γ [3, 5] ΜΈ= β
.
Finally if π = π and π β π (π) β {π’} then using the fact that ππ’ β© ππ ΜΈ= β
and the second and
fourth lines in (3.10), we get that
ππ β© ππ β (ππ’ β© ππ ) Γ [8, 10] Γ [6, 10] ΜΈ= β
.
This proves the rectangles {ππ } for a rectangular representation of πΊ.
To see that {ππ } in fact form a strong rectangular representation, it suffices to see that (2.2)
in condition (π2) holds for π£ = π’ and π£ = π. Using the fact that {ππ } β Rπ form a strong
rectangular representation of πΊπ , we let π₯π’ β Rπ and ππ’ > 0 be such that
β βπ
βοΈ
π΅π (π₯π’ , ππ’ ) β β ππ β .
1β€πΜΈ=π’β€πβ1
73
Figure 3: Rectangles used in constructing a strong rectangular representation for πΊ.
Using the first and second lines of (3.10), we then set π¦π’ := (π₯π’ , 0, 3) and π¦π := (π₯π’ , 10, 6)
respectively and choose ππ’ smaller if necessary to get
β βπ β βπ
βοΈ βοΈ
π΅π+2 (π¦π’ , ππ’ ) β β ππ β and π΅π+2 (π¦π , ππ’ ) β β ππ β .
1β€πΜΈ=π’β€π 1β€πβ€πβ1
By (2.5), we have that π¦π’ β πππ’ and π¦π β πππ and so π (πΊπ ) β€ π + 2.
Finally, in Figure 3, we pictorially represent a possible choice for the rectangles in R2 that
can be used to construct a strong rectangular representation for πΊ as follows: The rectangle πΏπ₯
with corners labelled π₯ β {π’, π} is used for the vertex π₯ and so we set ππ₯ = ππ₯ Γ πΏπ₯ . Similarly,
the rectangle πΏ1 with corners labelled 1 is for neighbours of π’ that are not adjacent to π and the
rectangle πΏ2 with corners labelled 2 is for neighbours of π that are not adjacent to π£. For the rest
of the vertices, we pick any rectangle πΏ0 that is adjacent all the rectangles in Figure 3. Defining
the appropriate rectangles ππ , 1 β€ π β€ π, we then get a strong rectangular representation of πΊ
in Rπ+2 .
Proof of Theorem 1: Follows from (3.3), (3.8) and (3.9).
4. Stealthy Attacks on Flow Graphs
A flow graph is a graph πΊ = (π, πΈ) with vertex set π = {1, 2, . . . , π} and edge set πΈ (which
we index as {π + 1, . . . , π‘}) along with the following additional properties: The state of the
system is given by a real valued vector x = [π₯1 , . . . , π₯π ]π where π₯π denotes the state of vector π.
An edge with index π joining vertices π and π is assigned a gain π΅π,π = π΅π,π > 0 and the flow
through the edge π from π to π is given by
π΅π,π (π₯π β π₯π ) = hπ Β· x, (4.1)
where hπ is the 1 Γ π vector with exactly two non-zero entries: π΅π,π in ππ‘β position and βπ΅π,π in
the π π‘β position. The net flow into the vertex π equals the sum of flows from all edges connected
74
to π and is given by
βοΈ βοΈ βοΈ
π΅π,π (π₯π β π₯π ) = π₯π π΅π,π β π΅π,π π₯π = hπ Β· x, (4.2)
πβΌπ πβΌπ πβΌπ
with π βΌ π denoting that vertices π and π are connected by an edge in πΊ. The 1βοΈ Γ π vector hπ
has values βπ΅π,π for positions 1 β€ π ΜΈ= π β€ π, π βΌ π and has the value π»π,π = π’βΌπ π΅π,π’ . All
other entries of hπ are zero. Letting H = [hπ1 , . . . , hππ‘ ]π be the π‘ Γ π gain matrix, we then have
π
βοΈ
π»π,π = 0 (4.3)
π=1
for all 1 β€ π β€ π‘.
Given the flow vector H Β· x, the gain matrix H and a reference state (say π₯1 ), it is possible to
calculate the overall state x : We first use (4.1) to get π₯π β π₯π across every edge (π, π) β πΈ. We
then calculate the states of all vertices adjacent to the vertex 1 and then iteratively calculate the
states of the rest of the vertices.
We see how the differential state calculation procedure described above can be affected by
stealthy attacks. For a subset β± of edges in πΊ, we define a β±βattack vector or simply an
attack vector to be a π‘ Γ 1 vector a = [π1 , . . . , ππ‘ ]π satisfying ππ ΜΈ= 0 if and only if the index π
corresponds to an edge in β± or is a vertex adjacent to an edge in β±.
We say that β± is stealthily attackable if there exists an attack vector a of the form a = H Β· s
for some π Γ 1 vector s = [π 1 , . . . , π π ]π . For convenience, we denote a = H Β· s to be a stealthy
attack vector and denote s to be the β±βstealth vector or simply the stealth vector corresponding
to the attack vector a. In other words, we say that an attack vector a is stealthy if a is also a
flow vector.
By definition the attack vector a affects only edges of β± or vertices adjacent to edges of β±.
From the flow equation (4.1), we therefore have that π π β π π ΜΈ= 0 if and only if the edge (π, π)
of πΊ with endvertices π and π belongs to β±. Given the corrupted flow vector H Β· x + H Β· s,
the differential state calculation procedure described before obtains the difference between the
values of the states at vertices π and π to be
(π₯π β π₯π ) + (π π β π π ) if edge (π, π) β β±
{οΈ
(4.4)
(π₯π β π₯π ) otherwise.
From (4.4), we have that different edges in β± are affected differently due to stealthy attacks
and so we define the edge variation factor π(β±) as
max(π,π)ββ± |π π β π π |
π(β±) := inf , (4.5)
s min(π,π)ββ± |π π β π π |
where the infimum is taken over all β±βstealth vectors s. The edge variation factor measures
the variation in the corruption of the state vector x due to stealthy attacks.
We have the following result regarding the variation factor of stealthy attacks on β±.
75
Theorem 2. The set of edges β± is stealthily attackable if and only if for every cycle πΆ β πΊ,
either πΆ β© β± = β
or #πΆ β© β± β₯ 2. Moreover, if β± is stealthily attackable, then
1 β€ π(β±) β€ π(β±) β 1, (4.6)
where π(β±) is the number of components in the graph πΊ β β± obtained after removing the edges
in β±.
A single edge is stealthily attackable if and only if it is a bridge; i.e., removal of the edge
results in disconnection of the graph πΊ into two distinct components.
In general, stealthily attacking multiple βnon-critical" edges whose disconnection results in
few components, creates a more βuniform" corruption across the attacked edges. Therefore from
the designer perspective, it would be beneficial to have extra protection in these non-critical
edges.
Proof of Theorem 2
Suppose β± is stealthily attackable and there exists a cycle πΆ such that
#πΆ β© β± = 1; i.e., there exists exactly one edge π = (π’, π£) β πΆ present in β±. We arrive
at a contradiction as follows. Let a = H Β· s be the stealthy attack vector on β± and let s =
[π 1 , . . . , π π ]π be the corresponding stealth vector. As argued prior to (4.4), we have that π π βπ π ΜΈ=
0 if and only if (π, π) β β±. Thus π π’ ΜΈ= π π£ .
Denoting the cycle πΆ = (π’, π’1 , π’2 , . . . , π’π‘ , π£, π’), we then have that the edge (π’, π’1 ) β/ β± and
so π π’ = π π’1 . Similarly (π’1 , π’2 ) β / β± and so π π’1 = π π’2 . Continuing this way, we get π π’ = π π’1 =
π π’2 = . . . = π π’π‘ . Finally, the edge (π’π‘ , π£) is also not in β± and so π π’ = π π’π‘ = π π£ , a contradiction.
Conversely, suppose every cycle πΆ in πΊ contains either zero or at least two edges of β±. We now
use minor reduction to obtain the desired stealth vector, by extracting appropriate components
of πΊ that allow the vector construction. The details are as follows. First we remove the edges
in β± to get π = π(β±) connected components π1 , . . . , ππ of πΊ. Every edge π = (π€, π¦) β πΊ
satisfies the following property:
The edge π β β± if and only if the vertices π€ β ππ€1 and π¦ β ππ¦1
belong to distinct components ππ€1 ΜΈ= ππ¦1 . (4.7)
Indeed, by construction, we have that if the vertices π€ and π¦ belong to distinct components ππ€1
and ππ¦1 , then the edge (π€, π¦) necessarily belongs to β±. Conversely if (π€, π¦) β β± and both π€
and π¦ were to belong to the same component ππ , then π€ and π¦ would be connected by a path ππ€π¦
in ππ . This in turn would imply that π βͺ ππ€π¦ is a cycle in πΊ containing only one edge π of β±, a
contradiction.
We now construct the stealth vector s = [π 1 , . . . , π π ] as follows. Let π > 0 be a real number
to be determined later. For a vertex π£ β πΊ we set
π π£ = π π£ (π) = ππβ1 , if π£ β ππ , 1β€πβ€π (4.8)
so that s(π) = [π 1 (π), . . . , π π (π)]. Letting a = H Β· s we first argue that ππ = 0 if π is neither a
vertex adjacent to some edge of β± nor the index of some edge in β±. Indeed if π is the index of
76
an edge (π’, π£) β/ β± then both π’ and π£ belong to the same component ππ0 for some 1 β€ π0 β€ π
(property (4.7)). This implies that π π’ = π π£ = ππ0 β1 and so from (4.1), we get that
|ππ | = π΅π’,π£ |π π’ β π π£ | = 0.
Next if π is a vertex and the vertex π is not the endvertex of any edge in β±, then by property (4.7)
all neighbours of π are present in the same component ππ0 for some 1 β€ π0 β€ π. This implies
that π π€ = π π = ππ0 β1 for every neighbour π€ of π and from (4.2), we again get that ππ = 0.
We now see that ππ ΜΈ= 0 if either π is the index of some edge (π€, π¦) β β± or is a vertex adjacent
to some edge of β±. First suppose that π is the index of (π€, π¦) β β±. From property (4.7) above,
we have that π€ and π¦ belong to distinct components ππ€1 ΜΈ= ππ¦1 and so by construction
π π€ = ππ€1 β1 ΜΈ= ππ¦1 β1 = π π¦ .
From (4.1), this implies that |ππ | = π΅π€,π¦ |π π€ β π π¦ | =
ΜΈ 0.
Finally, choosing π appropriately, we now show that ππ ΜΈ= 0 if π is a vertex adjacent to some
edge in β±. Suppose the vertex π belongs to the component ππ1 for some 1 β€ π1 β€ π so that
the corresponding entry π π = ππ1 β1 . Since π is the endvertex of some edge in β±, we have from
property (4.7) that π has at least one neighbour outside ππ1 . Let ππ1 , . . . , πππ€ be the set of all
components containing either π or a neighbour of π. Using the flow equation (4.2) we then get
that
βοΈπ€
ππ = ππ (π) = π½1,π Β· ππ1 β1 β π½π,π Β· πππ β1 (4.9)
π=2
where βοΈ βοΈ
π½1,π := π΅π,π β π΅π,π > 0
πβΌπ πβΌπ,πβππ1
and for 2 β€ π β€ π€ the term βοΈ
π½π,π := π΅π,π > 0
πβΌπ,πβπππ
is the sum of the gains of edges adjacent to the vertex π and present in the component πππ so
that
π€
βοΈ
π½1,π β π½π,π = 0. (4.10)
π=2
Let Ξπ be theβοΈfinite set of the roots of the equation ππ (π₯) = 0 so that 1 β Ξπ by (4.10)
and set Ξπ‘ππ‘ = π£ Ξπ£ , where the union is taken over all vertices adjacent to an edge in β±.
Choosing π β / Ξπ‘ππ‘ we have that ππ (π) ΜΈ= 0 and since π is arbitrary this implies that a(π) =
H Β· s(π) is a stealthy attack vector.
From (4.8) and property (4.7), we also get for any edge (π, π) β β± that the corresponding
difference |π π (π)βπ π (π)| is of the form |ππ1 βππ1 | for some distinct integers π1 , π1 β₯ 0. Therefore
if {ππ }πβ₯1 , ππ β
/ Ξπ‘ππ‘ , ππ < 1 is a sequence converging to one as π β β then using
max |π π (ππ ) β π π (ππ )| = 1 β ππβ1
π and min |π π (ππ ) β π π (ππ )| = ππβ2
π β ππβ1
π
(π,π)ββ± (π,π)ββ±
77
we get that
max(π,π)ββ± |π π (ππ ) β π π (ππ )| 1 β πππβ1
= πβ2 ββ π β 1 (4.11)
min(π,π)ββ± |π π (ππ ) β π π (ππ )| ππ (1 β ππ )
as π β β. This implies that π(β±) β€ π(β±) β 1 and completes the proof of Theorem 2.
5. Extension of results in Theorem 2
In this section, we extend the result of Theorem 2 in two directions. In the first subsection, we
use the structure of the graph πΊ β β± to improve the bound for the edge variation factor and in
the second subsection, we study stealthy attacks with partial information.
Improved Bound for the Variation Factor
We now describe a slight modification of the proof of Theorem 2 to obtain stealth vectors with
lesser variation. Consider the component graph πΊππππ = (πππππ , πΈππππ ) constructed as follows:
We represent the component ππ by a node ππ β πππππ and connect nodes ππ and ππ if there
exists an edge π β β± with one endvertex in ππ and other endvertex in ππ . A proper colouring
of πΊππππ using π β₯ 1 colours is a map π : πππππ β {1, 2, . . . , π} such that π(π£) ΜΈ= π(π’) if
vertices π’ and π£ are adjacent in πΊππππ . The chromatic number π0 of πΊππππ is the smallest
integer π§ such that πΊππππ admits a proper colouring using π§ colours [3].
Letting π0 : πππππ β {1, 2, . . . , π0 } be a proper colouring of πΊππππ using π0 colours, we
define the stealth vector y = [π¦1 , . . . , π¦π ]π as follows. If π0 (ππ ) = π, we assign π¦π£ = π¦π£ (π) =
ππβ1 for all vertices π£ β ππ . Finally, letting y = [π¦1 , . . . , π¦π ]π , we set c = H Β· y.
To see that c is a stealthy attack vector, we consider any edge (π’, π£) β πΊ with index π. If π’
and π£ belong to the same component in {ππ }, then π¦π’ β π¦π£ = 0 and so we have from (4.1) that
the corresponding entry ππ = π΅π’,π£ (π¦π’ β π¦π£ ) = 0. Similarly if a vertex π’ is not adjacent to any
edge in β± then using property (4.7) as before, we get that all neighbours of π’ belong to the same
component in {ππ } as π’. As before, we use (4.2) to get that the corresponding entry ππ’ = 0.
If an edge (π’, π£) β β± then by property (4.7), the vertices π’ β ππ’1 and π£ β ππ£1 belong to
distinct components ππ’1 ΜΈ= ππ£1 . In the graph πΊππππ constructed above, the nodes ππ’1 and ππ£1
are joined by an edge and so have different colours π(ππ’1 ) ΜΈ= π(ππ£1 ). This in turn implies
that π¦π’ ΜΈ= π¦π£ and so ππ = π΅π’,π£ (π¦π’ β π¦π£ ) ΜΈ= 0, by (4.1).
Finally, for a vertex adjacent to an edge in β±, we argue as in (4.9) to get the corresponding
polynomial expression for ππ (π). The expressions here have different degrees than in (4.9) and
therefore different set of roots. Again we choose an appropriate sequence {ππ } converging to
one so that
1 β πππ 0 β1
ββ π0 β 1
πππ 0 β2 β πππ 0 β1
as π β β. This implies that π(β±) β€ π0 β 1.
78
Partial Knowledge
In this subsection, we see how stealth attacks could possibly be carried out with coarse informa-
tion regarding the gain matrix H. This situation arises for example, when measurement noise
results in imperfect estimates of the gain values.
Suppose the attacker does not exactly know the true gains {π΅π,π } but knows that
π1 β€ π΅π,π β€ π2 (5.1)
for some positive finite constants π1 , π2 .
We construct the stealth vector s as follows. For a vertex π£ β πΊ, we choose π π£ as in (4.8)
and get from the proof of Theorem 2 that ππ = 0 if π is neither the index of an edge in β± nor
is a vertex adjacent to any edges in β±. Moreover ππ ΜΈ= 0 if π is the index of an edge of β±. The
knowledge of edge gains is required only to determine an appropriate value of π so that ππ ΜΈ= 0
for a vertex π adjacent to some edge in β±. Indeed from (4.9), we have that
π€
βοΈ
ππ = ππ (π, H) = π½1,π Β· ππ1 β1 β π½π,π Β· πππ β1 (5.2)
π=2
where the positive {π½π,π } are as in (4.9).
We now see that if π > 0 is chosen large, then |ππ | β₯ π· for some constant
π· = π·(π, π1 , π2 ) not depending on the choice of H. Indeed, assuming
π1 > π2 . . . > ππ€ in (5.2) and using (5.1) we have
β β
π€
β βοΈ π½π,π
β
|ππ | = π½1,π ππ1 β1 β1 β
β β
π½1,π Β· ππ1 βππ β
β
β
π=2
π€
(οΈ )οΈ
π1 β1
βοΈ π2
β₯ π1 π 1β
π1 Β· ππ1 βππ
π=2
so that (οΈ )οΈ (οΈ )οΈ
π1 β1 π€ Β· π2 π1 β1 π Β· π2
|ππ | β₯ π1 π 1β β₯ π1 π 1β (5.3)
π1 Β· ππ1 βππ π1 Β· ππ1 βππ
where π = π(β±) is the number of components of πΊββ±. The final relation in (5.3) is true because,
the number of distinct powers of π in the stealth vector s is π. Thus for all π β₯ π0 (π, π, π1 , π2 ) > 1
large we have from (5.3) that
π1 ππ1 β1 π1
|ππ | β₯ β₯ .
2 2
Choosing π > π1 = π1 (π, π1 , π2 ) large enough, we get that |ππ | β₯ π21 for all vertices π adjacent
to some edge in β±. This obtains our desired stealth vector s = s(π).
As a concluding remark, we state here that though the attack as described is possible, the
edge variation π(β±) could be quite large and therefore be possibly detected.
79
6. Conclusion and Future Work
In this paper, we have studied two applications of graph minor reduction in boxicity and stealthy
attacks on flowgraphs. We have used minor reduction recursively to estimate the boxicity of an
arbitrary graph. Similarly, we used a component reduction technique to determine necessary
and sufficient conditions that allows stealthy attacks in a flowgraph.
In the above, we have considered deterministic graphs. In the future, we plan to incorporate
and study analogous problems in random graphs.
Acknowledgments
I thank Professors V. Raman, C. R. Subramanian and the referee for crucial comments that led
to an improvement of the paper. I also thank IMSc for my fellowships.
References
[1] A. Adiga, D. Bhowmick and L. S. Chandran, Boxicity and Poset Dimension, SIAM Journal
of Discrete Mathematics, 25 (2011) 1687β1698.
[2] D. Bienstock, M. A. Langston, Chapter 8: Algorithmic Implications of the Graph Minor
Theorem, Handbooks in Operations Research and Management Science, Elsevier, 7 (1995)
481β502.
[3] B. BollobΓ‘s, Modern Graph Theory, Springer, 1998.
[4] L. S. Chandran and N. Sivadasan, Boxicity and Treewidth, Journal of Combinatorial Theory,
Series B, 97 (2007) 733β744.
[5] L. S. Chandran, M. C. Francis and N. Sivadasan, Boxicity and maximum degree, Journal of
Combinatorial Theory, Series B, 98(2008) 443β445.
[6] L. Esperet, Boxicity of graphs with bounded degree, European Journal of Combinatorics,
30 (2009) 1277β1280.
[7] H. Fawzi, P. Tabuada and S. Diggavi, Secure estimation and control for cyber-physical
systems under adversarial attacks, IEEE Transactions on Automatic Control, 59(2014)
1454β1467.
[8] H. He and J. Yan, Cyber-physical attacks and defences in the smart grid: a survey,IET
Cyber-Physical Systems: Theory and Applications, 1(2016) 13β27.
[9] O. Kosut, L. Jia, R. J. Thomas and L. Tong, Malicious data attacks on the smart grid, IEEE
Transactions on Smart Grid, 2(2011), 645β658.
[10] B. Kuo, Automatic control systems, Prentice Hall, 1995.
[11] N. V. R. Mahadev and U. N. Peled, Threshold graphs and related topics, North Holland,
First Edition, 1995.
[12] F. S. Roberts, On the boxicity and cubicity of a graph, Recent Progress in Combinatorics
(Proc. Third Waterloo Conf. on Combinatorics, 1968) Academic Press, New York, 1969, pp.
301β310.
[13] A. Scott and D. R. Wood, Better bounds for poset dimension and boxicity, Transactions of
the American Mathematical Society, (2019), https://doi.org/10.1090/tran/7962.
80