A Unifying Model for Locally Constrained Spanning Tree Problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Journal of Combinatorial Optimization Year : 2021

A Unifying Model for Locally Constrained Spanning Tree Problems

Abstract

Given a graph G and a digraph D whose vertices are the edges of G, we investigate the problem of finding a spanning tree of G that satisfies the constraints imposed by D. The restrictions to add an edge in the tree depend on its neighborhood in D. Here, we generalize previously investigated problems by also considering as input functions ℓ and u on E(G) that give a lower and an upper bound, respectively, on the number of constraints that must be satisfied by each edge. The produced feasibility problem is denoted by G-DCST, while the optimization problem is denoted by G-DCMST. We show that G-DCST is NP-complete even under strong assumptions on the structures of G and D, as well as on functions ℓ and u. On the positive side, we prove two polynomial results, one for G-DCST and another for G-DCMST, and also give a simple exponentialtime algorithm along with a proof that it is asymptotically optimal under the ETH. Finally, we prove that other previously studied constrained spanning tree (CST) problems can be modeled within our framework, namely, the Conflict CST, the Forcing CST, the At Least One/All Dependency CST, the Maximum Degree CST, the Minimum Degree CST, and the Fixed-Leaves Minimum Degree CST.
Fichier principal
Vignette du fichier
Unifying-JOCO.pdf (314.58 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03374555 , version 1 (12-10-2021)

Identifiers

Cite

Luiz Alberto Do Carmo Viana, Manoel Campêlo, Ignasi Sau, Ana Silva. A Unifying Model for Locally Constrained Spanning Tree Problems. Journal of Combinatorial Optimization, 2021, 42 (1), pp.125-150. ⟨10.1007/s10878-021-00740-2⟩. ⟨lirmm-03374555⟩
28 View
38 Download

Altmetric

Share

More