Hardness of approximating the Minimum Vertex Cover problem for 4-regular graphs

CHEN Wen-bin

PDF(981 KB)
PDF(981 KB)
Journal of Guangzhou University(Natural Science Edition) ›› 2014, Vol. 13 ›› Issue (1) : 65-69.

Hardness of approximating the Minimum Vertex Cover problem for 4-regular graphs

  • CHEN Wen-bin
Author information +
History +

Abstract

In this paper, we show that it is hard to approximate the Minimum Vertex Cover for 4-regular graphs within some constant factor. Similarly, the result is also correct for 5-regular graphs, 6-regular graphs and so on. It is known that approximating the Minimum Vertex Cover problem for3-regular graphs within some constant factor is NP-hard. We extend the result to 4-regular graphs. We use K-reductions to prove this result. We give a K-reduction from the Minimum Vertex Cover of 3-regular graphs to that of 4-regular graphs.

Key words

NP-hardness / computational complexity / regular graph / vertex cover / approximation

Cite this article

Download Citations
CHEN Wen-bin. Hardness of approximating the Minimum Vertex Cover problem for 4-regular graphs. Journal of Guangzhou University(Natural Science Edition). 2014, 13(1): 65-69

References

[1] PRIYA S, INMAN D J. Energy harvesting technologies[M]. New York: Springer,2009.
[2] 陈仁文. 新型环境能量采集技术[M]. 北京:国防工业出版社, 2011.
CHEN R W. New ambient energy harvesting technology[M]. Beijing:National Defence Industry Press, 2011.
[3] SUDEVALAYAM S, KULKARNI P. Energy harvesting sensor nodes: Survey and implications[J]. IEEE Commun Surv Tutor, 2011, 13(3): 443-461.
[4] LIU G Y, XU B G. Energy-efficient scheduling of distributed estimation with convolutional coding and rate-compatible punctured convolutional coding[J]. IET Commun, 2011, 5(12): 1650-1660.
[5] LUO Z Q. Universal decentralized estimation in a bandwidth constrained sensor network[J]. IEEE TransactInform Theory, 2005, 51(6): 2210-2219.
[6] XIAO J J, CUIS G, LUO Z Q, et al. Power scheduling of universal decentralized estimation in sensor networks[J]. IEEE Transac Sign Proces, 2006, 54(2): 413-422.
[7] LIU G Y, XU B G, ZENG M, et al. Distributed estimation over binary symmetric channels for wireless sensor networks[J]. IET Wirel Sens Sys, 2011, 1(2): 105-109.
[8] WANG X, YANG C Y. Decentralized estimation overorthogonalmultiple-access fading channels in wireless sensor networks-optimal and suboptimal estimators[J]. Eurasip J Advanc Sign Proces, 2011,R132.
[9] FANG J, LIU Y M, LI H B, et al. One-bit quantizer design for multisensor GLRT fusion[J].IEEE Sign Proces Lett, 2013, 20(3):257-260.
[10]LIU Z X. Distributed estimation in wireless sensor networks with heterogeneous sensors[J]. Intern J Innov Tech Explor Engin,2012,1(4):79-82.
[11]DREW F, JEAN T. Game theory[M]. Cambridge,MA:The MIT Press, 1991.
PDF(981 KB)

148

Accesses

0

Citation

Detail

Sections
Recommended

/