×

Weighted upper edge cover: complexity and approximability. (English) Zbl 1433.05261

Summary: Optimization problems consist of either maximizing or minimizing an objective function. Instead of looking for a maximum solution (resp. minimum solution), one can find a minimum maximal solution (resp. maximum minimal solution). Such “flipping” of the objective function was done for many classical optimization problems. For example, minimum vertex cover becomes maximum minimal vertex cover, maximum independent set becomes minimum maximal independent set and so on. In this paper, we propose to study the weighted version of maximum minimal edge cover called upper edge cover, a problem having application in genomic sequence alignment. It is well-known that minimum edge cover is polynomial-time solvable and the “flipped” version is NP-hard, but constant approximable. We show that the weighted upper edge cover is much more difficult than upper edge cover because it is not \(O(\frac{1}{n^{1/2-\varepsilon}})\) approximable, nor \(O(\frac{1}{\Delta^{1-\varepsilon}})\) in edge-weighted graphs of size \(n\) and maximum degree \(\Delta\) respectively. Indeed, we give some hardness of approximation results for some special restricted graph classes such as bipartite graphs, split graphs and \(k\)-trees. We counter-balance these negative results by giving some positive approximation results in specific graph classes.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C22 Signed and weighted graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] H. AbouEisha, S. Hussain, V. V. Lozin, J. Monnot, B. Ries, and V. Zamaraev.A boundary property for upper domination.In V. M¨akinen, S. J. Puglisi, and L. Salmela, editors,Proc. of IWOCA 2016, volume 9843 ofLNCS, pages 229-240. Springer, 2016. · Zbl 1392.68195 · doi:10.1007/
[2] P. Alimonti and V. Kann.Some APX-completeness results for cubic graphs.Theor. Comput. Sci., 237(1-2):123-134, 2000. · Zbl 0939.68052 · doi:10.1016/
[3] S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems.Journal of computer and system sciences, 58(1):193-210, 1999. · Zbl 0937.68160 · doi:10.1006/jcss.1998.1605
[4] S. Athanassopoulos, I. Caragiannis, C. Kaklamanis, and M. Kyropoulou. An improved approximation bound for spanning star forest and color saving.In R. Kr´alovic and D. Niwinski, editors,Proc. of 34th MFCS, volume 5734 ofLNCS, pages 90-101. Springer, 2009. · Zbl 1250.68285 · doi:10.1007/
[5] S. Athanassopoulos, I. Caragiannis, C. Kaklamanis, and E. Papaioannou. Energy-efficient communication in multi-interface wireless networks. In R. Kr´alovic and D. Niwinski, editors,Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings, volume 5734 ofLNCS, pages 102-111. Springer, 2009. · Zbl 1250.68061 · doi:10.1007/
[6] C. Bazgan, L. Brankovic, K. Casel, H. Fernau, K. Jansen, K. Klein, M. Lampis, M. Liedloff, J. Monnot, and V. T. Paschos.The many facets of upper domination.Theor. Comput. Sci., 717:2-25, 2018. · Zbl 1388.68099
[7] A. A. Bertossi. Dominating sets for split and bipartite graphs.Inf. Process. Lett., 19(1):37-40, 1984. · Zbl 0539.68058 · doi:10.1016/0020-0190(84)90126-1
[8] K. S. Booth and J. H. Johnson. Dominating sets in chordal graphs.SIAM J. Comput., 11(1):191-199, 1982. · Zbl 0485.05055 · doi:10.1137/0211015
[9] N. Boria, F. Della Croce, and V. T. Paschos. On the max min vertex cover problem.Discrete Applied Mathematics, 196:62-71, 2015. · Zbl 1321.05177 · doi:10.1016/
[10] N. Bourgeois, F. Della Croce, B. Escoffier, and V. T. Paschos. Fast algorithms for min independent dominating set.Discrete Applied Mathematics, 161(4-5):558-572, 2013. · Zbl 1259.05161 · doi:10.1016/j.dam.2012.01.003
[11] A. Boyaci and J. Monnot. Weighted upper domination number.Electronic Notes in Discrete Mathematics, 62:171-176, 2017. · Zbl 1383.05228 · doi:10.1016/j.endm.
[12] D. Chakrabarty and G. Goel. On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP.SIAM J. Comput., 39(6):2189-2211, 2010. · Zbl 1263.90037 · doi:10.1137/080735503
[13] P. Chalermsook, B. Laekhanukit, and D. Nanongkai. Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more. In S. Khanna, editor,Proc. of the 24th SODA, pages 1557-1576. SIAM, 2013. · Zbl 1423.05140 · doi:10.1137/1.9781611973105.112
[14] G. J. Chang.The weighted independent domination problem is NPcomplete for chordal graphs.Discrete Applied Mathematics, 143(1-3):351- 352, 2004. · Zbl 1053.05096 · doi:10.1016/j.dam.2003.05.004
[15] N. Chen, R. Engelberg, C. T. Nguyen, P. Raghavendra, A. Rudra, and G. Singh. Improved approximation algorithms for the spanning star forest problem. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings, pages 44-58, 2007. · Zbl 1171.05424
[16] N. Chen, R. Engelberg, C. T. Nguyen, P. Raghavendra, A. Rudra, and G. Singh.Improved approximation algorithms for the spanning star forest problem.Algorithmica, 65(3):498-516, 2013. · Zbl 1275.68159 · doi:10.1007/
[17] M. Chleb´ık and J. Chleb´ıkov´a. Complexity of approximating bounded variants of optimization problems.Theor. Comput. Sci., 354(3):320-338, 2006. · Zbl 1105.90110 · doi:10.1016/j.tcs.2005.11.029
[18] D. G. Corneil and J. M. Keil. A dynamic programming approach to the dominating set problem onk-trees.SIAM Journal on Algebraic Discrete Methods, 8(4):535-543, 1987. · Zbl 0635.05040 · doi:10.1137/0608044
[19] P. Damaschke, H. M¨uller, and D. Kratsch.Domination in convex and chordal bipartite graphs.Inf. Process. Lett., 36(5):231-236, 1990. · Zbl 0706.68055
[20] F. K. H. A. Dehne, M. R. Fellows, H. Fernau, E. Prieto-Rodriguez, and F. A. Rosamond. NONBLOCKER: parameterized algorithmics for minimum dominating set. InProc. of the 32nd SOFSEM, volume 3831 ofLNCS, pages 237-245. Springer, 2006. · Zbl 1175.68543 · doi:10.1007/11611257_21
[21] M. Farber. Independent domination in chordal graphs.Operations Research Letters, 4(1):134-138, 1982. · Zbl 0495.05053 · doi:10.1016/0167-6377(82)90015-3
[22] M. Farber. Domination, independent domination and duality in strongly chordal graphs.Discrete Appl. Math., 7(2):115-130, 1984. · Zbl 0531.05045 · doi:10.1016/
[23] L. Gai and G. Zhang.On lazy bureaucrat scheduling with common deadlines.J. Comb. Optim., 15(2):191-199, 2008. · Zbl 1138.90394 · doi:10.1007/
[24] M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979. · Zbl 0411.68039
[25] L. Gourv‘es, J. Monnot, and A. Pagourtzis. The lazy matroid problem. In Proc. of the 8th IFIP TCS, volume 8705 ofLNCS, pages 66-77. Springer, 2014. · Zbl 1417.68287 · doi:10.1007/978-3-662-44602-7_6
[26] J. He and H. Liang.On variants of the spanning star forest problem. In M. J. Atallah, X. Li, and B. Zhu, editors,Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Jinhua, China, May 28-31, 2011. Proceedings, volume 6681 ofLNCS, pages 70-81. Springer, 2011. · Zbl 1329.68140 · doi:10.1007/978-3-642-21204-8\_11
[27] J. He and H. Liang.Improved approximation for spanning star forest in dense graphs.J. Comb. Optim., 25(2):255-264, 2013. · Zbl 1268.90114 · doi:10.1007/
[28] K. Khoshkhah, M. K. Ghadikolaei, J. Monnot, and F. Sikora. Weighted upper edge cover: Complexity and approximability. In G. K. Das, P. S. Mandal, K. Mukhopadhyaya, and S. Nakano, editors,Proc. of WALCOM: Algorithms and Computation - 13th International Conference, volume 11355 ofLNCS, pages 235-247. Springer, 2019. · Zbl 1420.68093 · doi:10.1007/
[29] K. Khoshkhah, M. K. Ghadikolaei, J. Monnot, and D. O. Theis.Extended spanning star forest problems.InProc. of the 11th COCOA, volume 10627 ofLNCS, pages 195-209. Springer, 2017. · Zbl 1470.68062 · doi:10.1007/
[30] K. Khoshkhah, M. K. Ghadikolaei, J. Monnot, and D. O. Theis. Complexity and approximability of extended spanning star forest problems in general and complete graphs.Theoretical Computer Science, 775:1-15, 2019. · Zbl 1422.68121
[31] V. V. Lozin, D. S. Malyshev, R. Mosca, and V. Zamaraev. More results on weighted independent domination.Theor. Comput. Sci., 700:63-74, 2017. · Zbl 1378.68088 · doi:10.1016/j.tcs.2017.08.007
[32] D. F. Manlove.On the algorithmic complexity of twelve covering and independence parameters of graphs.Discrete Applied Mathematics, 91(13):155-175, 1999. · Zbl 0922.05041 · doi:10.1016/S0166-218X(98)00147-4
[33] C. T. Nguyen, J. Shen, M. Hou, L. Sheng, W. Miller, and L. Zhang. Approximating the spanning star forest problem and its application to genomic sequence alignment.SIAM J. Comput., 38(3):946-962, 2008. · Zbl 1187.68251 · doi:10.1137/070682150
[34] V. H. Nguyen.The maximum weight spanning star forest problem on cactus graphs.Discrete Math., Alg. and Appl., 7(2), 2015. · Zbl 1316.05095 · doi:10.1142/
[35] P. J. Slater. Enclaveless sets and MK-systems.J. Res. Nat. Bur. Stand., 82(3):197-202, 1977. · Zbl 0421.05053
[36] L. Trevisan.Non-approximability results for optimization problems on bounded degree instances. InProc. of the 33rd STOC, pages 453-461. ACM, 2001. · Zbl 1323.90059 · doi:10.1145/380752.380839
[37] M. Yannakakis and F. Gavril. Edge dominating sets in graphs.SIAM Journal on Applied Mathematics, 38(3):364-372, 1980. · Zbl 0455.05047
[38] M. Zehavi. Maximum minimal vertex cover parameterized by vertex cover. SIAM Journal on Discrete Mathematics, 31(4):2440-2456, 2017. · Zbl 1380.68236 · doi:10.
[39] D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number.Theory of Computing, 3(1):103-128, 2007. IntroductionGraph terminology and definitionsRelated workContributionsApproximation of Weighted Upper Edge Cover in complete graphsApproximation of Weighted Upper Edge Cover in bipartite graphsApproximation of Weighted Upper Edge Cover in split graphsApproximation of Weighted Upper Edge Cover in k-treesHardness of approximationPositive approximation resultApproximation of Weighted Upper Edge Cover in bounded degree graphsConclusion · Zbl 1213.68322 · doi:10.4086/toc.2007.v003a006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.