REAL

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

[img]
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.

Item Type: Article
Uncontrolled Keywords: Tree; PATH; Partitioning; PACKING; graph algorithm; FOREST; cut; Covering; CIRCUIT
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 20 Jan 2015 15:26
Last Modified: 20 Jan 2015 15:26
URI: http://real.mtak.hu/id/eprint/20689

Actions (login required)

Edit Item Edit Item