On improving matchings in trees, via bounded-length augmentations

Julien Bensmail 1 Valentin Garnero 1 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Due to a classical result of Berge, it is known that a matching of any graph can be turned into a maximum matching by repeatedly augmenting alternating paths whose ends are not covered. In a recent work, Nisse, Salch and Weber considered the influence, on this process, of augmenting paths with length at most k only. Given a graph G, an initial matching M ⊆ E(G) and an odd integer k, the problem is to find a longest sequence of augmenting paths of length at most k that can be augmented sequentially from M. They proved that, when only paths of length at most k = 3 can be augmented, computing such a longest sequence can be done in polynomial time for any graph, while the same problem for any k ≥ 5 is NP-hard. Although the latter result remains true for bipartite graphs, the status of the complexity of the same problem for trees is not known. This work is dedicated to the complexity of this problem for trees. On the positive side, we first show that it can be solved in polynomial time for more classes of trees, namely bounded-degree trees (via a dynamic programming approach), caterpillars and trees where the nodes with degree at least 3 are sufficiently far apart. On the negative side, we show that, when only paths of length exactly k can be augmented, the problem becomes NP-hard already for k = 3, in the class of planar bipartite graphs with maximum degree 3 and arbitrary large girth. We also show that the latter problem is NP-hard in trees when k is part of the input.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2018, 250 (11), pp.110-129
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01790130
Contributeur : Nicolas Nisse <>
Soumis le : vendredi 11 mai 2018 - 16:40:57
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : lundi 24 septembre 2018 - 19:45:42

Fichier

revised-matchings.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01790130, version 1

Collections

Citation

Julien Bensmail, Valentin Garnero, Nicolas Nisse. On improving matchings in trees, via bounded-length augmentations. Discrete Applied Mathematics, Elsevier, 2018, 250 (11), pp.110-129. 〈hal-01790130〉

Partager

Métriques

Consultations de la notice

322

Téléchargements de fichiers

38