zbMATH — the first resource for mathematics

Applying modular decomposition to parameterized cluster editing problems. (English) Zbl 1179.68111
Summary: A graph \(G\) is said to be a bicluster graph if \(G\) is a disjoint union of bicliques (complete bipartite subgraphs), and a cluster graph if \(G\) is a disjoint union of cliques (complete subgraphs). In this work, we study the parameterized versions of the NP-hard Bicluster Graph Editing and Cluster Graph Editing problems. The former consists of obtaining a bicluster graph by making the minimum number of modifications in the edge set of an input bipartite graph. When at most \(k\) modifications are allowed (Bicluster\((k)\) Graph Editing problem), this problem is FPT, and can be solved in \(O(4^{k } nm)\) time by a standard search tree algorithm. We develop an algorithm of time complexity \(O(4^{k}+n+m)\), which uses a strategy based on modular decomposition techniques; we slightly generalize the original problem as the input graph is not necessarily bipartite. The algorithm first builds a problem kernel with \(O(k^{2})\) vertices in \(O(n+m)\) time, and then applies a bounded search tree. We also show how this strategy based on modular decomposition leads to a new way of obtaining a problem kernel with \(O(k^{2})\) vertices for the Cluster\((k)\) Graph Editing problem, in \(O(n+m)\) time. This problem consists of obtaining a cluster graph by modifying at most \(k\) edges in an input graph. A previous FPT algorithm of time \(O(1.92^{k }+n^{3})\) for this problem was presented by J. Gramm, J. Guo, F. Hüffner and R. Niedermeier [Theory Comput. Syst. 38, No. 4, 373–392, (2005; Zbl 1084.68117); Algorithmica 39, No. 4, 321–347 (2004; Zbl 1090.68027)]. In their solution, a problem kernel with \(O(k ^{2})\) vertices is built in \(O(n ^{3})\) time.

68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Amit, N.: The bicluster graph editing problem. M.Sc. Thesis, Tel Aviv University (2004)
[2] Bauer, H., Möhring, R.H.: A fast algorithm for the decomposition of graphs and posets. Math. Oper. Res. 8, 170–184 (1983) · Zbl 0517.05057 · doi:10.1287/moor.8.2.170
[3] Bretscher, A., Corneil, D., Habib, M., Paul, C.: A simple linear time lexBFS cograph recognition algorithm. In: WG 2003. Lecture Notes in Computer Science, vol. 2880, pp. 119–130 (2003) · Zbl 1255.68108
[4] Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58, 171–176 (1996) · Zbl 0875.68702 · doi:10.1016/0020-0190(96)00050-6
[5] Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251–280 (1990) · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2
[6] Dahlhaus, E., Gustedt, J., McConnell, R.M.: Efficient and practical algorithms for sequential modular decomposition. J. Algorithms 41, 360–387 (2001) · Zbl 1017.68154 · doi:10.1006/jagm.2001.1185
[7] Dantas da Silva, M., Protti, F., Szwarcfiter, J.L.: Applying modular decomposition to parameterized bicluster editing. In: IWPEC 2006–Second International Workshop on Parameterized and Exact Computation, Zurich, Switzerland. Lecture Notes in Computer Science, vol. 4169, pp. 1–12 (2006) · Zbl 1154.68455
[8] Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873–921 (1995) · Zbl 0830.68063 · doi:10.1137/S0097539792228228
[9] Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci. 141, 109–131 (1995) · Zbl 0873.68059 · doi:10.1016/0304-3975(94)00097-3
[10] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)
[11] Fellows, M., Langston, M., Rosamond, F., Shaw, P.: Efficient parameterized preprocessing for cluster editing. Manuscript (2006)
[12] Fernau, H.: Parameterized Algorithms: A Graph-Theoretic Approach. University of Newcastle (2005) · Zbl 1117.68456
[13] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, New York (2006)
[14] Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung. 18, 26–66 (1967) · Zbl 0153.26002 · doi:10.1007/BF02020961
[15] Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Graph-modeled data clustering: fixed-parameter algorithms for clique generation. Theory Comput. Syst. 38(4), 373–392 (2005) · Zbl 1084.68117 · doi:10.1007/s00224-004-1178-y
[16] Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39(4), 321–347 (2004) · Zbl 1090.68027 · doi:10.1007/s00453-004-1090-5
[17] Guo, J.: A more effective linear kernelization for Cluster Editing. In: Proceedings of the 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE 2007), Hangzhou, China, April 2007. Lecture Notes in Computer Science (2007) · Zbl 1176.05078
[18] Habib, M., Montgolfier, F., Paul, C.: A simple linear-time modular decomposition algorithm for graphs, using order extension. In: 9th Scandinavian Workshop on Algorithm Theory (SWAT 2004). Lecture Notes in Computer Science, vol. 3111, pp. 187–198 (2004) · Zbl 1095.68622
[19] Möhring, R.H., Radermacher, F.J.: Substitution decomposition and connections with combinatorial optimization. Ann. Discret. Math. 19, 257–356 (1984) · Zbl 0567.90073
[20] McConnell, R.M., Spinrad, J.P.: Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 5, pp. 536–545 (1994) · Zbl 0867.05068
[21] McConnell, R.M., Spinrad, J.P.: Ordered vertex partitioning. Discret. Math. Theor. Comput. Sci. 4, 45–60 (2000) · Zbl 0946.68101
[22] Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discret. Appl. Math. 113, 109–128 (1999) · Zbl 0982.68104 · doi:10.1016/S0166-218X(00)00391-7
[23] Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006) · Zbl 1095.68038
[24] Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parameter-tractable algorithms. Inf. Process. Lett. 73, 125–129 (2000) · Zbl 1014.68064 · doi:10.1016/S0020-0190(00)00004-1
[25] Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discret. Appl. Math. 144, 173–182 (2004) · Zbl 1068.68107 · doi:10.1016/j.dam.2004.01.007
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.