Путевая ширина графа: различия между версиями
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 92: | Строка 92: | ||
4. Bodlaender, H.L., Thilikos, D.M.: Graphs with branchwidth at most three. J. Algorithms 32,167-194(1999) | 4. Bodlaender, H.L., Thilikos, D.M.: Graphs with branchwidth at most three. J. Algorithms 32,167-194(1999) | ||
5. Cook, W., Seymour, P.D.: Tour merging via branch-decomposition. Inf. J. Comput. 15, 233-248 (2003) | 5. Cook, W., Seymour, P.D.: Tour merging via branch-decomposition. Inf. J. Comput. 15, 233-248 (2003) | ||
6. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discret. Math. 18,501-511 (2004) | 6. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discret. Math. 18,501-511 (2004) | ||
7. Demaine, E.D., Hajiaghayi, M.T., Nishimura, N., Ragde, P., Thilikos, D. M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69,166-195(2004) | 7. Demaine, E.D., Hajiaghayi, M.T., Nishimura, N., Ragde, P., Thilikos, D. M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69,166-195(2004) | ||
8. Dorn, F., Fomin, F.V., Thilikos, D.M.: Subexponential algorithms for non-local problems on H-minor-free graphs. In: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA 2008). pp. 631-640. Society for Industrial and Applied Mathematics, Philadelphia (2006) | 8. Dorn, F., Fomin, F.V., Thilikos, D.M.: Subexponential algorithms for non-local problems on H-minor-free graphs. In: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA 2008). pp. 631-640. Society for Industrial and Applied Mathematics, Philadelphia (2006) | ||
9. Dorn, F.: Dynamic programming and fast matrix multiplication. In: Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006). Lecture Notes in Computer Science, vol. 4168, pp. 280-291. Springer, Berlin (2006) | 9. Dorn, F.: Dynamic programming and fast matrix multiplication. In: Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006). Lecture Notes in Computer Science, vol. 4168, pp. 280-291. Springer, Berlin (2006) | ||
10. Dorn, F., Fomin, F.V., Thilikos, D.M.: Fast subexponential algorithm for non-local problems on graphs of bounded genus. In: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Lecture Notes in Computer Science. Springer, Berlin (2005) | 10. Dorn, F., Fomin, F.V., Thilikos, D.M.: Fast subexponential algorithm for non-local problems on graphs of bounded genus. In: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Lecture Notes in Computer Science. Springer, Berlin (2005) | ||
11. Dorn, F., Penninkx, E., Bodlaender, H., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Proceedings of the 13th Annual European | 11. Dorn, F., Penninkx, E., Bodlaender, H., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Proceedings of the 13th Annual European | ||
Symposium on Algorithms (ESA 2005). Lecture Notes in Computer Science, vol. 3669, pp. 95-106. Springer, Berlin (2005) | Symposium on Algorithms (ESA 2005). Lecture Notes in Computer Science, vol. 3669, pp. 95-106. Springer, Berlin (2005) | ||
12. Downey, R.G., Fellows, M.R.: Parameterized complexity. In: Monographs in Computer Science. Springer, New York (1999) | 12. Downey, R.G., Fellows, M.R.: Parameterized complexity. In: Monographs in Computer Science. Springer, New York (1999) | ||
13. Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum-weight vertex separators. In: Proceedings of the 37th annual ACM Symposium on Theory of computing (STOC 2005), pp. 563-572. ACM Press, New York (2005) | 13. Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum-weight vertex separators. In: Proceedings of the 37th annual ACM Symposium on Theory of computing (STOC 2005), pp. 563-572. ACM Press, New York (2005) | ||
14. Fomin, F.V., Mazoit, F., Todinca, I.: Computing branchwidth via efficient triangulations and blocks. In: Proceedings of the 31 st Workshop on Graph Theoretic Concepts in Computer Science (WG 2005). Lecture Notes Computer Science, vol. 3787, pp. 374-384. Springer, Berlin (2005) | 14. Fomin, F.V., Mazoit, F., Todinca, I.: Computing branchwidth via efficient triangulations and blocks. In: Proceedings of the 31 st Workshop on Graph Theoretic Concepts in Computer Science (WG 2005). Lecture Notes Computer Science, vol. 3787, pp. 374-384. Springer, Berlin (2005) | ||
15. Fomin, F.V., Thilikos, D.M.: Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. | 15. Fomin, F.V., Thilikos, D.M.: Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. | ||
In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004). Lecture Notes Computer Science, vol. 3142, pp. 581-592. Springer, Berlin (2004) | In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004). Lecture Notes Computer Science, vol. 3142, pp. 581-592. Springer, Berlin (2004) | ||
16. Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput. 36, 281-309(2006) | 16. Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput. 36, 281-309(2006) | ||
17. Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. J. Graph Theor. 51, 53-81 (2006) | 17. Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. J. Graph Theor. 51, 53-81 (2006) | ||
18. Gu, Q.P., Tamaki, H.: Optimal branch-decomposition of planar graphs in O(n3) time. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005). Lecture Notes Computer Science, vol. 3580, pp. 373-384. Springer, Berlin (2005) | 18. Gu, Q.P., Tamaki, H.: Optimal branch-decomposition of planar graphs in O(n3) time. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005). Lecture Notes Computer Science, vol. 3580, pp. 373-384. Springer, Berlin (2005) | ||
19. Gu, Q.P., Tamaki, H.: Branch-width, parse trees, and monadic second-order logic for matroids. J. Combin. Theor. Ser. B 96, 325-351 (2006) | 19. Gu, Q.P., Tamaki, H.: Branch-width, parse trees, and monadic second-order logic for matroids. J. Combin. Theor. Ser. B 96, 325-351 (2006) | ||
20. Kloks, T., Kratochvfl, J., MCiller, H.: Computing the branchwidth of interval graphs. Discret. Appl. Math. 145, 266-275 (2005) | 20. Kloks, T., Kratochvfl, J., MCiller, H.: Computing the branchwidth of interval graphs. Discret. Appl. Math. 145, 266-275 (2005) | ||
21. Mazoit, F.:The branch-width of circular-arc graphs. In: 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), 2006, pp. 727-736 | 21. Mazoit, F.:The branch-width of circular-arc graphs. In: 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), 2006, pp. 727-736 | ||
22. Oum, S.I., Seymour, P.: Approximating clique-width and branch-width. J. Combin. Theor. Ser. B 96,514-528 (2006) | 22. Oum, S.I., Seymour, P.: Approximating clique-width and branch-width. J. Combin. Theor. Ser. B 96,514-528 (2006) | ||
23. Paul, C., Proskurowski, A., Telle, J.A.: Generating graphs of bounded branchwidth. In: Proceedings of the 32nd Workshop on Graph Theoretic Concepts in Computer Science (WG 2006). Lecture Notes Computer Science, vol. 4271, pp. 205-216. Springer, Berlin (2006) | |||
24. Paul, C., Telle, J.A.: New tools and simpler algorithms for branchwidth. In: Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), 2005 pp. 379-390 | |||
25. Robertson, N. Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition J. Combin. Theor. Ser. B 52, 153-190 (1991) | |||
26. Robertson, N. Seymour, P.D.: Graph minors. XII. Distance on a surface. J. Combin.Theor. Ser. B 64, 240-272 (1995) | |||
27. Robertson, N. Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Combin.Theor. Ser. B 63,65-110 (1995) | |||
28. Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. Combin. Theor. Ser. B 62, 323-348 (1994) | |||
29. Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14,217-241 (1994) |
Версия от 01:06, 13 августа 2012
Ключевые слова и синонимы: количество зацеплений
Постановка задачи
Путевая ширина, наряду с более известной древесной шириной, является мерой «глобальной связности» графа.
Пусть G – граф с n вершинами. Декомпозиция в форме ветвления применительно к графу G представляет собой пару
Ширина
Вышеприведенное определение может быть напрямую расширено на гиперграфы, в которых
Определение путевой ширины было введено Робертсоном и Сеймуром [25]; оно служило основным инструментом при доказательстве гипотезы Вагнера в их серии работ по минорам графов. Оно использовалось в качестве альтернативы понятию древесной ширины, поскольку оказалось более удобным для обращения в контексте этого доказательства. Отношение между путевой шириной и древесной шириной задается следующим образом.
Теорема 1 ([25])
Если G представляет собой граф, тогда
С понятием путевой ширины связаны алгоритмические задачи двух типов: нахождение быстрых алгоритмов, вычисляющих ее значение, и использование ее для разработки быстрых алгоритмов динамического программирования для решения других задач.
Основные результаты
Алгоритмы вычисления путевой ширины
Вычисление путевой ширины представляет собой NP-полную задачу ([29]). Более того, задача является NP-полной, даже если мы ограничим ее входные графы классом расщепляемых графов или двудольных графов [20].
С другой стороны, на интервальных графах [20, 24] и круговых аркграфах [21] путевая ширина поддается вычислению за полиномиальное время. Возможно, самым популярным положительным результатом в вычислении путевой ширины является алгоритм сложности
Алгоритм для планарных графов [29] может использоваться для построения приближенного алгоритма вычисления путевой ширины некоторых непланарных графов. На классах графов, исключающих граф с однократным пересечением в качестве минора, путевая ширина может быть аппроксимирована с коэффициентом 2.25 [7] (граф H является минором графа G, если H может быть получен из подграфа G после применения процедуры сжатия дуг). Наконец, из работы [13] следует, что для любого класса графов, замкнутых относительно операции взятия минора, может быть выполнена аппроксимация путевой ширины с постоянным коэффициентом.
Сжатие дуги или ее удаление не может привести к повышению путевой ширины. Согласно теории о минорах графов, из этого следует, что для любого фиксированного k существует конечное число минимальных относительно миноров графов, путевая ширина которых превышает k; обозначим это множество графов за
Точный алгоритм вычисления путевой ширины был приведен в [14]. Он имеет сложность
В отличие от древесной ширины, максимальные по количеству дуг графы заданной путевой ширины не так легко поддаются характеризации (в случае древесной ширины они представляют собой просто k-деревья, то есть хордальные графы, все максимальные клики которых имеют размер k + 1). Алгоритм генерации таких графов, приведенный в [23], выявляет несколько структурных задач, связанных с этим параметром.
Известно, что большое число теоретико-графовых задач может быть решено за линейное время в случае, если их входные данные ограничены графами небольшой (иначе говоря, фиксированной) древесной или путевой ширины [2].
Рис. 1. Путевая ширина графа
Пример графа и его декомпозиция в форме ветвления с путевой шириной 3
Понятие путевой ширины оказалось удобным инструментом при разработке точных субэкспоненциальных алгоритмов на планарных графах и их обобщениях. Основная идея этого подхода очень проста. Пусть P – задача на графах, а
для каждого графа
для каждого графа
В таком случае для каждого графа
Дорн [9] использует подход с матричным умножением в динамическом программировании для оценки констант c для различных задач. К примеру, в задаче нахождения максимального независимого множества
Подобный же подход может использоваться для параметризованных задач на планарных графах. К примеру, параметризованный алгоритм для нахождения доминирующего множества с размером, не превышающим k (или сообщения о том, что такого множества не существует) за время
Применение
В работе [5] можно ознакомиться с применением понятия путевой ширины для решения задачи коммивояжера.
Открытые вопросы
1. Известно, что любой планарный граф G имеет путевую ширину не более
2. В отличие от древесной ширины, известны очень немногие классы графов, путевая ширина которых может быть вычислена за полиномиальное время. Найти классы графов, путевая ширина которых может быть вычислена или аппроксимирована за полиномиальное время.
3. Найти
4. Найти точный алгоритм для вычисления путевой ширины сложности
5. Зависимость линейного по времени алгоритма вычисления путевой ширины от k очень велика [3]. Найти алгоритм, состоящий из
См. также
Литература
1. Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33,461-493 (2002)
2. Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability-A survey. BIT 25,2-23 (1985)
3. Bodlaender, H.L., Thilikos, D.M.: Constructive linear time algorithms for branchwidth. In: Automata, languages and programming (Bologna, 1997). Lecture Notes in Computer Science, vol. 1256, pp. 627-637. Springer, Berlin (1997)
4. Bodlaender, H.L., Thilikos, D.M.: Graphs with branchwidth at most three. J. Algorithms 32,167-194(1999)
5. Cook, W., Seymour, P.D.: Tour merging via branch-decomposition. Inf. J. Comput. 15, 233-248 (2003)
6. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discret. Math. 18,501-511 (2004)
7. Demaine, E.D., Hajiaghayi, M.T., Nishimura, N., Ragde, P., Thilikos, D. M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69,166-195(2004)
8. Dorn, F., Fomin, F.V., Thilikos, D.M.: Subexponential algorithms for non-local problems on H-minor-free graphs. In: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA 2008). pp. 631-640. Society for Industrial and Applied Mathematics, Philadelphia (2006)
9. Dorn, F.: Dynamic programming and fast matrix multiplication. In: Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006). Lecture Notes in Computer Science, vol. 4168, pp. 280-291. Springer, Berlin (2006)
10. Dorn, F., Fomin, F.V., Thilikos, D.M.: Fast subexponential algorithm for non-local problems on graphs of bounded genus. In: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Lecture Notes in Computer Science. Springer, Berlin (2005)
11. Dorn, F., Penninkx, E., Bodlaender, H., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005). Lecture Notes in Computer Science, vol. 3669, pp. 95-106. Springer, Berlin (2005)
12. Downey, R.G., Fellows, M.R.: Parameterized complexity. In: Monographs in Computer Science. Springer, New York (1999)
13. Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum-weight vertex separators. In: Proceedings of the 37th annual ACM Symposium on Theory of computing (STOC 2005), pp. 563-572. ACM Press, New York (2005)
14. Fomin, F.V., Mazoit, F., Todinca, I.: Computing branchwidth via efficient triangulations and blocks. In: Proceedings of the 31 st Workshop on Graph Theoretic Concepts in Computer Science (WG 2005). Lecture Notes Computer Science, vol. 3787, pp. 374-384. Springer, Berlin (2005)
15. Fomin, F.V., Thilikos, D.M.: Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004). Lecture Notes Computer Science, vol. 3142, pp. 581-592. Springer, Berlin (2004)
16. Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput. 36, 281-309(2006)
17. Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. J. Graph Theor. 51, 53-81 (2006)
18. Gu, Q.P., Tamaki, H.: Optimal branch-decomposition of planar graphs in O(n3) time. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005). Lecture Notes Computer Science, vol. 3580, pp. 373-384. Springer, Berlin (2005)
19. Gu, Q.P., Tamaki, H.: Branch-width, parse trees, and monadic second-order logic for matroids. J. Combin. Theor. Ser. B 96, 325-351 (2006)
20. Kloks, T., Kratochvfl, J., MCiller, H.: Computing the branchwidth of interval graphs. Discret. Appl. Math. 145, 266-275 (2005)
21. Mazoit, F.:The branch-width of circular-arc graphs. In: 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), 2006, pp. 727-736
22. Oum, S.I., Seymour, P.: Approximating clique-width and branch-width. J. Combin. Theor. Ser. B 96,514-528 (2006)
23. Paul, C., Proskurowski, A., Telle, J.A.: Generating graphs of bounded branchwidth. In: Proceedings of the 32nd Workshop on Graph Theoretic Concepts in Computer Science (WG 2006). Lecture Notes Computer Science, vol. 4271, pp. 205-216. Springer, Berlin (2006)
24. Paul, C., Telle, J.A.: New tools and simpler algorithms for branchwidth. In: Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), 2005 pp. 379-390
25. Robertson, N. Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition J. Combin. Theor. Ser. B 52, 153-190 (1991)
26. Robertson, N. Seymour, P.D.: Graph minors. XII. Distance on a surface. J. Combin.Theor. Ser. B 64, 240-272 (1995)
27. Robertson, N. Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Combin.Theor. Ser. B 63,65-110 (1995)
28. Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. Combin. Theor. Ser. B 62, 323-348 (1994)
29. Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14,217-241 (1994)