A story of diameter, radius, and (almost) Helly property
A story of diameter, radius, and (almost) Helly property
复制标题
直径、半径和（几乎）Helly 属性的故事
作者：
G. Ducoffe;F. Dragan
我们给出了这类Helly图的新的算法结果，即超凸度量空间的离散类似图。具体地说，如果每个两两相交的球族都有一个非空的公交点，则一个无向未赋权图是Helly的。众所周知，每个图都等距嵌入到一个Helly图中，这使得Helly图成为度量图论中一类重要的图。我们研究了Helly图的直径和半径计算，以及相关的图类。这在一定程度上是由于对有界分数Helly数图类中这两个距离问题的细粒度复杂性的猜想--作为特殊情况，这两个图类包含真次闭图类和有界团宽度图。请注意，在合理的复杂性假设下，在一般图上，直径和半径都不能在真正的次二次时间内计算。针对这些负面结果，我们首先提出了以n点m边Helly图G为输入，以高概率(W.H.P.)计算的算法。它的半径和直径在O˜(Mn)时间内(即n + m中的次二次)。我们的算法基于Helly性质和Helly图中偏心函数的单峰性：每个局部最小偏心率的顶点都是中心顶点。然后，我们改进了不含C4的Helly图的结果，即球是凸的Helly图。对于这个子类，我们给出了计算所有顶点偏心率的线性时间算法。这样，我们将以前关于强弦图的结果推广到一个更大的子类，其中包括所有桥Helly图和遗传Helly图。最后，我们得到了这类弦图结果的近似形式：后者满足几乎-Helly-型性质，并且比不含C4的Helly图具有更强的(诱导路)凸性。对于弦图，我们可以在准线性时间内计算所有顶点的偏心率，其附加单边误差最多为1，这在强指数时间假设下是最可能的。这回答了德拉甘的一个公开问题。事实上，我们得到的最后一个结果是一个更一般的简化的副产品：从弦图的直径计算到不相交集问题。粗略地说，这意味着分裂图是弦图上直径计算的唯一困难实例。我们的约化还得到，在VC维常的弦图的任何子类上(因此，对于无向路图)，直径可以在真正的次二次时间内计算出来。
We present new algorithmic results for the class of Helly graphs, that is, for the discrete analogues of hyperconvex metric spaces. Specifically, an undirected unweighted graph is Helly if every family of pairwise intersecting balls has a nonempty common intersection. It is known that every graph isometrically embeds into a Helly graph that makes of the latter an important class of graphs in metric graph theory. We study diameter and radius computations within the Helly graphs, and related graph classes. This is in part motivated by a conjecture on the fine‐grained complexity of these two distance problems within the graph classes of bounded fractional Helly number—that contain as particular cases the proper minor‐closed graph classes and the bounded clique‐width graphs. Note that under plausible complexity assumptions, neither the diameter nor the radius can be computed in truly subquadratic time on general graphs. In contrast to these negative results, we first present algorithms which given an n‐vertex m‐edge Helly graph G as input, compute with high probability (w.h.p.) its radius and its diameter in O˜(mn) time (i.e., subquadratic in n + m). Our algorithms are based on the Helly property and on the unimodality of the eccentricity function in Helly graphs: every vertex of locally minimum eccentricity is a central vertex. Then, we improve our results for the C4‐free Helly graphs, that are exactly the Helly graphs whose balls are convex. For this subclass, we present linear‐time algorithms for computing the eccentricity of all vertices. Doing so, we generalize previous results on strongly chordal graphs to a much larger subclass, that includes, among others, all the bridged Helly graphs and the hereditary Helly graphs. Lastly, we derive approximate versions of our results for the class of chordal graphs: with the latter satisfying an almost‐Helly‐type property, and a stronger (induced‐path) convexity property than the C4‐free Helly graphs. For the chordal graphs, we can compute in quasi linear time the eccentricity of all vertices with an additive one‐sided error of at most one, which is best possible under the strong exponential‐time hypothesis. This answers an open question of Dragan. In fact, we obtain this last result as a byproduct from a more general reduction: from diameter computation on chordal graphs to the Disjoint Sets problem. Roughly, it implies that the split graphs are the only hard instances for diameter computation on chordal graphs. We also get from our reduction that on any subclass of chordal graphs with constant VC‐dimension (and so, for undirected path graphs), the diameter can be computed in truly subquadratic time.