Введення.
На даний момент не відомо поліноміальних за часом алгоритмів точного вирішення NP-важких завдань. Більш того, фахівці з теорії складності схиляються до варіанту, що таких алгоритмів не існує. Однак, NP-важкі завдання часто зустрічаються в житті. Одним із способів боротьби з NP-важкими завданнями на практиці є застосування наближених алгоритмів.
Розглянемо найкращий відомий наближений алгоритм вирішення завдання про вершинне покриття.
Постановка завдання.
Вершинне покриття - це таке безліч S вершин графа, що у кожного ребра графа хоча б один кінець входить в S.
Завдання полягає в тому, щоб вибрати в неорієнтованому графі мінімальне (за кількістю вершин) вершинне покриття.
Мета.
Побудуємо простий алгоритм вирішення цього завдання, який помиляється не більш ніж удвічі. Це означає, що якщо є оптимальне рішення - безліч вершин T, то отримане нами рішення S задовольняє нерівності |S| < = 2|T|.
Приклад.
У наведеному прикладі вершинним покриттям є, наприклад, безліч вершин {0, 1, 2, 4}. Усі шість вершин графа також утворюють вершинне покриття. Однак, мінімальним вершинним покриттям в розглянутому графі буде безліч, що складається всього з двох вершин. Наприклад, це можуть бути вершини з номерами 1 і 3. Дійсно, всі ребра графа покриваються двома цими вершинами.
Алгоритм.
На кожному кроці алгоритму робимо такі дії:
- Вибираємо випадкове ребро графа e = (u, v).
- Додаємо до рішення S обидві вибрані вершини u і v.
- Видаляємо з графа всі ребра, інцидентні вершинам u або v.
Повторюємо цей крок до тих пір, поки не видалимо всі ребра графа.
Приклад роботи алгоритму.
У наведеному прикладі мінімальне вершинне покриття містить три вершини. Наприклад, це можуть бути вершини 1, 3 і 6. Розгляньмо роботу нашого алгоритму на наведеному прикладі.
Перша ітерація:
- Вибираємо випадкове ребро. Наприклад, ребро (1, 3).
- Додаємо в рішення S обидві вершини обраного ребра: S={1, 3}.
- Видаляємо з графа всі ребра, інцидентні вершинам 1 або 3.
Друга ітерація:
- Вибираємо випадкове ребро. Нехай це буде ребро (4, 6).
- Додаємо в рішення S обидві вершини обраного ребра: S={1, 3, 4, 6}.
- Видаляємо з графа всі ребра, інцидентні вершинам 4 або 6.
У графі не залишилося ребер. Отже, результатом роботи нашого алгоритму буде вершинне покриття S = {1, 3, 4, 6}.
Доказ.
Доведемо, що побудоване безліч є вершинним покриттям. Дійсно, на кожному кроці ми видаляли лише вже покриті ребра. Ми повторювали цю ітерацію, поки в графі ще залишалися ребра. Таким чином, ми покрили всі ребра графа.
Доведемо, що наш алгоритм помиляється не більше, ніж в 2 рази.
Всі розглянуті алгоритмом ребра e не мають спільних вершин. Отже, з кожного з цих ребер в оптимальне рішення T повинна входити хоча б одна вершина. Це означає, що 2|T|>=|S|.
Трохи історії
У знаменитій роботі Річарда Карпа «Reducibility among combinatorial problems» під назвою Node Cover розглядається відповідне Vertex Cover завдання дозвільності і доводиться її NP-повнота.
Розглянутий нами алгоритм був незалежно розроблений Fanica Gavril і Mihalis Yannakakis в 1974 році.
Найкраща відома на сьогоднішній день оцінка наближеного алгоритму завдання Vertex Cover належить George Karakostas. Оцінка доведена в роботі A better approximation ratio for the vertex cover problem.
Висновок.
На даний момент не відомо поліноміальних наближених алгоритмів для Vertex Cover значно покращують отриману нами точність. Тобто, не відомо поліноміального за часом алгоритму, який би помилявся не більше, ніж в 1.999 рази. Таким чином, ми отримали простий поліноміальний за часом алгоритм з хорошою точністю для вирішення NP-важкої задачі.
