平面强连通性增强 (Plane Strong Connectivity Augmentation)

We investigate the problem of strong connectivity augmentation within plane oriented graphs. We show that deciding whether a plane oriented graph $D$ can be augmented with (any number of) arcs $X$ such that $D+X$ is strongly connected, but still plane and oriented, is NP-hard. This question becomes trivial within plane digraphs, like most connectivity augmentation problems without a budget constraint. The budgeted version, Plane Strong Connectivity Augmentation (PSCA) considers a plane oriented graph $D$ along with some integer $k$, and asks for an $X$ of size at most $k$ ensuring that $D+X$ is strongly connected, while remaining plane and oriented. Our main result is a fixed-parameter tractable algorithm for PSCA, running in time $2^{O(k)} n^{O(1)}$. The cornerstone of our procedure is a structural result showing that, for any fixed $k$, each face admits a bounded number of partial solutions "dominating" all others. Then, our algorithm for PSCA combines face-wise branching with a Monte-Carlo reduction to the polynomial Minimum Dijoin problem, which we derandomize. To the best of our knowledge, this is the first FPT algorithm for a (hard) connectivity augmentation problem constrained by planarity.

翻译：我们研究了平面有向图中强连通性增强的问题。我们证明了判定一个平面有向图 $D$ 是否能通过添加（任意数量的）弧 $X$ 使得 $D+X$ 是强连通的，同时保持平面性和有向性，是一个NP难问题。在平面有向图中，这个问题变得平凡，就像大多数没有预算约束的连通性增强问题一样。预算版本，即平面强连通性增强问题（PSCA），考虑一个平面有向图 $D$ 和一个整数 $k$，要求找到一个大小至多为 $k$ 的弧集 $X$，确保 $D+X$ 是强连通的，同时保持平面性和有向性。我们的主要结果是针对PSCA的一个固定参数可处理算法，其运行时间为 $2^{O(k)} n^{O(1)}$。我们方法的核心是一个结构性的结果，表明对于任意固定的 $k$，每个面都允许有限数量的“支配”所有其他部分解的部分解。然后，我们的PSCA算法将面级分支与多项式时间的最小双连接问题的蒙特卡洛约简相结合，并对该约简进行去随机化处理。据我们所知，这是第一个针对受平面性约束的（困难）连通性增强问题的FPT算法。