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

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

Вялый М. Н., Карпов В. Е.
Дискретный анализ и исследование операций, 30, 3, 81-95 (2023)
Скачать статью

УДК 519.171 
DOI: 10.33048/daio.2023.30.757

Аннотация:

Изучается задача реализации гиперграфа на графе с условием, что каждое ребро гиперграфа реализуется подграфом, в котором ровно две вершины имеют нечётную степень. Установлена связь такой задачи реализации гиперграфов и гипотезы о двойном покрытии циклами. Доказана алгоритмическая трудность проверки существования реализации в различных постановках: реализации на всех графах, на простых графах и на графах из нескольких очень узких классов. 
Библиогр. 11.

Литература:
  1. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990.
     
  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. 1984. V. 13, No. 3. P. 566–579.
     
  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). Heidelberg: Springer, 2010. P. 345–356. (Lect. Notes Comput. Sci.; V. 5849).
     
  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). Heidelberg: Springer, 2011. P. 201–211. (Lect. Notes Comput. Sci.; V. 6460).
     
  5. Johnson D. S., Pollak H. O. Hypergraph planarity and the complexity of drawing Venn diagrams // J. Graph Theory. 1987. V. 11, No. 3. P. 309–325.
     
  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). Heidelberg: Springer, 2011. P. 20–33. (Lect. Notes Comput. Sci.; V. 6460).
     
  7. Szekeres G. Polyhedral decompositions of cubic graphs // Bull. Aust. Math. Soc. 1973. V. 8. P. 367–387.
     
  8. Seymour P. D. Sums of circuits // Graph theory and related topics. New York: Acad. Press, 1979. P. 341–355.
     
  9. Zhang C. Q. Integer flows and cycle covers of graphs. New York: Marcel Dekker, 1997.
     
  10. Дистель Р. Теория графов. Новосибирск: Изд-во Ин-та математики, 2002. 336 с.
     
  11. Tarsi M. Semi-duality and the cycle double cover conjecture // J. Comb. Theory. Ser. B. 1986. V. 41, No. 3. P. 332–340.

Работа первого автора выполнена при поддержке Программы фундаментальных исследований НИУ ВШЭ, а также в рамках государственного задания ФИЦ ИУ РАН (проект № 0063–2019–0003).

Вялый Михаил Николаевич
  1. Московский физико-технический институт (гос. университет), 
    Институтский пер., 9, 141701 Долгопрудный, Россия
  2. Федеральный исследовательский центр «Информатика и управление» РАН, 
    ул. Вавилова, 42, 119333 Москва, Россия
  3. Национальный исследовательский университет «Высшая школа экономики», 
    Покровский б-р, 11, 109028 Москва, Россия

E-mail: vyalyi@gmail.com

Карпов Владимир Евгеньевич
  1. Московский физико-технический институт (гос. университет), 
    Институтский пер., 9, 141701 Долгопрудный, Россия

E-mail: ve.karpov@yandex.ru

Статья поступила 21 ноября 2022 г. 
После доработки — 27 февраля 2023 г. 
Принята к публикации 3 марта 2023 г.

Abstract:

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.

References:
  1. V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lectures on Graph Theory (Nauka, Moscow, 1990 [Russian]; B. I. Wissenschaftsverlag, Mannheim, 1994).
     
  2. R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput. 13 (3), 566–579 (1984).
     
  3. K. Buchin, M. van Kreveld, H. Meijer, B. Speckmann, and K. Verbeek, On planar supports for hypergraphs, in Graph Drawing (Rev. Pap. 17th Int. Symp., Chicago, USA, Sept. 22–25, 2009) (Springer, Heidelberg, 2010), pp. 345–356 (Lect. Notes Comput. Sci., Vol. 5849).
     
  4. U. Brandes, S. Cornelsen, B. Pampel, and A. Sallaberry, Blocks of hypergraphs: Applied to hypergraphs and outerplanarity, in Combinatorial Algorithms (Rev. Sel. Pap. 21st Int. Workshop, London, UK, July 26–28, 2010) (Springer, Heidelberg, 2011), pp. 201–211 (Lect. Notes Comput. Sci., Vol. 6460).
     
  5. D. S. Johnson and H. O. Pollak, Hypergraph planarity and the complexity of drawing Venn diagrams, J. Graph Theory 11 (3), 309–325 (1987).
     
  6. U. Brandes, S. Cornelsen, B. Pampel, and A. Sallaberry, Path-based supports for hypergraphs, in Combinatorial Algorithms (Rev. Sel. Pap. 21st Int. Workshop, London, UK, July 26–28, 2010) (Springer, Heidelberg, 2011), pp. 20–33 (Lect. Notes Comput. Sci., Vol. 6460).
     
  7. G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Aust. Math. Soc. 8, 367–387 (1973).
     
  8. P. D. Seymour, Sums of circuits, in Graph Theory and Related Topics (Acad. Press, New York, 1979), pp. 341–355.
     
  9. C. Q. Zhang, Integer Flows and Cycle Covers of Graphs (Marcel Dekker, New York, 1997).
     
  10. R. Diestel, Graph Theory (Springer, Heidelberg, 2000; Izd. Inst. Mat., Novosibirsk, 2002 [Russian]).
     
  11. M. Tarsi, Semi-duality and the cycle double cover conjecture, J. Comb. Theory, Ser. B, 41 (3), 332–340 (1986).