Minimum length path decompositions

Bibliographic Details
Title:	Minimum length path decompositions
Authors:	Dereniowski, Dariusz, Kubiak, Wieslaw, Zwols, Yori
Source:	Journal of Computer and System Sciences 81 (2015) 1715-1747
Publication Year:	2013
Collection:	Computer Science Mathematics
Subject Terms:	Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics, 68Q25, 05C85, 68R10
More Details:	We consider a bi-criteria generalization of the pathwidth problem, where, for given integers $k,l$ and a graph $G$, we ask whether there exists a path decomposition $\cP$ of $G$ such that the width of $\cP$ is at most $k$ and the number of bags in $\cP$, i.e., the \emph{length} of $\cP$, is at most $l$. We provide a complete complexity classification of the problem in terms of $k$ and $l$ for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter tractable with respect to $k$, we prove that the generalized problem is NP-complete for any fixed $k\geq 4$, and is also NP-complete for any fixed $l\geq 2$. On the other hand, we give a polynomial-time algorithm that, for any (possibly disconnected) graph $G$ and integers $k\leq 3$ and $l>0$, constructs a path decomposition of width at most $k$ and length at most $l$, if any exists. As a by-product, we obtain an almost complete classification of the problem in terms of $k$ and $l$ for connected graphs. Namely, the problem is NP-complete for any fixed $k\geq 5$ and it is polynomial-time for any $k\leq 3$. This leaves open the case $k=4$ for connected graphs. Comment: Work presented at the 5th Workshop on GRAph Searching, Theory and Applications (GRASTA 2012), Banff International Research Station, Banff, AB, Canada
Document Type:	Working Paper
DOI:	10.1016/j.jcss.2015.06.011
Access URL:	http://arxiv.org/abs/1302.2788
Accession Number:	edsarx.1302.2788
Database:	arXiv

FullText	Text: Availability: 0 CustomLinks: – Url: http://arxiv.org/abs/1302.2788 Name: EDS - Arxiv Category: fullText Text: View this record from Arxiv MouseOverText: View this record from Arxiv – Url: https://resolver.ebsco.com/c/xy5jbn/result?sid=EBSCO:edsarx&genre=article&issn=&ISBN=&volume=&issue=&date=20130212&spage=&pages=&title=Minimum length path decompositions&atitle=Minimum%20length%20path%20decompositions&aulast=Dereniowski%2C%20Dariusz&id=DOI:10.1016/j.jcss.2015.06.011 Name: Full Text Finder (for New FTF UI) (s8985755) Category: fullText Text: Find It @ SCU Libraries MouseOverText: Find It @ SCU Libraries
Header	DbId: edsarx DbLabel: arXiv An: edsarx.1302.2788 RelevancyScore: 935 AccessLevel: 3 PubType: Report PubTypeId: report PreciseRelevancyScore: 935.329040527344
IllustrationInfo
Items	– Name: Title Label: Title Group: Ti Data: Minimum length path decompositions – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Dereniowski%2C+Dariusz%22">Dereniowski, Dariusz</searchLink><br /><searchLink fieldCode="AR" term="%22Kubiak%2C+Wieslaw%22">Kubiak, Wieslaw</searchLink><br /><searchLink fieldCode="AR" term="%22Zwols%2C+Yori%22">Zwols, Yori</searchLink> – Name: TitleSource Label: Source Group: Src Data: Journal of Computer and System Sciences 81 (2015) 1715-1747 – Name: DatePubCY Label: Publication Year Group: Date Data: 2013 – Name: Subset Label: Collection Group: HoldingsInfo Data: Computer Science<br />Mathematics – Name: Subject Label: Subject Terms Group: Su Data: <searchLink fieldCode="DE" term="%22Computer+Science+-+Data+Structures+and+Algorithms%22">Computer Science - Data Structures and Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematics+-+Combinatorics%22">Mathematics - Combinatorics</searchLink><br /><searchLink fieldCode="DE" term="%2268Q25%2C+05C85%2C+68R10%22">68Q25, 05C85, 68R10</searchLink> – Name: Abstract Label: Description Group: Ab Data: We consider a bi-criteria generalization of the pathwidth problem, where, for given integers $k,l$ and a graph $G$, we ask whether there exists a path decomposition $\cP$ of $G$ such that the width of $\cP$ is at most $k$ and the number of bags in $\cP$, i.e., the \emph{length} of $\cP$, is at most $l$. We provide a complete complexity classification of the problem in terms of $k$ and $l$ for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter tractable with respect to $k$, we prove that the generalized problem is NP-complete for any fixed $k\geq 4$, and is also NP-complete for any fixed $l\geq 2$. On the other hand, we give a polynomial-time algorithm that, for any (possibly disconnected) graph $G$ and integers $k\leq 3$ and $l>0$, constructs a path decomposition of width at most $k$ and length at most $l$, if any exists. As a by-product, we obtain an almost complete classification of the problem in terms of $k$ and $l$ for connected graphs. Namely, the problem is NP-complete for any fixed $k\geq 5$ and it is polynomial-time for any $k\leq 3$. This leaves open the case $k=4$ for connected graphs.<br />Comment: Work presented at the 5th Workshop on GRAph Searching, Theory and Applications (GRASTA 2012), Banff International Research Station, Banff, AB, Canada – Name: TypeDocument Label: Document Type Group: TypDoc Data: Working Paper – Name: DOI Label: DOI Group: ID Data: 10.1016/j.jcss.2015.06.011 – Name: URL Label: Access URL Group: URL Data: <link linkTarget="URL" linkTerm="http://arxiv.org/abs/1302.2788" linkWindow="_blank">http://arxiv.org/abs/1302.2788</link> – Name: AN Label: Accession Number Group: ID Data: edsarx.1302.2788
PLink	https://login.libproxy.scu.edu/login?url=https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.1302.2788
RecordInfo	BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.jcss.2015.06.011 Subjects: – SubjectFull: Computer Science - Data Structures and Algorithms Type: general – SubjectFull: Mathematics - Combinatorics Type: general – SubjectFull: 68Q25, 05C85, 68R10 Type: general Titles: – TitleFull: Minimum length path decompositions Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Dereniowski, Dariusz – PersonEntity: Name: NameFull: Kubiak, Wieslaw – PersonEntity: Name: NameFull: Zwols, Yori IsPartOfRelationships: – BibEntity: Dates: – D: 12 M: 02 Type: published Y: 2013
ResultId	1