On the Partial Vertex Cover Problem in Bipartite Graphs - a Parameterized Perspective
Theory of Computing Systems - Trang 1-22 - 2023
Tóm tắt
In this paper, we examine variants of the partial vertex cover problem from the perspective of parameterized algorithms. Recall that in the classical vertex cover problem (VC), we are given a graph
$$\mathbf{G = \langle V, E \rangle }$$
and a number k and asked if we can cover all of the edges in
$$\textbf{E}$$
, using at most k vertices from
$$\textbf{V}$$
. The partial vertex cover problem (PVC) is a more general version of the VC problem in which we are given an additional parameter
$$k'$$
. We then ask the question of whether at least
$$k'$$
of the edges in
$$\textbf{E}$$
can be covered using at most k vertices from
$$\textbf{V}$$
. Note that the VC problem is a special case of the PVC problem when
$$k'=|\textbf{E}|$$
. In this paper, we study the weighted generalizations of the PVC problem. This is called the weighted partial vertex cover problem (WPVC). In the WPVC problem, we are given two parameters R and L, associated respectively with the vertex set
$$\textbf{V}$$
and edge set
$$\textbf{E}$$
of the graph
$$\textbf{G}$$
respectively. Additionally, we are given non-negative integral weight functions for the vertices and the edges. The goal then is to cover edges of total weight at least L, using vertices of total weight at most R. This paper studies several variants of the PVC and WPVC problems and establishes new results from the perspective of fixed-parameter tractability and W[1]-hardness. We also introduce a new problem called the partial vertex cover with matching constraints and show that it is Fixed-Parameter Tractable (FPT) for a certain class of graphs. Finally, we show that the WPVC problem is APX-complete for bipartite graphs.
Tài liệu tham khảo
Amini, O., Fomin, F.V., Saurabh, S.: Implicit branching and parameterized partial cover problems. J. Comp. Sys. Sciences (77), 1159–1171 (2011)
Ageev A.A., Sviridenko M.: Approximation algorithms for maximum coverage and max cut with given size of parts. IPCO, pp. 17–30 (1999)
Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1–2), 123–134 (2000)
Apollonio, N., Simeone, B.: The maximum vertex coverage problem on bipartite graphs. Discrete Appl. Math. (165), 37–48 (2014)
Apollonio, N., Simeone, B.: Improved approximation of maximum vertex coverage problem on bipartite graphs. SIAM J. Discrete Math. 28(3), 1137–1151 (2014)
Bar-Yehuda, R.: Using homogeneous weights for approximating the partial cover problem. J. Algorithms 39(2), 137–144 (2001)
Bilgin, C.C., Caskurlu, B., Gehani, A., Subramani, K.: Analytical models for risk-based intrusion response. Computer Networks (Special issue on Security/Identity Architecture) 57(10), 2181–2192 (2013)
Bläser, M.: Computing small partial coverings. Inf. Process. Lett. 85(6), 327–331 (2003)
Bshouty N.H., Burroughs L.: Massaging a linear programming solution to give a \(2\)-approximation for a generalization of the vertex cover problem. In: Proceedings of STACS, pp. 298–308 (1998)
Caskurlu, B., Mkrtchyan, V., Parekh, O., Subramani, K.: Partial vertex cover and budgeted maximum coverage in bipartite graphs. SIAM J. Disc. Math. 31(3), 2172–2184 (2017)
Caskurlu B., Mkrtchyan V., Parekh O., Subramani K.: On partial vertex cover and budgeted maximum coverage problems in bipartite graphs. IFIP TCS, pp. 13–26 (2014)
Chen, J., Kanj, I.A.: Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. J. Comput. Syst. Sci. 67(4), 833–847 (2003)
Cygan M., Fomin F.V., Kowalik L., Lokshtanov D., Marx D., Pilipczuk M., Pilipczuk M., Saurabh S.: Parameterized algorithms. Springer, pp. 3–555 (2015)
Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. of Math. 162(1), 439–485 (2005)
Downey, R., Fellows, M., Regan, K.: Parameterized circuit complexity and the W hierarchy. Theoret. Comput. Sci. 191, 97–115 (1998)
Downey, R., Fellows, M.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873–921 (1995)
Hassin, R., Levin, A.: The minimum generalized vertex cover problem. ACM Trans. Algorithms 2(1), 66–78 (2006)
Hochbaum D.S.: The \(t\)-vertex cover problem: extending the half integrality framework with budget constraints. In: Proceedings of APPROX, pp. 111–122 (1998)
Joret, G., Vetta, A.: Reducing the rank of a matroid. Disc. Math. and Theor. Comp. Sci. 17(2), 143–156 (2015)
Karakostas, G.: A better approximation ratio for the vertex cover problem. ACM Transactions on Algorithms 5(4), 41:1-41:8 (2009)
Karp R.: Reducibility among combinatorial problems. In: Miller R., Thatcher J. (eds.), Complexity of Computer Computations, pp. 85–103. Plenum Press (1972)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within \(2-\epsilon \). J. Comput. Syst. Sci. (74), 335–349 (2008)
Khot S., Minzer D., Safra M.: Pseudorandom sets in grassmann graph have near-perfect expansion. Electronic colloquium on computational complexity, Report No. 6 (2018)
Khuller, S., Gandhi, R., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55–84 (2004)
Langer A., Kneis J., Rossmanith P.: Improved upper bounds for partial vertex cover. In: WG, pp. 240–251 (2008)
Mestre, J.: A primal-dual approximation algorithm for partial vertex cover: making educated guesses. Algorithmica 55(1), 227–239 (2009)
Mestre, J., Bar-Yehuda, R., Flysher, G., Rawitz, D.: Approximation of partial capacitated vertex cover. Lect. Notes Comput. Sci. (4698), 335–346 (2007)
Mkrtchyan V., Parekh O., Segev D., Subramani K.: The approximability of partial vertex covers in trees. In: SOFSEM, Limerick, Ireland, pp. 350–360 (2017)
Mkrtchyan V., Petrosyan G., Subramani K., Wojciechowski P.: Parameterized algorithms for partial vertex covers in bipartite graphs. In: IWOCA, pp. 395–408 (2020)
Mkrtchyan, V., Petrosyan, G.: On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs. J. Graph Algorithms Appl. 26(1), 91–110 (2022)
Mölle D., Kneis J., Rossmanith P.: Partial vs. complete domination: \(t\)-dominating set. In: SOFSEM (1), pp. 367–376 (2007)
Moss A., Khuller S., (Seffi) Naor J.: The budgeted maximum coverage problem. Inform. Process. Lett. 70(1), 39–45 (1999)
Niedermeier, R., Guo, J., Wernicke, S.: Parameterized complexity of generalized vertex cover problems. Lect. Notes Comput. Sci. (3608), 36–48 (2005)
Orponen P., Mannila H.: On approximation preserving reductions: complete problems and robust measures. Technical report, Department of Computer Science, University of Helsinki (1987)
Papadimitriou, Ch.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. System Sci. 43(3), 425–440 (1991)
Parekh, O., Könemann, J., Segev, D.: A unified approach to approximating partial covering problems. Algorithmica 59(4), 489–509 (2011)
Richter S., Kneis J., Mölle D., Rossmanith P.: Intuitive algorithms and \(t\)-vertex cover. In: ISAAC, pp. 598–607 (2006)
Stege U., van Rooij I., Hertel A., Hertel P.: An \(O(pn + 1.151^p)\)-algorithm for p-profit cover and its practical implications for vertex cover. In: ISAAC, pp. 249–261 (2002)
Paschos V.Th.: A polynomial time approximation schema for max \(k-\)vertex cover in bipartite graphs. arXiv:1909.08435v1 (2019)
Vazirani, V.V.: Approximation algorithms. Springer-Verlag, New York Inc., New York, NY, USA (2001)