Classical Complexity and Fixed-Parameter Tractability of Simultaneous Consecutive Ones Submatrix & Editing Problems

被引:0
|
作者
Rani, M. R. [1 ]
Jagalmohanan, Mohith [1 ]
Subashini, R. [1 ]
机构
[1] Natl Inst Technol, Dept Comp Sci & Engn, Calicut, Kerala, India
来源
FRONTIERS IN ALGORITHMICS (FAW 2018) | 2018年 / 10823卷
关键词
Simultaneous consecutive ones property; Parameterized complexity;
D O I
10.1007/978-3-319-78455-7_12
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
A binary matrix M has the consecutive ones property (C1P) for rows (resp. columns) if there is a permutation of its columns (resp. rows) that arranges the ones consecutively in all the rows (resp. columns). If M has the C1P for rows and the C1P for columns, then M is said to have the simultaneous consecutive ones property (SC1P). We focus on the classical complexity and fixed parameter tractability of Simultaneous Consecutive Ones Submatrix (SC1S) and Simultaneous Consecutive Ones Editing (SC1E) [1] problems here. SC1S problems focus on deleting a minimum number of rows, columns and rows as well as columns to establish the SC1P whereas SC1E problems deal with flipping a minimum number of 1-entries, 0-entries and 0-entries as well as 1-entries to obtain the SC1P. We show that the decision versions of the SC1S and SC1E problems are NP-complete. We consider the parameterized versions of the SC1S and SC1E problems with d, being the solution size, as the parameter and are defined as follows. Given a binary matrix M and a positive integer d, d-SC1S-R (d-SC1S-C) problem decides whether there exists a set of rows (columns) of size at most d whose deletion results in a matrix with the SC1P. The d-SC1S-RC problem decides whether there exists a set of rows as well as columns of size at most d whose deletion results in a matrix with the SC1P. The d-SC1P-0E (d-SC1P-1E) problem decides whether there exists a set of 0-entries (1-entries) of size at most d whose flipping results in a matrix with the SC1P. The d-SC1P-01E problem decides whether there exists a set of 0-entries as well as 1-entries of size at most d whose flipping results in a matrix with the SC1P. Using a related result from the literature [2], we show that d-SC1P-0E on general binary matrices is fixed-parameter tractable with a run time of O* (45.5625(d)). We also give FPT algorithms for SC1S and SC1E problems on certain restricted binary matrices.
引用
收藏
页码:154 / 168
页数:15
相关论文
共 50 条
  • [41] Fixed-parameter tractability of the Maximum Agreement Supertree problem
    Guillemot, Sylvain
    Berry, Vincent
    COMBINATORIAL PATTERN MATCHING, PROCEEDINGS, 2007, 4580 : 274 - +
  • [42] Fixed-parameter tractability of anonymizing data by suppressing entries
    Patricia A. Evans
    H. Todd Wareham
    Rhonda Chaytor
    Journal of Combinatorial Optimization, 2009, 18 : 362 - 375
  • [43] Fixed-Parameter Tractability of (n − k) List Coloring
    Aritra Banik
    Ashwin Jacob
    Vijay Kumar Paliwal
    Venkatesh Raman
    Theory of Computing Systems, 2020, 64 : 1307 - 1316
  • [44] Fixed-parameter tractability of anonymizing data by suppressing entries
    Chaytor, Rhonda
    Evans, Patricia A.
    Wareham, Todd
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2008, 5165 : 23 - +
  • [45] Fixed-Parameter Tractability of Satisfying Beyond the Number of Variables
    Robert Crowston
    Gregory Gutin
    Mark Jones
    Venkatesh Raman
    Saket Saurabh
    Anders Yeo
    Algorithmica, 2014, 68 : 739 - 757
  • [46] On the Fixed-Parameter Tractability of the Maximum Connectivity Improvement Problem
    Coro, Federico
    D'Angelo, Gianlorenzo
    Mkrtchyan, Vahan
    THEORY OF COMPUTING SYSTEMS, 2020, 64 (06) : 1094 - 1109
  • [47] Fixed-Parameter Tractability of Maximum Colored Path and Beyond
    V. Fomin, Fedor
    Golovach, Petr a.
    Korhonen, Tuukka
    Simonov, Kirill
    Plattner, Hasso
    Stamoulis, Giannos
    ACM TRANSACTIONS ON ALGORITHMS, 2024, 20 (04)
  • [48] Fixed-parameter complexity of λ-labelings
    Fiala, J
    Kloks, T
    Kratochvíl, J
    DISCRETE APPLIED MATHEMATICS, 2001, 113 (01) : 59 - 72
  • [49] Fixed-parameter tractability and data reduction for multicut in trees
    Guo, J
    Niedermeier, R
    NETWORKS, 2005, 46 (03) : 124 - 135
  • [50] Fixed-Parameter Tractability of Dependency QBF with Structural Parameters
    Ganian, Robert
    Peitl, Tomas
    Slivovsky, Friedrich
    Szeider, Stefan
    KR2020: PROCEEDINGS OF THE 17TH INTERNATIONAL CONFERENCE ON PRINCIPLES OF KNOWLEDGE REPRESENTATION AND REASONING, 2020, : 392 - 402