2017/09/14 by Jouke Witteveen, Witteveen, Jouke, Leen Torenvliet +1
Computer Science · #03G10 #68Q15 #68Q25 #68Q30 #Advanced Graph Theory Research #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1709.04699
openalex publication_date 2017/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Asking which sets are fixed-parameter tractable for a given parameterization constitutes much of the current research in parameterized complexity theory. This approach faces some of the core difficulties in complexity theory. By focussing instead on the parameterizations that make a given set fixed-parameter tractable, we circumvent these difficulties. We isolate parameterizations as independent measures of complexity and study their underlying algebraic structure. Thus we are able to compare parameterizations, which establishes a hierarchy of complexity that is much stronger than that present in typical parameterized algorithms races. Among other results, we find that no practically fixed-parameter tractable sets have optimal parameterizations.