4 papers
Parameterized Complexity of Domination Problems Using Restricted Modular Partitions
Manuel Lafond, Weidong Luo
For a graph class , we define the -modular cardinality of a graph as the minimum size of a vertex partition of into modules that each induces a gr…
Preprocessing Complexity for Some Graph Problems Parameterized by Structural Parameters
Manuel Lafond, Weidong Luo
Structural graph parameters play an important role in parameterized complexity, including in kernelization. Notably, vertex cover, neighborhood diversity, twin-cover, and modular-w…
Polynomial Turing Compressions for Some Graph Problems Parameterized by Modular-Width
Weidong Luo
A polynomial Turing compression (PTC) for a parameterized problem is a polynomial time Turing machine that has access to an oracle for a problem such that a polynomial in…
Frameworks for Solving Turing Kernel Lower Bound Problem and Finding Natural Candidate Problems in NP-intermediate
Weidong Luo
Kernelization is a significant topic in parameterized complexity. Turing kernelization is a general form of kernelization. In the aspect of kernelization, an impressive hardness th…