Thumbnail

Using greediness for parameterization: the case of max and min (k, n − k)-cut

Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012), Using greediness for parameterization: the case of max and min (k, n − k)-cut. https://basepub.dauphine.fr/handle/123456789/12148

View/Open
Type
Document de travail / Working paper
Date
2012
Publisher
Université Paris-Dauphine
Series title
Cahiers du Lamsade
Published in
Paris
Pages
13
Metadata
Show full item record
Author(s)
Bonnet, Édouard cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Escoffier, Bruno
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Tourniaire, Emeric
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
MAX (k, n−k)-CUT (resp., MIN (k, n−k)-CUT) is a constrained version of MAX-CUT (resp.,MIN-CUT) where one has to find a bipartition of the vertex set into two subsets with respectively k and n − k vertices (n being the total number of vertices of the input graph) which maximizes (resp., minimizes) the number of edges going from one subset to the other. In this paper, we investigate the parameterized complexity of these two graph problems by considering several parameters, such as the value p of the solution, k, the size á of a minimum vertex cover and the treewidth tw of the input graph. We also give approximation schemata in FPT time for parameterizations which turn out to be W[1]-hard.
Subjects / Keywords
Algorithme et structure de données; Complexité