wataの日記

プロコンや研究の話など書くかも

Linear-time Kernelization for Feedback Vertex Set

https://arxiv.org/abs/1608.01463 が ICALP 2017 に採択されたので内容の解説をします. 概略 取り除くと残りが無閉路になる頂点集合を Feedback Vertex Set (FVS)と言い,与えられた無向グラフの最小FVSを求める問題をFVS問題と言います.これは有名なNP困…

ICFPC 2016 参加記

運悪く日程が被ったDCJ決勝は棄権し今年もいつものチームでICFPCに参加.メンバーと役割分担,問題概要はchokudaiの記事を参照.ソルバの実行結果ログなどから思い出したところによると,以下の様に3日間作業した. 一日目(Lightning) 公式Twitterの発言か…