• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Представления ребер гиперграфов обобщенными путями
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
September 18, 2026
When Pictures Hinder Understanding: Illustrations May Impede Learning of Abstract Ideas
Illustrations can help remember specific actions but do not always make abstract ideas easier to learn. Researchers from HSE University and Humboldt University compared how people learn from texts with different levels of abstractness. They found that participants remembered illustrations better and performed better on related tasks after reading a multimedia text about yoga asanas than after reading an abstract text about the Nash equilibrium. The findings could help improve the selection of illustrations for educational and informational materials. The study has been published in Learning and Instruction.
September 17, 2026
'I Wish That People Would Place Greater Trust in Science'
When Tatiana Eremicheva chose Fundamental and Computational Linguistics as her field of study, she thought it would be about learning languages. Instead, she discovered it was about helping people. In this interview for the HSE Young Scientists project, she discusses science as a way of understanding the world, billiards as a team-building activity, and why learning to read is not always as easy as it seems.
September 15, 2026
Immunity to Chaos: How Personal Resources Help Us Cope with the Challenges of a Turbulent World
International conflicts, crises and digital overload—the modern world puts our minds to the test every day. Traditional psychology often focuses on the consequences: anxiety, depression, and psychosomatic disorders. But what if we looked at the problem differently—through the lens of the resources that prevent us from breaking down? Psychological immunity is precisely this set of resources. Alena Zolotareva and her group, Psychological Immunity as a Resource for Positive Functioning, are developing an integrative model of this phenomenon, adapting diagnostic tools and preparing for large-scale empirical research. Why do psychologists need to collaborate with medical professionals, and how could their research transform preventive care in clinics and corporations?

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Представления ребер гиперграфов обобщенными путями

Дискретный анализ и исследование операций. 2023. Т. 30. № 3(157). С. 81–95.
Vyalyi M., Карпов В. Е.

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.

Research target: Mathematics Computer Science
Language: Russian
DOI
Keywords: гиперграфNP-полнотаEulerian graphs hypergraphcycle cover NP-completenessпокрытие цикламиэйлеров граф
Publication based on the results of:
Mathematical methods inthe studies of definitional complexity, computational complexity and formal language (2023)
Similar publications
Some rigidity results for static three-manifolds with boundary and positive scalar curvature
Medvedev V., Annals of Global Analysis and Geometry 2026 Vol. 70 No. 2 P. 8–23
This paper studies three-dimensional compact static manifolds with boundary and positive scalar curvature. We prove that, under a suitable bound on the Ricci curvature, the orientable quotient of the Nariai static manifold with boundary  is the only such manifold with connected boundary, provided that the zero-level set of the potential is connected and does not intersect ...
Added: September 19, 2026
Improving the Accuracy of Automatic Wildlife Detection in Nature Reserves Using Infrared Imaging
Aleksei Samarin, Alexander Savelev, Aleksei Toropov et al., Pattern Recognition and Image Analysis 2026 Vol. 36 No. 2 P. 323–334
In this paper, an improved approach for automatic wildlife detection in natural environments based on the integration of a neural network architecture with a two-stream attention mechanism and a novel preclassification step based on infrared data has been presented. The proposed method addresses one of the key challenges in environmental monitoring: the need for scalable ...
Added: September 19, 2026
IDAP++: Advancing Divergence-Aware Pruning with Joint Filter and Layer Optimization
Aleksei Samarin, Nazarenko A., Kotenko E. et al., Proceedings of the ACM on Management of Data, USA 2026 Vol. 4 No. 1 P. 1–28
Modern knowledge and large volumes of data are increasingly encoded within neural networks, making the task of simplifying their structures and reducing the number of parameters especially relevant, both to improve efficiency and to facilitate deployment in resource-constrained environments. This paper presents a novel approach to neural network compression that addresses redundancy at both the ...
Added: September 19, 2026
Automated Feature Engineering-Based Approach for Micrococci Microscopic Image Classification and Taxonomic Characteristics Determination
Aleksei Samarin, Alexander Savelev, Aleksei Toropov et al., Pattern Recognition and Image Analysis 2025 Vol. 35 No. 2 P. 148–158
This paper describes our research on creating classifiers for microbial images (micrococci microscopy images) obtained from pictures of unfixed microscopic scenes. In our work, we propose an AutoML approach based on the automatic generation and analysis of the feature space for constructing the most optimal descriptors of microorganism images for subsequent classification. This makes it ...
Added: September 19, 2026
Improvement in Microbial Classification Quality Using Synthetic Microscopic Images Generated by Large Visual-Language Models
Aleksei Samarin, Alexander Savelev, Aleksei Toropov et al., Pattern Recognition and Image Analysis 2026 Vol. 36 No. 2 P. 302–312
The lack of annotated microscopic datasets remains a major obstacle to training robust deep learning models for microbial classification. In this paper, a novel data augmentation pipeline that uses visual–linguistic large-scale models to generate synthetic microscopic images of six different bacterial and nonbacterial classes has been proposed. Synthetic samples have gradually been added to the ...
Added: September 19, 2026
Advances in Neural Computation, Machine Learning, and Cognitive Research IX
Springer, Cham, 2026.
computer vision ...
Added: September 19, 2026
Proceedings of 18th International Conference on Machine Learning and Computing
Springer, Cham, 2026.
Added: September 19, 2026
Proceedings of the 35th Conference of Open Innovations Association FRUCT
FRUCT Oy, 2024.
Added: September 19, 2026
Proceedings of the 36th Conference of Open Innovations Association FRUCT
FRUCT Oy, 2024.
Added: September 19, 2026
Proceedings of the 37th Conference of Open Innovations Association FRUCT
FRUCT Oy, 2025.
Added: September 19, 2026
Proceedings of the 39th Conference of Open Innovations Association FRUCT
FRUCT Oy, 2026.
Added: September 19, 2026
Flow-Guided Neural Pruning: Signal-Flow Framework for Multi-Architecture Model Compression
Aleksei Samarin, Nazarenko A., Kotenko E. et al., Machine Learning and Knowledge Extraction 2026 Vol. 8 No. 8 P. 1–26
This paper presents a novel method for pruning deep neural networks based on the concept of flow, derived from the continuous modeling of signal propagation across layers. We derive flow functions for fully connected, convolutional, and self-attention architectures, and we propose a new iterative pruning algorithm, Iterative Flow-Aware Pruning (IFAP), that leverages these measures to ...
Added: September 19, 2026
NP-полнота игры “Ханаби” при минимальных параметрах
Onoprienko A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216
We study the algorithmic complexity of the cooperative card game Hanabi. The feature of Hanabi is that players see each other’s cards but not their own, and exchange information through hints. Even in the model with one player who has full information about the deck, Hanabi remains NP-hard. We found the minimal parameters ofthe game ...
Added: November 23, 2025
Hypergraph Edge Representations with the Use of Homological Paths
M. N. Vyalyi, Karpov V. E., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 3 P. 678–686
We consider the problem of realization of hypergraphs on a graph 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 ...
Added: November 30, 2023
COMPLEXITY OF LAMBEK CALCULI WITH MODALITIES AND OF TOTAL DERIVABILITY IN GRAMMARS
S. M. Dudakov, Karlov B. N., S. L. Kuznetsov et al., Algebra and Logic 2021 Vol. 60 No. 5 P. 308–326
The Lambek calculus with the unit can be defined as the atomic theory (algebraic logic) of the class of residuated monoids. This calculus, being a theory of a broader class of algebras than Heyting ones, is weaker than intuitionistic logic. Namely, it lacks structural rules: permutation, contraction, and weakening. We consider two extensions of the ...
Added: November 12, 2023
Distances in Higher-Order Networks and the Metric Structure of Hypergraphs
Vasilyeva E., Romance M., Ivan Samoylenko et al., Entropy 2023 Vol. 25 No. 6 Article 923
We explore the metric structure of networks with higher-order interactions and introduce a novel definition of distance for hypergraphs that extends the classic methods reported in the literature. The new metric incorporates two critical factors: (1) the inter-node distance within each hyperedge, and (2) the distance between hyperedges in the network. As such, it involves ...
Added: July 28, 2023
Структурные и алгоритмические свойства максимальных диссоциирующих множеств в графах
Дугинов О. И., Кускова Б. М., Malyshev D. et al., Труды института математики и механики УрО РАН 2022 Т. 28 № 2 С. 114–142
Подмножество вершин графа называется диссоциирующим, если степени вершин подграфа, порожденного этим подмножеством, не превосходят 1. Диссоциирующее множество максимально, если оно не содержится ни в каком другом диссоциирующем множестве с бо́льшим числом вершин. В данной работе предлагаются оценки наибольшего (наименьшего) числа вершин в максимальном диссоциирующем множестве графа. Доказано, что задача нахождения максимального диссоциирующего множества наибольшей мощности ...
Added: September 19, 2022
On the strong chromatic number of a random 3-uniform hypergraph
Balobanov A., Shabanov D. A., Discrete Mathematics 2021 Vol. 344 No. 3 Article 112231
This paper deals with estimating the threshold for the strong -colorability of a random 3-uniform hypergraph in the binomial model H(n,3,p). A vertex coloring is said to be strong for a hypergraph if every two vertices sharing a common edge are colored with distinct colors. It is known that the threshold corresponds to the sparse ...
Added: November 27, 2020
О предписанном хроматическом числе полных многодольных гиперграфов и кратных покрытиях независимыми множествами
Shabanov D. A., Шайхеева Т. М., Математические заметки 2020 Т. 107 № 3 С. 454–465
This paper deals with list colorings of uniform hypergraphs. Let H(m, r, k) be the complete r-partite k-uniform hypergraph with parts of equal size m in which each edge contains exactly one vertex from some k ≤ r parts. Using results on multiple covers by independent sets, we establish that, for fixed k and r, ...
Added: June 14, 2020
Полноцветные раскраски случайных гиперграфов
Shabanov D. A., Крохмаль Н. Е., Кравцов Д. А., Дискретная математика 2019 Т. 31 № 2 С. 84–113
Работа посвящена изучению пороговой вероятности наличия полноцветной раскраски в r цветов у случайного k-однородного гиперграфа в биномиальной модели H(n,k,p), т.е. такой раскраски, что каждое ребро гиперграфа содержит вершины всех r цветов. Показано, что данная пороговая вероятность при фиксированных r<k и растущем n отвечает разреженному случаю, т.е. случаю линейного среднего числа ребер cn для положительного фиксированного ...
Added: June 5, 2019
Оценка сложности проверки гипотезы о временном диктаторе с положительно-однородной функцией полезности
Klemashev N., Шананин А. А., Труды Московского физико-технического института 2015 Т. 7 № 4 С. 17–27
We prove NP-completeness of nonparametric test for the model of temporal dictator with several dictators with positively-homogeneous utility functions. ...
Added: March 5, 2019
Дискретная математика. Алгоритмы: теория и практика.
Avdoshin S. M., Набебин А. А., М.: ДМК Пресс, 2019.
The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms,  operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite ...
Added: August 24, 2018
Colourings of uniform hypergraphs with large girth and applications
Shabanov D. A., Kupavskii A., Combinatorics Probability and Computing 2018 Vol. 27 No. 2 P. 245–273
This paper deals with a combinatorial problem concerning colourings of uniform hypergraphs with large girth. We prove a new lower bound for the maximum edge degree for an n-uniform non-r-colourable simple hypergraph. As an application of our probabilistic technique we establish a lower bound for the classical van der Waerden number W(n, r), the minimum natural N ...
Added: February 22, 2018
О числе независимых множеств в простых гиперграфах
Shabanov D. A., Балобанов А. Е., Математические заметки 2018 Т. 103 № 1 С. 38–48
В работе исследуются экстремальные задачи о числе j-независимых множеств в однородных простых гиперграфах. Получены близкие к оптимальным результаты для максимального количества независимых множеств в классе простых регулярных гиперграфов, а также для минимального числа - в классе простых гиперграфов с заданной средней степенью вершины. ...
Added: February 13, 2018
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit