Inapproximability of dominating set on power law graphs

DOI10.1016/J.TCS.2014.10.021zbMATH Open1305.05174arXiv1212.3517OpenAlexW2964161862MaRDI QIDQ476891FDOQ476891

Authors: Mikael Gast, Mathias Hauptmann, Marek Karpinski 

Publication date: 2 December 2014

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

Abstract: We give logarithmic lower bounds for the approximability of the Minimum Dominating Set problem in connected (alpha,beta)-Power Law Graphs. We give also a best up to now upper approximation bound on the problem for the case of the parameters beta>2. We develop also a new functional method for proving lower approximation bounds and display a sharp phase transition between approximability and inapproximability of the underlying problem. This method could also be of independent interest.

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

Recommendations

• On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
• New techniques for approximating optimal substructure problems in power-law graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Algorithms – ESA 2004
• Hardness complexity of optimal substructure problems on power-law graphs

zbMATH Keywords

combinatorial optimizationapproximation algorithmsdominating setinapproximabilitypower law graphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• A threshold of ln n for approximating set cover
• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• Renormalization group analysis of the small-world network model
• A Random Graph Model for Power Law Graphs
• Approximability of the vertex cover problem in power-law graphs
• New techniques for approximating optimal substructure problems in 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

Cited In (12)

• Combinatorial properties of Farey graphs
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB
• Minimum vertex cover in generalized random graphs with power law degree distribution
• Complexity and inapproximability results for the power edge set problem
• EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET
• On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
• Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs
• An order-based algorithm for minimum dominating set with application in graph mining
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
• Near-Optimal Dominating Sets via Random Sampling
• Greed is good for deterministic scale-free networks

This page was built for publication: Inapproximability of dominating set on power law graphs

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