Torsten Mütze

STOC Conference 2023 Conference Paper

Kneser Graphs Are Hamiltonian

• Arturo Merino
• Torsten Mütze
• Namrata

For integers ‍ k ≥ 1 and n ≥ 2 k +1, the Kneser graph ‍ K ( n , k ) has as vertices all k -element subsets of an n -element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph ‍ K (5,2). This problem received considerable attention in the literature, including a recent solution for the sparsest case n =2 k +1. The main contribution of this paper is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph ‍ J ( n , k , s ) has as vertices all k -element subsets of an n -element ground set, and an edge between any two sets whose intersection has size exactly ‍ s . Clearly, we have K ( n , k )= J ( n , k ,0), i.e., generalized Johnson graph include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from ‍1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

FOCS Conference 2023 Conference Paper

Traversing combinatorial 0/1-polytopes via optimization

• Arturo Merino
• Torsten Mütze

In this paper, we present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets and polytopes. Our method relies on a simple and versatile algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope $\operatorname{conv}(X)$, where $X \subseteq\{0, 1\}^{n}$. The algorithm uses as a black box any algorithm that solves a variant of the classical linear optimization problem $\min \{w \cdot x \mid x \in X\}$, and the resulting delay, i. e. , the running time per visited vertex on the Hamilton path, is only by a factor of $\log n$ larger than the running time of the optimization algorithm. When X encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope $\operatorname{conv}(X)$ along a Hamilton path corresponds to listing the combinatorial objects by local change operations, i. e. , we obtain Gray code listings. As concrete results of our general framework, we obtain efficient algorithms for generating all (c-optimal) bases and independent sets in a matroid; (c-optimal) spanning trees, forests, matchings, maximum matchings, and c-optimal matchings in a general graph; vertex covers, minimum vertex covers, c-optimal vertex covers, stable sets, maximum stable sets and c-optimal stable sets in a bipartite graph; as well as antichains, maximum antichains, c-optimal antichains, and c-optimal ideals of a poset. Specifically, the delay and space required by these algorithms are polynomial in the size of the matroid ground set, graph, or poset, respectively. Furthermore, all of these listings correspond to Hamilton paths on the corresponding combinatorial polytopes, namely the base polytope, matching polytope, vertex cover polytope, stable set polytope, chain polytope and order polytope, respectively. As another corollary from our framework, we obtain an $\mathcal{O}\left(t_{\text{LP}} \log n\right)$ delay algorithm for the vertex enumeration problem on 0/1-polytopes $\left\{x \in \mathbb{R}^{n} \mid A x \leq b\right\}$, where $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^{m}$, and $t_{\text{LP}}$ is the time needed to solve the linear program $\min \{w \cdot x \mid A x \leq b\}$. This improves upon the 25-year old $\mathcal{O}\left(t_{\text{LP}} n\right)$ delay algorithm due to Bussieck and Lübbecke.

SODA Conference 2023 Conference Paper

Zigzagging through acyclic orientations of chordal graphs and hypergraphs

• Jean Cardinal
• Hung Phuc Hoang
• Arturo Merino
• Torsten Mütze

In 1993, Savage, Squire, and West described an inductive construction for generating every acyclic orientation of a chordal graph exactly once, flipping one arc at a time. We provide two generalizations of this result. Firstly, we describe Gray codes for acyclic orientations of hypergraphs that satisfy a simple ordering condition, which generalizes the notion of perfect elimination order of graphs. This unifies the Savage-Squire-West construction with a recent algorithm for generating elimination trees of chordal graphs (SODA 2022). Secondly, we consider quotients of lattices of acyclic orientations of chordal graphs, and we provide a Gray code for them, addressing a question raised by Pilaud (FPSAC 2022). This also generalizes a recent algorithm for generating lattice congruences of the weak order on the symmetric group (SODA 2020). Our algorithms are derived from the Hartung-Hoang-Mutze-Williams combinatorial generation framework, and they yield simple algorithms for computing Hamilton paths and cycles on large classes of polytopes, including chordal nestohedra and quotientopes. In particular, we derive an efficient implementation of the Savage-Squire-West construction. Along the way, we give an overview of old and recent results about the polyhedral and order-theoretic aspects of acyclic orientations of graphs and hypergraphs. * Arturo Merino was supported by ANID Becas Chile 2019-72200522. Torsten Mütze was supported by Czech Science Foundation grant GA 22-15272S. Arturo Merino and Torsten Mütze were also supported by German Science Foundation grant 413902284.

SODA Conference 2022 Conference Paper

Efficient generation of elimination trees and graph associahedra

• Jean Cardinal
• Arturo Merino
• Torsten Mütze

An elimination tree for a connected graph G is a rooted tree on the vertices of G obtained by choosing a root x and recursing on the connected components of G – x to produce the subtrees of x. Elimination trees appear in many guises in computer science and discrete mathematics, and they encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung-Hoang-Mütze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph G can be generated by tree rotations using a simple greedy algorithm. This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph G can be implemented in time (m + n ) per generated elimination tree, where m and n are the number of edges and vertices of G, respectively. If G is a tree, we improve this to a loopless algorithm running in time (1) per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of G, rather than just Hamilton path, if the graph G is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i. e. , it computes a Hamilton path on the graph associahedron of G if and only if G is chordal.

MFCS Conference 2022 Conference Paper

The Hamilton Compression of Highly Symmetric Graphs

• Petr Gregor
• Arturo Merino
• Torsten Mütze

We say that a Hamilton cycle C = (x₁, …, x_n) in a graph G is k-symmetric, if the mapping x_i ↦ x_{i+n/k} for all i = 1, …, n, where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices x₁, …, x_n equidistantly on a circle and draw the edges of G as straight lines, then the drawing of G has k-fold rotational symmetry, i. e. , all information about the graph is compressed into a 360^∘/k wedge of the drawing. We refer to the maximum k for which there exists a k-symmetric Hamilton cycle in G as the Hamilton compression of G. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases we determine their Hamilton compression exactly, and in other cases we provide close lower and upper bounds. The cycles we construct have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced.

SODA Conference 2021 Conference Paper

On a combinatorial generation problem of Knuth

• Arturo Merino
• Ondrej Micka
• Torsten Mütze

The well-known middle levels conjecture asserts that for every integer n ≥ 1, all binary strings of length 2( n + 1) with exactly n + 1 many 0s and 1s can be ordered cyclically so that any two consecutive strings differ in swapping the first bit with a complementary bit at some later position. In his book ‘The Art of Computer Programming Vol. 4A’ Knuth raised a stronger form of this conjecture (Problem 56 in Section 7. 2. 1. 3), which requires that the sequence of positions with which the first bit is swapped in each step of such an ordering has 2 n + 1 blocks of the same length, and each block is obtained by adding s = 1 (modulo 2 n + 1) to the previous block. In this work, we prove Knuth's conjecture in a more general form, allowing for arbitrary shifts s ≥ 1 that are coprime to 2 n + 1. We also present an algorithm to compute this ordering, generating each new bitstring in ( n ) time, using ( n ) memory in total.

SODA Conference 2020 Conference Paper

Combinatorial generation via permutation languages

• Elizabeth J. Hartung
• Hung Phuc Hoang
• Torsten Mütze
• Aaron Williams 0001

STOC Conference 2018 Conference Paper

Sparse Kneser graphs are Hamiltonian

• Torsten Mütze
• Jerri Nummenpalo
• Bartosz Walczak

For integers k ≥1 and n ≥2 k +1, the Kneser graph K ( n , k ) is the graph whose vertices are the k -element subsets of {1,…, n } and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K (2 k +1, k ) are also known as the odd graphs . We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every k ≥3, the odd graph K (2 k +1, k ) has a Hamilton cycle. This and a known conditional result due to Johnson imply that all Kneser graphs of the form K (2 k +2 a , k ) with k ≥3 and a ≥0 have a Hamilton cycle. We also prove that K (2 k +1, k ) has at least 2 2 k −6 distinct Hamilton cycles for k ≥6. Our proofs are based on a reduction of the Hamiltonicity problem in the odd graph to the problem of finding a spanning tree in a suitably defined hypergraph on Dyck words.

TCS Journal 2018 Journal Article

Trimming and gluing Gray codes

• Petr Gregor
• Torsten Mütze

We consider the algorithmic problem of generating each subset of [ n ]: = { 1, 2, …, n } whose size is in some interval [ k, l ], 0 ≤ k ≤ l ≤ n, exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For k = 0 and l = n this is the classical problem of generating all 2 n subsets of [ n ] by element additions/removals, and for k = l this is the classical problem of generating all ( n k ) subsets of [ n ] by element exchanges. We prove the existence of such cyclic minimum-change enumerations for a large range of values n, k, and l, improving upon and generalizing several previous results. For all these existential results we provide optimal algorithms to compute the corresponding Gray codes in constant O ( 1 ) time per generated set and O ( n ) space. Rephrased in terms of graph theory, our results establish the existence of (almost) Hamilton cycles in the subgraph of the n-dimensional cube Q n induced by all levels [ k, l ]. We reduce all remaining open cases to a generalized version of the middle levels conjecture, which asserts that the subgraph of Q 2 k + 1 induced by all levels [ k − c, k + 1 + c ], c ∈ { 0, 1, …, k }, has a Hamilton cycle. We also prove an approximate version of this generalized conjecture, showing that this graph has a cycle that visits a ( 1 − o ( 1 ) ) -fraction of all vertices.

SODA Conference 2017 Conference Paper

A constant-time algorithm for middle levels Gray codes

• Torsten Mütze
• Jerri Nummenpalo

For any integer n ≥ 1 a middle levels Gray code is a cyclic listing of all n -element and ( n + 1)- element subsets of {1, 2, …, 2n +1} such that any two consecutive subsets differ in adding or removing a single element. The question whether such a Gray code exists for any n ≥ 1 has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T. Mütze. Proof of the middle levels conjecture. To appear in Proc. London Math. Soc. , 2014]. In a follow-up paper [T. Mütze and J. Nummenpalo. An efficient algorithm for computing a middle levels Gray code. Proc. ESA, 2015] this existence proof was turned into an algorithm that computes each new set in the Gray code in time O ( n ) on average. In this work we complete this line of research by presenting an algorithm for computing a middle levels Gray code in optimal time and space: Each new set is generated in time O (1), and the required space is O ( n ).

SODA Conference 2011 Conference Paper

Coloring random graphs online without creating monochromatic subgraphs

• Torsten Mütze
• Thomas Rast
• Reto Spöhel