The complexity of the Pk partition problem and related problems in bipartite graphs

Monnot, Jérôme; Toulouse, Sophie

Monnot, Jérôme; Toulouse, Sophie (2005), The complexity of the Pk partition problem and related problems in bipartite graphs, in Plasil, Frantisek; Sack, Harald; Meinel, Christoph; Van der Hoek, Wiebe; Italiano, Giuseppe F.; Van Leeuwen, Jan, SOFSEM 2007: Theory and Practice of Computer Science 33nd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20-26, 2007, Proceedings, Springer : Berlin, p. 422-433. http://dx.doi.org/10.1007/978-3-540-69507-3_36

Type

Communication / Conférence

External document link

http://hal.archives-ouvertes.fr/hal-00152314/en/

Date

2005

Conference title

33nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2007)

Conference date

2007-01

Conference city

Harrachov

Conference country

République tchèque

Book title

SOFSEM 2007: Theory and Practice of Computer Science 33nd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20-26, 2007, Proceedings

Book author

Plasil, Frantisek; Sack, Harald; Meinel, Christoph; Van der Hoek, Wiebe; Italiano, Giuseppe F.; Van Leeuwen, Jan

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

4362

Published in

Berlin

ISBN

978-3-540-69506-6

Number of pages

937

Pages

422-433

Abstract (EN)

In this paper, we continue the investigation made in [MT05] about the approximability of Pk partition problems, but focusing here on their complexity. Precisely, we aim at designing the frontier between polynomial and NP-complete versions of the Pk partition problem in bipartite graphs, according to both the constant k and the maximum degree of the input graph. We actually extend the obtained results to more general classes of problems, namely, the minimum k-path partition problem and the maximum Pk packing problem. Moreover, we propose some simple approximation algorithms for those problems.

Subjects / Keywords

Pk-partition; maximum (weighted) Pk-packing; minimum k-path partition; bipartite graphs; NP-completeness; approximation algorithms