## Abstract

Efficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In this paper, we propose a more restrictive class of parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). For a problem to be in FPPT, it should possess an efficient parallel algorithm not only from a theoretical standpoint but in practice as well. The primary distinction between FPPT and FPP is the parallel processor utilization, which is bounded by a polynomial function in the case of FPPT. We initiate the study of FPPT with the well-known kvertex cover problem. In particular, we present a parallel algorithm that outperforms the best known parallel algorithm for this problem: using O(m) instead of O(n^{2}) parallel processors, the running time improves from 4 log n+O(k^{k}) to O(k · log^{3} n), where m is the number of edges, n is the number of vertices of the input graph, and k is an upper bound of the size of the sought vertex cover. We also note that a few P-complete problems fall into FPPT including the monotone circuit value problem (MCV) when the underlying graphs are bounded by a constant Euler genus.

Original language | English |
---|---|

Title of host publication | Proceeding of 10th International Conference on Combinatorial Optimization and Applications, COCOA 2016 |

Editors | T.H Chan , M. Li , L. Wang |

Place of Publication | Cham |

Publisher | Springer |

Pages | 477-488 |

Number of pages | 12 |

ISBN (Print) | 9783319487489 |

DOIs | |

Publication status | Published - 2016 |

Event | Conference on Combinatorial Optimization and Applications (COCOA 2016 10th) - Hong Kong, China Duration: 16 Dec 2016 → 18 Dec 2016 Conference number: 2016 (10th) |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10043 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | Conference on Combinatorial Optimization and Applications (COCOA 2016 10th) |
---|---|

Abbreviated title | COCOA |

Country/Territory | China |

City | Hong Kong |

Period | 16/12/16 → 18/12/16 |