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

A. V. Il'ev ; V. P. Il'ev

Prikladnaâ diskretnaâ matematika, no. 3 (2021), pp. 89-102

Résumé

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.

Détail

Keywords: graph, system of equations, computational complexity.