2025-11-19T14:49:14.164403

Graph Irregularity via Edge Deletions

Bensmail, Catherinot, Fioravantes et al.
We pursue the study of edge-irregulators of graphs, which were recently introduced in [Fioravantes et al. Parametrised Distance to Local Irregularity. IPEC, 2024]. That is, we are interested in the parameter Ie(G), which, for a given graph G, denotes the smallest k >= 0 such that G can be made locally irregular (i.e., with no two adjacent vertices having the same degree) by deleting k edges. We exhibit notable properties of interest of the parameter Ie, in general and for particular classes of graphs, together with parameterized algorithms for several natural graph parameters. Despite the computational hardness previously exhibited by this problem (NP-hard, W[1]-hard w.r.t. feedback vertex number, W[1]-hard w.r.t. solution size), we present two FPT algorithms, the first w.r.t. the solution size plus Delta and the second w.r.t. the vertex cover number of the input graph. Finally, we take important steps towards better understanding the behaviour of this problem in dense graphs. This is crucial when considering some of the parameters whose behaviour is still uncharted in regards to this problem (e.g., neighbourhood diversity, distance to clique). In particular, we identify a subfamily of complete graphs for which we are able to provide the exact value of Ie(G). These investigations lead us to propose a conjecture that Ie(G) should always be at most m/3 + c, where $m$ is the number of edges of the graph $G$ and $c$ is some constant. This conjecture is verified for various families of graphs, including trees.
academic

Graph Irregularity via Edge Deletions

基本信息

  • 论文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 (离散数学)
  • 发表时间: 2025年11月18日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2511.14514

摘要

本文研究图的边不规则化问题，即参数Ie(G)，它表示通过删除最少k条边使图G变为局部不规则图（任意两个相邻顶点度数不同）的最小k值。尽管该问题已被证明是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. 参数化算法：
    • 提出关于解大小k加最大度∆的FPT算法，核大小为O(k∆^(2k+2))
    • 提出关于顶点覆盖数vc的FPT算法，时间复杂度为2^O(vc^4)·n^O(1)，优于之前基于ILP的方法
  2. 结构性结果：
    • 证明对于路径和环，给出Ie的精确公式
    • 证明对于完全二部图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)：冲突数，即满足dG(u) = dG(v)的边uv的数量

核心技术方法

1. 关于k+∆的核化算法（定理2）

关键引理1：设S是G的最优边不规则化子，则S中任意边e到某个冲突边的距离至多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)包含距e端点至多2k+1的所有顶点
  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：邻接某个度数≤5vc的C中顶点的独立集顶点
    • 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）： 对任意与S1一致的最优边不规则化子S，有|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）

对于n≥2的路径Pn：

  • 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）：可在O(n∆^3)时间内精确计算树的Ie(G)

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使得对任意m条边的连通图G，Ie(G) ≤ m/3 + c

已验证的图类：

  • ✓ 环（c≥2）
  • ✓ 树
  • ✓ 阶数为三角数的完全图
  • ✓ 完全二部图
  • ✓ 通过定理12，一般图满足更弱的界

紧性（定理1）： 对于将图H的每条边细分两次得到的图G：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等研究将正则图分解为局部不规则子图

通过删除操作引入性质

  1. 引入正则性3,4：
    • Bazgan等通过边旋转实现度数匿名化
    • Belmonte和Sau研究寻找大的奇导出子图
  2. 顶点不规则化子11：
    • Fioravantes等引入通过删除顶点实现局部不规则性
    • 证明了FPT算法关于树宽和最大度
  3. 边不规则化子10：
    • 最近引入的概念（本文的直接前驱）
    • 证明了NP困难性和多个W1困难结果

本文的独特贡献

相比相关工作：

  • 首次提出关于k+∆和顶点覆盖数的FPT算法
  • 首次系统研究多个图类的精确值
  • 首次提出m/3+c猜想并大量验证
  • 深入研究完全图，为理解稠密图参数奠定基础

结论与讨论

主要结论

  1. 算法层面：尽管问题在多个参数下W1困难，通过组合参数（k+∆）或结构参数（顶点覆盖数）可以获得FPT算法
  2. 结构层面：
    • 多个图类的Ie(G)可以精确确定或紧界
    • 树和稀疏图的行为相对简单
    • 完全图展现出与三角数相关的精妙结构
  3. 理论层面：猜想1如果成立，将统一刻画Ie(G)的渐近行为

局限性

  1. 完全图的不完整性：只解决了阶数为三角数的情况，一般完全图Kn的精确值仍未知
  2. 猜想1的常数：虽然在多个图类上验证，但常数c的精确值和一般性证明仍然缺失
  3. 算法效率：
    • k+∆的FPT算法的指数依赖∆^(2k)，实际应用受限
    • 顶点覆盖算法虽然改进了ILP方法，但仍有2^O(vc^4)的依赖
  4. 稠密图参数：邻域多样性、到团的距离等参数的FPT性仍未解决

未来方向

作者明确提出的方向：

  1. 动态冲突参数：改进静态conf参数以动态捕捉冲突演化
  2. 完全图和立方图：
    • 确定一般完全图Kn的Ie精确值
    • 收紧立方图的界
  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猜想

总体评价：这是一篇高质量的理论计算机科学论文，在参数化复杂性和图论的交叉领域做出了实质性贡献。虽然某些问题（特别是完全图）未完全解决，但论文系统地推进了边不规则化子的理解，提出的猜想具有重要的理论意义。方法新颖，证明严谨，为后续研究提供了清晰的方向。建议发表在组合数学或理论计算机科学的顶级期刊。