  


On Recognizing Staircase Compatibility
Andreas Bärmann(Andreas.Baermannmath.unierlangen.de) Abstract: For the problem to find an mclique in an mpartite graph, staircase compatibility has recently been introduced as a polynomialtime solvable special case. It is a property of a graph together with an mpartition of the vertex set and total orders on each subset of the partition. In optimization problems involving mcliques in mpartite graphs as a subproblem, it allows for totally unimodular linear programming formulations which have shown to efficiently solve problems from different applications. In this work, we address questions concerning the recognizability of this property in the case where the mpartition of the graph is given, but suitable total orders are to be determined. While finding these total orders is NPhard in general, we give several conditions under which it can be done in polynomial time. For bipartite graphs, we present a polynomialtime algorithm to recognize staircase compatibility, and show that staircase total orders are unique up to a small set of reordering operations. On mpartite graphs, where the recognition problem is NPcomplete in the general case, we identify a polynomially solvable subcase and also provide a corresponding algorithm to compute the total orders. Finally, we evaluate the performance of our ordering algorithm for mpartite graphs on a set of artificial instances as well as realworld instances from a railway timetabling application. It turns out that applying the ordering algorithm to the realworld instances and subsequently solving the problem via the aforementioned totally unimodular reformulations indeed outperforms a generic formulation which does not exploit staircase compatibility. Keywords: Staircase Structure,Clique Problem,MultipleChoice Constraints,Scheduling Category 1: Combinatorial Optimization (Graphs and Matroids ) Category 2: Integer Programming (01 Programming ) Category 3: Applications  OR and Management Sciences (Scheduling ) Citation: Download: [PDF] Entry Submitted: 11/29/2020 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  