Algorithms for solving systems of equations over various classes of finite graphs
Prikladnaâ diskretnaâ matematika, no. 3 (2021), pp. 89-102
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{PDM_2021_3_a5,
author = {A. V. Il'ev and V. P. Il'ev},
title = {Algorithms for solving systems of equations over various classes of finite graphs},
journal = {Prikladna\^a diskretna\^a matematika},
pages = {89--102},
publisher = {mathdoc},
number = {3},
year = {2021},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/PDM_2021_3_a5/}
}
A. V. Il'ev; V. P. Il'ev. Algorithms for solving systems of equations over various classes of finite graphs. Prikladnaâ diskretnaâ matematika, no. 3 (2021), pp. 89-102. http://geodesic.mathdoc.fr/item/PDM_2021_3_a5/