Algorithms for the clique problem with multiple-choice constraints under a series–parallel dependency graph

Bärmann A, Gemander P, Merkert M, Wiertz AK, Zaragoza Martínez FJ (2023)

Publication Type: Journal article

Publication year: 2023

Journal

Discrete Applied Mathematics Elsevier

Book Volume: 324

Pages Range: 145-166

DOI: 10.1016/j.dam.2022.09.015

Abstract

The clique problem with multiple-choice constraints (CPMC), i.e. the problem of finding a k-clique in a k-partite graph with known partition, occurs as a substructure in many real-world applications, in particular scheduling and railway timetabling. Although CPMC is NP-complete in general, it is known to be solvable in polynomial time when the so-called dependency graph of G is a forest. In this article, we focus on the special case CPMCSP, where the dependency graph of G is series–parallel. We give a polynomial-time algorithm for CPMCSP using dynamic programming. Further, we provide some facet-inducing inequalities of the CPMCSP polytope, mainly using properties of the stable set polytope of the complement graph of G. Among these, we give a separation algorithm for the so-called embedded odd-clique-cycle inequalities using dynamic programming. If the number of vertices per subset of the k-partition is bounded, then its runtime is polynomial in the size of the dependency graph.

Authors with CRIS profile

Andreas Bärmann Professur für Data Driven Design of Dynamical Systems Ann-Kathrin Wiertz Professur für Volkswirtschaftslehre

Related research project(s)

B09 „Strategische Buchungsentscheidungen im Entry-Exit-System“ TRR 154: Mathematical Modelling, Simulation and Optimisation Using the Example of Gas Networks (TRR 154) July 1, 2018 - June 30, 2022

Involved external institutions

Fraunhofer-Institut für Integrierte Schaltungen (IIS) DE Germany (DE) Universidad Autónoma Metropolitana (UAM) MX Mexico (MX) Technische Universität Braunschweig DE Germany (DE)

How to cite

APA:

Bärmann, A., Gemander, P., Merkert, M., Wiertz, A.-K., & Zaragoza Martínez, F.J. (2023). Algorithms for the clique problem with multiple-choice constraints under a series–parallel dependency graph. Discrete Applied Mathematics, 324, 145-166. https://dx.doi.org/10.1016/j.dam.2022.09.015

MLA:

Bärmann, Andreas, et al. "Algorithms for the clique problem with multiple-choice constraints under a series–parallel dependency graph." Discrete Applied Mathematics 324 (2023): 145-166.

BibTeX: Download