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/