Obtaining a Bipartite Graph by Contracting Few Edges

Pinar Heggerness 1 Pim Van'T Hof 1 Daniel Lokshtanov 1 Christophe Paul 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We initiate the study of the Bipartite Contraction problem from the perspective of param- eterized complexity. In this problem we are given a graph G on n vertices and an integer k, and the task is to determine whether we can obtain a bipartite graph from G by a sequence of at most k edge contractions. Our main result is an $f(k)n^{O(1)}$ time algorithm for Bipartite Con- traction. Despite a strong resemblance between Bipartite Contraction and the classical Odd Cycle Transversal (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to Bipartite Contraction. To obtain our result, we combine several techniques and concepts that are central in parameterized complexity: iterative compression, irrelevant vertex, and important separators. To the best of our knowledge, this is the first time the irrelevant vertex technique and the concept of important separators are applied in unison. Furthermore, our algorithm may serve as a comprehensible example of the usage of the irrelevant vertex technique.
Type de document :
Communication dans un congrès
FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Dec 2011, Mumbai, India. 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp.217-228, 2011, 〈http://www.fsttcs.org/archives/2011/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00805189
Contributeur : Christophe Paul <>
Soumis le : mercredi 27 mars 2013 - 12:36:01
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00805189, version 1

Collections

Citation

Pinar Heggerness, Pim Van'T Hof, Daniel Lokshtanov, Christophe Paul. Obtaining a Bipartite Graph by Contracting Few Edges. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Dec 2011, Mumbai, India. 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp.217-228, 2011, 〈http://www.fsttcs.org/archives/2011/〉. 〈lirmm-00805189〉

Partager

Métriques

Consultations de la notice

65