ERC Starting Grant · 2021
Parameterized Complexity Through the Lens of Path Problems
Nowadays, numerous problems are known to be NP-hard, and hence unlikely to admit worst-case efficient algorithms. Fortunately, the field of Parameterized Complexity (PC) shows that the nutshell of hardness often lies in particular properties (called parameters) of the instances. Here, we answer the fundamental question: What makes an NP-hard problem hard? Specifically, how do different parameters of an NP-hard problem relate to its inherent difficulty? Based on this knowledge, we design efficient algorithms for wide-classes of instances of NP-hard problems. At the heart of PC lies the study of path (or cycle) problems. The inception of PC was inspired by the Graph Minors Theory, where the…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.