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

DOI10.1007/978-3-319-03898-8_7zbMATH Open1309.68084arXiv1306.2217OpenAlexW1579288166MaRDI QIDQ2867073FDOQ2867073

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)

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.

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

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

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)

Cited In (3)

• Parameterized algorithms for graph partitioning problems
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• Title not available (Why is that?)

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)