Algorithms for solving systems of equations over various classes of finite graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2021. № 53. DOI: 10.17223/20710410/53/6

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 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 Г is NP-complete. The computational complexity of the procedure for checking compatibility of a system of equations S over a simple graph Г 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 Г involving these procedures is O(k²n^k/2+1(k + n)²) for n ≥ 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²n(k + n)²) are proposed.