An FPT algorithm for node-disjoint subtrees ...
Document type :
Communication dans un congrès avec actes
DOI :
Title :
An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth
Author(s) :
Baste, Julien [Auteur]
Operational Research, Knowledge And Data [ORKAD]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Watel, Dimitri [Auteur]
Méthodes et modèles pour les réseaux [METHODES-SAMOVAR]
Statistiques, Optimisation, Probabilités [SOP - SAMOVAR]
Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise [ENSIIE]
Operational Research, Knowledge And Data [ORKAD]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Watel, Dimitri [Auteur]
Méthodes et modèles pour les réseaux [METHODES-SAMOVAR]
Statistiques, Optimisation, Probabilités [SOP - SAMOVAR]
Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise [ENSIIE]
Conference title :
The 11th International Colloquium on Graph Theory and combinatorics
City :
Montpellier
Country :
France
Start date of the conference :
2022-07-04
Book title :
ICGT 2022: The 11th International Colloquium on Graph Theory and combinatorics
Publisher :
ELSEVIER
Publication date :
2022-08-22
English keyword(s) :
Fixed-Parameter Algorithms
Fixed-Parameter Tractable FPT
Graph algorithm
Spanning Tree
Treewidth
Fixed-Parameter Tractable FPT
Graph algorithm
Spanning Tree
Treewidth
HAL domain(s) :
Informatique [cs]/Mathématique discrète [cs.DM]
Informatique [cs]/Complexité [cs.CC]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Complexité [cs.CC]
Informatique [cs]/Algorithme et structure de données [cs.DS]
English abstract : [en]
In this paper, we introduce a problem called Minimum subTree problem with Degree Weights, or MTDW. This problem generalized covering tree problems like Spanning Tree, Steiner Tree, Minimum Branch Vertices, Minimum Leaf ...
Show more >In this paper, we introduce a problem called Minimum subTree problem with Degree Weights, or MTDW. This problem generalized covering tree problems like Spanning Tree, Steiner Tree, Minimum Branch Vertices, Minimum Leaf Spanning Tree, or Prize Collecting Steiner Tree. It consists, given an undirected graph G = (V, E), a set of m + 1 mappings C1, C2, ..., Cm, D, a set of m integers K1, K2, ..., Km and an integer L, in the search of a forest (T1, T2, ..., TL) containing L node-disjoint trees of G. Each mapping is a function V x N -> Z. For each tree Ti, it associates each node v of V to a score depending only on the degree d_{T_i}(v) of v in Ti (possibly 0 if the node is not in Ti. We then get, for each tree, a set of m + 1 scores, one per mapping, by summing the scores of the nodes. For each tree in the forest and i <= m, the i-th score should be lower than Ki. In addition, the forest should minimize the sum of the scores of all the trees related to the mapping D. We proceed to a parameterized analysis of the \MTDW problem with regard to four parameters that are the number of constraints, the maximum degree after which the constraints and the objective function are constant, the value L, and the treewidth of the input graph G. For this problem, we provide a first dichotomy P versus NP-hard depending whether the previous parameters are fixed to be constant or not and a second dichotomy FPT versus W[1]-hard depending whether each of these parameters is constant, considered as a parameter, or disregard. As a side effet, we obtained parameterized algorithms, previously undescribed, for problems such that Budget Steiner Tree problem with Profits, Minimum Branch Vertices, Generalized branch vertices, or k-Bottleneck Steiner Tree.Show less >
Show more >In this paper, we introduce a problem called Minimum subTree problem with Degree Weights, or MTDW. This problem generalized covering tree problems like Spanning Tree, Steiner Tree, Minimum Branch Vertices, Minimum Leaf Spanning Tree, or Prize Collecting Steiner Tree. It consists, given an undirected graph G = (V, E), a set of m + 1 mappings C1, C2, ..., Cm, D, a set of m integers K1, K2, ..., Km and an integer L, in the search of a forest (T1, T2, ..., TL) containing L node-disjoint trees of G. Each mapping is a function V x N -> Z. For each tree Ti, it associates each node v of V to a score depending only on the degree d_{T_i}(v) of v in Ti (possibly 0 if the node is not in Ti. We then get, for each tree, a set of m + 1 scores, one per mapping, by summing the scores of the nodes. For each tree in the forest and i <= m, the i-th score should be lower than Ki. In addition, the forest should minimize the sum of the scores of all the trees related to the mapping D. We proceed to a parameterized analysis of the \MTDW problem with regard to four parameters that are the number of constraints, the maximum degree after which the constraints and the objective function are constant, the value L, and the treewidth of the input graph G. For this problem, we provide a first dichotomy P versus NP-hard depending whether the previous parameters are fixed to be constant or not and a second dichotomy FPT versus W[1]-hard depending whether each of these parameters is constant, considered as a parameter, or disregard. As a side effet, we obtained parameterized algorithms, previously undescribed, for problems such that Budget Steiner Tree problem with Profits, Minimum Branch Vertices, Generalized branch vertices, or k-Bottleneck Steiner Tree.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :