Задача изоморфизма порождённому подграфу

Задача изоморфизма порождённому подграфу является NP-полной задачей разрешимости в теории сложности и теории графов. Задача заключается в поиске данного графа как порождённого подграфа другого, большего графа.

Формулировка проблемы

Формально, задача принимает в качестве входа два графа $G_{1}=(V_{1},E_{1})$ и $G_{2}=(V_{2},E_{2})$, где число вершин в $V_{1}$ меньше либо равно числу вершин $V_{2}$. $G_{1}$ изоморфен порождённому подграфу графа $G_{2}$, если существует инъекция f, которая отображает вершины графа $G_{1}$ в вершине графа $G_{2}$ так, что для всех пар вершин x, y в V₁, ребро (x, y) присутствует в E₁ тогда и только тогда, когда ребро $(f(x),f(y))$ присутствует в E₂. Ответ на задачу решения да, если эта функция f существует, и нет в противном случае.

Задача отличается от задачи изоморфизма подграфу в том, что из отсутствия ребра в G₁ следует, что соответствующее ребро в G₂ должно также отсутствовать. При изоморфизме подграфу эти «лишние» рёбра в G₂ могут присутствовать.

Вычислительная сложность

Сложность задачи изоморфизма порождённому подграфу отделяет внешнепланарные графы от их обобщения, параллельно-последовательных графов — она может быть решена за полиномиальное время для 2-связных внешнепланарных графов, но NP-полна для 2-связных параллельно-последовательных графов.

Специальные случаи

Специальный случай поиска длинного пути как порождённого подграфа гиперкуба хорошо изучен и называется задачей о змее в коробке. Задача о наибольшем независимом множестве является также задачей изоморфизма порождённому подграфу, в которой ищется большое независимое множество как порождённый подграф большего графа, а задача о наибольшей клике является задачей изоморфизма порождённому подграфу, в которой ищется большая клика графа как порождённого подграфа большего графа.

Отличие от задачи изоморфизма подграфа

Хотя задача изоморфизма порождённому подграфу кажется лишь слегка отличающейся от задачи изоморфизма подграфу, ограничение словом «порождённому» вызывает достаточно большие изменения, чтобы заметить их с точки зрения вычислительной сложности.

Например, задача об изоморфизме подграфу является NP-полной на связных собственных интервальных графах и на связных двудольных графах перестановок, но задача изоморфизма порождённому подграфу может быть решена за полиномиальное время на этих двух классах.

Более того, задача об изоморфизме порождённому поддереву (то есть, задача об изоморфизме порождённого подграфа, где тип графа G₂ ограничен деревом) может быть решена за полиномиальное время на интервальных графах, в то время как задача об изоморфизме поддереву является NP-полной на собственных интервальных графах.