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

Bernáth, Attila and Király, Zoltán (2014) On the tractability of some natural packing, covering and partitioning problems. DISCRETE APPLIED MATHEMATICS, 180. pp. 25-35. ISSN 0166-218X

Preview

Text 1407.4999v1.pdf Download (518kB) | Preview

Abstract

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) 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 E of G, so that they are edge-disjoint? Partitioning problem: can we partition E into an object of type A and one of type B? Covering problem: can we cover E 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 s-t path P and an s′-t′ path P′ that are edge-disjoint. However, many others were not, for example can we find an s-t path P ⊆ E and a spanning tree T ⊆ 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). © 2014 Elsevier B.V. All rights reserved.

Actions (login required)

Edit Item