Легко ли изоморфизм индуцированного подграфа на бесконечном подклассе?

Существует ли последовательность неориентированных графов , где каждый имеет ровно вершин, и проблема $\{C_n\}_{n\in \mathbb N}$ $C_n$ $n$

При заданном и графе является ли индуцированным подграфом в ? $n$ $G$ $C_n$ $G$

известно, что он находится в классе ? (Например, когда , это проблема клики для NP-полной задачи.) $\mathsf{P}$ $C_n=K_n$

cc.complexity-theory graph-theory sdcvvc
источник

Кросспост

sdcvvc

Итак,

является частью определения проблемы,

является частью ввода, а

является частью ввода?

{C_{n}}

$\{ C_n \}$

n

$n$

G

$G$

Эндрю Д. Кинг,

@ Андрей Д. Кинг: Да.

sdcvvc

Как быть, если

является звездой (один центральный узел, соединенный с

узлами, которые образуют независимое множество)? чтобы проверить, просто перечислите все узлы степени

и проверьте, образуют ли соседи независимое множество.

C_{n}

$C_n$

n - 1

$n-1$

n - 1

$n-1$

G

$G$

Суреш Венкат

@Suresh: может быть вершина степени больше, чем

, чьи несколько

соседей образуют независимое множество. Их поиск NP-полон.

n - 1

$n-1$

n - 1

$n-1$

sdcvvc

Ответы:

Если я не ошибаюсь, на ваш вопрос ответили Chen-Thurley-Weyer-2008 по параметризованным предположениям о сложности.

Я еще не читал статью внимательно, но, насколько я понял, существует дихотомия в том смысле, что если конечен, то проблема в , но если имеет бесконечное число графов, то индуцированный изоморфизм подграфов является полная (следствие 4, страница 6). $C$ $P$ $C$ $W[1]$

Таким образом, представляется , что , если на первом уровне из иерархии не падает на , не существует такой бесконечный класс графов, подграфа изоморфизм в . $W[1]$ $W$ $FPT$ $P$

Есть еще один интересный результат, утверждающий, что если то существуют классы, для которых индуцированный изоморфизм не является ни ни полным. $P\neq NP$ $P$ $NP$

Матеус де Оливейра Оливейра
источник