Complexity of dense bicluster editing problems

Peng Sun, Jiong Guo, Jan Baumbach

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


Given a density measure Π, an undirected graph G and a nonnegative integer k, a Π-CLUSTER EDITING problem is to decide whether G can be modified into a graph where all connected components are Π-cliques, by at most k edge modifications. Previous studies have been conducted on the complexity and fixed-parameter tractability (FPT) of Π-CLUSTER EDITING based on several different density measures. However, whether these conclusions hold on bipartite graphs is yet to be examined. In this paper, we focus on three different density measures for bipartite graphs: (1) having at most s missing edges for each vertex (s-biplex), (2) having average degree at least |V|-s (average-s-biplex) and (3) having at most s missing edges within a single disjoint component (s-defective bicliques). First, the NP-completeness of the three problems is discussed and afterwards we show all these problems are fixed-parameter tractable with respect to the parameter (s,k).

Original languageEnglish
Title of host publicationComputing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319087825
StatePublished - 2014
Externally publishedYes
Event20th International Computing and Combinatorics Conference, COCOON 2014 - Atlanta, GA, United States
Duration: 4 Aug 20146 Aug 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8591 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Computing and Combinatorics Conference, COCOON 2014
Country/TerritoryUnited States
CityAtlanta, GA


  • Bicluster editing
  • Data reduction
  • NP-hardness
  • Parameterized complexity


Dive into the research topics of 'Complexity of dense bicluster editing problems'. Together they form a unique fingerprint.

Cite this