论文标题
计算弱闭合图的密集和稀疏子图
Computing Dense and Sparse Subgraphs of Weakly Closed Graphs
论文作者
论文摘要
如果每个引起的$ g $的子图包含一个顶点$ v $，则图$ g $是弱$γ$ clup的，因此对于每个非邻居$ u $ u $ $ v $，它都认为$ | n（u）\ cap n（v）| <γ$。 Fox等人最近引入的图的弱关闭$γ（g）$。 [Siam J. Comp。 2020]，是最小的数字，因此$ g $是薄弱的$γ$。该图参数永远不会大于变性（加一个），并且可能要小得多。扩展Fox等人的工作。 [Siam J. Comp。 [2020]]在集团枚举中，我们表明与寻找密集的子图有关的几个问题，例如枚举二数枚举和$ s $ plexes，相对于$γ（g）$，都是固定参数。此外，我们表明，确定弱$γ$ claph $ g $的问题是否在至少$ k $的顶点上有一个子图，该$ k $ dertices属于图形$ \ mathcal {g} $，该$ \ Mathcal {g} $在拍摄子图下封闭，该子图被带有子图的最多$γk^2 $ pertices。最后，当由$γ+k $参数化时，我们为独立主导集和主导集团提供固定参数算法，其中$ k $是解决方案大小。
A graph $G$ is weakly $γ$-closed if every induced subgraph of $G$ contains one vertex $v$ such that for each non-neighbor $u$ of $v$ it holds that $|N(u)\cap N(v)|<γ$. The weak closure $γ(G)$ of a graph, recently introduced by Fox et al. [SIAM J. Comp. 2020], is the smallest number such that $G$ is weakly $γ$-closed. This graph parameter is never larger than the degeneracy (plus one) and can be significantly smaller. Extending the work of Fox et al. [SIAM J. Comp. 2020] on clique enumeration, we show that several problems related to finding dense subgraphs, such as the enumeration of bicliques and $s$-plexes, are fixed-parameter tractable with respect to $γ(G)$. Moreover, we show that the problem of determining whether a weakly $γ$-closed graph $G$ has a subgraph on at least $k$ vertices that belongs to a graph class $\mathcal{G}$ which is closed under taking subgraphs admits a kernel with at most $γk^2$ vertices. Finally, we provide fixed-parameter algorithms for Independent Dominating Set and Dominating Clique when parameterized by $γ+k$ where $k$ is the solution size.
