.png){kind=icon}
.png){kind=icon}
Return
Two dependency constrained spanning tree problems
.png){kind=icon}
PRE
AI
DOI：10.1111/itor.12690.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We introduce two spanning tree problems with dependency constraints, where an edge can be chosen only if at least one or all edges in its dependency set are also chosen, respectively. The dependencies on the input graph G are described by a digraph D whose vertices are the edges of G, and the in-neighbors of a vertex are its dependency set. We show that both problems are NP-hard even if G is an outerplanar chordal graph with diameter 2 or maximum degree 3, and D is a disjoint union of arborescences of height 2. We also prove that the problems are inapproximable to a lnn factor, unless P=NP, and that they are W[2]-hard. As an attempt to narrow the hardness gap, we present two polynomial cases. We test integer linear programming formulations based on directed cut (DCUT) and Miller-Tucker-Zemlin (MTZ) constraints. Computational experiments are reported.
Keywords:
dependency constrained spanning tree
computational complexity
inapproximability
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.9
Papers:
1.8K
Citations:
3.7K