Treewidth Computation and Kernelization in the Parallel External Memory Model

Riko Jacob 1 Tobias Lieber 1 Matthias Mnich 2
2 Cluster of Excellence Multimodal Computing and Interaction
Saarland University [Saarbrücken], Max Planck Institute for Informatics [Saarbrücken], Max Planck Institute for Software Systems, German Research Center for Artificial Intelligence (DFKI)
Abstract : We present a randomized algorithm which computes, for any fixed k, a tree decomposition of width at most k of any input graph. We analyze it in the parallel external memory (PEM) model that measures efficiency by counting the number of cache misses on a multi-CPU private cache shared memory machine. Our algorithm has sorting complexity, which we prove to be optimal for a large parameter range.  We use this algorithm as part of a PEM-efficient kernelization algorithm. Kernelization is a technique for preprocessing instances of size n of NP-hard problems with a structural parameter κ by compressing them efficiently to a kernel, an equivalent instance of size at most g(κ). An optimal solution to the original instance can then be recovered efficiently from an optimal solution to the kernel. Our main results here is an adaption of the linear-time randomized protrusion replacement algorithm by Fomin et al. (FOCS 2012). In particular, we obtain efficient randomized parallel algorithms to compute linear kernels in the PEM model for all separable contraction-bidimensional problems with finite integer index (FII) on apex minor-free graphs, and for all treewidth-bounding graph problems with FII on topological minor-free graphs.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.78-89, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_7〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402030
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 10:48:38
Dernière modification le : lundi 2 octobre 2017 - 20:22:02
Document(s) archivé(s) le : mardi 21 mars 2017 - 05:00:11

Fichier

978-3-662-44602-7_7_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Riko Jacob, Tobias Lieber, Matthias Mnich. Treewidth Computation and Kernelization in the Parallel External Memory Model. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.78-89, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_7〉. 〈hal-01402030〉

Partager

Métriques

Consultations de la notice

49

Téléchargements de fichiers

11