University of Sussex
Browse

File(s) not publicly available

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

presentation
posted on 2023-06-07, 22:17 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková
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, infinity) a partition of V into three subsets V-0, V-1, V-1/(2), with no edges between V-0 and V-1/(2) or within V-0, such that the size of a minimum vertex cover for the graph induced by V-1/(2) is at 2 least (1)/(2)w(V-1/(2)), and every minimum vertex cover C for (G,w) satisfies V1 subset of or equal to C subset of or equal to V1 boolean OR V-1/(2) 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.

History

Publication status

  • Published

ISSN

0302-9743

Publisher

Springer Berlin / Heidelberg

Volume

LNCS 3

Pages

13.0

Presentation Type

  • paper

Event name

9th Scandinavian Workshop on Algorithm Theory

Event location

Louisiana Museum Modern Art, Humlebaek, DENMARK

Event type

conference

ISBN

3-540-22339-8

Department affiliated with

  • Mathematics Publications

Notes

Algorithm Theory - SWAT 2004

Full text available

  • No

Peer reviewed?

  • Yes

Editors

T Hagerup, J Katajainen

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC