A unifying model for locally constrained spanning tree problems

Luiz Viana (), Manoel Campêlo (), Ignasi Sau () and Ana Silva ()
Additional contact information
Luiz Viana: Universidade Federal do Ceará
Manoel Campêlo: Universidade Federal do Ceará
Ignasi Sau: Université de Montpellier, CNRS
Ana Silva: Universidade Federal do Ceará

Journal of Combinatorial Optimization, 2021, vol. 42, issue 1, No 7, 125-150

Abstract: 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 $$\ell $$ ℓ 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 $$\texttt {NP}$$ NP -complete even if functions $$\ell $$ ℓ and u are taken under tight assumptions, as well as G and D. On the positive side, we prove two polynomial results, one for G-DCST and another for G-DCMST, and also give a simple exponential-time 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.

Keywords: Spanning tree; Dependency constraints; Matroid intersection; Computational complexity; 05C05; 68Q17; 68Q25; 68R10 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00740-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:42:y:2021:i:1:d:10.1007_s10878-021-00740-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00740-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().