Эффективный алгоритм для удаления рёбер без F-подграфов на графах с произведённой структурой

Основная информация

• ID статьи: 2510.14674
• Название: An efficient algorithm for F-subgraph-free Edge Deletion on graphs having a product structure
• Авторы: Shinwoo An (Bar-Ilan University), Seonghyuk Im (KAIST & IBS), Seokbeom Kim (KAIST & IBS), Myounghwan Lee (Hanyang University)
• Классификация: cs.DM (дискретная математика), cs.DS (структуры данных и алгоритмы), math.CO (комбинаторика)
• Дата публикации: 17 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.14674

Аннотация

Для заданного семейства графов $\mathcal{F}$ граф называется $\mathcal{F}$-подграф-свободным, если он не содержит подграфа, изоморфного какому-либо члену $\mathcal{F}$. В данной работе предложен алгоритм с фиксированным параметром линейного времени для определения, может ли плоский граф быть преобразован в $\mathcal{F}$-подграф-свободный граф путём удаления не более $k$ рёбер, где параметры — это $k$, $|\mathcal{F}|$ и максимальное число вершин графов в $\mathcal{F}$. Время выполнения алгоритма является двойной экспонентой по параметрам и быстрее, чем алгоритм, полученный применением результатов проверки моделей первого порядка для графов с ограниченной twin-width.

Исследовательский контекст и мотивация

Определение задачи

Задача удаления рёбер без F-подграфов определяется следующим образом:

• Входные данные: граф $G$ и неотрицательное целое число $k$
• Задача: определить, существует ли множество рёбер $S \subseteq E(G)$ размером не более $k$ такое, что $G - S$ не содержит никакого графа из $\mathcal{F}$ в качестве подграфа

Значимость исследования

1. Практическая ценность: задача может моделировать различные сценарии реального мира, например:
   • Контроль распространения болезней животных: граф представляет сеть передачи между фермами, цель — контролировать эпидемию путём запрещения небольшого числа соединений
   • Кибербезопасность: нарушение вредоносных сетевых структур путём удаления небольшого числа рёбер
2. Теоретическая важность:
   • Включает множество классических задач, таких как двудольность рёбер (Edge Bipartization) и множество обратных дуг (Feedback Arc Set)
   • Является важным частным случаем задач модификации графов

Ограничения существующих методов

1. Барьеры сложности: даже когда $\mathcal{F}$ содержит только один граф $F$, задача является NP-полной для многих графов $F$
2. Параметризованная сложность:
   • При параметризации только по размеру решения $k$ задача содержит W1-полные проблемы (такие как клика и независимое множество)
   • При параметризации только по древесной ширине задача является W2-трудной
3. Время выполнения: существующие методы twin-width дают время выполнения с башнеобразной зависимостью

Основные вклады

1. Унифицированная схема алгоритма: разработана унифицированная схема на основе произведённой структуры графов, применимая к классам графов с произведённой структурой
2. Эффективные алгоритмы:
   • Алгоритм с фиксированным параметром линейного времени на плоских графах (временная сложность $2^{O(|\mathcal{F}|^2kr^3)} \cdot n$)
   • Алгоритм с фиксированным параметром линейного времени на дисковых графах с ограниченным локальным радиусом
   • Алгоритм с фиксированным параметром почти линейного времени на графах с ограниченным родом
3. Расширение теории произведённых структур: доказано, что дисковые графы с ограниченным локальным радиусом обладают произведённой структурой
4. Результаты плотности: доказано, что алгоритм оптимален в отношении параметрической зависимости, если только не нарушается гипотеза экспоненциального времени

Подробное описание методов

Основная техническая схема

Произведённая структура графов

Для двух графов $G$ и $H$ сильное произведение $G \boxtimes H$ определяется как:

• Множество вершин: $V(G) \times V(H)$
• Множество рёбер: две вершины $(u,v)$ и $(u',v')$ смежны тогда и только тогда, когда выполнено одно из следующих условий:
  • $u = u'$ и $vv' \in E(H)$
  • $v = v'$ и $uu' \in E(G)$
  • $uu' \in E(G)$ и $vv' \in E(H)$

Говорят, что класс графов $\mathcal{C}$ обладает произведённой структурой, если каждый граф в $\mathcal{C}$ является подграфом сильного произведения $H \boxtimes P$ некоторого графа $H$ с древесной шириной не более $w$ и пути $P$.

Основная схема алгоритма (теорема 1.5)

Входные данные:

• Граф $G$ ($n$ вершин)
• Граф $H$ (древесная ширина $\leq w$) и путь $P$
• Вложение $G$ в $H \boxtimes P$

Выходные данные: решение задачи удаления рёбер без $\mathcal{F}$-подграфов на $G$

Временная сложность: $2^{O(|\mathcal{F}|^2kr^3w)} \cdot n$

Проектирование алгоритма

Техника слоёв

1. Определение слоёв: вершины пути $P$ помечаются как $[ℓ]$, $i$-й слой определяется как $V_i = (V(H) \times \{i\}) \cap V(G)$
2. Разбиение интервалов: для каждого целого числа $j$ определяются $I_j = [3(j-1)r+1, 3jr]$ и $V_{I_j} = \bigcup_{i \in I_j} V_i$

Ключевое понимание обработки отключённых компонент связности (теорема 3.2)

Пусть $C$ — компонента связности $F \in \mathcal{F}$, $F' = F \setminus V(C)$. Если существует по крайней мере $k+r$ различных нечётных индексов $j$ таких, что $G[V_{I_j}]$ содержит копию $C$, то:

• Любое решение должно удалить все копии $F'$
• Задача эквивалентна удалению рёбер без $(\mathcal{F} \setminus \{F\}) \cup \{F'\}$-подграфов

Шаги алгоритма

1. Первый этап: итеративно проверяется, существует ли избыток копий компонент связности, и соответственно модифицируется $\mathcal{F}$
2. Второй этап: удаляются "средние" части слоёв, содержащих копии компонент связности, получается граф с ограниченной древесной шириной
3. Финальное решение: применяются существующие алгоритмы на графе с ограниченной древесной шириной

Расширение произведённой структуры

Произведённая структура дисковых графов (теорема 1.7)

Основной результат: каждый дисковый граф с локальным радиусом не более $\rho$ является подграфом $H \boxtimes P$, где $H$ имеет древесную ширину $O(\rho^9)$, $P$ — путь.

Ключевые технические приёмы:

1. Граф перестановок: использование графа перестановок $A_{\mathcal{D}}$ семейства дисков $\mathcal{D}$
2. Модель подграфа глубины-$d$: введение концепции модели подграфа с ограничениями радиуса
3. Операция раздутия: соединение дискового графа и графа перестановок через операцию раздутия

Вычисление линейного времени

Сложность алгоритма: $2^{O(\rho)} \cdot n$

Основные шаги:

1. Вычисление графа перестановок $A_{\mathcal{D}}$ (время $O(\rho n)$)
2. Вычисление раздутого графа $A'_{\mathcal{D}}$ (время $O(\rho^3 n)$)
3. Построение модели подграфа глубины-$\rho$ (время $2^{O(\rho)} \cdot n$)

Экспериментальные результаты

Теоретические результаты

Статья в основном предоставляет теоретические результаты, включая:

1. Плоские графы: временная сложность $2^{O(|\mathcal{F}|^2kr^3)} \cdot n$
2. Графы с ограниченным родом: временная сложность $2^{O(|\mathcal{F}|^2gkr^3)} \cdot n \log n$
3. Дисковые графы с ограниченным локальным радиусом: временная сложность $2^{O(|\mathcal{F}|^2kr^3\rho^9)} \cdot n$

Доказательство плотности

Предложение 1.10: задача удаления рёбер без $P_4$-подграфов на плоских графах является NP-трудной.

Схема доказательства:

1. Сведение из плоской задачи 1-in-3-SAT
2. Построение сложных гаджет-структур (гаджет переменной, гаджет предложения, гаджет разделителя)
3. Использование теоремы Эрдёша-Галлаи для установления связей

Связанные работы

Задачи модификации графов

• Классические результаты: алгоритм $O(1.977^k) \cdot nm$ для Edge Bipartization
• Параметризованная сложность: алгоритмы с параметризацией по древесной ширине и результаты W2-трудности

Теория произведённых структур

• Пионерские работы: теорема о произведённой структуре плоских графов Дуймовича и др.
• Приложения: решение задач о числе очередей, неповторяющейся раскраске, схемах маркировки и др.
• Расширения: произведённые структуры для $k$-плоских графов, графов без apex-minor и др.

Техника слоёв Бейкера

• Классический метод: применение для PTAS NP-полных задач на плоских графах
• Вклад данной работы: первое применение техники слоёв к задачам удаления рёбер с отключением целевых графов

Заключение и обсуждение

Основные выводы

1. Разработана унифицированная схема алгоритма на основе произведённой структуры для решения задачи удаления рёбер без $\mathcal{F}$-подграфов на нескольких классах графов
2. Доказано, что дисковые графы с ограниченным локальным радиусом обладают произведённой структурой, расширяя теорию произведённых структур
3. Установлены плотные нижние границы параметрической зависимости

Ограничения

1. Параметрическая зависимость: время выполнения алгоритма имеет двойную экспоненциальную зависимость от параметров
2. Ограничение на классы графов: применимо только к графам с произведённой структурой
3. Требование вложения: необходимо знание вложения графа в произведённую структуру

Направления будущих исследований

Статья предлагает два открытых вопроса:

1. Вопрос 1: существует ли FPT-аппроксимационный алгоритм для поиска произведённой структуры?
2. Вопрос 2: существует ли FPT-алгоритм без предварительного знания вложения?

Глубокая оценка

Преимущества

1. Теоретические инновации:
   • Первое систематическое применение теории произведённых структур к задачам модификации графов
   • Оригинальные техники обработки отключённых целевых графов
2. Технические вклады:
   • Доказаны новые результаты о произведённой структуре дисковых графов
   • Предоставлена унифицированная схема алгоритма
3. Полнота:
   • Предоставлены доказательства корректности алгоритма и анализ сложности
   • Установлены плотные нижние границы

Недостатки

1. Ограничения практичности:
   • Двойная экспоненциальная параметрическая зависимость ограничивает практическое применение
   • Требуется предварительное вычисление вложения в произведённую структуру
2. Отсутствие экспериментальной проверки:
   • Нет экспериментов на реальных данных
   • Отсутствует сравнение производительности с существующими методами
3. Ограниченная область применения:
   • Применимо только к специфическим классам графов с произведённой структурой
   • Не предоставляет решение для общих графов

Влияние

1. Теоретическая ценность: значительный вклад в параметризованные алгоритмы и теорию графов
2. Методологическое значение: демонстрирует мощный потенциал применения произведённых структур в разработке алгоритмов
3. Последующие исследования: предоставляет новые технические подходы для исследования связанных задач

Сценарии применения

1. Теоретические исследования: подходит как основа для исследований в параметризованных алгоритмах и теории графов
2. Специфические приложения: применимо к анализу сетей, включающему плоские графы или дисковые графы
3. Разработка алгоритмов: предоставляет шаблон проектирования для других задач модификации графов

Библиография

Статья цитирует 68 связанных работ, охватывающих важные результаты из нескольких областей, включая параметризованные алгоритмы, теорию графов и комбинаторную оптимизацию, обеспечивая прочную теоретическую основу для исследования.