Improvement of Nemhauser-Trotter Theorem and its applications  in parametrized complexity

Miroslav Chlebik; Janka Chlebikova

doi:10.1007/978-3-540-27810-8_16

Improvement of Nemhauser-Trotter Theorem and its applications in parametrized complexity

Miroslav Chlebik, Janka Chlebikova

School of Computing

University of Sussex

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

441 Downloads (Pure)

Abstract

We improve on the classical Nemhauser-Trotter Theorem, which is a key tool for the Minimum (Weighted) Vertex Cover problem in the design of both, approximation algorithms and exact fixed-parameter algorithms. Namely, we provide in polynomial time for a graph G with vertex weights w : V →〈0, ∞ 〉 a partition of V into three subsets V ₀, V ₁, V12 , with no edges between V ₀ and V12 or within V ₀, such that the size of a minimum vertex cover for the graph induced by V12 is at least 12w(V12) , and every minimum vertex cover C for (G, w) satisfies V1⊆C⊆V1∪V12 .

We also demonstrate one of possible applications of this strengthening of NT-Theorem for fixed parameter tractable problems related to Min-VC: for an integer parameter k to find all minimum vertex covers of size at most k, or to find a minimum vertex cover of size at most k under some additional constraints.

Original language	English
Title of host publication	Algorithm theory - SWAT 2004
Subtitle of host publication	9th Scandinaviaworkshop on algorithm theory, Humlebæk, Denmark, July 8-10, 2004. proceedings
Editors	Torben Hagerup , Jyrki Katajainen
Place of Publication	Berlin
Publisher	Springer
Pages	174-186
ISBN (Electronic)	9783540278108
ISBN (Print)	9783540223399
DOIs	https://doi.org/10.1007/978-3-540-27810-8_16
Publication status	Published - 2004

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	3111
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-540-27810-8_16

Nemhauser-Trotter Theorem post-print
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-27810-8_16.
Accepted author manuscript (Post-print), 218 KB

Cite this

Chlebik, M., & Chlebikova, J. (2004). Improvement of Nemhauser-Trotter Theorem and its applications in parametrized complexity. In T. Hagerup , & J. Katajainen (Eds.), Algorithm theory - SWAT 2004 : 9th Scandinaviaworkshop on algorithm theory, Humlebæk, Denmark, July 8-10, 2004. proceedings (pp. 174-186). (Lecture Notes in Computer Science; Vol. 3111). Springer. https://doi.org/10.1007/978-3-540-27810-8_16

Chlebik, Miroslav ; Chlebikova, Janka. / Improvement of Nemhauser-Trotter Theorem and its applications in parametrized complexity. Algorithm theory - SWAT 2004 : 9th Scandinaviaworkshop on algorithm theory, Humlebæk, Denmark, July 8-10, 2004. proceedings. editor / Torben Hagerup ; Jyrki Katajainen. Berlin : Springer, 2004. pp. 174-186 (Lecture Notes in Computer Science).

@inproceedings{54ff16281eca48f6855d6244e431edbc,

title = "Improvement of Nemhauser-Trotter Theorem and its applications in parametrized complexity",

abstract = "We improve on the classical Nemhauser-Trotter Theorem, which is a key tool for the Minimum (Weighted) Vertex Cover problem in the design of both, approximation algorithms and exact fixed-parameter algorithms. Namely, we provide in polynomial time for a graph G with vertex weights w : V →〈0, ∞ 〉 a partition of V into three subsets V 0, V 1, V12 , with no edges between V 0 and V12 or within V 0, such that the size of a minimum vertex cover for the graph induced by V12 is at least 12w(V12) , and every minimum vertex cover C for (G, w) satisfies V1⊆C⊆V1∪V12 .We also demonstrate one of possible applications of this strengthening of NT-Theorem for fixed parameter tractable problems related to Min-VC: for an integer parameter k to find all minimum vertex covers of size at most k, or to find a minimum vertex cover of size at most k under some additional constraints.",

author = "Miroslav Chlebik and Janka Chlebikova",

note = "The final publication is available at Springer via http://dx.doi.org/[10.1007/978-3-540-27810-8\_16]”.{"}",

year = "2004",

doi = "10.1007/978-3-540-27810-8\_16",

language = "English",

isbn = "9783540223399",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "174--186",

editor = "\{Hagerup \}, \{Torben \} and Jyrki Katajainen",

booktitle = "Algorithm theory - SWAT 2004",

address = "Netherlands",

}

Chlebik, M & Chlebikova, J 2004, Improvement of Nemhauser-Trotter Theorem and its applications in parametrized complexity. in T Hagerup & J Katajainen (eds), Algorithm theory - SWAT 2004 : 9th Scandinaviaworkshop on algorithm theory, Humlebæk, Denmark, July 8-10, 2004. proceedings. Lecture Notes in Computer Science, vol. 3111, Springer, Berlin, pp. 174-186. https://doi.org/10.1007/978-3-540-27810-8_16

Improvement of Nemhauser-Trotter Theorem and its applications in parametrized complexity. / Chlebik, Miroslav; Chlebikova, Janka.
Algorithm theory - SWAT 2004 : 9th Scandinaviaworkshop on algorithm theory, Humlebæk, Denmark, July 8-10, 2004. proceedings. ed. / Torben Hagerup ; Jyrki Katajainen. Berlin: Springer, 2004. p. 174-186 (Lecture Notes in Computer Science; Vol. 3111).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Improvement of Nemhauser-Trotter Theorem and its applications in parametrized complexity

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

N1 - The final publication is available at Springer via http://dx.doi.org/[10.1007/978-3-540-27810-8_16]”."

PY - 2004

Y1 - 2004

N2 - We improve on the classical Nemhauser-Trotter Theorem, which is a key tool for the Minimum (Weighted) Vertex Cover problem in the design of both, approximation algorithms and exact fixed-parameter algorithms. Namely, we provide in polynomial time for a graph G with vertex weights w : V →〈0, ∞ 〉 a partition of V into three subsets V 0, V 1, V12 , with no edges between V 0 and V12 or within V 0, such that the size of a minimum vertex cover for the graph induced by V12 is at least 12w(V12) , and every minimum vertex cover C for (G, w) satisfies V1⊆C⊆V1∪V12 .We also demonstrate one of possible applications of this strengthening of NT-Theorem for fixed parameter tractable problems related to Min-VC: for an integer parameter k to find all minimum vertex covers of size at most k, or to find a minimum vertex cover of size at most k under some additional constraints.

AB - We improve on the classical Nemhauser-Trotter Theorem, which is a key tool for the Minimum (Weighted) Vertex Cover problem in the design of both, approximation algorithms and exact fixed-parameter algorithms. Namely, we provide in polynomial time for a graph G with vertex weights w : V →〈0, ∞ 〉 a partition of V into three subsets V 0, V 1, V12 , with no edges between V 0 and V12 or within V 0, such that the size of a minimum vertex cover for the graph induced by V12 is at least 12w(V12) , and every minimum vertex cover C for (G, w) satisfies V1⊆C⊆V1∪V12 .We also demonstrate one of possible applications of this strengthening of NT-Theorem for fixed parameter tractable problems related to Min-VC: for an integer parameter k to find all minimum vertex covers of size at most k, or to find a minimum vertex cover of size at most k under some additional constraints.

U2 - 10.1007/978-3-540-27810-8_16

DO - 10.1007/978-3-540-27810-8_16

M3 - Conference contribution

SN - 9783540223399

T3 - Lecture Notes in Computer Science

SP - 174

EP - 186

BT - Algorithm theory - SWAT 2004

A2 - Hagerup , Torben

A2 - Katajainen, Jyrki

PB - Springer

CY - Berlin

ER -

Chlebik M, Chlebikova J. Improvement of Nemhauser-Trotter Theorem and its applications in parametrized complexity. In Hagerup T, Katajainen J, editors, Algorithm theory - SWAT 2004 : 9th Scandinaviaworkshop on algorithm theory, Humlebæk, Denmark, July 8-10, 2004. proceedings. Berlin: Springer. 2004. p. 174-186. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-27810-8_16

Improvement of Nemhauser-Trotter Theorem and its applications in parametrized complexity

Abstract

Publication series

Access to Document

Fingerprint

Cite this