Treewidth играет важную роль в алгоритмах FPT, отчасти потому, что многие проблемы FPT параметризуются с помощью treewidth. Связанное, более ограниченное понятие - это пропускная способность. Если граф имеет ширину пути , он также имеет ширину дерева не более k , в то время как в обратном направлении ширина дерева k подразумевает только ширину пути не более k log n, и это ограничено.
Учитывая вышеизложенное, можно ожидать, что может быть значительное алгоритмическое преимущество для графов ограниченной ширины пути. Однако, кажется, что большинство проблем, которые являются FPT для одного параметра, являются FPT для другого. Мне любопытно узнать какие-либо контрпримеры к этому, то есть проблемы, которые «легки» для пропускной способности, но «трудны» для ширины дерева.
Позвольте мне упомянуть, что я был мотивирован, чтобы задать этот вопрос, наткнувшись на недавнюю работу Игоря Разгона («Об OBDD для CNF с ограниченной шириной дерева», KR'14), в которой приведен пример проблемы с решением когда k является шириной пути и (приблизительно) n k нижней границей, когда k является шириной дерева. Мне интересно, существуют ли другие образцы с таким поведением.
Резюме: Есть ли примеры естественных проблем, которые W-hard параметризованы по ширине дерева, но FPT параметризован по ширине пути? В более широком смысле, есть ли примеры проблем, сложность которых, как известно / считается, намного лучше, если они параметризуются по ширине пути, а не по ширине дерева?
источник
Ответы:
Показано, что [1] смешанная китайская проблема почтальона (MCPP), параметризованная по ширине пути, является -твердой, даже если все ребра и дуги входного графа G имеют вес 1 и равны FPT относительно глубины дерева. Это первая проблема, о которой известно, что было показано, что она является W [ 1 ] -твердой по отношению к ширине дерева, а FPT - по глубине дерева. Обратите внимание, что ширина пути графа лежит между шириной дерева и глубиной дерева.W[ 1 ] грамм 1 W[ 1 ]
Проблема Штейнера Multicut, который спрашивает, учитывая неориентированный граф , коллекция T = { T 1 , . , , , T t } , T i ⊆ V ( G ) , наборов терминалов размером не более p и целым числом k , существует ли набор S из не более чем k ребер или узлов, таких что каждый набор T i, по меньшей мере, один пара терминалов в разных компонентах связности G S .грамм T= { T1, . , , , ТT} Tя⊆ V( G ) п К S К Tя G S
[1] https://core.ac.uk/download/pdf/77298274.pdf
[2] http://drops.dagstuhl.de/opus/volltexte/2015/4911/pdf/11.pdf
источник