Подграф изоморфизма

У нас есть графики G_1 = (V_1, E_1), G_2 = (V_2, E_2).

Вопрос: Является ли граф G_1 изоморфным подграфу G_2?

(т. е. существует ли подмножество вершин G_2, V ⊆ V_2 и подмножество ребер G_2, E ⊆ E_2 такое, что | V | = | V_1 | и | E | = | E_1 | и существует ли однозначный одно сопоставление вершин G_1 в подмножестве вершин V из G_2, f: V_1 -> V, такое, что {u, v} ∈ E_1 <=> {f (u), f (v)} ∈ E)

Покажите, что проблема изоморфизма подграфа принадлежит NP.Покажите, что проблема является NP-полной, сводя проблему к клику. (Подсказка: считайте, что граф G_1 полон)

Я пробовал следующее:

Недетерминированная машина Тьюринга сначала «угадывает» подмножество узлов V и подмножество ребер E в G_2, а затем проверяет, что | V | = | V_1 | и | E | = | E_1 | и что существует взаимно-однозначное соответствие f: V_1 -> V такое, что {u, v} ∈ E_1 <=> {f (u), f (v)} ∈ E.

Поскольку существует O (| V_2 | ^ 2) разных пар вершин, проверка требует полиномиального времени. Так что проблема принадлежит NP.

Пусть (G, k) произвольный экземпляр задачи клики, где k - количество вершин клики.

Мы можем построить экземпляр задачи об изоморфизме подграфа за полиномиальное время следующим образом: G_2 - граф на n вершинах.

G_1 - полный граф на k вершинах для некоторого k <= n. Пусть G = G_2. Задача Изоморфизм подграфа имеет решение, если существует полный подграф G_2 с k вершинами, т. Е. Если граф G имеет полный подграф с k вершинами.

Таким образом, экземпляр проблемы Подграф Изоморфизм имеет решение тогда и только тогда, когда исходный экземпляр проблемы имеет Клика.

Следовательно, проблема подграфа изоморфизма является NP-полной.

Не могли бы вы сказать мне, если это правильно или я мог бы что-то улучшить?