Approximability of the vertex cover problem in power-law graphs

DOI10.1016/J.TCS.2013.11.004zbMATH Open1277.68298arXiv1204.0982OpenAlexW2015692161MaRDI QIDQ385960FDOQ385960

Authors: Mikael Gast, Mathias Hauptmann 

Publication date: 13 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: In this paper we construct an approximation algorithm for the Minimum Vertex Cover Problem (Min-VC) with an expected approximation ratio of 2-f(beta) for random Power Law Graphs (PLG) in the (alpha,beta)-model of Aiello et. al., where f(beta) is a strictly positive function of the parameter beta. We obtain this result by combining the Nemhauser and Trotter approach for Min-VC with a new deterministic rounding procedure which achieves an approximation ratio of 3/2 on a subset of low degree vertices for which the expected contribution to the cost of the associated linear program is sufficiently large.

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

Recommendations

• On the approximability of the vertex cover and related problems
• On approximation of the vertex cover problem in hypergraphs
• Approximating vertex cover on dense graphs
• Parameterized power vertex cover
• Parameterized power vertex cover
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• Approximating vertex cover in dense hypergraphs
• On approximation of max-vertex-cover
• scientific article; zbMATH DE number 3853131

zbMATH Keywords

approximation algorithmsvertex cover problempower-law graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Optimization, approximation, and complexity classes
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• A general model of web graphs
• On the hardness of approximating minimum vertex cover
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Vertex packings: Structural properties and algorithms
• A Random Graph Model for Power Law Graphs
• Title not available (Why is that?)
• A random graph model for massive graphs
• Popularity based random graph models leading to a scale-free degree sequence
• On the hardness of optimization in power-law graphs
• On certain connectivity properties of the internet topology
• On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
• Assessing Significance of Connectivity and Conservation in Protein Interaction Networks

Cited In (4)

• Minimum vertex cover in generalized random graphs with power law degree distribution
• Inapproximability of dominating set on power law graphs
• Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry
• On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs

This page was built for publication: Approximability of the vertex cover problem in power-law graphs

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