Hardness Complexity of Optimal Substructure Problems on Power-Law Graphs

Yilin Shen (), Dung T. Nguyen () and My T. Thai ()
Additional contact information
Yilin Shen: University of Florida
Dung T. Nguyen: University of Florida
My T. Thai: University of Florida

Chapter Chapter 10 in Handbook of Optimization in Complex Networks, 2012, pp 255-277 from Springer

Abstract: Abstract The remarkable discovery of many large-scale real networks is the power-law distribution in degree sequence: the number of vertices with degree i is proportional to i −β for some constant β>1. A lot of researchers believe that it may be easier to solve some optimization problems in power-law graphs. Unfortunately, many problems have been proved NP-hard even in power-law graphs as Ferrante proposed in Ferrante et al. (Theoretical Computer Science 393(1–3):220–230, 2008). Intuitively, a theoretical question is raised: Are these problems on power-law graphs still as hard as on general graphs? The chapter shows that many optimal substructure problems, such as minimum dominating set, minimum vertex cover and maximum independent set, are easier to solve in power-law graphs by illustrating better inapproximability factors. An optimization problem has the property of optimal substructure if its optimal solution on some given graph is essentially the union of the optimal subsolutions on all maximal connected components. In particular, the above problems and a more general problem (ρ-minimum dominating set) are proven to remain APX-hard and their constant inapproximability factors on general power-law graphs by using the cycle-based embedding technique to embed any d-bounded graphs into a power-law graph. In addition, the corresponding inapproximability factors of these problems are further proven in simple power-law graphs based on the graphic embedding technique as well as that of maximum clique and minimum coloring using the embedding technique in Ferrante et al. (Theoretical Computer Science 393 (1–3):220–230, 2008). As a result of these inapproximability factors, the belief that there exists some (1+o(1))-approximation algorithm for these problems on power-law graphs is proven not always true. In addition, this chapter contains the in-depth investigations in the relationship between the exponential factor β and constant greedy approximation algorithms. The last part includes some minor NP-hardness results on simple power-law graphs for small β

Keywords: Optimal Substructure Property; Inapproximability Factor; Graph Embedding Techniques; Degree Sequence; Maximum Clique (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-1-4614-0754-6_10

Ordering information: This item can be ordered from
http://www.springer.com/9781461407546

DOI: 10.1007/978-1-4614-0754-6_10

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().