On the Parameterized Parallel Complexity and the Vertex Cover Problem
Abu-Khzam, Faisal N.
Li, Shouwei
Markarian, Christine
Meyer auf der Heide, Friedhelm
Podlipyan, Pavel
ddc:000
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 k-vertex 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(n2) parallel processors, the running time improves from 4logn+O(kk) to O(k⋅log3n), 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.
2016
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/177
Abu-Khzam FN, Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. On the Parameterized Parallel Complexity and the Vertex Cover Problem. In: <i>Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)</i>. LNCS. ; 2016:477-488. doi:<a href="https://doi.org/10.1007/978-3-319-48749-6_35">10.1007/978-3-319-48749-6_35</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-48749-6_35
info:eu-repo/semantics/closedAccess