Geodesic
On complexity of solving of equations over graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 62-69 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper the computational complexity of the problem of determining the compatibility of systems of equations without constants over an arbitrary fixed finite graph is studied. In this case, the graph is fixed, and the input is an arbitrary system of equations in the graph language without constants. A criterion is given for NP-completeness and polynomial decidability of this problem. Also its generic decidability in polynomial time is proved.
Keywords: NP-completeness, generic complexity, graphs
Mots-clés : equations. 
@article{SEMR_2024_21_1_a2,
     author = {A. N. Rybalov},
     title = {On complexity of solving of equations over graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {62--69},
     year = {2024},
     volume = {21},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a2/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On complexity of solving of equations over graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 62
EP  - 69
VL  - 21
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a2/
LA  - ru
ID  - SEMR_2024_21_1_a2
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On complexity of solving of equations over graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 62-69
%V 21
%N 1
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a2/
%G ru
%F SEMR_2024_21_1_a2
A. N. Rybalov. On complexity of solving of equations over graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 62-69. http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a2/

[1] E.Y. Daniyarova, A.G. Myasnikov, V.N. Remeslennikov, Algebraic geometry over algebraic structures, SB RAS, Novosibirsk, 2016 https://ofim.oscsbras.ru/r̃emesl/articles/monography.pdf | MR

[2] P. Erdős, D.J. Kleitman, B.L. Rothschild, “Asymptotic enumeration of $K_n$-free graphs”, Colloq. Int. Teorie Comb. (Roma, 1973), v. II, 1976, 19–27 https://www.renyi.hu/p̃_erdos/1976-03.pdf | MR | Zbl

[3] M. Garey, D. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W.H. Freeman and Company, San Francisco, 1979 https://bohr.wlu.ca/hfan/cp412/references/ChapterOne.pdf | Zbl

[4] P. Hell, “Algorithmic aspects of graph homomorphisms”, Surveys in combinatorics, Proceedings of the 19th British combinatorial conference (2003), Lond. Math. Soc. Lect. Note Ser., 307, ed. Wensley, C.D., Cambridge University Press, Cambridge, 2003, 239–276 https://www.cambridge.org/core/books/abs/surveys-in-combinatorics-2003/algorithmic-aspects-of-graph-homomorphisms/93035364B458D5282B1B19E1AC39CC96 | MR | Zbl

[5] A.V. Ilev, “Decidability of universal theories and axiomatizability of hereditary classes of graphs”, Trudy Inst. Mat. i Mekh. UrO RAN, 22, no. 1, 2016, 100–111 | MR

[6] A.V. Ilev, V.N. Remeslennikov, “Study of the compatibility of systems of equations over graphs and finding their general solutions”, Vestnik Omskogo Universiteta, 2017:4(86) (2017), 26–32 https://elib.omsu.ru/issues/68/1344.php

[7] A.V. Il'ev, V.P. Il'ev, “Algorithms for solving systems of equations over various classes of finite graphs”, Prikl. Diskretn. Mat., 53 (2021), 89–102 https://journals.tsu.ru/engine/download.php?id=223284&area=files | DOI | Zbl

[8] A.V. Ilev, “Study of systems of equations over various classes of finite matroids”, Sib. Èlectron. Mat. Izv., 19:2 (2022), 1094–1102 http://semr.math.nsc.ru/v19/n2/p1094-1102.pdf | MR

[9] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain, “Generic-case complexity and decision problems in group theory, and random walks”, J. Algebra, 264:2 (2003), 665–694, arXiv: math/0203239 | DOI | MR | Zbl

[10] G.S. Makanin, “The problem of solvability of equations in a free semigroup”, Math. USSR, Sb., 32 (1977), 129–198 | DOI | MR | Zbl

[11] V.A. Roman'kov, “Universal theory of nilpotent groups”, Math. Notes, 25 (1979), 253–258 | DOI | MR | Zbl