Geodesic
Hypergraph edge representations with the use of homological paths
Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 3, pp. 81-95 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2023},
     volume = {30},
     number = {3},
     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
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
%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/

[1] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994 | MR | MR | Zbl

[2] Tarjan R. E., Yannakakis M., “Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs”, SIAM J. Comput., 13:3 (1984), 566–579 | DOI | MR | Zbl

[3] Buchin K., van Kreveld M., Meijer H., Speckmann B., Verbeek K., “On planar supports for hypergraphs”, Graph drawing. Rev. Pap. 17th Int. Symp. (Chicago, USA, Sept. 22–25, 2009), Lect. Notes Comput. Sci., 5849, Springer, Heidelberg, 2010, 345–356 | DOI | MR | Zbl

[4] Brandes U., Cornelsen S., Pampel B., Sallaberry A., “Blocks of hypergraphs: Applied to hypergraphs and outerplanarity”, Combinatorial algorithms, Rev. Sel. Pap. 21st Int. Workshop (London, UK, July 26–28, 2010), Lect. Notes Comput. Sci., 6460, Springer, Heidelberg, 2011, 201–211 | DOI | MR | Zbl

[5] Johnson D. S., Pollak H. O., “Hypergraph planarity and the complexity of drawing Venn diagrams”, J. Graph Theory, 11:3 (1987), 309–325 | DOI | MR | Zbl

[6] Brandes U., Cornelsen S., Pampel B., Sallaberry A., “Path-based supports for hypergraphs”, Combinatorial algorithms, Rev. Sel. Pap. 21st Int. Workshop (London, UK, July 26–28, 2010), Lect. Notes Comput. Sci., 6460, Springer, Heidelberg, 2011, 20–33 | DOI | MR | Zbl

[7] Szekeres G., “Polyhedral decompositions of cubic graphs”, Bull. Aust. Math. Soc., 8 (1973), 367–387 | DOI | MR | Zbl

[8] Seymour P. D., “Sums of circuits”, Graph theory and related topics, Acad. Press, New York, 1979, 341–355 | MR

[9] Zhang C. Q., Integer flows and cycle covers of graphs, Marcel Dekker, New York, 1997 | MR

[10] R. Diestel, Graph Theory, Springer, Heidelberg, 2000 | MR

[11] Tarsi M., “Semi-duality and the cycle double cover conjecture”, J. Comb. Theory. Ser. B, 41:3 (1986), 332–340 | DOI | MR | Zbl