In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs

Arnaud Casteigts, Timothée Corsini, Nils Morawietz

A temporal graph is a graph whose edges appear at certain points in time. These graphs are temporally connected (in class TC) if all vertices can reach each other by temporal paths…