[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A unifying model for locally constrained spanning tree problems

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

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}\)-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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. We can always assume that \(0\le \ell (e)\le u(e)\le |\mathsf{dep}(e)|\), and so \(\ell (e)=u(e)=0\) if \(\mathsf{dep}(e)=\emptyset \).

  2. This means that \(\ell (e)=k\) and \(u(e)=k'\ge k\), for all \(e\in E(G)\) such that \(\mathsf{dep}(e)\ne \emptyset \), and \(\ell (e)=u(e)=0\) if \(\mathsf{dep}(e)=\emptyset \).

References

  • Akgün I, Tansel B (2010) Min-degree constrained minimum spanning tree problem: new formulation via Miller–Tucker–Zemlin constraints. Comput Oper Res 37(1):72–82

    Article  MathSciNet  Google Scholar 

  • Almeida AM, Martins P, Souza MC (2010) md-MST is NP-hard for \(d\ge 3\). Electron Notes Discrete Math 36:9–15

    Article  Google Scholar 

  • Almeida AM, Martins P, de Souza MC (2012) Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations. Int Trans Oper Res 19(3):323–352

    Article  MathSciNet  Google Scholar 

  • Arnborg S, Lagergren J, Seese D (1991) Easy problems for tree-decomposable graphs. J Algorithms 12(2):308–340. https://doi.org/10.1016/0196-6774(91)90006-K

    Article  MathSciNet  MATH  Google Scholar 

  • Arora S, Barak B (2009) Computational complexity: a modern approach. Cambridge University Press, Cambridge

    Book  Google Scholar 

  • Aschner R, Katz MJ (2017) Bounded-angle spanning tree: modeling networks with angular constraints. Algorithmica 77(2):349–373

    Article  MathSciNet  Google Scholar 

  • Baste J, Gözüpek D, Paul C, Sau I, Shalom M, Thilikos DM (2020) Parameterized complexity of finding a spanning tree with minimum reload cost diameter. Networks 75(3):259–277. https://doi.org/10.1002/net.21923

    Article  MathSciNet  MATH  Google Scholar 

  • Bicalho LH, da Cunha AS, Lucena A (2016) Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem. Comput Optim Appl 63(3):755–792

    Article  MathSciNet  Google Scholar 

  • Bodlaender HL, Jansen K (1993) On the complexity of scheduling incompatible jobs with unit-times. In: Borzyszkowski A, Sokołowski S (eds) MFCS—international symposium on mathematical foundations of computer science. Springer, Berlin, pp 191–300

  • Camerini PM, Galbiati G, Maffioli F (1980) Complexity of spanning tree problems: part I. Eur J Oper Res 5(5):346–352

    Article  Google Scholar 

  • Camerini PM, Galbiati G, Maffioli F (1983) On the complexity of finding multi-constrained spanning trees. Discrete Appl Math 5(1):39–50

    Article  MathSciNet  Google Scholar 

  • Carrabs F, Cerulli R, Pentangelo R, Raiconi A (2018) Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach. Ann Oper Res 2018:1–14

    MATH  Google Scholar 

  • Carrabs F, Cerrone C, Pentangelo R (2019) A multiethnic genetic approach for the minimum conflict weighted spanning tree problem. Networks 74(2):134–147

    Article  MathSciNet  Google Scholar 

  • Cook SA (1971) The complexity of theorem-proving procedures. In: Proceedings of the third annual ACM symposium on theory of computing, pp 151–158

  • Courcelle B (1990) The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf Comput 85(1):12–75. https://doi.org/10.1016/0890-5401(90)90043-H

    Article  MathSciNet  MATH  Google Scholar 

  • Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer, Berlin

    Book  Google Scholar 

  • da Cunha AS, Lucena A (2019) Modeling and solving the angular constrained minimum spanning tree problem. Comput Oper Res 112:104775

    Article  MathSciNet  Google Scholar 

  • Darmann A, Pferschy U, Schauer J (2009) Minimum spanning trees with conflict graphs. Optimization 8:191–205

    MATH  Google Scholar 

  • Darmann A, Pferschy U, Schauer J, Woeginger GJ (2011) Paths, trees and matchings under disjunctive constraints. Discrete Appl Math 159(16):1726–1735

    Article  MathSciNet  Google Scholar 

  • Deo N, Hakimi SL(1968) The shortest generalized Hamiltonian tree. In: Proceedings of the 6th annual Allerton conference, vol 17(3), pp 409–423

  • Deo N, Kumar N (1997) Computation of constrained spanning trees: a unified approach. In: Network optimization, vol 450. Lecture notes in economics and mathematical systems. Springer, Berlin, pp 196–220

  • Dias FCS, Campêlo M, Souza C, Andrade R (2017) Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations. Comput Oper Res 84:46–61

    Article  MathSciNet  Google Scholar 

  • Edmonds J (1979) Matroid intersection. Ann Discrete Math 4:39–49

    Article  MathSciNet  Google Scholar 

  • Epstein L, Favrholdt LM, Levin A (2011) Online variable-sized bin packing with conflicts. Discrete Optim 8(2):333–343

    Article  MathSciNet  Google Scholar 

  • Garey MR, Johnson DS (1979) Computers and intractability. Freeman, San Francisco

    MATH  Google Scholar 

  • Gurski F, Rehs C (2019) Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width. Math Methods Oper Res 89:411–432

    Article  MathSciNet  Google Scholar 

  • Hassin R, Tamir A (1995) On the minimum diameter spanning tree problem. Inf Process Lett 53(2):109–111

    Article  MathSciNet  Google Scholar 

  • Ho JM, Lee D, Chang CH, Wong C (1991) Minimum diameter spanning trees and related problems. SIAM J Comput 20(5):987–997

    Article  MathSciNet  Google Scholar 

  • Impagliazzo R, Paturi R (2001) On the complexity of \(k\)-SAT. J Comput Syst Sci 62(2):367–375. https://doi.org/10.1006/jcss.2000.1727

    Article  MathSciNet  MATH  Google Scholar 

  • Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J Comput Syst Sci 63(4):512–530. https://doi.org/10.1006/jcss.2001.1774

    Article  MathSciNet  MATH  Google Scholar 

  • Kanté MM, Laforest C, Momège B (2013) Trees in graphs with conflict edges or forbidden transitions. In: Proceedings of the of the 10th international conference on theory and applications of models of computation (TAMC), LNCS, vol 7876, pp 343–354

  • Könemann J, Levin A, Sinha A (2005) Approximating the degree-bounded minimum diameter spanning tree problem. Algorithmica 41(2):117–129

    Article  MathSciNet  Google Scholar 

  • Krishnamoorthy M, Ernst AT, Sharaiha YM (2001) Comparison of algorithms for the degree constrained minimum spanning tree. J Heurist 7(6):587–611

    Article  Google Scholar 

  • Lawler EL (1976) Combinatorial optimization: networks and matroids. Courier Corporation, New York

    MATH  Google Scholar 

  • Lu HI, Ravi R (1992) The power of local optimization: approximation algorithms for maximum-leaf spanning tree. In: Proceedings of the annual Allerton conference on communication control and computing, vol 30, pp 533–533

  • Mapa SMS, Urrutia S (2015) On the maximum acyclic subgraph problem under disjunctive constraints. Inf Process Lett 115(2):119–124

    Article  MathSciNet  Google Scholar 

  • Martinez LC, da Cunha AS (2014) The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm. Discrete Appl Math 164:210–224

    Article  MathSciNet  Google Scholar 

  • Oxley JG (1992) Matroid theory. Oxford University Press, Oxford

    MATH  Google Scholar 

  • Papadimitriou CH, Vazirani UV (1984) On two geometric problems related to the travelling salesman problem. J Algorithms 5(2):231–246

    Article  MathSciNet  Google Scholar 

  • Pferschy U, Schauer J (2013) The maximum flow problem with disjunctive constraints. J Combin Optim 26:109–119

    Article  MathSciNet  Google Scholar 

  • Robins G, Salowe JS (1995) Low-degree minimum spanning trees. Discrete Comput Geom 14(2):151–165

    Article  MathSciNet  Google Scholar 

  • Samer P, Urrutia S (2015) A branch and cut algorithm for minimum spanning trees under conflict constraints. Optim Lett 9(1):41–55

    Article  MathSciNet  Google Scholar 

  • Singh M, Lau LC (2015) Approximating minimum bounded degree spanning trees to within one of optimal. J ACM 62(1):1:1–1:19

    Article  MathSciNet  Google Scholar 

  • Viana LA (2016) Árvore geradora com dependências mínima. Master’s thesis, Federal University of Ceará (2016). http://mdcc.ufc.br/teses/doc_download/307-234-luiz-alberto-do-carmo-viana

  • Viana LA, Campêlo M (2020) Two dependency constrained spanning tree problems. Int Trans Oper Res 27(2):867–898. https://doi.org/10.1111/itor.12690

    Article  MathSciNet  Google Scholar 

  • West DB (1996) Introduction to graph theory. Prentice Hall, Upper Saddle River

    MATH  Google Scholar 

  • Zhang R, Kabadi SN, Punnen AP (2011) The minimum spanning tree problem with conflict constraints and its variations. Discrete Optim 8(2):191–205

    Article  MathSciNet  Google Scholar 

Download references

Funding

This work is partially supported by: CAPES-PRINT Institutional Internationalization Program, process 88887.468331/2019-00—French projects DEMOGRAPH (ANR-16-CE40-0028), ESIGMA (ANR-17-CE23-0010) and ELIT (ANR-20-CE48-0008-01)—CNPq projects 309315/2019-0 and 305264/2016-8—CNPq Universal 437841/2018-9 and CNPq Produtividade 304576/2017-4—CNPq/FUNCAP PRONEM PNE-0112-00061.01.00/16.

Author information

Authors and Affiliations

  1. Campus de Crateús, Universidade Federal do Ceará, Crateús, Brazil

    Luiz Viana

  2. Dep. de Estatística e Matemática Aplicada, Universidade Federal do Ceará, Fortaleza, Brazil

    Manoel Campêlo

  3. LIRMM, Université de Montpellier, CNRS, Montpellier, France

    Ignasi Sau

  4. Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil

    Ana Silva

Authors
  1. Luiz Viana
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Manoel Campêlo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ignasi Sau
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ana Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luiz Viana.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Viana, L., Campêlo, M., Sau, I. et al. A unifying model for locally constrained spanning tree problems. J Comb Optim 42, 125–150 (2021). https://doi.org/10.1007/s10878-021-00740-2

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-021-00740-2

Keywords

Mathematics Subject Classification

Search

Navigation