A Polynomial-Time Approximation Algorithm for Complete Interval Minors
Romain Bourneuf, Julien Cocquet, Chaoliang Tang, Stéphan Thomassé · 2025
Read A Polynomial-Time Approximation Algorithm for Complete Interval Minors by Romain Bourneuf, Julien Cocquet, Chaoliang Tang, Stéphan Thomassé (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-05997.txt.
Introduction
Romain Bourneuf and co-authors give a fast approximation algorithm for finding complete graph patterns inside ordered graphs, in a paper from 2025. A minor is what remains after shrinking connected parts of a graph to single points. For ordered graphs, the allowed shrinks respect the vertex order, forming interval minors.
Deciding whether a complete graph is a minor is tractable in general, but good approximations were missing. Their algorithm runs in polynomial time and guarantees a factor that depends only on the target size, not the graph size, though that factor grows very fast. The proof rests on delayed decompositions: ordered graphs avoiding the pattern are built from three simple operations. A side result shows such graphs need only boundedly many colors.
Catalog record
| CREATOR | Romain Bourneuf, Julien Cocquet, Chaoliang Tang, Stéphan Thomassé |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-05997
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Polynomial-Time Approximation Algorithm for Complete Interval Minors Romain Bourneuf, Julien Cocquet, Chaoliang Tang, Stéphan Thomassé Abstract As shown by Robertson and Seymour, deciding whether the complete graph K t K_{t} is a minor of an input graph G G is a fixed parameter tractable problem when parameterized by t t . From the approximation viewpoint, the gap to fill is quite large, as there is no PTAS for finding the largest complete minor unless 𝖯 = 𝖭𝖯 {\mathsf{P}}={\mathsf{NP}} , whereas a polytime O ( n ) O(\sqrt{n}) -approximation algorithm was given by Alon, Lingas and Wahlén. We investigate the complexity of finding K t 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 ) f(t) -approximation algorithm, where f f is triply exponential in t t but independent of n n . The algorithm is based on delayed decompositions and shows that ordered graphs without a K t 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 K_{t} as an interval minor have bounded chromatic number. 1 Introduction Complete minors in graphs form an extensively studied subject, notably featuring the fundamental result of Robertson and Seymour [ 29 ] , which asserts that testing whether the complete graph K_{t} is a minor of an input graph G on n vertices can be done in time f(t)\cdot n^{3} . This was proved in the series of Graph Minors papers, which also provided a decomposition theorem of K_{t} -minor-free graphs [ 30 ] (whose bounds were recently improved significantly by Gorsky, Seweryn and Wiederrecht [ 17 ] ). One of the key basic facts allowing such a result is that K_{t} -minor-free graphs are sparse, i.e. they have a linear number of edges. Recently, Korhonen, Pilipczuk and Stamoulis [ 24 ] provided an algorithm running in time f(t)\cdot n^{1+o(1)} for the same problem, improving on a quadratic algorithm from Kawarabayashi, Kobayashi and Reed [ 21 ] . From the approximation point of view, the landscape is much less understood. The first hardness result is due to Eppstein [ 12 ] : finding the size of a largest complete minor is {\mathsf{NP}} -hard. This was extended by Wahlén [ 32 ] , who showed that there is no polynomial time approximation scheme (PTAS) for the size of a largest complete minor, unless {\mathsf{P}}={\mathsf{NP}} . The current best known approximation factor achievable in polynomial time is O(\sqrt{n}) , as shown by Alon, Lingas and Wahlén [ 1 ] . Up to this day, it is still open whether this problem admits a polytime f(OPT) approximation algorithm. The goal of this paper is to investigate the corresponding problem for complete interval minors in ordered graphs. An ordered graph (G,<) is a graph G=(V,E) equipped with a linear order < on its vertices. We will consistently denote the number of vertices by n , and the number of edges by m . We usually denote the vertices as v_{1},\dots,v_{n} , enumerated according to < . For simplicity of notation, we will sometimes omit the order < and talk about an ordered graph G . An interval minor of (G,<) is obtained by deleting some edges of G as well as iteratively contracting pairs of vertices which are consecutive in < . An example is displayed in Figure 1 . Figure 1: A K_{4} interval minor: the red zones represent the intervals we contract and the red edges are the remaining edges. Observe that this interval minor model is not a minor model since we contracted non-connected subsets of vertices. The central computational problem on interval minors is the following: Interval Minor Detection Input: Two ordered graphs G and H . Question: Is H an interval minor of G ? The complete study of the computational complexity of this question is probably very challenging, and a good first step is to limit ourselves (as for usual minors) to the case where H is a complete graph. The crucial fact to observe is that K_{t} -interval-minor-free ordered graphs can be very complex. Say that a bipartite ordered graph (G,<) with edges between two parts X and Y is monotone if either X<Y or Y<X . Then, observe that the monotone K_{t,t} does not contain K_{4} as an interval minor. In particular, K_{4} -interval-minor-free ordered graphs can have a quadratic number of edges. They also form a large class of graphs (with growth at least 2^{n^{2}/4} ) as they contain all subgraphs of the monotone K_{n/2,n/2} . Therefore, any attempt to effectively construct K_{t} -interval-minor-free ordered graphs must involve an operation allowing the creation of arbitrary monotone bipartite graphs. The landscape of K_{t} -interval-minor-free ordered graphs thus seems very different from the one of K_{t} -minor-free graphs. However, a strong connection exists between these two worlds: the right analogy with graph minors involves monotone- K_{t,t} -interval-minor-free ordered graphs. To see this, let us first recall the celebrated Marcus-Tardos theorem [ 26 ] : Theorem 1 . There exists a function f such that every ordered graph on n vertices with at least f(t)\cdot n edges contains a monotone K_{t,t} as an interval minor. The notion of interval minors was formally introduced by Fox [ 13 ] to prove bounds on the function f of Theorem 1 . The upper bound was later improved by Cibulka and Kynčl [ 11 ] , again using interval minors. Theorem 1 gave a positive answer to a conjecture of Füredi and Hajnal [ 14 ] , stating that for every permutation matrix P , there exists a constant c_{P} such that every n\times n binary matrix with at least c_{P}\cdot n entries 1 contains P as a pattern. This result was later generalized to matrices in higher dimension by Klazar and Marcus [ 23 ] . The corresponding bound was later improved by Geneson and Tian [ 16 ] , once more using interval minors. In [ 13 ] , Fox suggested to conduct a thorough study of ordered graphs avoiding a given interval minor, with the hope of developing a theory analogue to the graph minor theory of Robertson and Seymour. There have been several papers going in that direction, see for instance [ 27 , 25 , 22 ] . In this paper, we continue this line of research by providing a decomposition theorem for K_{t} -interval-minor-free graphs. The Marcus-Tardos theorem therefore implies that monotone- K_{t,t} -interval-minor-free ordered graphs are sparse, as are K_{t} -minor-free graphs (in the non-ordered case). A second analogy between these two classes appears from the computational angle: Theorem 2 . There exists a function g such that testing whether an ordered graph (G,<) contains a monotone K_{t,t} as an interval minor can be done in time g(t)\cdot|V(G)| . The cornerstone of this algorithm is the {\mathsf{FPT}} algorithm of Guillemot and Marx [ 18 ] for detecting a pattern in a permutation. Their algorithm amounts to detecting a monotone K_{t,t} as an interval minor in a monotone matching.