
Pk partition problem and related problems in bipartite graphs
Monnot, Jérôme; Toulouse, Sophie (2007), Pk partition problem and related problems in bipartite graphs, in Van Leeuwen, Jan; Italiano, Giuseppe; Van der Hoek, Wiebe; Meinel, Christoph; Sack, Harald; Plasil, Franticek, 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
View/ Open
Type
Communication / ConférenceDate
2007Conference title
33nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM' 07)Conference date
2007-01Conference city
HarrachovConference country
République tchèqueBook 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, ProceedingsBook author
Van Leeuwen, Jan; Italiano, Giuseppe; Van der Hoek, Wiebe; Meinel, Christoph; Sack, Harald; Plasil, FranticekPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
4362Published in
Berlin
ISBN
978-3-540-69506-6
Number of pages
937Pages
422-433
Publication identifier
Metadata
Show full item recordAbstract (EN)
In this paper, we continue the investigation proposed in [15] about the approximability of P k partition problems, but focusing here on their complexity. More precisely, we prove that the problem consisting of deciding if a graph of nk vertices has n vertex disjoint simple paths {P 1, ⋯ ,P n } such that each path P i has k vertices is NP-complete, even in bipartite graphs of maximum degree 3. Note that this result also holds when each path P i is chordless in G[V(P i )]. Then, we prove that the optimization version of these problems, denoted by Max P 3 Packing and MaxInduced P 3 Packing, are not in PTAS in bipartite graphs of maximum degree 3. Finally, we propose a 3/2-approximation for Min3-PathPartition in general graphs within O(nm + n 2logn) time and a 1/3 (resp., 1/2)-approximation for MaxW P 3 Packing in general (resp., bipartite) graphs of maximum degree 3 within O(α(n,3n/2)n) (resp., O(n 2logn)) time, where α is the inverse Ackerman’s function and n = |V|, m = |E|.Subjects / Keywords
approximation algorithms; APX-hardness; NP-completeness; bipartite graphs; minimum k-path partition; maximum (weighted) induced Pk-packing; maximum (weighted) Pk- packing; Induced Pk-partition; Pk-partitionRelated items
Showing items related by title and author.
-
Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
-
Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
-
Monnot, Jérôme; Toulouse, Sophie (2007) Article accepté pour publication ou publié
-
Fritzilas, Epameinondas; Milanic, Martin; Monnot, Jérôme; Rios-Solis, Yasmin Agueda (2009) Document de travail / Working paper
-
Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence