Combinatorial optimization problems with conflict graphs

A. Darmann, U. Pferschy, J. Schauer, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Downloads (Pure)

Abstract

Conflict graphs impose disjunctive constraints for pairs of jobs, items, edges or other objects in a combinatorial optimization problem. Equivalently, the feasible domain of the considered problem is restricted to stable sets in the given conflict graph. After reviewing in our presentation results from the literature for bin packing and scheduling problems with conflict graphs, we first consider the classical 0-1 knapsack problem. Adding a conflict graph makes the problem strongly NP-hard but for three special graph classes, namely trees, graphs with bounded treewidth and chordal graphs, we can develop pseudopolynomial algorithms. From these we can easily derive fully polynomial time approximation schemes (FPTAS). Secondly, we study the minimum spanning tree problem and show that the border between polynomially solvable and NP-hard is given by moving from a conflict graph containing only isolated edges to paths of length 2.
Original languageEnglish
Title of host publicationProceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009, Paris, France, June 2-4, 2009)
EditorsS. Cafieri, A. Mucherino, G. Nannicini, F. Tarissan, L. Liberti
Pages293-296
Publication statusPublished - 2009

Fingerprint Dive into the research topics of 'Combinatorial optimization problems with conflict graphs'. Together they form a unique fingerprint.

  • Cite this

    Darmann, A., Pferschy, U., Schauer, J., & Woeginger, G. J. (2009). Combinatorial optimization problems with conflict graphs. In S. Cafieri, A. Mucherino, G. Nannicini, F. Tarissan, & L. Liberti (Eds.), Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009, Paris, France, June 2-4, 2009) (pp. 293-296)