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.

Bibliographie

[1] Matiyasevich Y. V., “Diophantineity of enumerable sets”, Doklady Akademii Nauk USSR, 191:2 (1970), 279–282 (in Russian) | Zbl

[2] Fischer M. J., Rabin M. O., “Super-exponential complexity of Presburger arithmetic”, Proc. SIAM-AMS Symp. Appl. Math., 7 (1974), 27–41

[3] Mayr E. W., Meyer A. R., “The complexity of the word problems for commutative semigroups and polynomial ideals”, Adv. Math., 46:3 (1982), 305–329 | DOI | Zbl

[4] Cook S. A., “The complexity of theorem proving procedures”, Proc. 3rd Ann. ACM Symp. on Theory of Computing, 1971, 151–158 | Zbl

[5] Daniyarova E. Y., Myasnikov A. G., Remeslennikov V. N., Algebraic Geometry over Algebraic Structures, SB RAS Publishing House, Novosibirsk, 2016, 243 pp. (in Russian)

[6] Nikitin A. Y., Rybalov A. N., “On complexity of the satisfiability problem of systems over finite posets”, Prikladnaya Diskretnaya Matematika, 2018, no. 39, 94–98 (in Russian) | Zbl

[7] Rybalov A. N., “On complexity of the existential and universal theories of finite fields”, Prikladnaya Diskretnaya Matematika, 2019, no. 45, 85–89 (in Russian) | Zbl

[8] Ilev A. V., “Decidability of universal theories and axiomatizability of hereditary classes of graphs”, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 22, no. 1, 2016, 100–111 (in Russian)

[9] Ilev A. V., Remeslennikov V. N., “Study of the compatibility of systems of equations over graphs and finding their general solutions”, Vestnik Omskogo Universiteta, 2017, no. 4(86), 26–32 (in Russian)

[10] Gorbunov V. A., Algebraic Theory of Quasivarieties, Plenum, New York, 1998, 298+xii pp.

[11] Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co, San Francisco, 1979, 338+x pp. | Zbl

[12] Fomin F. V., Grandoni F., Kratsch D., “A measure $\$ conquer approach for the analysis of exact algorithms”, J. ACM, 56:5 (2009), 25–32 | DOI | Zbl

[13] Van Rooij J. M. M., Nederlof J., van Dijk T. C., “Inclusion/exclusion meets measure and conquer: Exact algorithms for counting dominating sets”, LNCS, 5757, 2009, 554–565 | Zbl