The minimum spanning tree problem with conflict constraints and its variations

We consider the minimum spanning tree problem with conflict constraints (MSTC). It is observed that computing an $\epsilon$-optimal solution to MSTC is NP-hard for any $\epsilon >0$. For a general conflict graph, computing even a feasible solution is NP-hard. When the underlying graph is a cactus, we show that the feasibility problem is polynomially bounded … Read more