=Paper=
{{Paper
|id=Vol-2393/paper_298
|storemode=property
|title=On Some Classes of Problems on Graphs
|pdfUrl=https://ceur-ws.org/Vol-2393/paper_298.pdf
|volume=Vol-2393
|authors=Volodymyr G. Skobelev
|dblpUrl=https://dblp.org/rec/conf/icteri/Skobelev19
}}
==On Some Classes of Problems on Graphs==
https://ceur-ws.org/Vol-2393/paper_298.pdf
On Some Classes of Problems on Graphs
Volodymyr G. Skobelev1,2[0000−0002−7018−2319]
1
Glushlov Institute of Cybernetics of NAS of Ukraine,
Glushkov Ave., 40, Kyiv, 03187, Ukraine
2
Institute of Applied Mathematics and Mechanics of NAS of Ukraine,
Gen. Batjuk Str., 19, Donetsk Region, Slov’jansk, 84116, Ukraine
skobelevvg@gmail.com
Abstract. The relevance to research the complexity of resolving Graph
Theory problems is caused by its numerous applications. In the given
paper this problem is investigated in terms of space complexity of data
structures that represent analyzed graphs, orgraphs, and directed graphs.
The following two non-trivial the simplest sets of problems of Graph
Theory are investigated in detail. The first set consists of the problems
that can be resolved by some algorithm with space complexity linear
relative to the size of the data structure that represents the analyzed
graphs. The second set consists of the following problems, such that the
size of the solution significantly exceeds the size of the input data. To
resolve the problem some algorithm that operates on space linear relative
to the size of the data structure that represents the analyzed graphs can
be applied. Besides, this algorithm uses some memory of the same size
for sequential generation, one fragment after another, the solution of the
problem. Some model problems that are not in these two sets of problems
are considered briefly.
Keywords: Graphs · Algorithms · Complexity.
1 Introduction
At present finite graphs (i.e. ordinary graphs, orgraphs, and directed graphs) are
used as mathematical models in resolving a wide class of theoretic and applied
problems. Rather new areas for application of Graph Theory models are com-
puter and social networks, agent-based technologies, and transition systems used
for verification of the developed software. Therefore, analysis of the complexity
for algorithms on graphs is an actual problem from the theoretic and applied
point of view. In Algorithms Theory, the main attention is paid to the analysis
of time complexity, while many questions for space complexity remain obscure.
The aim of the given paper is to investigate the classification of Graph Theory
problems in terms of the memory size necessary to represent the analyzed graphs
by basic data structures. These data structures are vertices-adjacency matrices,
edges-adjacency matrices, vertices-adjacency lists, and edges-adjacency lists. The
main ratios for the complexity of these data structures are established in terms
”for almost all” and ”on average”.
Two sets of Graph Theory problems are investigated in detail.
The first set consists of the problems that can be resolved by some algorithm
with space complexity linear relative to the size of data structure that represents
the analyzed graphs. For these problems, the memory size necessary to represent
the solution is also bounded above by some linear function of the memory size
necessary to represent the input data.
The second set consists of the problems that satisfy the following three con-
ditions.
Firstly, the memory size necessary to represent the solution significantly ex-
ceeds the memory size necessary to represent the input data.
Secondly, to resolve the problem some algorithm that operates on space linear
relative to the size of data structure that represents the analyzed graphs can be
applied.
Thirdly, this algorithm uses some memory of the same size to generate se-
quentially, one fragment after another, the solution of the problem in the explicit
form.
Some problems of Discrete Mathematics and its applications that can be nat-
urally reformulated in Graph Theory terms, and that are not in the investigated
two sets of problems are briefly considered.
The basic concepts used in the given paper are the same as in [1-3].
2 Mathematical Background
In the given Section the basic concepts and definitions necessary for the presen-
tation of the main results are introduced.
2.1 Data Structures for Graphs Representation
It is well-known that the main data structures used for representations of graphs
are matrices of adjacency (either vertices or edges), incidence matrices, and lists
of adjacency (either vertices or edges). We denote R any of these data structures.
→
− or →
− dir
Let G(n, m), G (n, m), and G (n, m) be the set of all graphs, orgraphs
and directed graphs G = (V, E) such that V = {1, . . . , n} and |E| = m, R(G) be
→
− or →
− dir
the representation of G ∈ X(n, m) (X ∈ {G, G , G }) by the data structure
R, and v(R(G)) be the size of memory necessary for the representation R(G).
We set
→
− or →
− dir
v(R, X, n, m) = max V (R(G)) (X ∈ {G, G , G }).
G∈X(n,m)
Due to the traditional approach in the Algorithms Theory, we will deal with
asymptotic space complexity V (R, X, n, m) of v(R, X, n, m).
→− or →
− dir
It is well-known that for all X ∈ {G, G , G }:
V (R, X, n, m) = O(n2 ) (n → ∞), if R is the vertices-adjacency matrix;
V (R, X, n, m) = O(m2 ) (m, n → ∞), if R is the edges-adjacency matrix;
V (R, X, n, m) = O(mn) (m, n → ∞), if R is the incidence matrix;
V (R, X, n, m) = O(max{m, n}) (m, n → ∞), if R are the vertices-adjacency
lists;
V (R, X, n, m) = O(m · max{1, min{m, n}}) (m, n → ∞), if R are the edges-
adjacency lists.
Since X is a dummy variable in V (R, X, n, m), we will write V (R, n, m).
→− or →
− dir
Let vA (R, X, G) (X ∈ {G, G , G }) be the size of memory necessary for
an algorithm A to carry out the given processing of the data structure R(G)
(G ∈ X(n, m)) and
vA (R, X, n, m) = max vA (R, X, G).
G∈X(n,m)
In what follows, we will deal with asymptotic space complexity VA (R, X, n, m)
of vA (R, X, n, m).
2.2 Some Classes of Problems in Graph Theory
Let’s distinguish the following set of algorithms on graphs.
Definition 1. An algorithm A is called a local algorithm on the set X(n, m)
→
− or →
− dir
(X ∈ {G, G , G }) and the data structure R, if
VA (R, X, n, m) = V (R, n, m) (n → ∞, m → ∞). (1)
Example 1. Let X = G and R be the representation of a graph G ∈ G(n, m) by
the vertices-adjacency matrix. It can be proved that the problem of checking the
validity of the property ”to be a connected graph” can be solved by some local
algorithm.
It is evident that the validity of equality (1) can significantly depend on the
law of the growth m → ∞. To avoid this dependence, we will act as follows.
For any fixed positive integer n we set
[
X(n) = X(n, m), (2)
m
VA (R, X, n) = max VA (R, X, n, m), (3)
m
and
V (R, n) = max V (R, n, m), (4)
m
where union and maximum are over all admissible values of m.
On the base of formulae (2)-(4) we get the following definition.
Definition 2. An algorithm A is called a local algorithm on the set X(n) (X ∈
→− or →
− dir
{G, G , G }) and the data structure R for any admissible law of the growth
m → ∞, if
VA (R, X, n) = V (R, n) (n → ∞).
Example 2. Let X = G. It can be proved that following three statements are
true:
1. Let R be the representation of a graph G ∈ G(n, m) either by the vertices-
adjacency matrix, or by the vertices-adjacency lists. Then the problem of check-
ing the validity of the property ”the given two graphs are isomorphic” can be
solved by some algorithm that is a local algorithm for any admissible law of the
growth m → ∞.
2. Let R be the representation of a graph G ∈ G(n, m) either by the vertices-
adjacency matrix, or by the edges-adjacency matrix. Then the problem of check-
ing the validity of the property ”some sub-graphs of the given graph are the
triangles” can be solved by some algorithm that is a local algorithm for any
admissible law of the growth m → ∞.
3. Let R be the representation of a graph G ∈ G(n, m) by the vertices-
adjacency matrix. Then the problem of checking the validity of the property ”to
be a bipartite graph”, and each of the problems of computing for the given graph
G ∈ G(n, m) the radius, the diameter, the center, and the connected components
can be solved by some algorithm that is a local algorithm for any admissible law
of the growth m → ∞.
On the base of Definition 2, we can distinguish the following set of Graph
Theory problems.
→
− or →
− dir
Definition 3. The set Lcl(R, X) (X ∈ {G, G , G }) is the set of all Graph
Theory problems P , such that the problem P can be resolved by some local al-
gorithm on the set X(n) and the data structure R for any admissible law of the
growth m → ∞.
Example 3. 1. Let An (n = 1, 2, . . .) be the algebraic system with the basic set
[
G(n) = G(n.m),
m≥0
the set of operations
FA
op = {\, ∪, ∩, ⊕, ¬},
n
and the set of relations
FA
rel = {=, ⊂}.
n
It can be proved that in the algebraic system An the problems of implementation
of any operation f ∈ FA An
op and checking the validity of any relation ρ ∈ Frel are
n
elements of the set Lcl(R, G) for any data structure R.
2. Let B be the algebraic system with the basic set
∞
[
T= G(n),
n=1
the set of operations
∞
FB FA
[
op = op ∪ {◦, →, •, ∗, ∧, ∨},
n
n=1
and the set of relations
∞
FB FA
[
rel = rel ∪ {≤, /}.
n
n=1
It can be proved that for the algebraic system B the following two statements
are true:
1. The problems of implementation of any operation f ∈ {◦, →} and checking
the validity of any relation ρ ∈ {≤, /} are elements of the set Lcl(R, G) for any
data structure R.
2. For each operation f ∈ {•, ∗, ∧, ∨} the problem of its implementation is
not an element of the set Lcl(R, G) for any data structure R.
Remark 1. The operations ∨ and ∧ are often used in the design and analysis of
algorithms. In particular, for parallel and concurrent computing. Indeed, let the
graphs G1 , G2 ∈ T be the models of the two given sub-problems. The vertices
present the separate stages of solving these problems, and the edges specify what
stages are the neighbors.
The graph G1 ∧ G2 describes the situation when only simultaneous advance
on stages of both sub-problems is admissible.
The graph G1 ∨ G2 describes the situation when advance on stages at least
of one of the sub-problems is admissible.
For a wide class of Graph Theory problems the size of the solution signifi-
cantly exceeds the size of the input data. Due to this situation, it is reasonable
to distinguish the following set of Graph Theory problems.
→
− or →
− dir
Definition 4. The set P-Work-Space(R, X) (X ∈ {G, G , G }) is the set of
all Graph Theory problems P , such that the problem P can be resolved on the
set X(n) and the data structure R for any admissible law of the growth m → ∞
by some algorithm A that satisfies to the following two conditions:
Condition 1. The algorithm A operates on the memory size V (R, n) (n → ∞).
Condition 2. The algorithm A explores as an output channel some additional
memory of the size that is a polynomial of V (R, n) to generate the solution
sequentially, one fragment after another.
We denote Work-Lcl(R, X) the set of all problems P ∈ P-Work-Space(R, X),
such that the size of additional memory, pointed in Condition 2 of Definition 4 is
→− or →
− dir
a linear polynomial of V (R, n). It can be proved that for any X ∈ {G, G , G }
and any data structure R the following strict inclusions hold
Lcl(R, X) ⊂ Work-Lcl(R, X) ⊂ P-Work-Space(R, X).
Example 4. It can be proved that the following three statements are true:
1. Let R be the representation either by the vertices-adjacency matrix, or by
the vertices-adjacency lists. Then the problem of the design of the edge-to-vertex
dual graph is an element of the set Work-Lcl(R, G)\Lcl(R, G).
2. The problem of the design of some the longest path between the two given
vertices in a graph G ∈ G(n), and consequently, the problem of the design of the
set of all longest paths between the two given vertices in a graph G ∈ G(n), are
elements of the set Work-Lcl(R, X)\Lcl(R, X) for any data structure R.
3. In the algebraic system B (see example 3.2), the problem of implementation
of any operation f ∈ {•, ∗, ∧, ∨} is an element of the set Work-Lcl(R, G)\Lcl(R, G)
for any data structure R.
3 Analysis of Graphs Representations
Similarly to the algebraic systems An (n = 1, 2, . . .) and B (see example 3),
→
− or
there can be defined the algebraic system A n (n = 1, 2, . . .) with the basic set
→
− or →
− or
G (n), the algebraic system B with the basic set
[→ ∞
→
− or − or
T = G (n),
n=1
→
− dir →
− dir
the algebraic system A n (n = 1, 2, . . .) with the basic set G (n), and the
→
− dir
algebraic system B with the basic set
∞
[→
→
− dir − dir
T = G (n).
n=1
In Subsection 2.2, when we were speaking about complexity, we meant ”com-
plexity in the worst case”. From the theoretic and applied point of view, both,
a significant role also play ”the average-case complexity” and ”complexity for
almost all input data”.
The following factors form the strong base for the application of this approach
for the detailed analysis of complexity for problems formulated in terms of the
→
− or →− dir →
− or →− dir
algebraic systems Yn (Y ∈ {A, A , A }) and Z (Z ∈ {B, B , B }).
On the base of standard methods used for computing the mathematical ex-
pectation of the random variable defined on a finite set, the following theorem
can be proved.
→
− or →
− dir
Theorem 1. Let X ∈ {G, G , G }. For chosen randomly element of the set
X(n) the average number of edges equals to:
1) 0.25n(n − 1), if X = G;
→
− or
2) 13 n(n − 1), if X = G ;
→
− dir
3) 0.5n(n − 1), if X = G .
Proceeding from this theorem, the following two propositions can be proved.
→
− or →
− dir
Proposition 1. Let the elements of the basic set X(n) (X ∈ {G, G , G }) be
→
− or →
− dir
chosen randomly. Then in the relevant algebraic system Yn (Y ∈ {A, A , A })
the average time for the implementation of any operation, as well as the average
time for checking validity of any relation, is asymptotically the same for repre-
sentations of elements of the basic set X(n) by the vertices-adjacency lists and
by the vertices-adjacency matrices.
→
− or →− dir
Proposition 2. Let the elements of the basic set X(n) (X ∈ {G, G , G }) be
→
− or →− dir
chosen randomly. Then in the relevant algebraic system Yn (Y ∈ {A, A , A })
the average time for the implementation of any operation, as well as the average
time for checking validity of any relation, for representations of elements of
the basic set X(n) by the edge-adjacency lists is less asymptotically than the
appropriate time for representations of elements of the basic set X(n) by the
edges-adjacency matrices.
On the base of standard methods used for computing the variance of the
random variable defined on a finite set, and using Chebyshev’s inequality, the
following theorem can be proved.
→
− or →− dir
Theorem 2. Let X ∈ {G, G , G }. For almost all elements of the set X(n)
(n → ∞) the number m of edges satisfy to the following asymptotic equality
m = Θ(n2 ) (n → ∞).
Proceeding from this theorem, the following two propositions can be proved.
→
− or →− dir
Proposition 3. In the algebraic system Yn (Y ∈ {A, A , A }) for almost
→− or →
− dir
all elements of the relevant basic set X(n) (X ∈ {G, G , G }) the time for the
implementation of any operation, as well as the time for checking validity of any
relation, is asymptotically the same for representations of elements of the basic
set X(n) by the vertices-adjacency lists and by the vertices-adjacency matrices.
→
− or →− dir
Proposition 4. In the algebraic system Yn (Y ∈ {A, A , A }) for almost
→
− or →
− dir
all elements of the relevant basic set X(n) (X ∈ {G, G , G }) the time for the
implementation of any operation, as well as the time checking validity of any re-
lation, for representations of elements of the basic set X(n) by the edge-adjacency
lists is asymptotically less than the appropriate time for representations of ele-
ments of the basic set X(n) by the edges-adjacency matrices.
4 Some Remark About the Set Work-Lcl(R, X)\Lcl(R, X)
One of the main reason owing to which the considerable number of problems of
Graph Theory are elements of the set Work-Lcl(R, X)\Lcl(R, X) is based on the
following factor. The problem of the design of any object is an element of the
set Lcl(R, X), but the number of objects, which are required to be designed as
the solution of the analysed problem, is an exponent or some sub-exponent of n
and m. This situation can be illustrated as follows.
→
− or →
− dir
Example 5. It can be proved that for all X ∈ {G, G , G } and for all data
structures R the following problems are elements of the set Lcl(R, X):
1. The problem of the design of some the shortest path between the given
two vertices in G ∈ X(n).
2. The problem of the design of some Hamiltonian path between the given
two vertices in G ∈ X(n).
3. The problem of the design of some Hamiltonian cycle in G ∈ X(n).
4. The problem of the design of some cycle that visits the given vertex in
G ∈ X(n).
5. The problem of the design of some spanning tree in G ∈ X(n).
6. The problem of the design of some minimum spanning tree in G ∈ X(n).
On the base of estimation the number of objects which can be designed
→
− or →
− dir
in each of listed above case, it can be proved that for all X ∈ {G, G , G }
and for all data structures R the following problems are elements of the set
Work-Lcl(R, X)\Lcl(R, X):
1. The problem of the design of the set of all shortest paths between the two
given vertices in G ∈ X(n).
2. The problem of the design of the set of all Hamiltonian path between the
given two vertices in G ∈ X(n).
3. The problem of the design of the set of all Hamiltonian cycles in G ∈ X(n).
4. The problem of the design of the set of all cycles that visit the given vertex
in G ∈ X(n).
5. The problem of the design of the set of all spanning trees in G ∈ X(n).
6. The problem of the design of the set of all minimum spanning trees in
G ∈ X(n).
5 Out of the Set Work-Lcl(R, X)
Analysis of problems pointed in the Section 4, show that each of them can be
solved by backtracking with linear space complexity. Unfortunately, there is a
wide class of problems of Discrete Mathematics and its applications, such that
the following two conditions hold:
1. Searching is the only known method of the solution of the given problem.
2. At implementation of searching there is an essential growth of lengths and
the number of the designed and analyzed sequences of objects, both (just this
factor results in exponential space complexity of searching).
All these problems formulated in terms of Graph Theory are the problems
that are out of the set Work-Lcl(R, X).
An important non-trivial subset of the above-pointed problems of Discrete
Mathematics consists of the problems that can be reduced to the design of some
strategy for walks of special type on some graph. This subset includes in itself
the problems, at least, of the following three types:
1. The problems that can be reduced to the design some unconditional, adap-
tive or cooperative strategy for some walk on the given graph, intended to iden-
tify the vertices covered by blots. In particular, to these problems can be reduced
problems of identification of states for finite automata. Interpretation of these
adaptive and cooperative strategies in terms of automata-experimenters demon-
strates high complexity for computing the values of predicates defined on graphs
by some finite automaton or some interacting group of finite automata.
2. The problems that are connected with the design of the supervisor intended
to carry out adaptive control for discrete events systems presented by finite
automata models.
3. The problems connected with the design of the winning strategies for
considerable number of two persons games on graphs.
6 Conclusions
In the given paper we have analyzed two sets of Graph Theory problems. The first
set consists of all Graph Theory problems that can be resolved by algorithms with
linear space complexity. The second set consists of all Graph Theory problems,
for which the size of the solution essentially exceeds the size of the input data,
but there exists some algorithm that operates on space linear relative to the size
of the input data, and this algorithm uses some additional memory of the same
size, intended to generate the solution sequentially, one fragment after another.
It has been illustrated that these sets consist of sufficiently wide class of
Graph Theory problems.
The carried-out analysis of sufficiently powerful algebraic systems on graphs
gave the possibility to establish a number of estimates in terms ”in average” and
”for almost all objects”.
Presented in the given paper results form some strong base for research of
the structure of the set P-Work-Space(R, X), for analysis complexity, accuracy
and efficiency of local search strategies on graphs, for investigation problems of
design different strategies for walks on graphs, etc.
References
1. Harary, F.: Graph theory. Addison-Wesley Publishing Company, Inc., Reading, MA,
USA (1969)
2. Aho, A.V., Hopcroft, J.E., and Ullman, J.D.: The design and analysis of computer
algorithm. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA (1975)
3. Bollobas, B.: Modern graph theory. Springer-Verlag, New York, Berlin, Heidelberg
(1998)