競技プログラミングにおける最大クリーク問題、最大独立集合問題まとめ

はじめに

• 最大クリーク問題
  • 無向グラフの中での最大の完全グラフを求める問題
  • 最大クリークを半分前列挙で効率よく扱うテクがある
  • 最小次数がkとなる部分グラフが存在 ↔ 無効グラフ中にサイズk以上のクリークが存在
    • 問題
    • matheticsの記事
    • ヒント1 ヒント2
• 最大独立集合問題
  • 無向グラフの中で、どの頂点間にも辺が無い最大成分を求める問題
  • 最大クリーク問題の逆の問題
  • 特殊なグラフだと特有の解決法がある
    • 詳しい記事 詳しいツイート
    • 二部グラフなら最大流 復元方法
    • 木なら木DP

問題

• 最大クリーク問題
  • ABC002 派閥
  • SRM 696 Clicounting 解説 解説
  • CF428 Mother of Dragons 解説
  • yukicoder No.382 シャイな人たち (2)
• 最大独立集合問題
  • AC Mixture Drug
  • CF533 Helping Hiasat
• 最大独立集合問題（二部グラフ）
  • AC 広告 解説
• 最大独立集合問題（未分類）
  • http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2551