Подграф изоморфизма с деревом

Если у нас есть большой (направленный) граф и меньшее корневое дерево , какова наиболее известная сложность для нахождения подграфов группы изоморфных ? Мне известны результаты для изоморфизма поддеревьев, где и являются деревьями, а также где плоская или имеет ограниченную ширину дерева (и другие), но не для этого графа и случая дерева. $G$ $H$ $G$ $H$ $G$ $H$ $G$

ds.algorithms reference-request graph-theory Рафаэль
источник

Вы имеете в виду индуцированный подграф вместо подграфа?

Кристоффер Арнсфельт Хансен

@Kristoffer, я заинтересован в обоих. Я что-то упустил из-за неиндуцированного случая?

Рафаэль

Ваша проблема NP-трудна, даже если

- путь, так как самая длинная (индуцированная или неиндуцированная) проблема пути - NP-сложна.

H

$H$

Йота Отачи

Да. Меня интересует, что еще известно, что является особенным для

был деревом. Например, в зависимости от свойств

таких как те, что в вопросе, или предположения, что

является фиксированным и т. Д.

H

$H$

G

$G$

H

$H$

Рафаэль

Проблема индуцированного пути является W [1] -полной (Papadimitriou-Yannakakis 1991), в то время как (неиндуцированная) проблема пути - FPT (Monien 1985). Смотрите также Chen-Flum 2007. Я также хочу знать параметризованную сложность для других классов деревьев.

Йота Отачи

Ответы:

Вопрос о том, является ли какой-либо фиксированный граф (индуцированным) подграфом в является определяемым свойством первого порядка, т. Е. Для каждого существует формула ( ) такая, что является (индуцированным) подграфом в $H$ $G$ $H$ $\varphi_H$ $\psi_H$ $H$ $G$ если и только если ( ). $G \models \varphi_H$ $G\models\psi_H$

Ранее было известно, что задача проверки модели трактуется с фиксированным параметром на классах графов, которые (локально) исключают минор, и на классах (локально) ограниченного расширения . Недавно Гроэ, Кройцер и С. объявили еще более общую мета-теорему, заявив, что каждое свойство первого порядка может быть определено за почти линейное время на нигде не плотных классах графов.

Для вашего вопроса это подразумевает следующее. Пусть - фиксированное корневое дерево. Тогда за линейное время можно решить, является ли (индуцированным) подграфом входного (направленного или ненаправленного) графа если $H$ $H$ $G$ плоский, или, в более общем случае, из класса, который исключает минор, или из класса ограниченного расширения. Задача может быть решена почти за линейное время, если принадлежит к классу, локально исключающему минор, или к классу локально ограниченного разложения или, в более общем случае, из нигде не плотного класса графов. $G$ $G$ $G$

Себастьян Сибертц
источник

Это может быть решено в рандомизированном ожидаемом времени где - размер небольшого ориентированного дерева, которое будет найдено, и $O(2^km)$ $k$ $m$ - количество ребер большого ориентированного графа, в котором его можно найти. См. Теорему 6.1 Алона Н., Юстера Р. и Цвика У. (1995). Цветовая кодировка. J. ACM 42 (4): 844–856 . Alon et al. также заявите, что их алгоритм может быть дерандомизирован, но не предоставьте детали для этой части; Я думаю, что детерминированное время может быть немного больше, что-то вроде . $O(k!\,m)$

Дэвид Эппштейн
источник

Версия с дерандомизацией должна быть как обычно, например, как описано в разделе 4, просто использовать идеальную хеш-функцию для отображения

узлов в

цветах, что приводит к дополнительному

коэффициенту. (также может быть улучшен до

factor, то есть полностью равен

n

$n$

k

$k$

\log^{2} n

$\log^2 n$

\log n

$\log n$

O (2^{k} \cdot m \cdot \log n)

$O(2^k \cdot m \cdot \log n)$

Саид

$H$ к корневым деревьям. Положительные результаты, относящиеся к вашей проблеме, уже описаны в предыдущих ответах.

Раду Куртиканский
источник