TY - GEN
T1 - Complexity of dense bicluster editing problems
AU - Sun, Peng
AU - Guo, Jiong
AU - Baumbach, Jan
PY - 2014
Y1 - 2014
N2 - 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).
AB - 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).
KW - Bicluster editing
KW - Data reduction
KW - NP-hardness
KW - Parameterized complexity
UR - http://www.scopus.com/inward/record.url?scp=84904722808&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-08783-2_14
DO - 10.1007/978-3-319-08783-2_14
M3 - Conference contribution
AN - SCOPUS:84904722808
SN - 9783319087825
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 154
EP - 165
BT - Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings
PB - Springer Verlag
T2 - 20th International Computing and Combinatorics Conference, COCOON 2014
Y2 - 4 August 2014 through 6 August 2014
ER -