TY - JOUR

T1 - The minimum spanning tree problem with conflict constraints and its variations

AU - Zhang, Ruonan

AU - Kabadi, Santosh N.

AU - Punnen, Abraham P.

N1 - Funding Information:
This work was supported by NSERC discovery grants awarded to Santosh N. Kabadi and Abraham P. Punnen.

PY - 2011/5

Y1 - 2011/5

N2 - We consider the minimum spanning tree problem with conflict constraints (MSTC). The problem is known to be strongly NP-hard and computing even a feasible solution is NP-hard. When the underlying graph is a cactus, we show that the feasibility problem is polynomially bounded whereas the optimization version is still NP-hard. When the conflict graph is a collection of disjoint cliques, (equivalently, when the conflict relation is transitive) we observe that MSTC can be solved in polynomial time. We also identify other special cases of MSTC that can be solved in polynomial time. Exploiting these polynomially solvable special cases we derive strong lower bounds. Also, various heuristic algorithms and feasibility tests are discussed along with preliminary experimental results. As a byproduct of this investigation, we show that if an ε-optimal solution to the maximum clique problem can be obtained in polynomial time, then a (3ε-1)-optimal solution to the maximum edge clique partitioning (Max-ECP) problem can be obtained in polynomial time. As a consequence, we have a polynomial time approximation algorithm for the Max-ECP with performance ratio O(n(loglogn)2/log3n), improving the best previously known bound of O(n).

AB - We consider the minimum spanning tree problem with conflict constraints (MSTC). The problem is known to be strongly NP-hard and computing even a feasible solution is NP-hard. When the underlying graph is a cactus, we show that the feasibility problem is polynomially bounded whereas the optimization version is still NP-hard. When the conflict graph is a collection of disjoint cliques, (equivalently, when the conflict relation is transitive) we observe that MSTC can be solved in polynomial time. We also identify other special cases of MSTC that can be solved in polynomial time. Exploiting these polynomially solvable special cases we derive strong lower bounds. Also, various heuristic algorithms and feasibility tests are discussed along with preliminary experimental results. As a byproduct of this investigation, we show that if an ε-optimal solution to the maximum clique problem can be obtained in polynomial time, then a (3ε-1)-optimal solution to the maximum edge clique partitioning (Max-ECP) problem can be obtained in polynomial time. As a consequence, we have a polynomial time approximation algorithm for the Max-ECP with performance ratio O(n(loglogn)2/log3n), improving the best previously known bound of O(n).

KW - Combinatorial optimization

KW - Conflict graphs

KW - Heuristics

KW - Matroid intersection

KW - Minimum spanning tree

UR - http://www.scopus.com/inward/record.url?scp=79955596950&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2010.08.001

DO - 10.1016/j.disopt.2010.08.001

M3 - Article

AN - SCOPUS:79955596950

SN - 1572-5286

VL - 8

SP - 191

EP - 205

JO - Discrete Optimization

JF - Discrete Optimization

IS - 2

ER -