On the Power of Tree-Depth for Fully Polynomial FPT Algorithms

Yoichi Iwata, Tomoaki Ogasawara, Naoto Ohsaka

There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of su…