Known algorithms for EDGE CLIQUE COVER are probably optimal.

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk

Browse the full SODA paper archive.