Optimization Online


Paths, Trees and Matchings under Disjunctive Constraints

Andreas Darmann (andreas.darmann***at***uni-graz.at)
Ulrich Pferschy (pferschy***at***uni-graz.at)
Joachim Schauer (joachim.schauer***at***uni-graz.at)
Gerhard J. Woeginger (gwoegi***at***win.tue.nl)

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

Download: [PDF]

Entry Submitted: 10/04/2009
Entry Accepted: 10/13/2009
Entry Last Modified: 12/01/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society