Задача пошуку ізоморфного підграфа

Для доведення, що задача пошуку ізоморфного підграфа NP-повна, її потрібно сформулювати як задачу розв'язності. Входом задачі розв'язності є пара графів ${\displaystyle G}$ і ${\displaystyle H}$ . Відповідь задачі ствердна, якщо ${\displaystyle H}$ ізоморфний деякому підграфу графа ${\displaystyle G}$ і заперенчна в іншому випадку.

Формальна задача: Нехай ${\displaystyle G=(V,E)}$ , ${\displaystyle H=(V^{\prime },E^{\prime })}$  — два графи. Чи існує підграф ${\displaystyle G_{0}=(V_{0},E_{0}):V_{0}\subseteq V,E_{0}\subseteq E\cap (V_{0}\times V_{0})}$ , такий, що ${\displaystyle G_{0}\cong H}$ ? Тобто, чи існує відображення ${\displaystyle f\colon V_{0}\rightarrow V^{\prime }}$ , таке, що ${\displaystyle (v_{1},v_{2})\in E_{0}\Leftrightarrow (f(v_{1}),f(v_{2}))\in E^{\prime }}$ ?

Доведення NP-повноти задачі пошуку ізоморфного підграфа просте і ґрунтується на зведенні до цієї задачі задачі про кліку, NP-повної задачі розв'язності, в якій входом є один граф ${\displaystyle G}$ і число ${\displaystyle k}$ , а питання полягає таке: чи містить граф ${\displaystyle G}$ повний підграф із ${\displaystyle k}$ вершинами. Для зведення цієї задачі до пошуку ізоморфного підграфа, просто візьмемо як граф ${\displaystyle H}$ повний граф ${\displaystyle K_{k}}$ . Тоді відповідь задачі пошуку ізоморфного подграфа зі вхідними графами ${\displaystyle G}$ і ${\displaystyle H}$ дорівнює відповіді для задачі про кліку для графа ${\displaystyle G}$ і числа ${\displaystyle k}$ . Оскільки задача про кліку NP-повна, така поліноміальна звідність показує, що задача пошуку ізоморфного підграфа також NP-повна^[4].

Альтернативне зведення задачі про гамільтонів цикл відображає граф ${\displaystyle G}$ , який перевіряється на гамільтоновість, на пару графів ${\displaystyle G}$ і ${\displaystyle H}$ , де ${\displaystyle H}$  — цикл, що має таке ж число вершин, як і ${\displaystyle G}$ . Оскільки задача про гамільтонів цикл є NP-повною навіть для планарних графів, то задача пошуку ізоморфного підграфа також залишається NP-повною навіть для планарного випадку^[5].

Задача пошуку ізоморфного підграфа є узагальненням задачі про ізоморфізм графів, у якій запитується, чи граф граф ${\displaystyle G}$ ізоморфний графу ${\displaystyle H}$  — відповідь для задачі про ізоморфізм графів «так» тоді й лише тоді, коли графи ${\displaystyle G}$ і ${\displaystyle H}$ мають однакове число вершин і ребер та задача пошуку ізоморфного підграфа для графів ${\displaystyle G}$ та ${\displaystyle H}$ дає «так». Проте статус задачі ізоморфізму графів з погляду теорії складності залишається відкритим.

Грегер^[6] показав, що якщо виконано гіпотезу Аандераа — Карпа — Розенберга^[ru]про складність запиту^[en] монотонних властивостей графа, то будь-яка задача пошуку ізоморфного підграфа має складність запиту ${\displaystyle \Omega (n^{3/2})}$ . Тобто розв'язання задачі пошуку ізоморфного підграфа вимагає перевірки існування або відсутності у вході ${\displaystyle \Omega (n^{3/2})}$ різних ребер графа^[7].

Ульман^[8] описав рекурсивну процедуру із поверненням для розв'язання задачі пошуку ізоморфного підграфа. Хоча час роботи цього алгоритму, в загальному випадку, експоненційний, він працює за поліноміальний час для будь-якого фіксованого ${\displaystyle H}$ (тобто час роботи обмежено поліномом, який залежить від вибору ${\displaystyle H}$ ). Якщо ${\displaystyle G}$  — планарний граф (або, загальніше, граф із обмеженим розширенням), а ${\displaystyle H}$  — фіксований, час розв'язання задачі пошуку ізоморфного підграфа можна скоротити до лінійного часу^[2][3].

2010 року Ульман^[9] суттєво оновив алгоритм зі статті 1976 року.

Задачу пошуку ізоморфного подграфа застосовано в галузі хемоінформатики для пошуку схожості хімічних сполук за їх структурними формулами. Часто в цій галузі використовують термін підструктурний пошук^[8]. Структура запиту часто визначається графічно з використанням структурного редактора. Засновані на SMILES бази даних зазвичай визначають запити з використанням SMARTS^[en], розширення SMILES.

Тісно пов'язані задачі підрахунку числа ізоморфних копій графа ${\displaystyle H}$ у більшому графі ${\displaystyle G}$ використовуються для виявлення шаблону в базах даних^[10], у біоінформатиці взаємодії протеїн-протеїн^[11] і в методах експоненційних випадкових графів для математичного моделювання соціальних мереж^[12].

Ольріх, Ебелінг, Гітинг і Сатер^[13] описали затсосування задачі пошуку ізоморфного підграфа в системі автоматизованого проєктування електронних схем. Задача є також підкроком під час перетворення графа (що потребує найбільшого часу виконання), тому надається інструментальними засобами перетворення графа.

До задачі також є інтерес у галузі штучного інтелекту, де її вважають частиною групи завдань зіставлення зі зразком у графах. Також у цій галузі розглядається розширення задачі пошуку ізоморфного графа, відоме як аналіз графа^[en][14].