Том 24, номер 1, 2017 г., Стр. 81-96

УДК 519.17
Малышев Д. С.
Критические элементы в комбинаторно замкнутых семействах классов графов

Аннотация:
Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До результатов настоящей работы имелся пример только одной задачи на графах, для которой в семействе сильно наследственных классов выявлены граничные классы. Более того, в семействе минорно замкнутых классов ни для одной задачи на графах не было известно ни одного граничного класса. В настоящей работе для обоих рассматриваемых семейств и нескольких классических задач на графах приводятся полные описания граничных классов. Для задачи 2-аддитивной аппроксимации ленточной ширины графа в семействе минорно замкнутых классов найден граничный класс, причём для двух других семейств критические классы для этой задачи не известны.
Библиогр. 21.

Ключевые слова: вычислительная сложность, наследственный класс, критический класс, эффективный алгоритм.

DOI: 10.17377/daio.2017.24.523

Малышев Дмитрий Сергеевич ^1,2
1. Национальный исследовательский университет «Высшая школа экономики»,
ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
2. Нижегородский гос. университет им. Н. И. Лобачевского,
пр. Гагарина, 23, 603950 Нижний Новгород, Россия
е-mail: dmalishev@hse.ru, dsmalyshev@rambler.ru

Статья поступила 11 января 2016 г.
Исправленный вариант — 29 апреля 2016 г.

Литература

[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 c.

[2] Малышев Д. С. Континуальные множества граничных классов графов для задач о раскраске // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 5. С. 41–51.

[3] Малышев Д. С. О минимальных сложных классах графов // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 6. С. 43–51.

[4] Малышев Д. С. Критические классы графов для задачи о рёберном списковом ранжировании // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 6. С. 59–76.

[5] Alekseev V. E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Appl. Math. 2003. Vol. 132, No. 1–3. P. 17–26.

[6] Alekseev V. E., Boliac R., Korobitsyn D. V., Lozin V. V. NP-hard graph problems and boundary classes of graphs // Theor. Comput. Sci. 2007. Vol. 389, No. 1–2. P. 219–236.

[7] Alekseev V. E., Korobitsyn D. V., Lozin V. V. Boundary classes of graphs for the dominating set problem // Discrete Math. 2004. Vol. 285, No. 1–3. P. 1–6.

[8] Arnborg S., Proskurowski A. Linear time algorithms for NP-hard problems restricted to partial $k$-trees // Discrete Appl. Math. 1989. Vol. 23, No. 1. P. 11–24.

[9] Bodlaender H. L. Dynamic programming on graphs with bounded treewidth // Automata, Languages and Programming. Proc. 15th Int. Colloq. (Tampere, Finland, July 11–15, 1988). Heidelberg: Springer-Verl., 1988. P. 105–118. (Lect. Notes Comput. Sci.; Vol. 317).

[10] Bodlaender H. L. A partial $k$-arboretum of graphs with bounded treewidth // Theor. Comput. Sci. 1998. Vol. 209, No. 1–2. P. 1–45.

[11] Boliac R., Lozin V. V. On the clique-width of graphs in hereditary classes // Algorithms and Computation. Proc. 13th Int. Symp. (Vancouver, Canada, Nov. 21–23, 2002), Heidelberg: Springer, 2002. P. 44–54. (Lect. Notes Comput. Sci.; Vol. 2518).

[12] Courcelle B., Makowsky J., Rotics U. Linear time solvable optimization problems on graphs of bounded clique-width // Theory Comput. Syst. 2000. Vol. 33, No. 2. P. 125–150.

[13] Dubey C., Feige U., Unger W. Hardness results for approximating the bandwidth // J. Comput. Syst. Sci. 2011. Vol. 77, No. 1. P. 62–90.

[14] Fellows M., Lokshtanov D., Misra N., Rosamond F., Saurabh S. Graph layout problems parameterized by vertex cover // Algorithms and Computation. Proc. 19th Int. Symp. (Gold Coast, Australia, Dec. 15–17,
2008), Heidelberg: Springer, 2008. P. 294–305. (Lect. Notes Comput. Sci., Vol. 5369).

[15] Gurski F., Wanke E. Line graphs of bounded clique-width // Discrete Math. 2007. Vol. 307, No. 22. P. 2734–2754.

[16] Kobler D., Rotics D. Edge dominating set and colorings on graphs with fixed clique-width // Discrete Appl. Math. 2003. Vol. 126, No. 2–3. P. 197–221.

[17] Miller Z. The bandwidth of caterpillar graphs // Congr. Numerantium. 1981. Vol. 33. P. 235–252.

[18] Muradian D. The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete // Theor. Comput. Sci. 2003. Vol. 307, No. 3. P. 567–572.

[19] Robertson N., Seymour P. Graph minors. V: Excluding a planar graph // J. Comb. Theory, Ser. B. 1986. Vol. 41, No. 1. P. 92–114.

[20] Robertson N., Seymour P. Graph minors. XX: Wagner’s conjecture // J. Comb. Theory, Ser. B. 2004. Vol. 92, No. 2. P. 325–357.

[21] Saxe J. B. Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time // SIAM J. Algebraic Discrete Methods. 1980. Vol. 1, No. 4. P. 363–369.