Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization

DOI10.1007/978-3-319-03898-8_7MaRDI QIDQ2867073zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire

Publication date 10 December 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.2217

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We study the parameterized complexity of a broad class of problems called "local graph partitioning problems" that includes the classical fixed cardinality problems as max k-vertex cover, k-densest subgraph, etc. By developing a technique "greediness-for-parameterization", we obtain fixed parameter algorithms with respect to a pair of parameters k, the size of the solution (but not its value) and Delta, the maximum degree of the input graph. In particular, greediness-for-parameterization improves asymptotic running times for these problems upon random separation (that is a special case of color coding) and is more intuitive and simple. Then, we show how these results can be easily extended for getting standard-parameterization results (i.e., with parameter the value of the optimal solution) for a well known local graph partitioning problem.

Recommendations

• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• On the parameterized complexity of multiple-interval graph problems
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• Approximation algorithms for multi-parameter graph optimization problems
• scientific article; zbMATH DE number 1748022
• On the Parameterized Complexity of Maximum Degree Contraction Problem.
• On the parameterized complexity of maximum degree contraction problem
• Parameterized complexity of finding small degree-constrained subgraphs

Cited in

(2)

• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• scientific article; zbMATH DE number 1305498 (Why is no real title available?)

This page was built for publication: Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867073)