Finding Christmas cacti

The Christmas cactus is a kind of plant with jointed leaves, but it's also (after a recent FOCS paper by Leighton and Moitra) a kind of graph: one in which every edge belongs to at most one cycle (that is, a cactus graph) with the additional property that every vertex belongs to at most two biconnected components. These constraints cause the Christmas cactus graphs to have a similar jointed shape to the Christmas cactus plants: they consist of cycles and single-edge degenerate cycles, joined in a tree-like structure in which pairs of cycles meet at articulation points.

Leighton and Moitra showed that every Christmas cactus can have its vertices placed in the plane in such a way that all pairs of vertices can be connected by greedy paths, paths in which the distance to the destination decreases at each step; the motivation behind this sort of embedding is to provide virtual coordinates for each node of a distributed communications network in order to allow simple greedy routing algorithms to route messages from any node to any other node. The same sort of greedy embedding for Christmas cacti was also independently found by Angelini, Frati, and Grilli in a paper from Graph Drawing 2008. But Leighton and Moitra also showed that every \(3\)-connected planar graph (or a little more generally every \(3\)-connected \(K_{3,3}\)-minor-free graph) has a spanning Christmas cactus subgraph, settling an open question of Papadimitriou and Ratajczak on whether greedy embeddings could always be found for this larger class of graphs.

So this naturally raises the question, just what are the graphs that have Christmas cactus spanning subgraphs? They include, for instance, hard-to-recognize subclasses such as the Hamiltonian graphs, because a Hamiltonian path or cycle is itself a Christmas cactus, but they also include easier classes such as the planar \(3\)-connected graphs. Is a Christmas cactus hard to find?

Sadly, but unsurprisingly, the answer turns out to be yes: recognizing graphs with spanning Christmas cactus subgraphs is \(\mathsf{NP}\)-complete. A reduction from the Hamiltonian cycle problem is easy: given a graph \(G\) such as the Petersen graph in the figure below, form another graph \(H\) by adding a new degree-one neighbor to each vertex of \(G\) (this is the rooted product of \(G\) with a single edge). Then if \(G\) is Hamiltonian, \(H\) has a Christmas cactus formed by the Hamiltonian cycle together with the edges connecting to all the new vertices. But that's the only shape a Christmas cactus in \(H\) can take, because the leaves use up one of the two biconnected components at each vertex, so the part in \(G\) has to be biconnected, and a Hamiltonian cycle is the only possible biconnected cactus.

The reduction preserves planarity, and finding Hamiltonian cycles is known hard even in planar graphs, so finding Christmas cacti in planar graphs without the assumption of \(3\)-connectedness is also hard.

Comments: