Details

Autor(en) / Beteiligte

• Li, Shouwei
• Meyer auf der Heide, Friedhelm[Akademischer Betreuer]
• Scheideler, Christian[Akademischer Betreuer]

Titel

Parallel fixed parameter tractable problems

Ort / Verlag

Paderborn

Erscheinungsjahr

2017

Link zu anderen Inhalten

• Volltext
• Volltext

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 12.10.2017
• Open Access
• ger: Parametrisierte Komplexitätstheorie beschreibt eine neu-denierte Klassikation von schweren Problemen basierend auf einem mehrdimensionalen Design und der Komplexitätsanalyse von deterministischen Algorithmen. Die Forschung von parametrisierter Komplexität wurde auf das parallele Rechnen erweitert und ist im Allgemeinen als Parametrisierte Parallele Komplexität bekannt. Diese Arbeit konzentriert sich auf die Fragestellung, welche Probleme effiziente parametrisierbare parallele Algorithmen erlauben. Ein Problem ist fixed-parameter parallel-tractable (FPPT), wenn es einen Algorithmus gibt, der Laufzeit O(f(k)(log n)) mit O(n) parallelen Prozessoren hat. Wir präsentieren einen effizienten parallelen Algorithmus für das generelle MONOTONE CIRCUIT VALUE PROBLEM mit n Gattern und einem zugrunde liegenden Graphen mit k-begrenzendem Geschlecht. Insbesondere implizieren unsere Ergebnisse, dass für ein gegebenes P-vollständiges Problem ein Algorithmus gefunden werden kann, der das Problem in NC sein lässt durch Fixierung von ein oder mehreren Parametern. Wenn wir uns auf P-vollständige Probleme eingrenzen, existiert folgende Analogie: FPPT für P-vollständige Probleme ist ähnlich wie FPT für NP-vollständige Probleme. Diese Arbeit erweitert das FPPT Framework zu einer generellen Kernelmethode, crown decomposition. Aus diesem Ergebnis erhalten wir direkt einen effizienten parallelen Algorithmus, der den besten bekannten parallelen Algorithmus für das VERTEX COVER PROBLEM verbessert. Daher ist sowohl die parallele crown decomposition als auch die parametrisierte Knotenüberdeckung in FPPT.Des Weiteren haben wir einen weiteren Parameter, die modular-width, untersucht. Wir haben die Forschung von modular-width auf die parametrisierte parallele Komplexität erweitert und zeigen.
• eng: 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 employ 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-complete what FPT is with respect to NP-complete. 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 problems that are still open for P-complete or NC, there do have parameterized parallel solutions with non-trivial parameters; Thus, FPPT is orthogonal to P-complete, NP-complete and probably some unknown classes between NC and P-complete (if P is not equal to NC). Further, there exist some parameters that make a large number of problems in FPPT, which are in different complexity classes in the traditional hierarchy.