Paths, Trees and Matchings under Disjunctive Constraints
Andreas Darmann (andreas.darmannuni-graz.at)
Abstract: We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints. We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge. Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.
Keywords: minimal spanning tree; matching; shortest path; conflict graph; binary constraints.
Category 1: Combinatorial Optimization (Graphs and Matroids )
Category 2: Network Optimization
Citation: The final version of this article appeared in Discrete Applied Mathematics: http://www.sciencedirect.com/science/article/pii/S0166218X1000435X DOI: 10.1016/j.dam.2010.12.016
Entry Submitted: 10/04/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|