Нерегулярность графа посредством удаления рёбер

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

• ID статьи: 2511.14514
• Название: Graph Irregularity via Edge Deletions
• Авторы: Julien Bensmail, Noémie Catherinot, Foivos Fioravantes, Clara Marcille, Nacim Oijid
• Классификация: math.CO (комбинаторика), cs.CC (вычислительная сложность), cs.DM (дискретная математика)
• Дата публикации: 18 ноября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2511.14514

Аннотация

В данной работе исследуется проблема нерегулярности рёбер графа, параметр Ie(G), который представляет минимальное количество k рёбер, которые необходимо удалить из графа G, чтобы сделать его локально нерегулярным (любые два смежные вершины имеют разные степени). Несмотря на то, что задача доказана NP-трудной и W1-трудной, авторы предлагают два FPT-алгоритма: один относительно размера решения плюс максимальная степень ∆, другой относительно числа вершинного покрытия. Кроме того, авторы проводят глубокое исследование плотных графов, в частности полных графов, и выдвигают важную гипотезу: для любого связного графа G, Ie(G) ≤ m/3 + c, где m — число рёбер, c — константа. Гипотеза верифицирована на нескольких классах графов, включая деревья.

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

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

В теории графов регулярные графы представляют графы, у которых все вершины имеют одинаковую степень. В качестве двойственной концепции исследователи предложили несколько определений нерегулярности:

1. Нерегулярные графы: все вершины имеют попарно различные степени
2. Высоконерегулярные графы: у каждой вершины соседи имеют различные степени
3. Локально нерегулярные графы: любые две смежные вершины имеют различные степени

Данная работа сосредоточена на концепции локально нерегулярных графов.

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

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

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

• Fioravantes и др. 10 недавно ввели концепцию подграфа нерегулярности рёбер, доказав, что вычисление оптимального подграфа нерегулярности рёбер является NP-трудным
• Задача W1-трудна относительно размера решения и обратного набора вершин
• Поведение для плотных графов (таких как полные графы) и некоторых структурных параметров (разнообразие соседства, расстояние до клики) остаётся неясным

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

Авторы ставят целью:

1. Разработать эффективные FPT-алгоритмы для конкретных параметров
2. Понять точные значения или верхние границы Ie(G) для различных классов графов
3. Исследовать универсальные отношения между Ie(G) и числом рёбер m графа

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

1. Параметризованные алгоритмы:
   • Предложен FPT-алгоритм относительно размера решения k плюс максимальная степень ∆ с размером ядра O(k∆^(2k+2))
   • Предложен FPT-алгоритм относительно числа вершинного покрытия vc с временной сложностью 2^O(vc^4)·n^O(1), превосходящий предыдущие методы на основе целочисленного линейного программирования
2. Структурные результаты:
   • Доказаны точные формулы для путей и циклов
   • Для полных двудольных графов Kn,m: Ie = 0 при n≠m, Ie = n при n=m
   • Для деревьев T: Ie(T) ≤ |E(T)|/3 (кроме случая, когда T — путь)
   • Для полных графов порядка треугольного числа tk дана точная формула: Ie(Ktk) = |E(Ktk)| - k(k+1)(k-1)(3k+2)/24
3. Важная гипотеза (Гипотеза 1): Существует константа c такая, что для любого связного графа G с m рёбрами выполняется Ie(G) ≤ m/3 + c
4. Теоретические результаты:
   • Предоставлена общая нижняя граница для Ie(G): Ie(G) ≥ ⌈conf(G)/(2∆-1)⌉
   • Доказано, что рёбра в оптимальном подграфе нерегулярности должны быть близки к конфликтным рёбрам (Лемма 1)

Детальное описание методов

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

Вход: граф G = (V, E) и положительное целое число k ≥ 1
Выход: определить, верно ли Ie(G) ≤ k (версия решения) или вычислить оптимальный подграф нерегулярности рёбер (версия оптимизации)

Определения:

• Граф G является локально нерегулярным, если для любого ребра uv ∈ E выполняется dG(u) ≠ dG(v)
• Подграф нерегулярности рёбер: множество рёбер S ⊆ E такое, что G-S локально нерегулярен
• Ie(G): размер минимального подграфа нерегулярности рёбер
• conf(G): число конфликтов, т.е. количество рёбер uv, для которых dG(u) = dG(v)

Основные технические методы

1. Алгоритм ядеризации относительно k+∆ (Теорема 2)

Ключевая лемма 1: Пусть S — оптимальный подграф нерегулярности рёбер графа G. Тогда любое ребро e ∈ S находится на расстоянии не более 2|S|-1 от некоторого конфликтного ребра.

Схема доказательства (математическая индукция):

• Базис: при k=1 единственное удаляемое ребро должно быть смежно некоторому конфликту
• Индукция: для k≥2 для любого конфликтного ребра uv существует e∈S, смежное u или v; применяем индукционное предположение к G-{e}

Правила ядеризации:

1. Если conf(G) ≥ k(2∆+1), возвращаем отрицательный ответ
2. Для каждого конфликтного ребра e определяем шар B(e, 2k+1), содержащий все вершины на расстоянии не более 2k+1 от концов e
3. Строим подграф H = G∪e∈EC Ve, где Ve — шар ребра e
4. Корректируем степени вершин в H, чтобы они совпадали с G (путём добавления листьев)

Анализ размера ядра:

• Число конфликтов |EC| ≤ k(2∆+1)
• Каждый шар содержит не более 2∆^(2k) вершин
• Общее число вершин: |V(H)| ≤ 2k(2∆+1)∆^(2k+1) = O(k∆^(2k+2))

2. Алгоритм относительно числа вершинного покрытия (Теорема 5)

Схема алгоритма:

1. Пусть C = {u1,...,uvc} — минимальное вершинное покрытие, I = V\C — независимое множество
2. Разбиваем I на I1 и I2:
   • I1: вершины независимого множества, смежные некоторой вершине из C со степенью ≤ 5vc
   • I2: остальные вершины независимого множества
3. Определяем G1 = GC∪I1, G2 = GC∪I2
4. Перечисляем все возможные S1 = S∩E(G1) (не более 2^O(vc^4) вариантов)
5. Для каждого S1 вычисляем минимальное S2⊆E2 такое, что G-(S1∪S2) локально нерегулярен

Ключевое наблюдение (Утверждение 7): Для любого оптимального подграфа нерегулярности S, согласованного с S1, выполняется |S∩E2| ≤ vc^2

Техника оптимизации (Утверждение 8): Для u∈C и v1,v2∈I2, если uv1∈S но uv2∉S, можно поменять их местами и получить эквивалентное оптимальное решение. Поэтому достаточно для каждого u∈C угадать количество удаляемых рёбер ki, где Σki ≤ vc^2.

Временная сложность: 2^(vc+5vc^2)^2 · vc^(vc^2) · n^2 = 2^O(vc^4) · n^O(1)

Технические инновации

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

Экспериментальная установка

Данная работа является теоретическим исследованием, основанным на математических доказательствах, а не на экспериментальной верификации. Однако авторы проводят конструктивный анализ нескольких классов графов:

Исследуемые классы графов

1. Пути Pn и циклы Cn
2. Полные двудольные графы Kn,m
3. Деревья
4. Полные графы Kn (особенно порядка треугольных чисел)
5. Общие связные двудольные графы
6. Общие связные графы

Методы анализа

• Вывод точных формул: для путей, циклов, специальных полных графов
• Доказательство верхних границ: для деревьев, двудольных графов, общих графов
• Конструктивные доказательства: демонстрация конкретных подграфов нерегулярности рёбер, достигающих границ
• Рекурсивные алгоритмы: для деревьев с временной сложностью O(n∆^3)

Результаты экспериментов

Основные результаты

1. Пути и циклы (Теорема 9)

Для пути Pn при n≥2:

• Ie(Pn) = (n-1)/3, когда n≡1 (mod 3)
• Ie(Pn) = ⌈(n-1)/3⌉, когда n≡2 (mod 3)
• Ie(Pn) = ⌊(n-1)/3⌋, в остальных случаях

Для цикла при n≥3: Ie(Cn) = Ie(Pn) + 1

Стратегия доказательства: разбиваем путь на последовательные группы из трёх рёбер, из каждой группы удаляем по крайней мере одно ребро

2. Полные двудольные графы (Теорема 10)

• Ie(Kn,m) = 0, когда n≠m (уже локально нерегулярен)
• Ie(Kn,n) = n (удаляем все рёбра одной вершины)

3. Деревья (Теорема 13)

Основная теорема: для любого дерева T либо T является путём, либо Ie(T) ≤ |E(T)|/3

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

• Для звёзд и двойных звёзд удаляем рёбра на расстоянии 2 от центра
• Для общих деревьев используем индукцию, выбирая самую глубокую вершину степени ≥3
• Детальный анализ случаев (по структуре поддеревьев и степеням)

Алгоритмический результат (Теорема 15): можно вычислить Ie(G) для дерева за время O(n∆^3)

4. Полные графы (Теорема 16)

Для полного графа порядка n = tk = k(k+1)/2 (k-е треугольное число):

Ie(Ktk) = |E(Ktk)| - mk

где mk = k(k+1)(k-1)(3k+2)/24

Конструкция: максимальный локально нерегулярный подграф Tk имеет последовательность степеней: 1 вершина степени n-1, 2 вершины степени n-2, ..., k вершин степени n-k

5. Верхние границы для общих графов

Двудольные графы (Теорема 11): Для связного двудольного графа с минимальной степенью 1: Ie(G) ≤ n-1

Общие графы (Теорема 12): Для любого связного графа: Ie(G) ≤ ⌊m/2⌋ + n + ∆ - 2

Верификация гипотезы

Гипотеза 1: существует константа c такая, что для любого связного графа G с m рёбрами выполняется Ie(G) ≤ m/3 + c

Верифицированные классы графов:

• ✓ Циклы (c≥2)
• ✓ Деревья
• ✓ Полные графы порядка треугольных чисел
• ✓ Полные двудольные графы
• ✓ По теореме 12 общие графы удовлетворяют более слабой границе

Точность (Теорема 1): Для графа G, полученного путём двойного подразделения каждого ребра графа H: Ie(G) ≥ m/3 Следовательно, коэффициент 1/3 является точным.

Ключевые результаты

1. Эффективность разрешения конфликтов: удаление одного ребра разрешает не более 2∆-1 конфликтов (Замечание 1)
2. Требование связности: связность в гипотезе 1 необходима (совершенное паросочетание требует удаления всех рёбер)
3. Разреженные vs плотные: разреженные графы (такие как деревья) легче достигают границы m/3, плотные графы (такие как полные) имеют сложное поведение

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

Спектр исследований нерегулярности графов

1. Нерегулярные графы 6: Chartrand и др. ввели силу нерегулярности (irregularity strength), достигая различных степеней всех вершин путём увеличения кратности рёбер
2. Высоконерегулярные графы 1,5: Alavi и др. исследовали графы, у которых соседи каждой вершины имеют различные степени
3. Локально нерегулярные графы 2,12:
   • Karoński, Luczak, Thomason выдвинули гипотезу 1-2-3 (недавно решена Keusch 13)
   • Baudon и др. исследовали разложение регулярных графов на локально нерегулярные подграфы

Введение свойств путём операций удаления

4. Введение регулярности 3,4:
   • Bazgan и др. достигают анонимизации степеней путём ротации рёбер
   • Belmonte и Sau исследуют поиск больших нечётных индуцированных подграфов
5. Подграфы нерегулярности вершин 11:
   • Fioravantes и др. ввели достижение локальной нерегулярности путём удаления вершин
   • Доказали FPT-алгоритмы относительно древесной ширины и максимальной степени
6. Подграфы нерегулярности рёбер 10:
   • Недавно введённая концепция (прямой предшественник данной работы)
   • Доказана NP-трудность и несколько результатов W1-трудности

Уникальные вклады данной работы

По сравнению со связанными работами:

• Впервые предложены FPT-алгоритмы относительно k+∆ и числа вершинного покрытия
• Впервые систематически исследованы точные значения для нескольких классов графов
• Впервые выдвинута гипотеза m/3+c и проведена её обширная верификация
• Глубокое исследование полных графов, закладывающее основу для понимания параметров плотных графов

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

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

1. Алгоритмический уровень: несмотря на W1-трудность задачи относительно нескольких параметров, через комбинированные параметры (k+∆) или структурные параметры (число вершинного покрытия) можно получить FPT-алгоритмы
2. Структурный уровень:
   • Ie(G) для многих классов графов может быть точно определён или ограничен
   • Поведение деревьев и разреженных графов относительно простое
   • Полные графы демонстрируют тонкую структуру, связанную с треугольными числами
3. Теоретический уровень: если гипотеза 1 верна, она будет единообразно характеризовать асимптотическое поведение Ie(G)

Ограничения

1. Неполнота для полных графов: решена только задача для полных графов порядка треугольных чисел, точные значения для общих полных графов Kn остаются неизвестны
2. Константа в гипотезе 1: хотя верифицирована на нескольких классах графов, точное значение константы c и общее доказательство остаются открытыми
3. Эффективность алгоритмов:
   • FPT-алгоритм для k+∆ имеет экспоненциальную зависимость от ∆^(2k), что ограничивает практическое применение
   • Алгоритм для вершинного покрытия, хотя и улучшает методы на основе целочисленного линейного программирования, всё ещё имеет зависимость 2^O(vc^4)
4. Параметры для плотных графов: FPT-свойства параметров разнообразия соседства и расстояния до клики остаются нерешёнными

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

Авторы явно указывают следующие направления:

1. Динамический параметр конфликтов: улучшение статического параметра conf для динамического отслеживания эволюции конфликтов
2. Полные графы и кубические графы:
   • Определение точных значений Ie для общих полных графов Kn
   • Уточнение границ для кубических графов
3. Расширение на k-вырожденные графы: применение аналогичных техник для получения верхней границы (k-1)n + ⌊n/3⌋
4. Параметризация по древесной ширине: алгоритм для вершинной версии из работы 11 должен быть адаптируем к рёберной версии
5. Разнообразие соседства: требует полного решения задачи для полных графов перед обработкой

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

Достоинства

1. Теоретическая глубина:
   • Техники доказательства изящны, особенно ограничение расстояния в лемме 1 и индукционное доказательство для деревьев
   • Алгоритм ядеризации демонстрирует глубокое понимание параметризованной сложности
   • Результат для полных графов с треугольными числами раскрывает глубокую комбинаторную структуру
2. Систематичность:
   • Охватывает множество классов графов от разреженных до плотных
   • Сочетает алгоритмические и структурные результаты
   • Объединяет теоретический анализ и конструктивные доказательства
3. Выдвижение гипотезы:
   • Гипотеза 1 обладает сильной объединяющей силой и вдохновляющим характером
   • Верификация на нескольких классах графов повышает её достоверность
   • Теорема 1 доказывает точность коэффициента 1/3
4. Качество изложения:
   • Ясная структура, постепенное развитие от простого к сложному
   • Детальные, но не избыточные доказательства
   • Иллюстрации помогают пониманию (например, рисунки 3, 4)
5. Практические алгоритмы:
   • Алгоритм O(n∆^3) для деревьев имеет полиномиальную временную сложность
   • FPT-алгоритмы предоставляют теоретические гарантии для практического применения

Недостатки

1. Пробелы в полноте:
   • Общий случай полных графов не решён, что ограничивает понимание плотных графов
   • Гипотеза 1 лишена общего доказательства
2. Практичность алгоритмов:
   • Двойная экспоненциальная зависимость алгоритма k+∆ ограничивает практическое применение
   • Отсутствует экспериментальная оценка практической производительности алгоритмов
3. Оптимизация констант:
   • Граница в теореме 12 ⌊m/2⌋+n+∆-2 может быть неточной
   • Точные значения константы c для различных классов графов не определены
4. Анализ нижних границ:
   • Кроме conf(G)/(2∆-1), отсутствуют более тонкие техники нижних границ
   • Не обсуждаются приближённые алгоритмы
5. Иерархия параметров:
   • Граница между FPT и W1-hard не полностью охарактеризована
   • Некоторые естественные параметры (такие как древесная ширина+∆) не исследованы

Влияние

1. Теоретический вклад:
   • Закладывает прочную основу для исследования подграфов нерегулярности рёбер
   • Гипотеза 1, если верна, будет важным комбинаторным результатом
   • Методы (особенно лемма 1) могут быть применены к другим задачам модификации графов
2. Последующие исследования:
   • Задача для полных графов привлечёт внимание комбинатористов
   • Техники FPT-алгоритмов могут быть обобщены на другие локальные свойства
   • Предоставляет новую перспективу на понимание локальной нерегулярности графов
3. Практическая ценность:
   • Алгоритм для деревьев может быть непосредственно применён к анализу сетей
   • Предоставляет теоретическую поддержку для приложений в анонимизации графов, робастности сетей и т.д.
4. Открытость:
   • Оставляет явные и привлекательные открытые проблемы
   • Различные уровни сложности подходят для исследователей разного уровня

Применимые сценарии

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

Ключевые ссылки

2 Baudon et al. (2015): разложение регулярных графов на локально нерегулярные подграфы
6 Chartrand et al. (1988): нерегулярные сети, введение силы нерегулярности
10 Fioravantes et al. (2024): введение подграфов нерегулярности рёбер, доказательство базовых результатов сложности
11 Fioravantes et al. (2025): сложность подграфов нерегулярности вершин
12 Karoński et al. (2004): гипотеза 1-2-3
13 Keusch (2024): решение гипотезы 1-2-3

Общая оценка: это высококачественная работа в области теоретической информатики, вносящая существенный вклад в пересечение параметризованной сложности и теории графов. Хотя некоторые проблемы (особенно полные графы) остаются нерешёнными, работа систематически продвигает понимание подграфов нерегулярности рёбер, выдвинутая гипотеза имеет важное теоретическое значение. Методы новаторские, доказательства строгие, работа предоставляет ясные направления для последующих исследований. Рекомендуется к публикации в ведущих журналах по комбинаторной математике или теоретической информатике.