Geodesic
NP-completeness of the minimum spanning tree problem of a multiple graph of multiplicity $k \geqslant 3$
Modelirovanie i analiz informacionnyh sistem, Tome 28 (2021) no. 1, pp. 22-37.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we study undirected multiple graphs of any natural multiplicity $k > 1$. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of $k$ linked edges, which connect $2$ or $(k + 1)$ vertices correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of $k$ linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge. A multiple tree is a connected multiple graph with no cycles. Unlike ordinary trees, the number of edges in a multiple tree is not fixed. The problem of finding the spanning tree can be set for a multiple graph. Complete spanning trees form a special class of spanning trees of a multiple graph. Their peculiarity is that a multiple path joining any two selected vertices exists in the tree if and only if such a path exists in the initial graph. If the multiple graph is weighted, the minimum spanning tree problem and the minimum complete spanning tree problem can be set. Also we can formulate the problems of recognition of the spanning tree and complete spanning tree of the limited weight. The main result of this article is the proof of NP-completeness of such recognition problems for arbitrary multiple graphs as well as for divisible multiple graphs in the case when multiplicity $k \geqslant 3$. The corresponding optimization problems are NP-hard.
Keywords: multiple graph, multiple tree, spanning tree, complete spanning tree, minimum spanning tree, NP-completeness.
Mots-clés : divisible graph 
@article{MAIS_2021_28_1_a1,
     author = {A. V. Smirnov},
     title = {NP-completeness of the minimum spanning tree problem of a multiple graph of multiplicity $k \geqslant 3$},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {22--37},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2021_28_1_a1/}
}
TY  - JOUR
AU  - A. V. Smirnov
TI  - NP-completeness of the minimum spanning tree problem of a multiple graph of multiplicity $k \geqslant 3$
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2021
SP  - 22
EP  - 37
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2021_28_1_a1/
LA  - ru
ID  - MAIS_2021_28_1_a1
ER  - 
%0 Journal Article
%A A. V. Smirnov
%T NP-completeness of the minimum spanning tree problem of a multiple graph of multiplicity $k \geqslant 3$
%J Modelirovanie i analiz informacionnyh sistem
%D 2021
%P 22-37
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2021_28_1_a1/
%G ru
%F MAIS_2021_28_1_a1
A. V. Smirnov. NP-completeness of the minimum spanning tree problem of a multiple graph of multiplicity $k \geqslant 3$. Modelirovanie i analiz informacionnyh sistem, Tome 28 (2021) no. 1, pp. 22-37. http://geodesic.mathdoc.fr/item/MAIS_2021_28_1_a1/

[1] A. V. Smirnov, “The shortest path problem for a multiple graph”, Automatic Control and Computer Sciences, 52:7 (2018), 625–633 | DOI | MR

[2] A. V. Smirnov, “The spanning tree of a divisible multiple graph”, Automatic Control and Computer Sciences, 52:7 (2018), 871–879 | DOI | MR

[3] J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem”, Proceedings of the American Mathematical Society, 7:1 (1956), 48–50 | DOI | MR | Zbl

[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, 3rd, The MIT Press, McGraw-Hill Book Company, 2009 | MR

[5] C. Berge, Graphs and hypergraphs, North-Holland Publishing Company, 1973 | MR | Zbl

[6] A. Basu, R. W. Blanning, “Metagraphs in workflow support systems”, Decision Support Systems, 25:3 (1999), 199–208 | DOI

[7] A. Basu, R. W. Blanning, Metagraphs and their applications, Integrated Series in Information Systems, 15, Springer US, 2007 | Zbl

[8] V. S. Rublev, A. V. Smirnov, “Flows in multiple networks”, Yaroslavsky Pedagogichesky Vestnik, 3:2 (2011), 60–68

[9] A. V. Smirnov, “The problem of finding the maximum multiple flow in the divisible network and its special cases”, Automatic Control and Computer Sciences, 50:7 (2016), 527–535 | DOI

[10] L. R. Ford, D. R. Fulkerson, Flows in networks, Princeton University Press, 1962 | MR | Zbl

[11] V. S. Roublev, A. V. Smirnov, “The problem of integer-valued balancing of a three-dimensional matrix and algorithms of its solution”, Modeling and Analysis of Information Systems, 17:2 (2010), 72–98 | MR

[12] A. V. Smirnov, “Network model for the problem of integer balancing of a four-dimensional matrix”, Automatic Control and Computer Sciences, 51:7 (2017), 558–566 | DOI

[13] M. R. Garey, D. S. Johnson, Computers and intractability: a guide to the theory of np-completeness, W. H. Freeman and Company, 1979 | MR | Zbl

[14] R. Karp, Complexity of computer computations, eds. R. E. Miller, J. W. Thatcher \title Reducibility among combinatorial problems, Plenum, 1972, 85–103 | DOI | MR | Zbl