论文标题
用稀疏图建造大k核
Building large k-cores from sparse graphs
论文作者
论文摘要
衡量网络稳定性的一种流行模型是$ k $ core，即最大的诱发子图，每个顶点至少具有$ k $。例如，$ k $ cores通常用于建模社交网络中的分散现象。在此模型中，网络中具有少于$ K $连接的用户将其留下，因此其余用户恰好形成了$ k $ core。在本文中，我们研究了一个问题，是否可以通过在新连接上花费有限的资源来使网络更强大。 $ k $ core构造问题的数学模型是以下边缘$ k $ - 核优化问题。给我们一个图形$ g $和整数$ k $，$ b $和$ p $。任务是确保$ g $的$ k $ core至少通过添加$ b $边缘具有至少$ p $的顶点。 先前关于边缘$ K $核心的研究表明，该问题在计算上具有挑战性。特别是，当$ k = 3 $，w [1] - 由$ k+b+p $（Chitnis and Talmon，2018）和APX-HARD参数化时，它是NP-HARD。但是，我们表明，当必须从具有一些其他结构属性的稀疏图构建$ k $ core时，有有效的算法具有可证明的保证。我们的结果是1）当输入图是森林时，边缘$ k $ - 可在多项式时间内解决； 2）边缘$ k $ - 核心是固定参数可处理的（FPT），该参数是通过输入图中顶点盖的最小尺寸进行参数化的。另一方面，通过这种参数化，该问题并未接受从复杂性理论中受到广泛假设的多项式内核。 3）边缘$ k $ -core是由$ \ mathrm {tw}+k $参数化的。不需要$ b $很小，这取决于Chitnis和Talmon的结果。我们的每种算法都是基于一个新的图理论结果而构建的。
A popular model to measure network stability is the $k$-core, that is the maximal induced subgraph in which every vertex has degree at least $k$. For example, $k$-cores are commonly used to model the unraveling phenomena in social networks. In this model, users having less than $k$ connections within the network leave it, so the remaining users form exactly the $k$-core. In this paper we study the question whether it is possible to make the network more robust by spending only a limited amount of resources on new connections. A mathematical model for the $k$-core construction problem is the following Edge $k$-Core optimization problem. We are given a graph $G$ and integers $k$, $b$ and $p$. The task is to ensure that the $k$-core of $G$ has at least $p$ vertices by adding at most $b$ edges. The previous studies on Edge $k$-Core demonstrate that the problem is computationally challenging. In particular, it is NP-hard when $k=3$, W[1]-hard being parameterized by $k+b+p$ (Chitnis and Talmon, 2018), and APX-hard (Zhou et al, 2019). Nevertheless, we show that there are efficient algorithms with provable guarantee when the $k$-core has to be constructed from a sparse graph with some additional structural properties. Our results are 1) When the input graph is a forest, Edge $k$-Core is solvable in polynomial time; 2) Edge $k$-Core is fixed-parameter tractable (FPT) being parameterized by the minimum size of a vertex cover in the input graph. On the other hand, with such parameterization, the problem does not admit a polynomial kernel subject to a widely-believed assumption from complexity theory; 3) Edge $k$-Core is FPT parameterized by $\mathrm{tw}+k$. This improves upon a result of Chitnis and Talmon by not requiring $b$ to be small. Each of our algorithms is built upon a new graph-theoretical result interesting in its own.
