10. January 2018

We congratulate Shouwei Li to his doctorate

Shouwei Li has successfully passed his doctoral examination. He received his doctorate for the topic „Parallel Fixed Parameter Tractable Problems“ under Prof. Dr. math. Friedhelm Meyer auf der Heide.

Parameterized complexity theory provides a refined classification of intractable problems on the basis of multivariate design and complexity analysis of deterministic algorithms. We focus on the issue of which problems allow efficient fixed-parameter parallel algorithms. We propose an efficient parallel algorithm for the general Monotone Circuit Value Problem with n gates and an underlying graph of genus k and show that the problem is in FPPT when parameterized by genus. This result implies that it is possible to find an algorithm that makes some P-complete problems fall into NC by fixing one or more non-trivial parameters.

Hence, if we confine ourselves to P- complete problems, an analogy would be: FPPT is with respect to P-completeness what FPT is with respect to NP-completeness. We extend the FPPT framework to a general kernelization method called crown decomposition. This result directly implies an efficient parallel algorithm for the parameterized vertex cover problem. Thus, the parallel crown decomposition and the parameterized vertex cover problem are in FPPT. Furthermore, we explore a parameter called modular-width and show that the Weighted Maximum Clique Problem and the Maximum Matching Problem are in FPPT when parameterized by modular-width. This result implies that, not only P-complete and NP-complete problems but also some problems that are neither known to be P-complete nor in NC, do have parameterized parallel solutions with non-trivial parameters.


back to overview