zbMATH — the first resource for mathematics

Applying modular decomposition to parameterized bicluster editing. (English) Zbl 1154.68455
Bodlaender, Hans L. (ed.) et al., Parameterized and exact computation. Second international workshop, IWPEC 2006, Zürich, Switzerland, September 13–15, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-39098-5/pbk). Lecture Notes in Computer Science 4169, 1-12 (2006).
Summary: A graph \(G\) is said to be a cluster graph if \(G\) is a disjoint union of cliques (complete subgraphs), and a bicluster graph if \(G\) is a disjoint union of bicliques (complete bipartite subgraphs). In this work, we study the parameterized version of the NP-hard Bicluster Graph Editing problem, which 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 in the edge set of any input graph (Bicluster\((k)\) Graph Editing problem), this problem is FPT, solvable in \(O(4^{k}m)\) time by applying a search tree algorithm. It is shown an algorithm with \(O(4^{k} + n + m)\) time, which uses a new strategy based on modular decomposition techniques. Furthermore, the same techniques lead to a new form 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 for this problem was presented by J. Gramm, J. Guo, F. Hüffner and R. Niedermeier [“Graph-modeled data clustering: Exact algorithms for clique generation”, Theory Comput. Syst. 38, No. 4, 373–392 (2005; Zbl 1084.68117)]. In their solution, a problem kernel with \(O(k^{2})\) vertices and \(O(k^{3})\) edges is built in \(O(n^{3})\) time.
For the entire collection see [Zbl 1136.68003].

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI