On the tractability of some natural packing, covering and partitioning problems

In this paper we fix 7 types of undirected graphs: paths, paths with prescribed endvertices, circuits, forests, spanning trees, (not necessarily spanning) trees and cuts. Given an undirected graph G=(V,E)G=(V,E) and two “object types” A and B chosen from the alternatives above, we consider the following questions. Packing problem: can we find an object of type A and one of type B in the edge set EE of GG, so that they are edge-disjoint? Partitioning problem: can we partition EE into an object of type A and one of type B? Covering problem: can we cover EE with an object of type A, and an object of type B? This framework includes 44 natural graph theoretic questions. Some of these problems were well-known before, for example covering the edge-set of a graph with two spanning trees, or finding an ss-tt path PP and an s′s′-t′t′ path P′P′ that are edge-disjoint. However, many others were not, for example can we find an ss-tt path P⊆EP⊆E and a spanning tree T⊆ET⊆E that are edge-disjoint? Most of these previously unknown problems turned out to be NP-complete, many of them even in planar graphs. This paper determines the status of these 44 problems. For the NP-complete problems we also investigate the planar version, for the polynomial problems we consider the matroidal generalization (wherever this makes sense).