Inapproximability of dominating set on power law graphs

DOI10.1016/J.TCS.2014.10.021MaRDI QIDQ476891zbMATHOpenAlexFDO

Authors Mikael Gast, Mathias Hauptmann, Marek Karpinski

Publication date 2 December 2014

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 6469213 (Why is no real title available?)
• A Random Graph Model for Power Law Graphs
• A random graph model for massive graphs
• A threshold of ln n for approximating set cover
• Approximability of the vertex cover problem in power-law graphs
• Emergence of Scaling in Random Networks
• New techniques for approximating optimal substructure problems in power-law graphs
• On the hardness of optimization in power-law graphs
• Popularity based random graph models leading to a scale-free degree sequence
• Renormalization group analysis of the small-world network model

Cited in

(12)

• On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
• An order-based algorithm for minimum dominating set with application in graph mining
• Greed is good for deterministic scale-free networks
• COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB
• Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
• Minimum vertex cover in generalized random graphs with power law degree distribution
• Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• Complexity and inapproximability results for the power edge set problem
• Combinatorial properties of Farey graphs
• Near-optimal dominating sets via random sampling

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)