日時: 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).