Исследование границ эффективной разрешимости в семействе наследственных классов графов

Изучение тех или иных классов графов уже достаточно давно составляет содержание значительной части работ по теории графов и ее приложениям. Вместе с тем, с некоторого времени наметился устойчивый интерес к исследованию не отдельных классов графов, а именно целых семейств классов графов, обладающих некоторым общим свойством [3, 22]. Одной из фундаментальных научных проблем, на решение которых направлена часть этих работ и сама постановка которых выводит на такой высокий уровень общности, является задача анализа сложности задач на графах.

Развитие теории сложности вычислений способствовало формированию фактических стандартов эффективной разрешимости и «труднорешаемости». В соответствии с этой концепцией под быстрой (эффективной) разрешимостью данной массовой задачи понимается возможность ее решения на детерминированной машине Тьюринга за время, ограниченное полиномом от длины входных данных. В то же время, имеется ряд «неподдающихся» (называемых в теории сложности NP-иолными) задач, для которых в настоящее время не получено быстрых алгоритмов. Справедливость известной гипотезы P^NP означает, что таких алгоритмов вообще не существует. Некоторые результаты данной диссертации и цитируемых в ней работ также справедливы при выполнении этого неравенства. Это условие не будет включаться явно в формулировки соответствующих утверждений.

Многие задачи теории графов, представляющие определенный теоретический и практический интерес, являются NP-полными. Одним из возможных путей преодоления алгоритмической сложности этих задач является сужение — наложение дополнительных ограничений на рассматриваемый класс графов. Иногда учет этого обстоятельства, т. е. принадлежности только определенной части класса всех графов, приводит к созданию эффективных алгоритмов. В других случаях удается доказать NP-полноту задачи для графов из того или иного класса. Вместе с тем, рассмотрение именно представительных семейств классов графов, а не отдельных классов, придает процессу поиска «простых» и «сложных» классов определенную систематичность и позволяет ставить более общие задачи, а также надеяться на обнаружение явлений общего характера. Так, переходя к рассмотрению какого-либо такого семейства, можно ставить вопрос о нащупывании линии раздела между его «простыми» и «сложными» частями.

В настоящей диссертации содержатся результаты исследования наследственных классов графов, нацеленного на решение указанной задачи демаркации. Наследственные классы, т. е. классы, замкнутые относительно изоморфизма и удаления вершин, образуют достаточно представительную совокупность — как показано в [3], это семейство является континуальным. С другой стороны, данные классы графов (и только они) допускают описание при помощи множества запрещенных порожденных подграфов. Повышенный интерес именно к таким классам, особенно к тем из них, которые задаются конечным множеством запрещенных порожденных подграфов (называемых конечно определенными), не случаен. Так, в работе [24] было введено понятие граничного класса графов и обоснована его полезность для анализа сложности задач на графах в семействе конечно определенных классов графов. Именно, любой такой класс является «сложным» для данной задачи тогда и только тогда, когда он содержит некоторый граничный для этой задачи класс. Таким образом, выявление граничных классов графов представляет определенный интерес.

В работе [24] рассматривалась задача о независимом множестве, а также класс Т — класс всех графов, у которых каждая компонента связности является деревом с не более чем 3 листьями. Там же было установлено, что этот класс является граничным для задачи о независимом множестве. Исследования по нахождению граничных классов были продолжены в статьях [25, 26], в которых помимо класса Т рассматривался еще и класс D, а также задачи, для которых эти классы являются граничными. Класс D состоит из графов, каждая компонента связности которых является либо простым путем, либо получается отождествлением всех вершин треугольника с тремя концевыми вершинами трех простых путей.

В первой главе настоящей диссертации исследуются общие свойства задач на графах, для которых два указанных класса являются граничными. Внимание именно к этому вопросу обусловлено тем обстоятельством, что к настоящему времени доказана граничность класса Т для 9 задач, а класса D для 5 задач. В данной главе понятие граничного класса уточняется и доказывается критерий граничности произвольного класса графов. Здесь также формулируются условия граничности двух рассматриваемых классов графов и на их основе к известным случаям граничности этих классов добавляется определенное количество новых. Большинство из данных примеров принадлежат списку Гэри и Джонсона [7]. В первой главе решается вопрос о мощности множества задач на графах, для которых классы Т и D — граничные одновременно. Именно, конструктивным образом доказывается, что оно несчетно. Наконец, указываются первые примеры задач, для которых классы, состоящие из графов, дополнительных к графам из Т и D, являются граничными. Результаты первой главы опубликованы в работах [5, 12, 16, 20].

До сих пор неизвестно, существуют ли граничные классы для задачи о независимом множестве, отличные от класса Т. Вопрос о существовании таких классов эквивалентен вопросу о существовании такого графа G & Т, что эта задача в наследственном классе графов, определяемом запрещенным порожденным подграфом G, не является полиномиально разрешимой [24]. О трудности проблемы говорит тот факт, что в настоящее время не известен сложностной статус указанного класса даже для случая G = Р5.

Вопросу о единственности класса Т в семействе наследственных подклассов класса план арных графов, как граничного для задачи о независимом множестве, посвящена вторая глава. В этой главе вводится понятие относительного граничного класса, обобщающее понятие просто граничного класса. Класс Т является относительным граничным в рассматриваемом случае.

Единственность класса Т эквивалентна доказательству того, что для любого G? Т задача о независимом множестве в классе планарных графов, не содержащих порожденного подграфа G, полиномиально разрешима. Хотя и здесь этого доказать не удается, имеется более значительный прогресс к достижению намеченной цели, чем в общем случае. Именно, во второй главе устанавливается полиномиальная разрешимость рассматриваемой задачи для бесконечного количества различных классов графов исследуемого типа. Эти результаты опубликованы в [4, 10, 11, 13, 27, 28].

Третья глава диссертации посвящена количественным вопросам теории граничных классов. Повышенный интерес к этой проблематике вызван выдвинутой в работе [25] гипотезой о существовании задач на графах с бесконечным множеством граничных классов. Первую часть данной главы составляет конструктивное доказательство этого предположения. Именно, для каждой из задач о 3-раскраске (вершинного и реберного варианта) указывается континуальная совокупность граничных классов графов. Там же показывается, что задачи на графах с множеством граничных классов такой мощности образуют несчетное множество. Полученные здесь результаты позволили существенно расширить совокупность классов графов, граничных хотя бы для одной задачи. Ранее она состояла из нескольких классов.

Вторая часть, в основном, посвящена обзору известных случаев полного описания множества относительных граничных классов. Эти сведения могут быть полезными при оценках мощности множества просто граничных классов или при выдвижении предположений о его строении. Данная часть завершается полным указанием рассматриваемой совокупности для ряда новых случаев. Полученные в третьей главе результаты опубликованы в [14, 15, 17, 19, 20].

Наследственный класс графов, определяемый бесконечным минимальным множеством запрещенных порожденных подграфов и содержащий некоторый граничный класс, не обязательно будет «сложным». Таким образом, для решения задачи демаркации в решетке всех наследственных классов необходимо помимо граничных опираться и на другие «экстремальные» классы. Естественными кандидатами в их число являются максимальные «простые» и минимальные «сложные» классы, т. е. тупиковые классы графов соответствующей сложности из рассматриваемой решетки. Использование понятия максимального «простого» класса графов оказывается безрезультатным. Так, в работе [24] было установлено, что ни один «простой» класс не является максимальным «простым» (правда, в [24] это утверждается только про задачу о независимом множестве, но все рассуждения из данной работы легко переносятся и на общий случай).

Четвертая глава диссертации нацелена на исследование существования минимальных «сложных» классов. Основополагающим мотивом обращения к данному вопросу являлось отсутствие какой-либо информации о таких классах графов. В первой части главы рассматривается задача распознавания принадлежности наследственному классу графов и показывается, что для любой такой NP-полной задачи нет ни одного минимального «сложного» класса. В частности, это верно при любом фиксированном к > 3 для обеих задач о fc-раскраске. Вторая часть посвящена доказательству минимальности некоторых классов для задач о списковом ранжировании. Данные классы графов для этих задач являются еще и граничными. Тем самым получен ответ на выдвинутое в работе [25] предположение о существовании «сложных» граничных классов, поскольку все известные до этого граничные классы являлись «простыми». Результаты, полученные в четвертой главе, опубликованы в работах [18, 21].

Автор работы выражает глубокую признательность своему научному руководителю проф. Владимиру Евгеньевичу Алексееву за постоянное внимание к работе, полезные советы и замечания.

1. Алексеев В. Е. О сжимаемых графах // В сб. Проблемы кибернетики, вып. 36, 1979. — Стр. 23−32.

2. Алексеев В. Е., Малышев Д. С. Классы планарных графов с полиномиально разрешимой задачей о независимом множестве // Дискретный анализ и исследование операций. — 2008. — Том 15, № 1. — Стр. 3−10.

3. Алексеев В. Е., Малышев Д. С. Критерий граничности и его применения // Дискретный анализ и исследование операций. — 2008. — Том 15, № 6.Стр. 3−11.

4. Алексеев В. Е., Таланов В. А. Графы. Модели вычислений. Алгоритмы.Н.Новгород: Из-во Нижегородского университета, 2005. — 308 Стр.

5. Гэри М., Джонсон Д. Вычислительные машины и трудпорешаемые задачи. — М.: Мир, 1982. — 416 Стр.

6. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. — М.: Наука, гл. ред. физ.-мат. лит., 1990. — 384 Стр.

7. Зыков А. А. Основы теории графов. —- М.: Наука, 1987. — 383 Стр.

8. Малышев Д. С. Граничные классы для задачи о независимом множестве в классе плапарных графов // Вестник Нижегородского университета им. Н. И. Лобачевского. Раздел «Математика». — 2007. — № 6. — Р. 165−168.

9. Малышев Д. С. Граничные классы относительно класса планарных графов для задачи о независимом множестве // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, 16−21 апреля 2007 г.), часть II. — Стр. 16−20.

10. Малышев Д. С. Граничные классы для задач на графах // Вестник Нижегородского университета им. Н. И. Лобачевского. Раздел «Математическое моделирование и оптимальное управление». — 2008. — № 6. Р. 141−146.

11. Малышев Д. С. О бесконечности множества граничных классов для задачи о 3-раскраске // Тезисы докладов XV международной конференции «Проблемы теоретической кибернетики» (Казань, 2−7 июня 2008 г.). — Стр. 79.

12. Малышев Д. С. О бесконечности множества граничных классов в задаче о реберной 3-раскраске // Дискретный анализ и исследование операций. 2009. Т.16, т. — Стр. 37−43.

13. Малышев Д. С. Граничные классы графов для некоторых задач расноз-нования // Дискретный анализ и исследование операций. — 2009.— Т.16, № 2. Стр. 85−94.

14. Малышев Д. С. О количестве граничных классов в задаче о 3-раскраске // Дискретная математика. — 2009. — Т. 21. (принято к публикации).

15. Малышев Д. С. О недавних результатах в теории граничных классов графов // Материалы VIII международной конференции «Дискретные модели в теории управляющих систем» (Моск. обл., 6−9 апреля 2009 г.).- Стр. 132−136.

16. Малышев Д. С. О минимальных сложных элементах решетки наследственных классов графов // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (Москва, 18−23 мая 2009 г.) (в печати).

17. Харари Ф. Теория графов. — М.: Мир, 1982. — 301 Стр.

18. Alekseev V. E., Korobitsyn D. V., Lozin V. V. Boundary classes of graphs for the dominating set problem // Discrete Mathematics. — 2004. — V. 285. P. 1−6.

19. Alekseev V. E., Malyshev D. S. Planar graph classes with the independent set problem solvable in polynomial time // (Russian) translation in Journal of Applied and Industrial Mathematics. 2009. — V. 3, № 1. — P. 1−5.

20. Arnborg S., Proskurowski A. Linear time algorithms for NP-hard problems, restricted to partial &-trees // Discrete Applied Mathematics. — 1989. — V. 23. P. 11−24.

21. Bodlaender H. L. Dynamic programming on graphs with bounded treewidth // Automata, Languages and Programming (Tampere, 11−15 July 1988). Proc. in Lecture Notes in Computer Science. — 1988. — V. 317. — P. 105−118.

22. Breu H., Kirkpatrick D.G. Unit disk graph recognition is NP-hard // Computational Geometry. — 1998. — V. 9. P. 3−24.

23. Chudnovsky M., Robertson N., Seymour P., Thomas R. The strong perfect graph theorem // Arm. of Math. — 2006. V. 164. — P. 51−229.

24. Courcelle В., Makowsky J. A., Rotics U. Linear time solvable optimization problems on graphs of bounded clique-width // Theory Comput. Syst. — 2000. V. 33. — P. 125−150.

25. Corneil D. G., Perl Y., Stewart L. K. A linear recognition algorithm for cographs // SIAM J. Comput. 1985. — V. 14. — P. 926−934.

26. Dereniowski D. The complexity of list ranking of trees // Ars Combinatoria.- 2008. V. 86. — P. 97−114.

27. Faria L., Figueiredo С. H., Gravier S., Mendonga C. F. X., Stolfi J. On maximum planar induced subgraphs // Discrete Applied Mathematics. — 2006. V. 154. — P. 1774−1782.

28. Faria L., Figueiredo С. H., Mendonga C. F. X. Splitting number is NP-complete // Discrete Applied Mathematics. — 2001. — V. 108. — P. 65−83.38| Gallai T. Transitiv orientierbare graphen // Acta Math. Acad. Sci. Hung. — 1967. V. 18. — P. 25−66.

29. Hladky J. Structural properties of graphs — probabilistic and deterministic point of view (Biparite subgraphs in a random cubic graph) // Bachelor’s degree thesis, Department of Applied Mathematics, Charles University in Prague, 2006.

30. Holyer I. The NP-completeness of edge-coloring // SIAM J. Comput. — 1981. V. 10, m. P. 718−720.

31. Jamison R.E. Coloring parameters associated with rankings of graphs // Congressus Numerantum. — 2003. V. 164. — P. 111−127.

32. Kochol M., Lozin V., Randerath B. The 3-colorability problem on graphs with maximum degree four// SIAM J.Comput. — 2003. — V. 32, № 5. — P. 1128−1139.

33. Ladner R. E. The computational complexity of provability in systems of modal prepositional logic // SIAM J. Comput. — 1977. — V. 6. — P. 467−480.

34. Lozin V. V. Boundary classes of planar graphs // Combinatorics, Probability and Computing. 2008. — V. 17. — P. 287−295.

35. Lozin V. V., Rautenbach D. On the band-, treeand clique-width of graphs with bounded vertex degree // Discrete Mathematics. — 2004. — V. 18. — P. 195−206.

36. Lozin V. V., Millanic M. Maximum independent sets in graphs of low degree // Proceedings of the ACM-SIAM symposium on descrete algorithms (New Orleans, 7−9 January 2007). P. 874−880.

37. Middendorf M., Pfeiffer F. On the complexity of the disjoint path problem // Combinatorica. 1993. — V. 13, K°- 1. — P. 97−107.

38. Minty G. J. On maximal independent sets in claw-free graphs // J. Cornbin Theory, Series B. 1980. — V. 28, № 3. — P. 284−304.

39. Muradian D. The bandwidth minimization problem for cyclic caterpillars with hairs length 1 is NP-complete // Theoretical Computer Science. — 2003. — V. 307. P. 567−572.

40. Roussopoulos N. A max{m, n} algorithm for determining the graph H from its line graph G // Information Processing Letters. — 1973. V. 2, № 4. — P. 108−112.

41. Robertson N., Seymour P. Graph minors. III. Planar tree-width // J. Combin. Theory, Series B. 1986. — V. 41. — P. 92−114.

42. Scheffier P. A practical linear algorithm for vertex disjoint path in graphs with bounded treewidth // Technical report № 396, Department of Mathematics, Technische Universitat Berlin. — 1994. — P. 21.

43. Sprague A.P. An 0(n^opn)-algorithm for bandwidth of interval graphs // J. Discr. Math. 1994. — V. 9. — P. 213- 220.