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

Задача пошуку ізоморфного підграфа — обчислювальна задача, в якій входом є два графи $G$ і $H$ і потрібно визначити, чи містить $G$ підграф, ізоморфний графу $H$. Задача є узагальненням як задачі про найбільшу кліку, так і задачі про перевірку, чи містить граф гамільтонів цикл, тому є NP-повною. Проте, з деякими видами підграфів задачу пошуку ізоморфного підграфа можна розв'язати за поліноміальний часШаблон:SfnШаблон:Sfn.

Задача розв'язності та обчислювальна складність

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

Формальна задача: Нехай $G=(V,E)$, $H=(V^{\prime },E^{\prime })$ — два графи. Чи існує підграф $G_0=(V_0,E_0):V_0\subseteq V,E_0\subseteq E\cap (V_0\times V_0)$, такий, що $G_0\cong H$? Тобто, чи існує відображення $f:V_0\to V^{\prime }$, таке, що $(v_1,v_2)\in E_0\iff (f(v_1),f(v_2))\in E^{\prime }$?

Доведення NP-повноти задачі пошуку ізоморфного підграфа просте і ґрунтується на зведенні до цієї задачі задачі про кліку, NP-повної задачі розв'язності, в якій входом є один граф $G$ і число $k$, а питання полягає таке: чи містить граф $G$ повний підграф із $k$ вершинами. Для зведення цієї задачі до пошуку ізоморфного підграфа, просто візьмемо як граф $H$ повний граф $K_k$. Тоді відповідь задачі пошуку ізоморфного подграфа зі вхідними графами $G$ і $H$ дорівнює відповіді для задачі про кліку для графа $G$ і числа $k$. Оскільки задача про кліку NP-повна, така поліноміальна звідність показує, що задача пошуку ізоморфного підграфа також NP-повнаШаблон:Sfn.

Альтернативне зведення задачі про гамільтонів цикл відображає граф $G$, який перевіряється на гамільтоновість, на пару графів $G$ і $H$, де $H$ — цикл, що має таке ж число вершин, як і $G$. Оскільки задача про гамільтонів цикл є NP-повною навіть для планарних графів, то задача пошуку ізоморфного підграфа також залишається NP-повною навіть для планарного випадкуШаблон:Sfn.

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

ГрегерШаблон:Sfn показав, що якщо виконано Шаблон:Нппро Шаблон:Не перекладено монотонних властивостей графа, то будь-яка задача пошуку ізоморфного підграфа має складність запиту $\mathrm{\Omega }(n^{3/2})$. Тобто розв'язання задачі пошуку ізоморфного підграфа вимагає перевірки існування або відсутності у вході $\mathrm{\Omega }(n^{3/2})$ різних ребер графа.

Алгоритми

УльманШаблон:Sfn описав рекурсивну процедуру із поверненням для розв'язання задачі пошуку ізоморфного підграфа. Хоча час роботи цього алгоритму, в загальному випадку, експоненційний, він працює за поліноміальний час для будь-якого фіксованого $H$ (тобто час роботи обмежено поліномом, який залежить від вибору $H$). Якщо $G$ — планарний граф (або, загальніше, граф із обмеженим розширенням), а $H$ — фіксований, час розв'язання задачі пошуку ізоморфного підграфа можна скоротити до лінійного часуШаблон:SfnШаблон:Sfn.

2010 року УльманШаблон:Sfn суттєво оновив алгоритм зі статті 1976 року.

Застосування

Задачу пошуку ізоморфного подграфа застосовано в галузі хемоінформатики для пошуку схожості хімічних сполук за їх структурними формулами. Часто в цій галузі використовують термін підструктурний пошукШаблон:Sfn. Структура запиту часто визначається графічно з використанням структурного редактора. Засновані на SMILES бази даних зазвичай визначають запити з використанням Шаблон:Не перекладено, розширення SMILES.

Тісно пов'язані задачі підрахунку числа ізоморфних копій графа $H$ у більшому графі $G$ використовуються для виявлення шаблону в базах данихШаблон:Sfn, у біоінформатиці взаємодії протеїн-протеїнШаблон:Sfn і в методах експоненційних випадкових графів для математичного моделювання соціальних мережШаблон:Sfn.

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

До задачі також є інтерес у галузі штучного інтелекту, де її вважають частиною групи завдань зіставлення зі зразком у графах. Також у цій галузі розглядається розширення задачі пошуку ізоморфного графа, відоме як Шаблон:Не перекладено.

Література

• Шаблон:Книга
• Шаблон:Стаття Від середини 1970-х відомо, що задачу пошуку ізоморфного підграфа для планарних графів можна розв'язати за поліноміальний час. Однак, було помічено, що задача пошуку підізоморфізму залишається NP-повною, зокрема, оскільки задача про гамільтонів цикл для планарних графів є NP-повною.
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга. A1.4: GT48, стр.202.
• Шаблон:Стаття.
• Шаблон:Книга.
• Шаблон:Книга
• Шаблон:Книга.
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга.
• Шаблон:Стаття