Efficient algorithms for the Max k-Vertex Cover problem
Paschos, Vangelis; Della Croce, Federico (2014), Efficient algorithms for the Max k-Vertex Cover problem, Journal of Combinatorial Optimization, 28, 3, p. 674-691. 10.1007/s10878-012-9575-7
TypeArticle accepté pour publication ou publié
Journal nameJournal of Combinatorial Optimization
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Della Croce, Federico
Dipartimento di Automatica e Informatica [Torino] [DAUIN]
Abstract (EN)Given a graph G(V,E) of order n and a constant k⩽n , the max k -vertex cover problem consists of determining k vertices that cover the maximum number of edges in G . In its (standard) parameterized version, max k -vertex cover can be stated as follows: “given G, k and parameter ℓ, does G contain k vertices that cover at least ℓ edges?”. We first devise moderately exponential exact algorithms for max k -vertex cover, with time-complexity exponential in n but with polynomial space-complexity by developing a branch and reduce method based upon the measure-and-conquer technique. We then prove that, there exists an exact algorithm for max k -vertex cover with complexity bounded above by the maximum among ck and γτ, for some γ<2, where τ is the cardinality of a minimum vertex cover of G (note that \textscmax k \textsc−vertexcover∉FPT with respect to parameter k unless FPT=W ), using polynomial space. We finally study approximation of max k -vertex cover by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time.
Subjects / Keywordsmax k-vertex cover problem; Exact exponential algorithms; Measure-and-conquer
Showing items related by title and author.
Baburin, Aleksei; Della Croce, Federico; Gimadi, Edward; Glazkov, Yuri; Paschos, Vangelis (2009) Article accepté pour publication ou publié
Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié