论文标题
查找密度$ k $连接的子图
Finding Densest $k$-Connected Subgraphs
论文作者
论文摘要
密集的子图发现是一个重要的图形原始性，具有多种现实世界的应用。对于密集的子图发现，最深入的优化问题之一是最密集的子图问题，在给定边缘加权的无向图$ g =（v，e，e，w）$中，我们被要求找到$ s \ subseteq v $最大化密度$ d（s）$的密度最大的平均平均平均水平。这个问题可以在几乎线性的时间内准确地解决多项式时间和良好的解决方案。但是，最密集的子图具有结构性缺陷，即，子图可能对顶点/边缘失败不健壮。实际上，最密集的子图可能没有很好地连接，这意味着可以通过仅删除其中的几个顶点/边来断开该子图。在本文中，我们提供了一个算法框架，以找到一个密集的子图，该子图在顶点/边缘连接方面良好连接。具体来说，我们介绍了以下问题：给定图$ g =（v，e，w）$和一个正整数/真实$ k $，我们被要求找到$ s \ subseteq v $，该$ s $ d（s）在$ g [s] $ IS $ k $ k $ vertex/ende edgex contection上最大化密度$ d（s）$。对于这两个问题，我们都建议使用经典的Mader定理在图理论及其扩展中提出多项式时间（双晶和普通）近似算法。
Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph discovery is the densest subgraph problem, where given an edge-weighted undirected graph $G=(V,E,w)$, we are asked to find $S\subseteq V$ that maximizes the density $d(S)$, i.e., half the weighted average degree of the induced subgraph $G[S]$. This problem can be solved exactly in polynomial time and well-approximately in almost linear time. However, a densest subgraph has a structural drawback, namely, the subgraph may not be robust to vertex/edge failure. Indeed, a densest subgraph may not be well-connected, which implies that the subgraph may be disconnected by removing only a few vertices/edges within it. In this paper, we provide an algorithmic framework to find a dense subgraph that is well-connected in terms of vertex/edge connectivity. Specifically, we introduce the following problems: given a graph $G=(V,E,w)$ and a positive integer/real $k$, we are asked to find $S\subseteq V$ that maximizes the density $d(S)$ under the constraint that $G[S]$ is $k$-vertex/edge-connected. For both problems, we propose polynomial-time (bicriteria and ordinary) approximation algorithms, using classic Mader's theorem in graph theory and its extensions.
