Parameterized algorithms for edge biclique and related problems. (English) Zbl 1393.68132
Summary: Maximum Edge Biclique and related problems have wide applications in management science, bioinformatics, etc. In this paper, we study parameterized algorithms for Parameterized Edge Biclique problem, Parameterized Edge Biclique Packing problem, Parameterized Biclique Edge Deletion problem, and Parameterized Bipartite Biclique Clustering problem. For the Parameterized Edge Biclique problem, the current best result is of running time \(O^\ast(2^k)\), and we give a parameterized algorithm of running time \(O(n k^{2.5} k^{\lceil \sqrt{k} \rceil})\), where \(k\) is the parameter and \(n\) is the number of vertices in the given graph. For the Parameterized Edge Biclique Packing problem, based on randomized divide-and-conquer technique, a parameterized algorithm of running time \(O^\ast(k^{\lceil \sqrt{k} \rceil \log k} 4^{(2 k - 1) t)})\) is given, where \(k\) is the parameter and \(t\) is the number of bicliques in the solution. We study the Parameterized Biclique Edge Deletion problem on bipartite graphs and general graphs, and give parameterized algorithms of running time \(O^\ast(2^k)\) and \(O^\ast(3^k)\), respectively. For the Parameterized Bipartite Biclique Clustering problem, based on modular decomposition method, a kernel of size \(O(k^2)\) and a parameterized algorithm of running time \(O(2.42^k(n + m))\) are presented, where \(k\) is the parameter, \(n\) is the number of vertices, and \(m\) is the number of edges in the given graph.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W40 | Analysis of algorithms |
References:
| [1] | Acuña, V.; Ferreira, C. E.; Freire, A. S.; Moreno, E., Solving the maximum edge biclique packing problem on unbalanced bipartite graphs, Discrete Appl. Math., 164, 2-12 (2014) · Zbl 1321.05195 |
| [2] | Babela, L.; Brandstädt, A.; Le, V. B., Recognizing the \(P_4\)-structure of bipartite graphs, Discrete Appl. Math., 93, 2, 157-168 (1999) · Zbl 0931.68074 |
| [3] | Ben-Dor, A.; Chor, B.; Karp, R.; Yakhini, Z., Discovering local structure in gene expression data: the order-preserving submatrix problem, J. Comput. Biol., 10, 3-4, 373-384 (2003) |
| [4] | Betzler, N.; Guo, J.; Niedermeier, R., Parameterized computational complexity of Dodgson and Young elections, Inform. and Comput., 208, 2, 165-177 (2010) · Zbl 1191.68338 |
| [5] | Bu, S., The Summarization of Hierarchical Data with Exceptions (2004), Department of Computer Science, University of British Columbia, Master Thesis |
| [6] | Chen, J.; Kneis, J.; Lu, S.; Mölle, D.; Richter, S.; Rossmanith, P.; Sze, S.; Zhang, F., Randomized divide-and-conquer: improved path, matching, and packing algorithms, SIAM J. Comput., 38, 6, 2526-2547 (2009) · Zbl 1191.68849 |
| [7] | Chen, J.; Shi, F.; Wang, J., Approximating maximum agreement forest on multiple binary trees, Algorithmica, 76, 4, 867-889 (2016) · Zbl 1352.68288 |
| [8] | Cheng, Y.; Church, G. M., Biclustering of expression data, (Proc. 8th International Conference on Intelligent Systems for Molecular Biology (2000)), 93-103 |
| [9] | Cygan, M.; Fomin, F. V.; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer International Publishing: Springer International Publishing Switzerland · Zbl 1334.90001 |
| [10] | Dawande, M.; Keskinocak, P.; Tayur, S., On the Biclique Problem in Bipartite Graphs (1997), Carnegie-Mellon University, GSIA working paper, 1996-04 |
| [11] | Feige, U.; Kogan, S., Hardness of Approximation of the Balanced Complete Bipartite Subgraph Problem (2004), Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Technical Report MCS04-04 |
| [12] | Gottlob, G.; Scarcello, F.; Sideri, M., Fixed-parameter complexity in AI and non-monotonic reasoning, Artificial Intelligence, 138, 55-86 (2002) · Zbl 0995.68118 |
| [13] | Guillemot, S.; Havet, F.; Paul, C.; Perez, A., On the (non-)existence of polynomial kernels for \(P_l\)-free edge modification problems, Algorithmica, 65, 4, 900-926 (2013) · Zbl 1262.68048 |
| [14] | Habib, M.; Paul, C., A survey of the algorithmic aspects of modular decomposition, Comput. Sci. Rev., 4, 1, 41-59 (2010) · Zbl 1302.68140 |
| [15] | Habib, M.; Montgolfier, F.; Paul, C., A simple linear-time modular decomposition algorithm for graphs, using order extension, (Proc. 9th Scandinavian Workshop on Algorithm Theory. Proc. 9th Scandinavian Workshop on Algorithm Theory, LNCS, vol. 3111 (2004)), 187-198 · Zbl 1095.68622 |
| [16] | Hochbaum, D. S., Approximating clique and biclique problems, J. Algorithms, 29, 1, 174-200 (1998) · Zbl 0919.68056 |
| [17] | Li, W.; Feng, Q.; Chen, J.; Hu, S., Improved kernel results for some FPT problems based on simple observations, Theoret. Comput. Sci., 657, 20-27 (2017) · Zbl 1356.68102 |
| [18] | Li, W.; Cao, Y.; Chen, J.; Wang, J., Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree, Inform. and Comput., 252, 187-200 (2017) · Zbl 1357.68296 |
| [19] | Lin, M.; Feng, Q.; Chen, J.; Li, W., Partition on trees with supply and demand: kernelization and algorithms, Theoret. Comput. Sci., 657, 11-19 (2017) · Zbl 1356.68104 |
| [20] | Mishra, N.; Ron, D.; Swaminathan, R., On finding large conjunctive clusters, (Proc. 16th Annual Conference on Learning Theory. Proc. 16th Annual Conference on Learning Theory, LNCS, vol. 2777 (2003)), 448-462 · Zbl 1274.68340 |
| [21] | Nastos, J.; Gao, Y., Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes, Discrete Math. Algorithms Appl., 4, 1, Article 1250008 pp. (2012) · Zbl 1247.05243 |
| [22] | Peeters, R., The maximum edge biclique problem is NP-complete, Discrete Appl. Math., 131, 3, 651-654 (2003) · Zbl 1026.68068 |
| [23] | Swaminathan, J. M.; Tayur, S. R., Managing broader product lines through delayed differentiation using vanilla boxes, Manage. Sci., 44, 161-172 (1998) · Zbl 1004.90040 |
| [24] | Tan, J., Inapproximability of maximum weighted edge biclique and its applications, (Proc. 5th International Conference on Theory and Applications of Models of Computation. Proc. 5th International Conference on Theory and Applications of Models of Computation, LNCS, vol. 4978 (2008)), 282-293 · Zbl 1139.68395 |
| [25] | Tan, J.; Chua, K.; Zhang, L.; Zhu, S., Algorithmic and complexity issues of three clustering methods in microarray data analysis algorithmica, Algorithmica, 48, 2, 203-219 (2007) · Zbl 1124.68044 |
| [26] | Tanay, A.; Sharan, R.; Shamir, R., Discovering statistically significant biclusters in gene expression data, Bioinformatics, 18, suppl 1, S136-S144 (2002) |
| [27] | Zhang, L.; Zhu, S., A new clustering method for microarray data analysis, (Proc. 1st IEEE Computer Society Bioinformatics Conference (2002)), 268-275 |
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.
