以下の通り，第12回研究会を開催いたしました．
日時: 2021年12月10日 (金) 13:00～15:00
場所: 京都大学 数理解析研究所 (RIMS) 4階 420室
参加者: 15 名
講演者: 小穴 智大 氏（ベルリン工科大学）
題目: 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).
なお、数理解析研究所入館にあたり、以下の点をお守りください。また、COVID-19 の感染状況により、オンライン開催に変更する可能性があります。
体温測定： RIMS 内の「自動検温器」「非接触式体温計」で検温、再検温してください。37.5℃以上または平熱より 1.0℃以上の発熱がある方は RIMS 入館禁止です。
手洗い・アルコール消毒：衛生管理を徹底願います。手洗いうがいの励行、会場設置のアルコール消毒液の活用をお願いします。
マスク着用： RIMS 内では可能な範囲でマスクを着用してください。
立ち入り制限区域：会場・トイレ・図書室以外の立ち入りを制限しています。通路など共用部分での長時間の会話などはお控えください。当分の間、１F ロビーの立ち入りや給茶機の使用も禁止します。
体調不良かな？に敏感に：体調に変化（風邪症状、発熱など）があれば、速やかに申告してください。決して無理をして参加しないようにしてください。
海外から帰国・入国後 2 週間以内の方：該当する方は、政府による二週間の自宅待機要請が解除されるまでの間、対面での参加はご遠慮いただき、オンラインでの参加をお願いします。
密にならず座る：席は２つ以上離れて座る、講演者に近い前方の席には座らないなど、参加者同士が密にならないよう心掛けてください。
ソーシャルディスタンスを守る：会場内などでの議論等の際、参加者同士が適度な距離（２m以上）をとって、多人数や近距離での会話を避けるように心がけてください。
多人数での食事を控える：開催期間中は多人数での食事を控えてください。