第12回研究会 (2021/12/10)

以下の通り，第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 の感染状況により、オンライン開催に変更する可能性があります。

  1. 体温測定： RIMS 内の「自動検温器」「非接触式体温計」で検温、再検温してください。37.5℃以上または平熱より 1.0℃以上の発熱がある方は RIMS 入館禁止です。

  2. 手洗い・アルコール消毒：衛生管理を徹底願います。手洗いうがいの励行、会場設置のアルコール消毒液の活用をお願いします。

  3. マスク着用： RIMS 内では可能な範囲でマスクを着用してください。

  4. 立ち入り制限区域：会場・トイレ・図書室以外の立ち入りを制限しています。通路など共用部分での長時間の会話などはお控えください。当分の間、１F ロビーの立ち入りや給茶機の使用も禁止します。

  5. 体調不良かな？に敏感に：体調に変化（風邪症状、発熱など）があれば、速やかに申告してください。決して無理をして参加しないようにしてください。

  6. 海外から帰国・入国後 2 週間以内の方：該当する方は、政府による二週間の自宅待機要請が解除されるまでの間、対面での参加はご遠慮いただき、オンラインでの参加をお願いします。

  7. 密にならず座る：席は２つ以上離れて座る、講演者に近い前方の席には座らないなど、参加者同士が密にならないよう心掛けてください。

  8. ソーシャルディスタンスを守る：会場内などでの議論等の際、参加者同士が適度な距離（２m以上）をとって、多人数や近距離での会話を避けるように心がけてください。

  9. 多人数での食事を控える：開催期間中は多人数での食事を控えてください。