← All papers
First page of Recognizing Label-Connected Graphs

Recognizing Label-Connected Graphs

Ralf Klasing, George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis

cs.DS Nov 3, 2026 · v1 cs.DM
The classical T-/M-witness characterization of temporally connectable (gossiping) multigraphs is formalized in Lean 4, with the formalization provided as an artifact.
In classical gossiping, each participant initially knows a distinct piece of information. Whenever two participants call each other, they exchange everything they know. We study Gossiping: given an undirected multigraph whose vertices represent participants and whose edges represent available calls, decide whether the calls can be ordered so that every participant learns all information, using each edge at most once. Equivalently, can one time label per edge make the graph temporally connected by strict temporal paths? This recognition problem is NP-complete; we study its parameterized complexity. After linear-time preprocessing, we give an exact $O(3^{n/3}n^3)$-time algorithm and a deterministic $2^{O(tw)}n$-time algorithm, where $n$ is the number of vertices and $tw$ is the treewidth of the underlying simple graph. We introduce a Tree Contraction Rule that extends the treewidth algorithm to single-exponential algorithms for parameters that may remain small on dense graphs, such as tree-independence number and clique-width, without requiring a decomposition as input. For the excess $δ=m-(2n-4)$ over the minimum number of calls, where $m$ is the number of edges, we give a randomized $2^{O(δ)}n^3$-time algorithm with one-sided error. Its main subroutine solves Rooted Independent Cycle: finding a cycle through four prescribed vertices whose edges are independent in a represented linear matroid. We solve this problem deterministically in $2^{O(r)}m$ arithmetic operations over the finite field representing the matroid, where $r$ is its rank. Gossiping is polynomial-time solvable at maximum degree four, counting parallel edges, but NP-complete on planar simple graphs of maximum degree five. The treewidth algorithm yields a $2^{O(\sqrt n)}$-time algorithm on planar graphs.

Gossiping asks whether the edges of a multigraph can be ordered as calls, each used at most once, so that every participant learns all information. Equivalently, it asks whether one time label per edge makes the graph temporally connected. The problem is NP-complete, and its parameterized complexity was open.

The algorithms build on the classical characterization of yes-instances via T-witnesses and M-witnesses. A self-contained proof of this characterization is given and formalized in Lean 4. The authors develop a linear-time clean-up rule, a Tree Contraction Rule, connectivity dynamic programming over tree decompositions, and matroid-based cycle finding (Rooted Independent Cycle) for the excess parameter.

The algorithms run in O(3^{n/3} n^3) time exactly, in deterministic 2^{O(tw)} n time, and in single-exponential time for tree-independence number and clique-width. A randomized 2^{O(δ)} n^3 algorithm handles the excess δ. Gossiping is polynomial at maximum degree four and NP-complete on planar simple graphs of maximum degree five.