Planar Subgraph Isomorphism Revisited

Frédéric Dorn 1, *
* Auteur correspondant
Abstract : The problem of Subgraph Isomorphism is defined as follows: Given a pattern H and a host graph G on n vertices, does G contain a subgraph that is isomorphic to H? Eppstein [SODA 95, J'GAA 99] gives the first linear time algorithm for subgraph isomorphism for a fixed-size pattern, say of order k, and arbitrary planar host graph, improving upon the O(n^\sqrt{k})-time algorithm when using the ``Color-coding'' technique of Alon et al [J'ACM 95]. Eppstein's algorithm runs in time k^O(k) n, that is, the dependency on k is superexponential. We solve an open problem posed in Eppstein's paper and improve the running time to 2^O(k) n, that is, single exponential in k while keeping the term in n linear. Next to deciding subgraph isomorphism, we can construct a solution and enumerate all solutions in the same asymptotic running time. We may list w subgraphs with an additive term O(w k) in the running time of our algorithm. We introduce the technique of "embedded dynamic programming" on a suitably structured graph decomposition, which exploits the topology of the underlying embeddings of the subgraph pattern (rather than of the host graph). To achieve our results, we give an upper bound on the number of partial solutions in each dynamic programming step as a function of pattern size--as it turns out, for the planar subgraph isomorphism problem, that function is single exponential in the number of vertices in the pattern.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.263-274, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00455215
Contributeur : Publications Loria <>
Soumis le : mardi 9 février 2010 - 17:25:16
Dernière modification le : mercredi 29 novembre 2017 - 10:26:31
Document(s) archivé(s) le : vendredi 18 juin 2010 - 19:47:29

Fichier

dorn.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455215, version 1

Collections

Citation

Frédéric Dorn. Planar Subgraph Isomorphism Revisited. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.263-274, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455215〉

Partager

Métriques

Consultations de la notice

184

Téléchargements de fichiers

219