Chain-constrained spanning trees

N.K. Olver, R. Zenklusen

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider the problem of finding a spanning tree satisfying a family of additional constraints. Several settings have been considered previously, the most famous being the problem of finding a spanning tree with degree constraints. Since the problem is hard, the goal is typically to find a spanning tree that violates the constraints as little as possible. Iterative rounding has become the tool of choice for constrained spanning tree problems. However, iterative rounding approaches are very hard to adapt to settings where an edge can be part of more than a constant number of constraints. We consider a natural constrained spanning tree problem of this type, namely where upper bounds are imposed on a family of cuts forming a chain. Our approach reduces the problem to a family of independent matroid intersection problems, leading to a spanning tree that violates each constraint by a factor of at most 9. We also present strong hardness results: among other implications, these are the first to show, in the setting of a basic constrained spanning tree problem, a qualitative difference between what can be achieved when allowing multiplicative as opposed to additive constraint violations.

Original languageEnglish
Pages (from-to)293–314
Number of pages22
JournalMathematical Programming
Volume67
Issue number2
DOIs
Publication statusPublished - 2018

Fingerprint Dive into the research topics of 'Chain-constrained spanning trees'. Together they form a unique fingerprint.

Cite this