–
2021-12-10
日時: 2021年12月10日(金) 13:00-15:00
会場: 京都大学 数理解析研究所(RIMS)
講演者: 小穴 智大 氏（ベルリン工科大学）
題目: Parameterized algorithms on (weakly) closed graphs
概要: For a graph G and one of its vertices v, let cl(v) = max |N(v) ∩ N(u)|, where the maximum is over all vertices u not adjacent to v. We say that G is c-closed if cl(v) < c for every vertex v and weakly γ-closed if every induced subgraph H of G contains a vertex v with cl(v) < γ in H. The closure (weak closure) of G is the smallest integer c (γ) such that G is c-closed (weakly γ-closed). Fox et al. [ICALP ’18, SICOMP 20] recently introduced these parameters motivated by triadic closure---a phenomenon occurring in social networks that pairs of vertices with common vertices tend to be adjacent. We discuss parameterized algorithms for classical graph problems on (weakly) closed graphs such as:
- s-plex (a relaxation of Clique) is O*(2^γ)-time solvable.
- Independent Set has a kernel with at most γk^2 vertices.
- Dominating Set has a kernel of size k^O(c).
- Induced Matching has kernels with at most O(c^7 k^8) vertices and at most k^O(γ) vertices.
The talk will be based on three joint works with Christian Komusiewicz and Frank Sommer:
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems. ESA 2020.
- Computing Dense and Sparse Subgraphs of Weakly Closed Graphs. ISAAC 2020.
- Essentially Tight Kernels for (Weakly) Closed Graphs. ISAAC 2021 (to appear).