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

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

Для доведення, що задача пошуку ізоморфного підграфа 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].