Contracting Chordal Graphs and Bipartite Graphs to Paths and Trees

Pinar Heggernes 1 Pim Van 'T Hof 1 Benjamin Lévêque 2 Christophe Paul 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Some of the most well studied problems in algorithmic graph theory deal with modifying a graph into an acyclic graph or into a path, using as few operations as possible. In Feedback Vertex Set and Longest Induced Path, the only allowed operation is vertex deletion, and in Spanning Tree and Longest Path, only edge deletions are permitted. We study the edge contraction variant of these problems: given a graph G and an integer k, decide whether G can be transformed into an acyclic graph or into a path using at most k edge contractions. Both problems are known to be NP-complete in general. We show that on chordal graphs these problems can be solved in O(n+m) and O(nm) time, respectively. On the negative side, both problems remain NP-complete when restricted to bipartite input graphs.
Type de document :
Communication dans un congrès
LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. Elsevier, VI Latin-American Algorithms, Graphs and Optimization Symposium, 37, pp.87-92, 2011, Electronic Notes in Discrete Mathematics
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00620732
Contributeur : Benjamin Lévêque <>
Soumis le : jeudi 8 septembre 2011 - 14:49:47
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00620732, version 1

Collections

Citation

Pinar Heggernes, Pim Van 'T Hof, Benjamin Lévêque, Christophe Paul. Contracting Chordal Graphs and Bipartite Graphs to Paths and Trees. LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. Elsevier, VI Latin-American Algorithms, Graphs and Optimization Symposium, 37, pp.87-92, 2011, Electronic Notes in Discrete Mathematics. 〈lirmm-00620732〉

Partager

Métriques

Consultations de la notice

179