Complexity of Dense Bicluster Editing Problems

Peng Sun, Jiong Guo, Jan Baumbach

Publikation: Kapitel i bog/rapport/konference-proceedingKapitel i bogForskningpeer review

Abstrakt

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).
OriginalsprogEngelsk
TitelComputing and Combinatorics : 20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings
RedaktørerZhipeng Cai, Alex Zelikovsky, Anu Bourgeois
Antal sider12
ForlagSpringer
Publikationsdato2014
Sider154-165
ISBN (Trykt)978-3-319-08782-5
ISBN (Elektronisk)978-3-319-08783-2
DOI
StatusUdgivet - 2014
Begivenhed20th International Conference on Computing and Combinatorics - Atlanta, GA, USA
Varighed: 4. aug. 20146. aug. 2014

Konference

Konference20th International Conference on Computing and Combinatorics
Land/OmrådeUSA
ByAtlanta, GA
Periode04/08/201406/08/2014
NavnLecture Notes in Computer Science
Vol/bind8591
ISSN0302-9743

Citationsformater