Geodesic
Hypergraph edge representations with~the~use~of~homological paths
Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 3, pp. 81-95

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

We consider a problem of realization of hypergraphs on graphs provided each hyperedge is realized by a subgraph in which exactly two vertices have odd degree. This problem is related to Cycle Double Cover conjecture. We prove that checking the existence of realization is computationally hard. The hardness is proved in various settings: for realizations on all graphs, on simple graphs, and on graphs from several restricted classes. Bibliogr. 11.
Keywords: hypergraph, cycle cover, Eulerian graph, NP-completeness. 
@article{DA_2023_30_3_a3,
     author = {M. N. Vyalyi and V. E. Karpov},
     title = {Hypergraph edge representations with~the~use~of~homological paths},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {81--95},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2023_30_3_a3/}
}
TY  - JOUR
AU  - M. N. Vyalyi
AU  - V. E. Karpov
TI  - Hypergraph edge representations with~the~use~of~homological paths
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2023
SP  - 81
EP  - 95
VL  - 30
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2023_30_3_a3/
LA  - ru
ID  - DA_2023_30_3_a3
ER  - 
%0 Journal Article
%A M. N. Vyalyi
%A V. E. Karpov
%T Hypergraph edge representations with~the~use~of~homological paths
%J Diskretnyj analiz i issledovanie operacij
%D 2023
%P 81-95
%V 30
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2023_30_3_a3/
%G ru
%F DA_2023_30_3_a3
M. N. Vyalyi; V. E. Karpov. Hypergraph edge representations with~the~use~of~homological paths. Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 3, pp. 81-95. http://geodesic.mathdoc.fr/item/DA_2023_30_3_a3/