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 条
  • [31] Fixed-parameter tractability of anonymizing data by suppressing entries
    Evans, Patricia A.
    Wareham, H. Todd
    Chaytor, Rhonda
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 18 (04) : 362 - 375
  • [32] Fixed-Parameter Tractability of Maximum Colored Path and Beyond
    Fomin, Fedor, V
    Golovach, Petr A.
    Korhonen, Tuukka
    Simonov, Kirill
    Stamoulis, Giannos
    PROCEEDINGS OF THE 2023 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2023, : 3700 - 3712
  • [33] Fixed-Parameter Tractability of (n - k) List Coloring
    Banik, Aritra
    Jacob, Ashwin
    Paliwal, Vijay Kumar
    Raman, Venkatesh
    THEORY OF COMPUTING SYSTEMS, 2020, 64 (07) : 1307 - 1316
  • [34] On the Fixed-Parameter Tractability of the Maximum Connectivity Improvement Problem
    Federico Corò
    Gianlorenzo D’Angelo
    Vahan Mkrtchyan
    Theory of Computing Systems, 2020, 64 : 1094 - 1109
  • [35] Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
    Marx, Daniel
    Razgon, Igor
    STOC 11: PROCEEDINGS OF THE 43RD ACM SYMPOSIUM ON THEORY OF COMPUTING, 2011, : 469 - 478
  • [36] Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
    Kratsch, Stefan
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Wahlstroem, Magnus
    AUTOMATA, LANGUAGES, AND PROGRAMMING, ICALP 2012 PT I, 2012, 7391 : 581 - 593
  • [37] Fixed-Parameter Tractability of Token Jumping on Planar Graphs
    Ito, Takehiro
    Kaminski, Marcin
    Ono, Hirotaka
    ALGORITHMS AND COMPUTATION, ISAAC 2014, 2014, 8889 : 208 - 219
  • [38] FIXED-PARAMETER TRACTABILITY OF MULTICUT PARAMETERIZED BY THE SIZE OF THE CUTSET
    Marx, Daniel
    Razgon, Igor
    SIAM JOURNAL ON COMPUTING, 2014, 43 (02) : 355 - 388
  • [39] FIXED-PARAMETER TRACTABILITY OF MULTICUT IN DIRECTED ACYCLIC GRAPHS
    Kratsch, Stefan
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Wahlstroem, Magnus
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (01) : 122 - 144
  • [40] Fixed-Parameter Tractability of (n - k) List Coloring
    Banik, Aritra
    Jacob, Ashwin
    Paliwal, Vijay Kumar
    Raman, Venkatesh
    COMBINATORIAL ALGORITHMS, IWOCA 2019, 2019, 11638 : 61 - 69