Том 28, номер 4, 2021 г., Стр. 117-124

УДК 519.178
Ключиков А. Г., Вялый М. Н.
Win-win алгоритм для задачи $(k + 1)-LST/k$-путевого представления

Аннотация:
Описывается win-win алгоритм, строящий за полиномиальное от |$V (G)$| и $k$ время для любого графа $G$ и любого натурального числа $k$ либо остовное дерево с хотя бы $k + 1$ листьями, либо предоставляет путевое представление (path decomposition) ширины не большей $k$. Данный алгоритм оптимален в силу следствия теоремы о путевом представлении [1].
Библиогр. 5.

Ключевые слова: путевое представление, остовное дерево, задача $k$-LST, win-win алгоритм, параметрическая сложность.

DOI: 10.33048/daio.2021.28.710

Ключиков Артём Геннадиевич ¹
Вялый Михаил Николаевич ^1,2,3
1. Московский физико-технический институт (гос. университет),
Институтский пер., 9, 141701 Долгопрудный, Россия
2. Федеральный исследовательский центр «Информатика и управление» РАН,
ул. Вавилова, 44, корп. 2, 119333 Москва, Россия
3. Национальный исследовательский университет «Высшая школа экономики»,
Покровский б-р, 11, 109028 Москва, Россия
е-mail: klyuchikov@phystech.edu, vyalyi@gmail.com

Статья поступила 12 апреля 2021 г.
После доработки — 2 августа 2021 г.
Принята к публикации 3 августа 2021 г.

Литература

[1] Bienstock D., Robertson N., Seymour P. D., Thomas R. Quickly excluding a forest // J. Comb. Theory, Ser. B. 1991. Vol. 52. P. 274–283.

[2] Douglas R. J. NP-completeness and degree restricted spanning trees // Discrete Math. 1992. Vol. 105, No. 1–3. P. 41–47.

[3] Kashiwabara T., Fujisawa T. NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph // Proc. 1979 Int. Symp. Circuits and Systems (Tokyo, Japan, July 17–19, 1979). New York: IEEE, 1979. P. 657–660.

[4] Bodlaender H. L., Demaine E. D., Fellows M. R. [et al.]. Open problems in parameterized and exact computation—IWPEC 2008. Technical Report UU–CS–2008–017. Utrecht: Utrecht Univ., 2008. Available at http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-017.pdf (accessed Aug. 3, 2021).

[5] Diestel R. Graph minors I: A short proof of the path-width theorem // Comb. Prob. Comput. 1995. Vol. 4, No. 1. P. 27–30.