Исследование количественных и сложностных характеристик наследственных классов графов

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

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

Похоже обстоит дело с проблемой экономного представления графов. Если принять в качестве стандарта кодирование графов словами двухбуквенного алфавита, то любой (обыкновенный) граф с п вершинами может быть представлен словом длины п{п — 1) / 2. При отсутствии какой-либо априорной информации о кодируемых графах такое представление оптимально по длине слова, если же мы имеем дело с графами из некоторого более узкого класса, чем класс всех графов, то, вообще говоря, их можно закодировать более короткими словами. Возможность сжатия определяется мощностными характеристиками класса. Необходимо также принимать во внимание трудоемкость алгоритмов кодирования и декодирования. Например, дерево с п вершинами можно представить двоичным словом длины (и-2)[1о§ 2 л] при достаточно эффективном кодировании и декодировании. Для отдельных классов графов могут быть разработаны индивидуальные методы экономного кодирования, но теоретический анализ проблемы кодирования требует рассмотрения представительных семейств классов графов.

Настоящая диссертация содержит результаты исследования наследственных классов графов, ориентированного на решение двух упомянутых проблем. Наследственные классы, т. е. классы, замкнутые относительно операций переименования и удаления вершин, образуют достаточно представительное семейство — оно континуально, содержит многие известные классы, включает такие известные семейства, как семейство всех монотонных классов [31] (здесь называемых сильно наследственными) и семейство всех минорно замкнутых классов. Наследственные классы и только они допускают описание заданием множества запрещенных порожденных подграфов — способ описания, распространенный в теории графов. Представленные в работе результаты относятся к трем направлениям: исследование количественных характеристик наследственных классов, анализ сложности задач на графах из наследственных классов и кодирование графов из наследственных классов.

В вопросах количественного анализа наследственных классов в работе принят асимптотический подход, основанный на понятии энтропии множества графов. Энтропия представляет собой «логарифмическую плотность» — предел отношения логарифмов числа графов с п вершинами в данном множестве и числа всех графов с п вершинами. Существование этого предела является одним из общих свойств наследственных классов. Это и некоторые другие свойства наследственных классов аналогичны свойствам инвариантных классов булевых функций, введенных и изученных С. В. Яблонским [25]. Имеются, однако, и существенные различия между этими двумя семействами. Так, С В. Яблонский доказал, что параметр, аналогичный энтропии наследственных классов, для инвариантных классов может принимать любые вещественные значения в интервале [0,1]. Для наследственных классов, как выяснилось, множество значений энтропии счетно.

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

Если энтропия класса графов положительна, то она дает асимптотику логарифма числа графов с п вершинами в этом классе. В случае же, когда энтропия равна нулю, можно лишь заключить, что этот логарифм растет медленнее, чем п 2 и для установления асимптотики требуется более глубокое исследование. В [9] доказано, что если логарифм числа графов с п вершинами в некотором наследственном классе растет не быстрее, чем п log п, то эта функция по порядку совпадает с одной из функций 1, log л, n, nogn. Найдены минимальные классы для каждого из четырех типов поведения и получены полные структурные описания для первых трех. Изложение этих результатов составляет содержание главы 3.

Вопросам алгоритмической сложности посвящены главы 4 и 5. В них рассматривается одна из классических NP-трудных задач на графах — задача о независимом множестве (ЗНМ). Немало работ посвящено доказательствам полиномиальной разрешимости или NP-трудности этой задачи для отдельных классов графов. В числе работ последнего времени можно отметить [12, 27, 28, 33, 34, 42, 43, 47, 48, 53, 56], более ранние отражены в книгах [16, 44, 45, 52]. Излагаемые в диссертации результаты получены в рамках общего подхода к проблеме, основанного на рассмотрении семейств всех наследственных классов, сильно наследственных классов (классов, замкнутых относительно операций переименования вершин, удаления вершин и удаления ребер) и конечно определенных классов (классов, определяемых конечными множествами запрещенных подграфов).

Классы, для которых ЗНМ разрешима за полиномиальное время, называются в диссертации а-простыми, а те, для которых она остается NPтрудной — а-сложными. Выявлен класс, который играет особую роль в теории а-сложных классов. Это класс Т, состоящий из всех графов, у которых каждая компонента связности является деревом с не более чем тремя листьями. Доказано, что конечно определенный класс, у которого среди запрещенных подграфов нет графов из Т, является а-сложным (теорема 4.1). Отсюда следует, что для многих известных а-простых классов любое конечно определенное расширение является а-сложным. Доказана полиномиальная разрешимость ЗНМ для сильно наследственных конечно определенных классов, у которых хотя бы один запрещенный подграф принадлежит Т. Тем самым получена исчерпывающая классификация сильно наследственных конечно определенных классов по сложности решения ЗНМ. В последнем разделе главы 4 вводится понятие граничного класса и обосновывается его полезность для описания множества всех конечно определенных а-полных классов. Доказывается, что класс Т является граничным, а в семействе сильно наследственных классов — единственным граничным классом. Результаты главы 4 опубликованы в работах [4, 10, 27].

Теорема 4.1 указывает перспективное направление поиска новых а-простых классов: имеет смысл рассматривать наследственные классы, у которых среди запрещенных подграфов имеется хотя бы один граф из Т. Особый интерес представляют классы, определяемые одним запрещенным подграфом, принадлежащим Т. В главе 5 излагаются результаты, полученные на этом пути и опубликованные в работах [7, 12, 27]. В первом разделе полностью характеризуются наследственные классы, в которых количество локальных экстремумов для задачи ЗНМ ограничено полиномом от числа вершин графа. Как выяснилось, это те классы, у которых среди запрещенных подграфов имеется граф со степенями вершин, не превосходящими 1. Для таких классов ЗНМ решается за полиномиальное время исчерпывающим перебором. Попутно получено доказательство справедливости слегка ослабленного варианта гипотезы о числе максимальных независимых множеств, выдвинутой в работе [29]. Два следующих раздела главы 5 посвящены доказательству полиномиальной разрешимости ЗНМ для графов без вилок. Этот класс является расширением класса графов без звезд, для которого полиномиальные алгоритмы были предложены в работах [52, 54, 58]. Наименьшими графами из Т, для 8 которых К настоящему времени не установлена а-простота или а-сложность классов, определяемых этими графами в качестве запрещенных подграфов, являются графы с пятью вершинами Р5 и Р2+ РъПервому из них посвящен ряд работ, в которых доказывается полиномиальная разрешимость ЗНМ для некоторых его подмножеств [28, 33, 34, 37, 41, 42, 43, 47, 49, 53, 56]. Новые результаты такого рода излагаются в последнем разделе главы 5.

В главе 6 рассматривается проблема кодирования графов. Предлагается универсальный метод, дающий асимптотически оптимальное кодирование для любого наследственного класса с ненулевой энтропией. При этом кодирование и декодирование реализуются алгоритмами невысокой трудоемкости. Эти результаты опубликованы в [3].

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

2. Алексеев В. Е., Марков A.A., Носков В. В. Оптимизация независимых и опорных множеств в гиперграфах // В сб. Комбинаторно-алгебраические методы в прикладной математике / Под ред. Ал. А. Маркова.- Горький: Изд-во Горьковского ун-та, 1981. С. 3−25.

3. Алексеев В. Е. Наследственные классы и кодирование графов//В сб. Проблемы кибернетики, выи. 39 / Под ред. С. В. Яблонского.- М.: Наука, 1982. С. 151−164.

4. Алексеев В. Е. О влиянии локальных ограничений на сложность определения числа независимости графа // В сб. Комбинаторно-алгебраические методы в прикладной математике / Под ред. Ал. А. Маркова.- Горький: Изд-во Горьковского ун-та, 1982, — С. 3−13.

5. Алексеев В. Е. Об энтропии фрагментно замкнутых классов графов// В сб. Комбинаторно-алгебраические методы в прикладной математике / Под ред. Ал. А. Маркова.- Горький: Изд-во Горьковского ун-та, 1986.-С. 5−15.

6. Алексеев В. Е. Об энтропии двумерных фрагментно замкнутых языков // В сб. Комбинаторно-алгебраические методы и их применения / Под ред. Ал. А. Маркова.- Горький: Изд-во Горьковского ун-та, 1987.С. 5−13.

7. Алексеев В. Е. О числе тупиковых независимых множеств в графах из наследственных классов // В сб. Комбинаторно-алгебраические методы в дискретной оптимизации / Под ред. В. Н. Шевченко.-Горький: Изд-во Горьковского ун-та, 1991. С. 5−8.

8. Алексеев В. Е. Область значений энтропии наследственных классов графов // Дискретная математика .-1992. Т. 4, N 2. С. 148−157.

9. Алексеев В. Е. О нижних ярусах решетки наследственных классов графов // Дискретный анализ и исследование операций. Серия 1 .1997. Т. 4, N 1. С. 3−12.

10. Алексеев В. Е., Коробицын Д. В. О сложности некоторых задач на наследственных классах графов //Дискретная математика .- 1992.-T.4,N4. С. 34−40.

11. Алексеев В. Е., Лозин В. В. О локальных преобразованиях графов, сохраняющих число независимости // Дискретный анализ и исследование операций. Серия 1. 1998. Т. 5, N1. С. 3−19.

12. Алексеев В. Е. Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок // Дискретный анализ и исследование операций. Серия 1. 1999.-Т. 6, N 4. С. 3−19.

13. Алексеев В. Е., Сорочан С В. Об энтропии наследственных классов цветных графов // Дискретная математика .- 2000. Т. 12, N 2. С. 99 102.

14. Алексеев В. Е., Сорочан СВ. Об энтропии наследственных классов ориентированных графов // Дискретный анализ и исследование операций. Серия 1. 2000. Т. 7, N 4. С. 20−28.

15. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализвычислительных алгоритмовМ.: Мир, 1979.

16. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.: Мир, 1982.

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

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

19. Мак-Вильямс Ф.Дж., Слоэн Н.Дж. Теория кодов, исправляющих ошибки.- М.: Связь, 1979.

20. Коробицьш Д. В. О сложности определения числа доминирования в моногенных классах графов // Дискретная математика .- 1990. Т. 2, вып. 2. С. 90−97.

21. Харари Ф. Теория графов, — М.: Мир, 1973.

22. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.

23. Чандрасекхаран К.

Введение

в аналитическую теорию чисел.- М.: Мир, 1974.

24. Эрдеш П., Спенсер Дж. Вероятностные методы в комбинаторике. -М.: Мир, 1976.

25. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем. // В сб. Проблемы кибернетики, вып.2. М.: Физматгиз, 1959. С. 75−121.

26. Alekseev V. Е. On the entropy values of hereditary classes of graphs // Discrete Mathematics and Applications.- 1993.-V. 3, N 2. P. 191−199.

27. Alekseev V. E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Applied Mathematics, to appear.

28. Arbib C, Mosca R. On (P5, diamond)-free graphs // Research report (1999). Departament of Pure and Applied Mathematics, Universita di I’Aquila.

29. Balas E., Yu Ch. S. On graphs with polynomially solvable maximum-weight clique problem //Networks.-V. 19. 1989, — 247−253.

30. Bollobas B. Extremal graph theory. London: Acad. Press, 1978.

31. Bollobas B. Hereditary properties of graphs: asymptotic enumeration, global structure, and colouring // Proceedings of the International Congress of Mathematicians, Berlin, 1988, Aug. 18−27, v. III.- P. 333−341.

32. Bollobas В., Thomason A. Projections of bodies and hereditary properties of graphs // Bull. London Math. Soc- 1995. V. 27. P. 417−424.

33. Brandstadt A., Hammer P.L. On the stability number of claw-free P5-free and more general graphs // Discrete Appl. Math. 1999. V. 95. P. 63−167.

34. Brandstadt A., Lozin V. V. A note on a-redundant vertices in graphs// Discrete Appl. Math. 2001.-V. 108, — P. 01−308.

35. Chernoff H. A measure of asymtotic efficiency for tests of a hypothesis based on a sum of observations// Ann. Math. Stat.- 1952. V. 23. P. 493−507.

36. Chvatal V. Determining the stability number of a graph // SIAM J. Comput.-1977. V. 6, N4. P. 643−662.

37. Chvatal V., Hoang C.T., Mahadev N.V.R., de Werra D., Four classes of perfectly orderable graphs//L Graph Theory.- 1987. V. 11. P. 181−195.

38. Cornell D. G, Lerch H., Stewart-Burlingham L. Complement reducible graphs // Discrete Applied Math.-1981. V. 3. P.163−174.

39. Erdos P., Simonovits M. A limit theorem in graph theory // Stud. Sci. Math. Hungar.- 1966.-V.1.-P. 51−57.

40. Farber M., Hujter M., Tuza Z. An upper bound on the number of cliques in a graph// Networks.- 1993. V. 23, N3. P. 207−210.

41. Fouquet J.-L. A decomposition for a class of (/A,/A5) -free graphs // Discrete Math.- 1993.-V. 121. P. 75−83.

42. Fouquet J.-L, Giakoumakis V. On semiP4 -sparse graphs // Discrete Math.-1997. V. 165−166. P. 277−300.

43. Giakoumakis V., Rusu I. Weighted parameters in (PA,?A) -free graphs // Discrete Appl. Math. 1997. V. 80. P. 255−261.

44. Golumbic M.Ch., Algorithmic graph theory and perfect graphs.- N. Y.: Academic Press, 1980.

45. Grotschel M., Lovasz L. Schrijver A, Polynomial algorithms for perfect graphs // Annals of Discrete Mathematics.- 1984. V. 21. P. 325−356.

46. Grotschel M., Lovasz L., Schrijver A., Geometric algorithms and combinatorial Optimization. Springer Verlag, 1994.

47. Hertz A. Polynomially solvable classes for the maximum stable set problem // Discrete Appl. Math.- 1995. V. 60. P. 195−210.

48. Hertz A. On the use of boolean methods for the computation of the stability number// Discrete Applied Mathematics .- 1997. V. 76. P. 183−203.

49. Hoang C.T., Reed B., Some classes of perfectly ordered graphs // J. Graph Theory.- 1989. V. 13, — P. 445−463.

50. Lazebnik F., Ustimenko V.A., Woldar A.J. A new series of dense graphs of high girth // Bull. Amer. Math. Soc. 1995. V. 32, N1. P. 73−79.

51. Lekkerkerker C.G., :Boland J.Ch. Representation ofa finite graph by a set of intervals on the real line // Fund. Math.- 1962. V. 51. P. 45−64.

52. Lovasz L., Plummer M.D. Matching theory .- Amsterdam: North-Holland, 1986.

53. LozinV.V. Stability in P5- and Banner-free graphs//European Journal of Operational Research .- 2000. V. 125. P. 292−297.

54. Minty G.J. On maximal independent sets of vertices in claw-free graphs // J. Combin. Theory Ser. B.- 1980. V. 28, N3. P. 284−304.

55. Moon J.W., Moser L. On cliques in graphs // Israel J. Math. 1965, 23−28.

56. Mosca R. Polynomial algorithms for the maximum stable set problem on particular classes of P5 -free graphs // Inform. Processing Letters.- 1997.-V. 61. P. 137−143.

57. Sauer N. On the density of families of sets // J. of Combinatorial Theory, Ser. A. 1972. V. 13. P. 145−147.

58. Sbihi N. Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile//Discrete Math.- 1980. V. 29, N1. P. 505−517.

59. Shelah S. A combinatorial problemstability and order for models and theories in infmitary languages//Pacific Journal of Mathematics.- 1972. V. 41. P. 241−261.

60. De Simone C, Sassano A. Stability number of bulland chair-free graphs // Discrete Appl. Math.- 1993. V. 41, N2. P. 121−129.

61. Tarjan R.E. Decomposition by clique separators // Discrete Mathematics.-1985. V. 55 .- P. 221 -232.

62. Tsukiyama S., Ide M., Arioshi H., Ozaki H. A new algorithm for generating all the maximal independent sets. // SIAM J. Comput. 1977. V. 6, N 3.-P. 505−517.

63. Whitesides S.H. An algorithm for finding clique cut-sets // Information processing Letters.- 1981. V. 12. P. 31−32.