Treewidth reduction for constrained separation and bipartization problems

Abstract : We present a method for reducing the treewidth of a graph while preserving all the minimal $s-t$ separators. This technique turns out to be very useful for establishing the fixed-parameter tractability of constrained separation and bipartization problems. To demonstrate the power of this technique, we prove the fixed-parameter tractability of a number of well-known separation and bipartization problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set). These results answer a number of open questions in the area of parameterized complexity.
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.561-572, 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 [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455767
Contributeur : Publications Loria <>
Soumis le : jeudi 11 février 2010 - 10:33:03
Dernière modification le : samedi 14 octobre 2017 - 01:03:59
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:11:05

Fichier

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

Identifiants

  • HAL Id : inria-00455767, version 1

Collections

Citation

Dániel Marx, Barry O'Sullivan, Igor Razgon. Treewidth reduction for constrained separation and bipartization problems. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.561-572, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455767〉

Partager

Métriques

Consultations de la notice

127

Téléchargements de fichiers

108