This article is cited in 4 papers

Applied Graph Theory

Algorithms for solving systems of equations over various classes of finite graphs

A. V. Il'ev^a, V. P. Il'ev<sup>b

a</sup> Sobolev Institute of Mathematics SB RAS, Omsk, Russia
^b Dostoevsky Omsk State University, Omsk, Russia

Abstract: The aim of the paper is to study and to solve finite systems of equations over finite undirected graphs. Equations over graphs are atomic formulas of the language ${\rm L}$ consisting of the set of constants (graph vertices), the binary vertex adjacency predicate and the equality predicate. It is proved that the problem of checking compatibility of a system of equations $S$ with $k$ variables over an arbitrary simple $n$-vertex graph $\Gamma$ is $\mathcal{NP}$-complete. The computational complexity of the procedure for checking compatibility of a system of equations $S$ over a simple graph $\Gamma$ and the procedure for finding a general solution of this system is calculated. The computational complexity of the algorithm for solving a system of equations $S$ with $k$ variables over an arbitrary simple $n$-vertex graph $\Gamma$ involving these procedures is $O(k^2n^{k/2+1}(k+n)^2)$ for ${n \geq 3}$. Polynomially solvable cases are distinguished: systems of equations over trees, forests, bipartite and complete bipartite graphs. Polynomial time algorithms for solving these systems with running time $O(k^2n(k+n)^2)$ are proposed.

Keywords: graph, system of equations, computational complexity.

UDC: 510.52, 510.67, 519.17

DOI: 10.17223/20710410/53/6

Bibliographic databases:

• 
•