2026-08-11T07:40:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24381 2025-12-12T15:01:16Z ddc:004 open_access

A Polynomial-Time Approximation Algorithm for Complete Interval Minors Bourneuf, Romain Cocquet, Julien Tang, Chaoliang Thomassé, Stéphan Approximation algorithm Ordered graphs Interval minors Delayed decompositions As shown by Robertson and Seymour, deciding whether the complete graph K_t is a minor of an input graph G is a fixed parameter tractable problem when parameterized by t. From the approximation viewpoint, a substantial gap remains: there is no PTAS for finding the largest complete minor unless P = NP, whereas the best known result is a polytime O(√ n)-approximation algorithm by Alon, Lingas and Wahlén. We investigate the complexity of finding K_t as interval minor in ordered graphs (i.e. graphs with a linear order on the vertices, in which intervals are contracted to form minors). Our main result is a polytime f(t)-approximation algorithm, where f is triply exponential in t but independent of n. The algorithm is based on delayed decompositions and shows that ordered graphs without a K_t interval minor can be constructed via a bounded number of three operations: closure under substitutions, edge union, and concatenation of a stable set. As a byproduct, graphs avoiding K_t as an interval minor have bounded chromatic number. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Romain Bourneuf and Julien Cocquet and Chaoliang Tang and Stéphan Thomassé 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.15 urn:nbn:de:0030-drops-243814 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.15 eng https://creativecommons.org/licenses/by/4.0/legalcode