  


Paths, Trees and Matchings under Disjunctive Constraints
Andreas Darmann (andreas.darmannunigraz.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 socalled 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 NPhard, 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 NPhard 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 APXhardness 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 Download: [PDF] Entry Submitted: 10/04/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  