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 条
  • [21] Fixed-parameter complexity of minimum profile problems
    Gutin, Gregory
    Szeider, Stefan
    Yeo, Anders
    PARAMETERIZED AND EXACT COMPUTATION, PROCEEDINGS, 2006, 4169 : 60 - 71
  • [22] Fixed-parameter complexity of minimum profile problems
    Gutin, Gregory
    Szeider, Stefan
    Yeo, Anders
    ALGORITHMICA, 2008, 52 (02) : 133 - 152
  • [23] Fixed-Parameter Complexity of Minimum Profile Problems
    Gregory Gutin
    Stefan Szeider
    Anders Yeo
    Algorithmica, 2008, 52 : 133 - 152
  • [24] Fixed-Parameter Enumerability of Cluster Editing and Related Problems
    Peter Damaschke
    Theory of Computing Systems, 2010, 46 : 261 - 283
  • [25] Fixed-Parameter Enumerability of Cluster Editing and Related Problems
    Damaschke, Peter
    THEORY OF COMPUTING SYSTEMS, 2010, 46 (02) : 261 - 283
  • [26] Fixed-parameter tractability for subset feedback set problems with parity constraints
    Kakimura, Naonori
    Kawarabayashi, Ken-ichi
    THEORETICAL COMPUTER SCIENCE, 2015, 576 : 61 - 76
  • [27] Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability
    Yongjie Yang
    Jianxin Wang
    Autonomous Agents and Multi-Agent Systems, 2023, 37
  • [28] Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability
    Yang, Yongjie
    Wang, Jianxin
    AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS, 2023, 37 (02)
  • [29] Fixed-parameter tractability for the Tree Assembly problem
    Shi, Feng
    You, Jie
    Zhang, Zhen
    Liu, Jingyi
    Wang, Jianxin
    THEORETICAL COMPUTER SCIENCE, 2021, 886 : 3 - 12
  • [30] Tree projections and constraint optimization problems: Fixed-parameter tractability and parallel algorithms
    Gottlob, Georg
    Greco, Gianluigi
    Scarcello, Francesco
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2018, 94 : 11 - 40