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

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

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

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

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

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

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

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

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