2014/07/18 by Attila Bernáth, Bernáth, Attila, Zoltán Király +1 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Packing Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1407.4999
openalex publication_date 2014/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we fix 7 types of undirected graphs: paths, paths with\nprescribed endvertices, circuits, forests, spanning trees, (not necessarily\nspanning) trees and cuts. Given an undirected graph G=(V,E) and two "object\ntypes" \A and \B chosen from the alternatives above, we\nconsider the following questions. \Packing problem: can we find an\nobject of type \A and one of type \B in the edge set E of\nG, so that they are edge-disjoint? \Partitioning problem: can we\npartition E into an object of type \A and one of type \B?\n\Covering problem: can we cover E with an object of type\n\A, and an object of type \B? This framework includes 44\nnatural graph theoretic questions. Some of these problems were well-known\nbefore, for example covering the edge-set of a graph with two spanning trees,\nor finding an s-t path P and an s'-t' path P' that are\nedge-disjoint. However, many others were not, for example can we find an\ns-t path P\⊆ E and a spanning tree T\⊆ E that are\nedge-disjoint? Most of these previously unknown problems turned out to be\nNP-complete, many of them even in planar graphs. This paper determines the\nstatus of these 44 problems. For the NP-complete problems we also investigate\nthe planar version, for the polynomial problems we consider the matroidal\ngeneralization (wherever this makes sense).\n