最大クリーク問題は，無向グラフから全ての節点が互いに枝でつながる最大サイズのクリークを見つける課題で，顔認証や化学分野，デジタルマーケティングで応用されている．
既存解法では，深さ優先探索と分枝限定法を用いた厳密解法や，並列計算を活用する専用ハードウェアが提案されている．
本研究では，探索効率向上のために，特定タイミングで部分グラフを再彩色する手法を構築する．
提案手法において，ハードウェアとソフトウェアの連携と，最大クリーク候補とならない節点を事前に削除する前処理の導入を行い，枝刈り精度の向上とグラフサイズの縮小により探索時間の短縮を行う．