文章基本信息
- 标题：Computing Dense and Sparse Subgraphs of Weakly Closed Graphs
- 本地全文：下载
- 作者：Tomohiro Koana ; Christian Komusiewicz ; Frank Sommer 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：181
- 页码：1-17
- DOI：10.4230/LIPIcs.ISAAC.2020.20
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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)â^© 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 ð'¢ which is closed under taking subgraphs admits a kernel with at most γ k² vertices. Finally, we provide fixed-parameter algorithms for Independent Dominating Set and Dominating Clique when parameterized by γ k where k is the solution size.
- 关键词：Fixed-parameter tractability; c-closure; degeneracy; clique relaxations; bicliques; dominating set
