On Recognizing Staircase Compatibility

Andreas Bärmann (), Patrick Gemander (), Alexander Martin () and Maximilian Merkert ()
Additional contact information
Andreas Bärmann: Friedrich-Alexander-Universität Erlangen-Nürnberg
Patrick Gemander: Fraunhofer-Institut für Integrierte Schaltungen IIS
Alexander Martin: Friedrich-Alexander-Universität Erlangen-Nürnberg
Maximilian Merkert: Technische Universität Braunschweig

Journal of Optimization Theory and Applications, 2022, vol. 195, issue 2, No 4, 449-479

Abstract: Abstract For the problem to find an m-clique in an m-partite graph, staircase compatibility has recently been introduced as a polynomial-time solvable special case. It is a property of a graph together with an m-partition of the vertex set and total orders on each subset of the partition. In optimization problems involving m-cliques in m-partite 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 m-partition of the graph is given, but suitable total orders are to be determined. While finding these total orders is NP-hard in general, we give several conditions under which it can be done in polynomial time. For bipartite graphs, we present a polynomial-time algorithm to recognize staircase compatibility and show that staircase total orders are unique up to a small set of reordering operations. On m-partite graphs, where the recognition problem is NP-complete 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 m-partite graphs on a set of artificial instances as well as real-world instances from a railway timetabling application. It turns out that applying the ordering algorithm to the real-world 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; Multiple-choice constraints; Scheduling; 90C27; 90C35; 90C57; 90C90 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-022-02091-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:195:y:2022:i:2:d:10.1007_s10957-022-02091-2

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-022-02091-2

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().