Algorithms for the Clique Problem with Multiple-Choice Constraints under a Series-Parallel Dependency Graph

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.

Article

Download

View Algorithms for the Clique Problem with Multiple-Choice Constraints under a Series-Parallel Dependency Graph