On the Identification of Conflicting Contiguities in Ancestral Genome Reconstruction

Abstract

In computional biology, up-to-date homology-based methods for the reconstruction of ancestral gene orders usually rely on two phases. First, potential ancestral co-localizations of some genomic markers are detected from homologies between extant species. Next, the assembling phase mainly consists in resolving the conflicts between the potential ancestral features. This can be done using many methods, but one of the most advanced solutions is to identify and discard from the set of potential features those that belong to inclusivewise minimal conflicting sets of features. It relies on the consecutive ones property (C1P), and the notion of minimal conflicting set (MCS), widely used in physical mapping problems. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal C}$$ \end{document} be a finite set of n elements and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal R} = \{ r_1 , r_2 , \ldots , r_m \} $$ \end{document} a family of m subsets of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal C}$$ \end{document} . A subset \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal R}$$ \end{document} satisfies the C1P if there exists a permutation P of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal C}$$ \end{document} such that each r_i in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} is an interval of P. An MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S} \subseteq { \cal R}$$ \end{document} is a subset of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal R}$$ \end{document} that does not satisfy the C1P, but such that any of its proper subsets does. In this article, we present a new simpler and faster algorithm to decide if a given element \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in { \cal R}$$ \end{document} belongs to at least one MCS. Our algorithm runs in O(n²m² + nm⁷), largely improving upon the current O(m⁶n⁵(m + n)² log(m + n)) fastest algorithm. The new algorithm is based on an alternative approach considering minimal forbidden induced subgraphs of interval graphs instead of Tucker matrices.

1. Introduction

In paleogenomics, the reconstruction of ancestral genomes contributes to understanding the evolutionary history that led to the genome diversity in current genomes.

Up-to-date reconstruction of ancestral gene orders from homologies between extant species usually consists of two phases. First, potential ancestral co-localizations of some genomic markers are detected from homologies between extant species by detecting potential ancestral contiguities of some genomic loci (see Ma et al., 2006; Chauve and Tannier, 2008; Bertrand et al., 2010; Muffato et al., 2010). In practice, these genomic loci are genes or genomic segments present in extant genomes. The potential ancestral syntenies are sets of genomic loci that are found co-localized in some extant genomes, inferring a signal of potential co-localization in the ancestral genomes.

Next, the assembling phase mainly consists in resolving the conflicts between the potential ancestral features. They are nonconflicting if they can be assembled into a single ancestral genome such that all syntenies are preserved. Given a set of n genomic loci and m potential ancestral syntenies, this property can be exactly translated into the consecutive ones property (C1P) in a 0-1 matrix.

Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal C} = \{ c_1 , \ldots , c_n \} $$ \end{document} be a finite set of n elements and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal R} = \{ r_1 , r_2 , \ldots , r_m \} $$ \end{document} a family of m subsets of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal C}$$ \end{document} . Those sets can be seen as an m × n 0-1 matrix \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$M = ( { \cal R} , { \cal C} )$$ \end{document} , such that the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal C}$$ \end{document} represents the columns of the matrix and the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal R}$$ \end{document} the rows of the matrix: each \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_i \in { \cal R}$$ \end{document} represents the set of columns where row i has an entry 1.

A subset \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal R}$$ \end{document} satisfies the C1P if there exists a permutation P of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal C}$$ \end{document} such that each r_i in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} is an interval of P. Testing the C1P is the core of many algorithms that have applications in a wide range of domains, from VLSI (very large-scale integration) circuit conception through planar embeddings (Nishizeki and Rahman, 2004) to computational biology for the reconstruction of ancestral genomes (see Bergeron et al., 2004; Chauve and Tannier, 2008; Chauve et al., 2009; Stoye and Wittler, 2009; Blin et al., 2010).

On real biological matrices, the C1P is rarely satisfied as some potential ancestral co-localizations might be due to false-positive signals. Thus, only some subsets of rows might satisfy the desired property. However, the combinatorics of such sets is difficult to handle, and a strategy to deal with them has been proposed by Bergeron et al. (2004), Chauve and Tannier (2008), and Stoye and Wittler (2009). It consists in identifying and discarding some rows belonging to minimal conflicting subsets of rows that do not satisfy the C1P, but such that any of their proper subsets does.

Definition 1

A set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S} \subseteq { \cal R} , { \cal S} \neq \emptyset$$ \end{document} is a minimal conflicting set (MCS) if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} does not satisfy the C1P, but such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\forall { \cal X} , { \cal X} \subset S$$ \end{document} , the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} satisfies the C1P.

However, it is not difficult to build examples of matrices such that the number of MCS is polynomial or even exponential in the number of rows. Figure 1 shows an example of a matrix for which the number of MCS is exponential in the number of rows. Indeed, let k be the number of nodes of external rows, which are r₇, r₈, and r₉ in the figure. The total number of rows is 3k, the number of columns 2k, and the number of MCS is 2^k because any induced chordless cycle in the row intersection graph of the matrix (Fig. 1b) constitutes an MCS.

FIG. 1.
(a) A matrix not satisfying the C1P and such that the number of MCS is exponential in the number of rows. (b) A row intersection graph of the matrix whose vertices correspond to the rows of the matrix, and such that there exists an edge between two rows r_i and r_j if r_i ∩ r_j ≠ ∅.

From a computational point of view, the first question that arises is the following: is a given row \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in { \cal R}$$ \end{document} included in at least one MCS? This question has been raised by Bergeron et al. (2004), recalled by Chauve et al. (2009) and Chauve and Tannier (2008), and recently solved in polynomial time O(m⁶n⁵(m + n)² log(m + n)) by Blin et al. (2011). This currently fastest algorithm is based on the identification of minimal Tucker forbidden submatrices (see Tucker, 1972; Dom, 2009).

In this article we present a new simpler O(m²n² + nm⁷) time algorithm for deciding if a given row belongs to at least one MCS and if true, exhibits one. Our algorithm is based on an alternative approach considering minimal forbidden induced subgraphs of interval graphs (see Lekkerkerker and Boland, 1962) instead of Tucker matrices. Moreover, our central paradigm consists in reducing the recognition of complex forbidden induced subgraphs to the detection of induced cycles in ad-hoc graphs. Our approach is faster and simpler, but a difficulty shared by both approaches resides in avoiding to report conflicting sets that are not minimal.

2. MCS And Forbidden Induced Subgraphs

The row–column intersection graph of a 0-1 matrix \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$M = ( { \cal R} , { \cal C} )$$ \end{document} is a vertex-colored bipartite graph G_RC(M) whose set of vertices is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal R} \cup { \cal C}$$ \end{document} ; the vertices corresponding to rows (or columns) are black (or white); there exists an edge between two rows \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_i \in { \cal R}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_j \in { \cal R}$$ \end{document} if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_i \cap r_j \neq \emptyset$$ \end{document} , and there exists an edge between a row \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in { \cal R}$$ \end{document} and a column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in { \cal C}$$ \end{document} if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in r$$ \end{document} .

It should be noted that a column vertex (white) is only connected to row vertices (black). The neighborhood N(r) of a row r is the set of rows intersecting r, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$N ( r ) = \{ x \in { \cal R} : r \cap x \neq \emptyset \} $$ \end{document} and N(r_i, r_j) = N(r_i) ∩ N(r_j). The span L(c) of a column c is the set of rows containing \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c , L ( c ) = \{ r \in { \cal R} : c \in r \} $$ \end{document} .

Theorem 1 (Lekkerkerker and Boland, 1962; Theorem 4)

A 0-1 matrix \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$M = ( { \cal R} , { \cal C} )$$ \end{document} satisfies the C1P if and only if its row–column intersection graph does not contain a forbidden induced subgraph of the form I, II, III, IV, or V (Fig. 2).

FIG. 2.
Forbidden induced subgraphs for the row–column intersection graph of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$M = ( { \cal R} , { \cal C} )$$ \end{document} to satisfy the C1P. Black vertices correspond to rows, and white vertices to columns.

Property 1

From Theorem 1, a set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S} \subseteq { \cal R}$$ \end{document} is an MCS if the row–column intersection graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$G_{RC} ( { \cal S} , { \cal C} )$$ \end{document} contains a subgraph of the form I, II, III, IV, or V; and for any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal T} \subset { \cal S}$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$G_{RC} ( { \cal T} , { \cal C} )$$ \end{document} does not contain a subgraph of the form I, II, III, IV, or V.

Given an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S} \subseteq { \cal R}$$ \end{document} , a forbidden induced subgraph contained in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$G_{RC} ( { \cal S} , { \cal C} )$$ \end{document} is said to be responsible for the MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} . If this forbidden induced subgraph is of the form I (or II, III, IV, or V), we simply say that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} is a MCS of the form I (or II, III, IV, or V, respectively).

Definition 2

A row of an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} that intersects all other rows of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} is called a kernel of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} . In a forbidden induced subgraph responsible for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} , any kernel of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} constitutes a black vertex that is connected to all other black vertices.

Property 2

An induced subgraph of the form II, III, IV, or V always contains at least one kernel, whereas an induced subgraph of the form I contains no kernel.

We denote by G_R(M) the subgraph of G_RC(M) induced by the set of rows \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal R}$$ \end{document} , thus containing only black vertices.

Graph sizes

G_R(M) has m vertices and at most m(m − 1)/2 edges, whereas G_RC(M) has m + n vertices and at most nm + m(m − 1)/2 edges.

3. A Global Algorithm

Our algorithm to decide if a row \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in { \cal R}$$ \end{document} of a 0-1 matrix \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$M = ( { \cal R} , { \cal C} )$$ \end{document} belongs to at least one MCS is based on a sequence of algorithms for finding a forbidden subgraph of G_RC(M) responsible for an MCS containing r. It looks for some MCS of the form I, II, III, IV, or V, containing r, in the following order:
1. MCS of type I,

2. MCS of size 3 (type IV or V),

3. MCS of type II,

4. MCS of type III,

5. MCS of type IV and size larger than 3, and MCS of type V and size larger than 3.

See Figure 3 for an overview. Steps 2 to 4 are based on brute-force algorithms to detect forbidden induced subgraphs of G_RC(M) containing at most four black vertices (rows) including r. Steps 1, 5, and 6 rely on a reduction to the detection of induced chordless cycles in ad-hoc graphs.

FIG. 3.
The different steps of the algorithm: in each case, when row r has a specific location in the forbidden induced subgraph that is looked for, this location is indicated in bold character. Other rows and columns of the forbidden induced subgraph are indicated in lightface characters.

In the following, we simply write G_RC(M) as G and G_R(M) as G_R.

3.1. Step 1: Forbidden Induced subgraph I

We first test if r belongs to an MCS of the form I. The rows (black vertices) of such an MCS necessarily constitute an induced chordless cycle in G_R. If it is true, then r belongs to an induced chordless cycle of G of length at least 4 containing only black vertices. Such a cycle exists in G if and only if it is also a chordless cycle in G_R because G_R is the subgraph of G induced by the set of rows \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal R}$$ \end{document} . Thus, it suffices to search for an induced chordless cycle in G_R containing r (see Fig. 3.I and Algorithm 1; a P₄ of a graph is an induced chordless path of the graph containing 4 vertices).

Algorithm 1: Check_I (r, G_R) – O(m⁵)

Input: a row r, the subgraph G_R.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} given by a forbidden induced subgraph of the form I containing r if such an MCS exists, otherwise returns “NO”.

1: for any P₄ of G_R containing r do

2: Consider the graph G′ obtained from G_R after removing the two internal vertices of the P₄ and their neighborhood from the graph, and consider the extremities r_i and r_j of the P₄

3: if there exists an r_ir_j-path in G′ then

4: find a chordless path P in this graph linking r_i and r_j.

5: return the set of vertices of the P₄ plus the set of vertices of P

6: end if

7: end for

8: return “NO”

Proposition 1

Algorithm Check_I is correct and worst case O(m⁵) time.

Proof

The correctness of Algorithm Check_I comes from the fact that r is contained in a MCS of the form I if and only if r belongs to an induced chordless cycle of G_R of length at least 4 whose set of vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} constitutes the MCS (Fig. 3.I). A P₄ of G_R is an induced chordless path of G_R containing 4 vertices. In this case, Algorithm Check_I returns such a set of vertices because an induced chordless cycle of G_R of length at least 4 containing r is a P₄ containing r whose extremities are linked by a chordless path in the subgraph of G that does not contain the neighborhood of the internal vertices of the P₄. This set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} cannot contain a smaller subset of rows that is an MCS, as no subset of S can be an MCS of the form I, or an MCS of any other form because of Property 2.

Algorithm Check_I might be implemented in O(m⁵). The test performed on a given P₄ containing r (lines 2–5 of the algorithm) can be achieved in O(m² + m log m) as follows: removing the neighborhood of its internal vertices might be done in m² time, and finding a chordless path between the two extremities might be performed using Dijkstra's algorithm in O(m² + m log m) time. Enumerating all P₄ containing r might be done in time O(m³) using a BFS from r stopping at depth 4. Eventually, the whole algorithm is in O(m³(m² + m log m)) = O(m⁵) time. ■

Precomputation

In the following steps, we assume that the following precomputations have been achieved:
• For any triplet of rows (r, r_i, r_j) that are pairwise intersecting, i.e., each couple is an edge in G, r − (r_i ∪ r_j) and (r_i ∩ r_j) − r are precomputed;

• Two rows r_i and r_j are overlapping if r_i ∩ r_j ≠ ∅ and r_i − r_j ≠ ∅ and r_j − r_i ≠ ∅. The overlapping relation between any couple of rows is precomputed;

• For any quadruplet of rows (r, r_i, r_j, r_k) such that r_i, r_j, and r_k overlap r, r − (r_i ∩ r_j ∩ r_k) is precomputed.

All those precomputations can simply be performed in O(nm⁴) time using straightforward algorithms, that is, scanning the n columns of the input matrix for each triplet or quadruplet of rows.

3.2. Step 2: Forbidden induced subgraph responsible for an MCS of size 3

We then test if r belongs to an MCS of size 3. An MCS of size 3 is necessarily caused by a forbidden induced subgraph of the form IV or V. As a consequence, the following property is immediate.

Property 3

An MCS of size 3 is always composed of 3 rows that are pairwise overlapping.

Thus, in this step, it suffices to use a brute-force algorithm, Check_IV_V_3 (see Algorithm 2), running in O(m²) time to search for a triplet of rows in G including r, satisfying one of the two configurations shown in Figure 3. IV_V_3.

Proposition 2

Algorithm Check_IV_V_3 is correct and runs in O(m²) time.

Algorithm 2: Check_IV_V_3 (r, G) – O(m²)

Input: a row r, the row–column intersection graph G.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size 3 given by a forbidden induced subgraph of the form IV or V containing r if such an MCS exists, otherwise returns “NO”.

1: for any couple (r_i, r_j) of black vertices that both overlap r, and overlap each other do

2: if r − (r_i ∪ r_j) ≠ ∅ and r_i − (r ∪ r_j) ≠ ∅ and r_j − (r ∪ r_i) ≠ ∅ then

3: return {r, r_i, r_j}

4: end if

5: if (r_i ∩ r_j) − r ≠ ∅ and (r ∩ r_j) − r_i ≠ ∅ and (r ∩ r_i) − r_j ≠ ∅ then

6: return {r, r_i, r_j}

7: end if

8: end for

9: return “NO”

Proof

The correctness of Algorithm Check_IV_V_3 comes from the fact that r is contained in an MCS of size 3 if and only if this MCS is caused by a forbidden induced subgraph of the form IV or V (Property 3). Thus, r should belong to a triplet of rows (r, r_i, r_j) that are pairwise overlapping, and satisfy the conditions given in:
• either line 2 of the algorithm to produce a forbidden induced subgraph of the form IV (left-hand graph in Fig. 3.IV_V_3),

• or line 5 of the algorithm to produce a forbidden induced subgraph of the form V (right-hand graph in Fig. 3.IV_V_3).

In both cases, Algorithm Check_IV_V_3 returns the set {r, r_i, r_j} as an MCS if such a set of rows exists. This set cannot contain a smaller subset of rows that is an MCS as 3 is the minimum size of any MCS.

Algorithm Check_IV_V_3 runs in O(m²) time because, given r, there might be O(m²) couples (r_i, r_j) on which the tests performed (lines 2–8 of the algorithm) might be achieved in O(1), thanks to the precomputations that have been done. ■

3.3. Step 3: Forbidden induced subgraph II

We test here if r belongs to an MCS of the form II, with the assumption that r is not contained in an MCS of size 3. Note that such an MCS is of size 4. In this step, it suffices to use a brute-force algorithm, Check_II_4 (see Algorithm 3), running in O(m³) time to search for a quadruplet of rows in G including r, satisfying one of the two configurations shown in Figure 3.II_4.

Algorithm 3: Check_II_4 (r, G) – O(m³)

Input: a row r, the row–column intersection graph G.

Assumption: r is not contained in an MCS of size 3.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} given by a forbidden induced subgraph of the form II containing r if such an MCS exists, otherwise returns “NO”.

1: for any triplet (r_i, r_j, r_k) of black vertices such that r_i, r_j, r_k overlap r do

2: if there are no edges (r_i, r_j), (r_i, r_k), and (r_j, r_k) in G then

3: return {r, r_i, r_j, r_k}

4: end if

5: end for

6: for any triplet (r_i, r_j, r_k) of black vertices such that r_i overlaps r, and r_j,r_k overlap r_i do

7: if there are no edges (r, r_j), (r, r_k), or (r_j, r_k) in G then

8: return {r_i, r, r_j, r_k}

9: end if

10: end for

11: return “NO”

Proposition 3

Algorithm Check_II_4 is correct and runs in O(m³) time.

Proof

The correctness of Algorithm Check_II_4 comes from the fact that, if r belongs to an MCS of the form II, then r should belong to a quadruplet of rows (r, r_i, r_j, r_k) such that one of these rows is a kernel, and the three other rows do not intersect each other. Thus, the row r is:
• either a kernel of the MCS, tested in lines 1–5 of the algorithm (left-hand graph in Fig. 3.II_4),

• or not a kernel of the MCS tested in lines 6–10 of the algorithm (right-hand graph in Fig. 3.II_4).

In both cases, Algorithm Check_II_4 returns the set {r, r_i, r_j, r_k} as an MCS if such a set of rows exists. This set cannot contain a smaller subset of rows that is an MCS as this subset would be a subset of 3 rows that cannot satisfy Property 3.

Algorithm Check_IV_V_4 runs in O(m³) time because all the tests performed on a given triplet (r_i, r_j, r_k) in lines 2–4 and 7–9 of the algorithm can be achieved in O(1), and given r there might be O(m³) such triplets. ■

3.4. Step 4: Forbidden induced subgraph III

We test here if r belongs to an MCS of the form III, with the assumption that r is not contained in an MCS of size 3. Note that such an MCS is of size 4. In this step, we use a brute-force algorithm, Check_III_4 (see Algorithm 4), running in O(m³) time to search for a quadruplet of rows in G including r, satisfying one of the three configurations shown in Figure 3.III_4.

Algorithm 4: Check_III_4 (r, G) – O(m³)

Input: a row r, the row–column intersection graph G.

Assumption: r is not contained in an MCS of size 3.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} given by a forbidden induced subgraph of the form III containing r if such an MCS exists, otherwise returns “NO”.

1: for any triplet (r_i, r_j, r_k) of black vertices such that r_i, r_j, r_k overlap r, and r − (r_i ∩ r_j ∩ r_k) ≠ ∅ do

2: if there is no edge (r_i, r_k) in G, and (r_i ∩ r_j) − r ≠ ∅, and (r_j ∩ r_k) − r ≠ ∅ then

3: return {r, r_i, r_j, r_k}

4: end if

5: end for

6: for any triplet (r_i, r_j, r_k) of black vertices of such that r_i overlaps r, and r_j, r_k overlap r_i, and r_i − (r ∩ r_j ∩ r_k) ≠ ∅, and {r_i, r_j, r_k}is not an MCS do

7: if there is no edge (r, r_k) in G, and (r ∩ r_j) − r_i ≠ ∅, and (r_j ∩ r_k) − r_i ≠ ∅ then

8: return {r_i, r, r_j, r_k}

9: end if

10: end for

11: for any triplet (r_i, r_j, r_k) of black vertices of such that r_i overlaps r, and r_j, r_k overlap r_i, and r_i − (r ∩ r_j ∩ r_k) ≠ ∅ do

12: if there is no edge (r_j, r_k) in G, and (r_j ∩ r) − r_i ≠ ∅, and (r ∩ r_k) − r_i ≠ ∅ then

13: return {r_i, r_j, r, r_k}

14: end if

15: end for

16: return “NO”

Proposition 4

Algorithm Check_III_4 is correct and runs in O(m³) time.

Proof

The correctness of Algorithm Check_III_4 comes from the fact that r belongs to an MCS of the form III if and only if r should belong to an quadruplet of rows (r, r_i, r_j, r_k) included in an induced subgraph of the form III such that two of these rows are kernels of the subgraph, and one of these kernels contains a column of the induced subgraph that is not shared with any of the other rows. Let us call this kernel kernel_1, and the other kernel kernel_2. For example, in the left-hand graph in Figure 3.III_4, kernel_1 = r, and kernel_2 = r_j.

Thus, the row r is:
• either kernel_1, tested in lines 1–5 of the algorithm (left-hand graph in Fig. 3.III_4),

• or not a kernel, tested in lines 6–10 of the algorithm (middle graph in Fig. 3.III_4),

• or kernel_2, tested in lines 11–15 of the algorithm (right-hand graph in Fig. 3.III_4).

In the first and third cases, the set {r_i, r_j, r_k} cannot be an MCS because such a set cannot satisfy Property 3, In all cases, Algorithm Check_III_4 returns the set {r, r_i, r_j, r_k} as an MCS if such a set of rows exists, and {r_i, r_j, r_k} is not an MCS (in the second case). As we made the assumption that r is not contained in an MCS of size 3, there cannot exist a smaller subset of {r_i, r_j, r_k} containing r that is an MCS.

Algorithm Check_III_4 runs in O(m³) time using a similar proof as the complexity proof for Check_IV_V_4: all the tests performed by the algorithm (lines 2–4, 7–9, and 12–14 of the algorithms) on a given triplet (r_i, r_j, r_k) are achieved in O(1) thanks to the precomputations, and given r there might be O(m³) such triplets. ■

3.5. Step 5: Forbidden induced subgraph IV

We test here if r belongs to an MCS of the form IV, with the assumption that r is contained, neither in an MCS of size 3 nor in an MCS of type I. Depending on whether the size of the MCS is 4 or larger than 4, we describe two algorithms.

3.5.1. MCS of size 4

We first test if r belongs to an MCS of the form IV of size 4. In this step, it suffices to use a brute-force algorithm, Check_IV_4 (See Algorithm 5), running in O(m³) time to search for a quadruplet of rows in G including r, satisfying the configurations shown in Figure 3.IV_4.

Algorithm 5: Check_IV_4 (r, G) – O(m³)

Input: a row r, the row–column intersection graph G.

Assumption: r is not contained in an MCS of size 3.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size 4 given by a forbidden induced subgraph of the form IV containing r if such an MCS exists, otherwise returns “NO”.

1: for any triplet (r_i, r_j, r_k) of black vertices such that r_i, r_j, r_k are connected to r, and r − (r_i ∩ r_j ∩ r_k) ≠ ∅ do

2: if there is no edge (r_i, r_k) in G, and (r_i ∩ r_j) ≠ ∅, and (r_j ∩ r_k) ≠ ∅, and r_i − (r ∪ r_j) ≠ ∅, and r_k − (r ∪ r_j) ≠ ∅ then

3: return {r, r_i, r_j, r_k}

4: end if

5: end for

6: for any triplet (r_i, r_j, r_k) of black vertices of such that r_i is connected to r, and r_j, r_k are connected to r_i, and r_i −(r ∩ r_j ∩ r_k) ≠ ∅, and {r_i, r_j, r_k}is not an MCS do

7: if there is no edge (r, r_k) in G, and (r ∩ r_j) ≠ ∅, and (r_j ∩ r_k) ≠ ∅, and r − (r_i ∪ r_j) ≠ ∅, and r_k −(r_i ∪ r_j) ≠ ∅ then

8: return {r_i, r, r_j, r_k}

9: end if

10: end for

11: for any triplet (r_i, r_j, r_k) of black vertices of such that r_i is connected to r, and r_j, r_k are connected to r_i, and r_i − (r ∩ r_j ∩ r_k) ≠ ∅ do

12: if there is no edge (r_j, r_k) in G, and (r_j ∩ r) ≠ ∅, and (r ∩ r_k) ≠ ∅, and r_j − (r ∪ r_i) ≠ ∅, and r_k − (r ∪ r_i) ≠ ∅ then

13: return {r_i, r_j, r, r_k}

14: end if

15: end for

16: return “NO”

Proposition 5

Algorithm Check_IV_4 is correct and runs in O(m³) time.

We look for a triplet of rows (r_i, r_j, r_k) such that the set {r, r_i, r_j, r_k} is an MCS of the form IV (Fig. 3.IV_4). In an induced subgraph of the form IV containing 4 rows {r, r_i, r_j, r_k}, two rows are kernels, and in that case, r is either a kernel of the MCS, or not. If r is a kernel, then it is either a kernel—called kernel_1—containing a column of the induced subgraph that is not shared with any of the other rows, or not—called kernel_2. For example, in the left-hand graph in Figure 3.IV_4, the two kernels are the two central black vertices of the graph: the top one is a kernel_1, and the bottom one a kernel_2. Algorithm Check_IV_4 looks for each of these configurations: r is a kernel_1, tested in lines 1–5 of the algorithm; r is not a kernel, tested in lines 6–10 of the algorithm; r is a kernel_2, tested in lines 11–15 of the algorithm.

3.5.2. MCS of size larger than 4

We test here if r belongs to an MCS of the form IV of size larger than 4. An MCS of the form IV of size larger than 4 contains one and only one kernel. Depending on whether r is the kernel or not, we distinguish two cases here.

Case 1: If row r is the kernel of the MCS

Algorithm Check_IV_k (see Algorithm 6) recovers an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of the form IV of size larger than 4 containing r as a kernel, with the assumption that r is not contained in an MCS of size 3 (Fig. 3.IV k ). The principle of the algorithm relies on first choosing the column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in { \cal C}$$ \end{document} , of the forbidden induced subgraph of type IV responsible for the MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} , such that c is contained in r, and in no other row of the MCS (see Fig. 3.IV k ). Next, it considers the subgraph H of G induced by the set of black vertices (rows) that are neighbors of r, but do not contain the column c. We denote this subgraph by H = G[N(r) - L(c)]. Then it looks for a set of rows Q, constituting a chordless path in H, such that {r} ∪ Q is an MCS of the form IV.

Algorithm 6: Check_IV_k (r, G) – O(nm²)

Input: a row r, the row–column intersection graph G.

Assumption: r is not contained in an MCS of size 3.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger that 4 given by a forbidden induced subgraph of the form IV whose kernel is r if such an MCS exists, otherwise returns “NO”.

1: for any column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in r$$ \end{document} do

2: H = G[N(r) − L(c)]

3: for any connected component C of H do

4: pick a couple (r_i, r_j) of black vertices in C that satisfies (1) r_i and r_j are not connected, and (2) r_i, r_j overlap r.

5: find a chordless path P in C linking r_i and r_j

6: pick the smallest subpath Q of P linking two vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_i^{ \prime}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_j^{ \prime}$$ \end{document} , such that the couple ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_i^{ \prime} , r_j^{ \prime}$$ \end{document} ) also satisfies (1) and (2)

7: return {r} ∪ Q

8: end for

9: end for

10: return “NO”

Proposition 6

Algorithm Check_IV_k is correct and runs in O(nm²) time.

Proof

Note that, if the MCS exists, then all the rows belonging to the MCS, except r, belong to a same connected component of H. Thus, in each connected component of H, the algorithm looks for a chordless path Q linking two vertices r_i, r_j satisfying (1) r_i and r_j are not connected, and (2) r_i, r_j overlap r, and (3) Q does not contain any smaller subpath satisfying conditions (1) and (2). These conditions are necessary and sufficient for the set {r} ∪ Q to form the rows of an induced subgraph of the form IV. The set {r} ∪ Q cannot contain a subset that is an MCS as such a smaller MCS should be:
• either an MCS of size 3 including r, which is impossible by assumption,

• or an MCS of type II or III necessarily including r as kernel,

• or an MCS of type IV and size larger than 3 having r as kernel.

The two last cases are also impossible, because Q would not satisfy condition (3) in these cases.

Next, there might be n columns \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in r$$ \end{document} and up to m² couples (r _i, r_j) of black vertices to test before finding a valid couple (r_i, r_j) satisfying the conditions in line 4 of the algorithm. Up to this point, the complexity is in O(nm²). Assume now that such a couple exists. Then finding a chordless path between r_i and r_j might be done by searching for a shortest path between r_i and r_j in the connected component C using Dijkstra's algorithm, which thus requires at worst O(m² + m log m) time. The path is of length at most m, and thus identifying \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${r_i^{ \prime}}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${r_j^{ \prime}}$$ \end{document} is bounded by testing each pair on this path in C, which requires at worst O(m²) time. Thus, in total, the algorithm is O(nm²) worst case time. ■

Case 2: If row r is not the kernel of the MCS

Algorithm Check_IV_p (see Algorithm 7) recovers an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of the form IV of size larger than 4 containing r, such that r is not a kernel of the MCS, with the assumptions that r is not contained in an MCS of size 3, and r does not belong to an induced chordless cycle of G_R (Fig. 3.IV p ). The principle of the algorithm consists in first choosing the kernel a of the MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} among the black vertices (rows) neighbors of r, and the column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in { \cal C}$$ \end{document} , of the induced subgraph of type IV responsible for the MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} , that is contained in a, but in no other row of the MCS (see Fig. 3.IV p ). Next, the algorithm calls Algorithm Check_IV (see Algorithm 8) to look for the MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} with r, a, c, and G given as parameters.

Algorithm 7: Check_IV_p (r, G) – O(nm⁶)

Input: a row r, the row–column intersection graph G.

Assumption: r is not contained in an MCS of size 3.

r does not belong to an induced chordless cycle of G_R.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger than 4 given by a forbidden induced subgraph of the form IV containing r whose kernel is not r if such an MCS exists, otherwise returns “NO”.

1: for any black vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a \in N ( r )$$ \end{document} do

2: for any column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in a - r$$ \end{document} do

3: return Check_IV(r, a, c, G)

4: end for

5: end for

6: return “NO”

Algorithm 8: Check_IV (r, a, c, G) – O(m⁵)

Input: two rows r and a, and a column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in a$$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in ( N ( a ) - L ( c ) )$$ \end{document} .

Assumption: r is not contained in an MCS of size 3.

r does not belong to an induced chordless cycle of G_R.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger than 4 given by a forbidden induced subgraph of the form IV containing r and a, whose kernel is a if such an MCS exists, otherwise returns “NO”.

1: H = G[N(a) − L(c)]

2: let C = (V_C, E_C) be the connected component of H to which r belongs.

3: let V_a be the set of vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_a = \{ u \in V_C : u - a \neq \emptyset \} $$ \end{document} .

4: let E_a be the set of edges \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$E_a = \{ ( u , v ) \in V_a^2 : u \cap v = \emptyset \} $$ \end{document} .

5: let D = (V_D, E_D) be the graph such that V_D = V_C and E_D = E_C ∪ E_a.

6: Q = Check_I (r, D)

7: if Q ≠ “NO” then

8: return {a} ∪ Q

9: end if

10: return “NO”

Algorithm Check_IV is called in Algorithm Check_IV_p. It recovers an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of the form IV of size larger than 4 containing r, given the row r, the kernel a of the MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} , and the column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in { \cal C}$$ \end{document} , of the induced subgraph of type IV responsible for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} , that is contained in a, but in no other row of the MCS (Fig. 3.IV p ).

Proposition 7

Algorithm Check_IV_p is correct, and runs in O(nm⁶) time.

Proof

The correctness and the complexity of Check_IV_p follows directly from the correctness and the complexity of Algorithm Check_IV that is called in Algorithm Check_IV_p.

The correctness of Check_IV comes from the fact that r does not belong to any chordless cycle in the graph C computed at line 2 of the algorithm by assumption. Then at line 6 of the algorithm, any chordless cycle in the graph D containing vertex r necessarily contains at least one edge (r_i, r_j) belonging to the set E_a. The number of edges belonging to the set E_a in such a chordless cycle Q cannot be greater than 1, as any couple of such edges in the chordless cycle would induce a chord. Indeed, if Q contains more than one edge belonging to E_a, any two such edges would have two extremities in V_a, one from each of the two edges, that are not connected in the graph C. These extremities would thus be linked by an edge in E_a, creating a chord for the cycle Q in the graph D.

Therefore, the set of vertices of the chordless cycle Q induces a chordless path in G such that each vertex of Q is connected to vertex a by definition of the graph H, and the extremities r_i and r_j of Q satisfy (1) r_i and r_j are not connected in G, and (2) r_i, r_j overlap r, and (3) Q does not contain any smaller subpath satisfying conditions (1) and (2). These conditions are necessary and sufficient for the set {a} ∪ Q to form the rows of an induced subgraph of the form IV, and this set cannot contain a smaller MCS because such an MCS would be: (a) either an MCS of size 3 including a; (b) or an MCS of type II or III necessarily including a as kernel; (c) or an MCS of type IV and size larger than 3 having a as kernel.

The three cases are impossible, because they would induce a chord from the set E_a in the chordless cycle induced by Q in the graph D.

Algorithm Check_IV calls Algorithm Check_I. Both algorithms have the same time complexity in O(m⁵) time. It follows immediately that Algorithm Check_IV _p runs in O(nm⁶) time. ■

3.6. Step 6: Forbidden induced subgraph V

We test here if r belongs to an MCS of the form V, with the assumption that r is contained neither in an MCS of size 3 nor in an MCS of type I. Depending on whether the size of the MCS is 4, 5, or larger than 5, we describe three algorithms.

3.6.1. MCS of size 4 or 5

We first test if r belongs to an MCS of the form V of size 4 or 5.

In this step, it suffices to use two brute-force algorithms, Check_V_4 (See Algorithm 9) and Check_V_5) (see Algorithm 10), running in O(m³) time and O(m⁴) time, respectively to search for a quadruplet and a quintuplet of rows in G including r, satisfying the configurations shown in Figure 3.V_4 and V_5).

Algorithm 9: Check_V_4 (r, G) – O(m³)

Input: a row r, the row–column intersection graph G.

Assumption: r is not contained in an MCS of size 3.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size 4 given by a forbidden induced subgraph of the form V containing r if such an MCS exists, otherwise returns “NO”.

1: for any triplet (r_i, r_j, r_k) of black vertices such that r_i, r_j, r_k are connected to r, and are pairwise connected do

2: if (r_i, r_j, r_k) is not an MCS, and (r ∩ r_i) − (r_j ∪ r_k) ≠ ∅, and (r_j ∩ r_k) − (r ∪ r_i) ≠ ∅ then

3: if (r_i ∩ r_j) − (r ∪ r_k) ≠ ∅ then

4: return {r, r_i, r_j, r_k}

5: end if

6: if (r ∩ r_j) − (r_i ∪ r_k) ≠ ∅ then

7: return {r_i, r, r_j, r_k}

8: end if

9: end if

10: end for

11: return “NO”

Algorithm 10: Check_V_5 (r, G) – O(m⁴)

Input: a row r, the row–column intersection graph G.

Assumption: r is not contained in an MCS of size 3 or 4.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size 5 given by a forbidden induced subgraph of the form V containing r if such an MCS exists, otherwise returns “NO”.

1: for any quadruplet (r_i, r_j, r_k, r_l) of black vertices such that r, r_i, r_j, r_k, r_l are pairwise connected, except for one edge (r_a, r_b) in {r, r_i, r_j, r_k, r_l} × {r, r_i, r_j, r_k, r_l} missing do

2: if {r_i, r_j, r_k, r_l}is C1P then

3: for any pair (a, b) in ({r, r_i, r_j, r_k, r_l}−{r_a, r_b}) × ({r, r_i, r_j, r_k, r_l}−{r_a, r_b}) do

4: if (a ∩ b) − ∪ {r, r_i, r_j, r_k, r_l}−{a, b} ≠ ∅, and (r_k ∩ a) − ∪ {r, r_i, r_j, r_k, r_l} − {r_k, a} ≠ ∅, and (r_l ∩ b) − ∪ {r, r_i, r_j, r_k, r_l}−{r_l, b} ≠ ∅ then

5: return {r, r_i, r_j, r_k, r_l}

6: end if

7: end for

8: end if

9: end for

10: return “NO”

Proposition 8

Algorithm Check_V_4 is correct and runs in O(m³) time.

Proof

Algorithm Check_V_4 looks for an induced subgraph with 4 black vertices {r, r_i, r_j, r_k} that are pairwise connected to each other. These 4 black vertices should be such that there exist three different couples of vertices among them, such that two couples are disjoint and the third one (called couple_kernel) overlaps the two first, and the 2 rows of each of these couples share a column that is not shared with the two other rows of the set. In this case, if {r_i, r_j, r_k} is not an MCS, then the subgraph induced by {r, r_i, r_j, r_k} and the 3 columns (white vertices) connected to the 3 couples of rows is of the form V, and is responsible for an MCS {r, r_i, r_j, r_k}. Algorithm Check_V_4 looks for two cases, depending on whether r belongs to couple_kernel (lines 3–5) or not (lines 6–8).

Next, all the tests performed by Algorithm Check_V_4 (lines 2–9 of the algorithm) on a given triplet (r_i, r_j, r_k) are achieved in O(1) thanks to the precomputations, and given r there might be O(m³) such triplets. Thus, Algorithm Check_V_4 runs in O(m³) time. ■

Next, for an MCS of size 5, we look for a quadruplet of rows (r_i, r_j, r_k, r_l) such that the set {r, r_i, r_j, r_k, r_l} is an MCS of the form V (Fig. 3.V_5). Algorithm Check_V_5 looks for an induced subgraph of the form V, consisting of 5 rows (black vertices) r, r_i, r_j, r_k, r_l that are pairwise connected, except for one missing edge, say (r_a, r_b) in {r, r_i, r_j, r_k, r_l} × {r, r_i, r_j, r_k, r_l}, and three columns (white vertices) satisfying the configuration of Figure 3.V_5.

Proposition 9

Algorithm Check_V_5 is correct and runs in O(m⁴) time.

Proof

Algorithm Check_V_5 looks for an induced subgraph with 5 black vertices {r, r_i, r_j, r_k, r_l} that are pairwise connected, except for one missing edge (r_a, r_b) in {r, r_i, r_j, r_k, r_l} × {r, r_i, r_j, r_k, r_l}. The 4 black vertices that belong to the set with r should correspond to a set of rows that is C1P. Moreover, there should exist two particular rows (black vertices) of the set, with three columns (white vertices) that satisfy the conditions on line 4 of the algorithm in order to fit the configuration depicted in Figure 3.V_5.

Next, all the tests performed by Algorithm Check_V_5 (lines 2–8 of the algorithm) on a given quadruplet (r_i, r_j, r_k, r_l) are achieved in O(1) thanks to the precomputations, and given r there might be O(m⁴) such triplets. Thus, Algorithm Check_V_5 runs in O(m⁴) time. ■

3.6.2. MCS of size larger than 5

An MCS of the form V of size larger than 5 contains exactly two kernels. Depending on whether r is a kernel or not, we distinguish two cases.

Case 1: If row r is a kernel of the MCS

Algorithm Check_V_k (see Algorithm 11) recovers an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of the form V of size larger than 5 containing r as a kernel, with the assumption that r is not contained in an MCS of size 3 or 4 (Fig. 3.V k ). The principle of the algorithm is similar to that of Algorithm Check_IV_k. It relies on first choosing the second kernel a of the MCS, and the column c, of the induced subgraph of type V responsible for the MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} , such that c is contained in both r and a, but in no other row of the MCS (see Fig. 3.V k ). Next, it considers the subgraph H of G induced by the set of black vertices (rows) that are neighbors of both r and a, but do not contain c. We denote this subgraph by H = G[N(r,a) − L(c)]. Then it looks for a set of rows Q, constituting a chordless path in H, such that {r} ∪ Q is an MCS of the form V.

Algorithm 11: Check_V_k (r, G) – O(n²m²)

Input: a row r, the row–column intersection graph G.

Assumption: r is not contained in an MCS of size 3 or 4.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger than 5 given by a forbidden induced subgraph of the form V such that r is one of its kernel, if such an MCS exists, otherwise returns “NO”.

1: for any black vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a \in N ( r )$$ \end{document} do

2: for any column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in ( r \cap a )$$ \end{document} do

3: H = G[N(r, a) − L(c)]

4: for any connected component C of H do

5: pick a couple (r_i, r_j) of black vertices in C that satisfies (1) r_i and r_j are not connected, and (2) (r_i ∩ r) − a ≠ ∅, and (3) (r_j ∩ a) − r ≠ ∅.

6: find a chordless path P in C linking r_i and r_j

7: pick the smallest subpath Q of P linking two vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_i^{ \prime}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_j^{ \prime}$$ \end{document} , such that the couple ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_i^{ \prime} , r_j^{ \prime}$$ \end{document} ) also satisfies (1) and (2) and (3)

8: return {r} ∪ Q

9: end for

10: end for

11: end for

12: return “NO”

Proposition 10

Algorithm Check_V_k is correct and runs in O(n²m²) time.

Proof

The proofs are similar to the proofs for the correctness and the complexity of Algorithm Check_IV_k as the two algorithms are based on the same principle. However, here the complexity is multiplied by a factor n due to considering all black vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a \in N ( r )$$ \end{document} . ■

Case 2: If row r is not a kernel of the MCS

Algorithm Check_V_p (See Algorithm 12) recovers an MCS S of the form V of size larger than 5 containing r, such that r is not a kernel of the MCS, with the assumptions that r is not contained in an MCS of size 3 or 4, and r does not belong to an induced chordless cycle of G_R (Fig. 3.V).

Algorithm 12: Check_V_p (r, G) – O(nm⁷)

Input: a row r, the row–column intersection graph G.

Assumption: r is not contained in an MCS of size 3 or 4.

r does not belong to an induced chordless cycle of G_R.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger than 5 given by a forbidden induced subgraph of the form V containing r, but not as a kernel, if such an MCS exists, otherwise returns “NO”.

1: for any couple of connected black vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( a , b ) \in N ( r ) ^2$$ \end{document} do

2: for any column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in ( a \cap b ) - r$$ \end{document} do

3: return Check_V (r, (a, b), c, G)

4: end for

5: end for

6: return “NO”

The principle of the algorithm is similar to that of Algorithm Check_IV_p. It consists in first choosing the two kernels (a, b) of the MCS S among the black vertices (rows) neighbors of r, and the column c, of the induced subgraph responsible for S, that is contained in both a and b, but in no other row of the MCS. Next, the algorithm calls Algorithm Check_V (see Algorithm 13) to look for the MCS S with r, (a, b), c, and G given as parameters.

Algorithm 13: Check_V (r, (a, b), c, G) – O(m⁵)

Input: three rows r, a, and b, and a column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in a \cap b$$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in ( N ( a , b ) - L ( c ) )$$ \end{document} .

Assumption: r is not contained in an MCS of size 3, 4, or 5.

r is not contained in an MCS of type IV.

r does not belong to an induced chordless cycle of G_R.

Output: returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger than 5 given by a forbidden induced subgraph of the form V containing a, b, and r, and whose kernels are a and b, if such an MCS exists, otherwise returns “NO”.

1: H = G[N(a, b) − L(c)]

2: let C = (V_C, E_C) be the connected component of H to which r belongs.

3: let V_A be the set of vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_A = \{ u \in V_C : ( u \cap a ) - b \neq \emptyset \} $$ \end{document} .

4: let V_B be the set of vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_B = \{ v \in V_C : ( v \cap b ) - a \neq \emptyset \} $$ \end{document} .

5: let E_AB be the set of edges \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$E_{AB} = \{ ( u , v ) , u \in V_A , v \in V_B : u \cap v = \emptyset \} $$ \end{document} .

6: let V_a be the set of vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_a = \{ u \in V_C : u - a \neq \emptyset \} $$ \end{document} , and E_a be the set of edges \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$E_a = \{ ( u , v ) \in V_a^2 : u \cap v = \emptyset \} $$ \end{document} .

7: let V_b be the set of vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_b = \{ u \in V_C : u - b \neq \emptyset \} $$ \end{document} , and E_b be the set of edges \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$E_b = \{ ( u , v ) \in V_b^2 : u \cap v = \emptyset \} $$ \end{document} .

8: let D = (V_D, E_D) be the graph such that V_D = V_C and E_D = E_C ∪ E_AB ∪ E_a ∪ E_b

9: Q = Check_I (r, D)

10: if Q ≠ “NO” then

11: return {a, b} ∪ Q

12: end if

13: return “NO”

Proposition 11

Algorithm Check_V_p is correct and runs in O(nm⁷) time.

Proof

In order to prove the correctness and the complexity of Algorithm Check_V_p, we need to prove the correctness and give the complexity of Algorithm Check_V that is called in Check_V_p.

The correctness of Check_V comes from the fact that r does not belong to any chordless cycle in the graph C computed at line 2 of the algorithm by assumption. Let Q be a chordless cycle in the graph D containing vertex r, computed at line 9 of the algorithm. As r does not belong to an induced chordless cycle of the C by assumption, then Q necessarily contains at least one edge belonging to the set E_AB ∪ E_a ∪ E_b. We first give two trivial but useful properties for the remaining of the proof: (i) for any two edges of Q, there always exist two extremities u and v of these edges, one from each edge, that are not connected by an edge in the graph C, i.e., u ∩ v = ∅; (ii) V_A ⊆ V_b and V_B ⊆ V_a. We also prove the following useful property: (iii) V_a ⊆ (V_B ∪ V_b) and V_b ⊆ (V_A ∪ V_a). Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$x \in V_a$$ \end{document} , there exists c such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in x$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \notin a$$ \end{document} . Then either \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \notin b$$ \end{document} , in which case \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$x \in V_b$$ \end{document} , or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in b$$ \end{document} , which implies that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$x \in V_B$$ \end{document} . The proof is similar for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_b \subseteq ( V_A \cup V_a )$$ \end{document} .

We now prove that the cycle Q necessarily contains at most one edge of the set E_AB ∪ E_a ∪ E_b. Indeed, let us suppose that Q contains two edges of E_AB ∪ E_a ∪ E_b. Then let u, v be two disconnected extremities of these edges in the graph C [Property (i)]. We show that (u, v) necessarily constitutes an edge that is a chord for the chordless cycle Q in the graph D : contradiction.
(1) If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_A^2$$ \end{document} [or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_B^2$$ \end{document} ], then from Property (ii), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_b^2$$ \end{document} [or. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_a^2$$ \end{document} , and thus \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_b$$ \end{document} [or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_a$$ \end{document} ];

(2) If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_a^2$$ \end{document} [or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_b^2$$ \end{document} , then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_a$$ \end{document} [or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_b$$ \end{document} ;

(3) If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_A \times V_B$$ \end{document} (or the symmetric), then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_{AB}$$ \end{document} ;

(4) If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_A \times V_a$$ \end{document} (or the symmetric), then from Property (iii), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_A \times V_B$$ \end{document} or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_A \times V_b$$ \end{document} , and thus \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_{AB}$$ \end{document} or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_b$$ \end{document} from cases 3 and 6;

(5) If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_B \times V_b$$ \end{document} (or the symmetric), then from Property (iii), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_B \times V_A$$ \end{document} or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_B \times V_a$$ \end{document} , and thus \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_{AB}$$ \end{document} or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_a$$ \end{document} from cases 3 and 6;

(6) If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_A \times V_b$$ \end{document} [or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_B \times V_a$$ \end{document} (or the symmetric), then from Property (ii), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_b^2$$ \end{document} [or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_a^2$$ \end{document} ], and thus \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_b$$ \end{document} [or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_a$$ \end{document} ];

(7) If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_a \times V_b$$ \end{document} (or the symmetric), then from Property (iii), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_b \times V_b$$ \end{document} or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in V_B \times V_b$$ \end{document} , and thus \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_b$$ \end{document} or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v ) \in E_{AB} \cup E_a$$ \end{document} from cases 1 and 5.

In consequence, there exists at most one edge, and then exactly one edge of the set E_AB ∪ E_a ∪ E_b in the cycle Q in the graph D. Next, let (r_i, r_j) be the only edge of Q belonging to E_AB ∪ E_a ∪ E_b. We show that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( r_i , r_j )\ \notin \ E_a \cup E_b$$ \end{document} . Indeed, if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( r_i , r_j ) \in E_a$$ \end{document} [or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( r_i , r_j ) \in E_b$$ \end{document} ], then the set {a} ∪ Q (or {b} ∪ Q) satisfies the conditions to be an MCS of type IV with a (or b) as kernel, which is impossible by assumption.

So we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( r_i , r_j ) \in E_{AB} - ( E_a \cup E_b )$$ \end{document} . Finally, removing the edge (r_i, r_j) from the cycle yields a chordless path Q in G containing r such that each vertex of Q is connected to vertices a and b, and the extremities r_i and r_j of Q satisfy (1) r_i and r_j are not connected, and (2) (r_i ∩ a) − b ≠ ∅, and (3) (r_j ∩ b) − a ≠ ∅. and (4) Q does not contain any smaller subpath satisfying conditions (1) and (2) and (3). These conditions are necessary and sufficient for the set {a, b} ∪ Q to form the rows of an induced subgraph of the form V, and this set cannot contain a smaller MCS because such an MCS would be either an MCS of size 3 including a or b; or an MCS of type II or III necessarily including a or b as kernel; or an MCS of type IV and size larger than 3 having a or b as kernel; or an MCS of type V and size larger than 3 having a and b as kernels. These three last cases are impossible, because they would induce a chord from the set E_AB ∪ E_a ∪ E_b in the chordless cycle induced by Q in the graph D.

The correctness of Algorithm Check_V_p follows immediately from the correctness of Algorithm Check_V. Algorithm Check_V calls Algorithm Check_I. Both algorithms have the same time complexity in O(m⁵) time. It follows immediately that Algorithm Check_IV _p runs in O(nm⁷) time. ■

4. Conclusion

We describe an O(n²m² + nm⁷) time algorithm for deciding if a given row r of an m × n 0-1 matrix M belongs to at least one MCS.

The algorithm consists of a precomputation phase that runs in O(nm⁴), followed by 6 consecutive steps in which we look for some MCS containing r, and constituting the set of rows of a forbidden induced subgraph in the row–column intersection graph of M (see Table 1). The core of the algorithm relies on reducing the recognition of complex forbidden induced subgraphs to the detection of induced cycles in ad-hoc graphs.

Table 1.
Summary of 6 Steps in Algorithm

Steps Algorithms Comp.

Step 1 Check_I O(m⁵)

Step 2 Check_IV_V_3 O(m²)

Step 3 Check_II_4 O(m³)

Step 4 Check_III_4 O(m³)

Check_IV_4 O(m³)

Check_IV _k O(nm²)

Step 5 Check_IV _p O(nm⁶)

Check_V_4 O(m³)

Check_V_5 O(m⁴)

Check_V_k O(n²m²)

Step 6 Check_V_p O(nm⁷)

Algorithm 1: Check_I (r, G_R) – O(m⁵)
Input:	a row r, the subgraph G_R.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} given by a forbidden induced subgraph of the form I containing r if such an MCS exists, otherwise returns “NO”.
1:	for any P₄ of G_R containing r do
2:	Consider the graph G′ obtained from G_R after removing the two internal vertices of the P₄ and their neighborhood from the graph, and consider the extremities r_i and r_j of the P₄
3:	if there exists an r_ir_j-path in G′ then
4:	find a chordless path P in this graph linking r_i and r_j.
5:	return the set of vertices of the P₄ plus the set of vertices of P
6:	end if
7:	end for
8:	return “NO”

Algorithm 2: Check_IV_V_3 (r, G) – O(m²)
Input:	a row r, the row–column intersection graph G.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size 3 given by a forbidden induced subgraph of the form IV or V containing r if such an MCS exists, otherwise returns “NO”.
1:	for any couple (r_i, r_j) of black vertices that both overlap r, and overlap each other do
2:	if r − (r_i ∪ r_j) ≠ ∅ and r_i − (r ∪ r_j) ≠ ∅ and r_j − (r ∪ r_i) ≠ ∅ then
3:	return {r, r_i, r_j}
4:	end if
5:	if (r_i ∩ r_j) − r ≠ ∅ and (r ∩ r_j) − r_i ≠ ∅ and (r ∩ r_i) − r_j ≠ ∅ then
6:	return {r, r_i, r_j}
7:	end if
8:	end for
9:	return “NO”

Algorithm 3: Check_II_4 (r, G) – O(m³)
Input:	a row r, the row–column intersection graph G.
Assumption:	r is not contained in an MCS of size 3.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} given by a forbidden induced subgraph of the form II containing r if such an MCS exists, otherwise returns “NO”.
1:	for any triplet (r_i, r_j, r_k) of black vertices such that r_i, r_j, r_k overlap r do
2:	if there are no edges (r_i, r_j), (r_i, r_k), and (r_j, r_k) in G then
3:	return {r, r_i, r_j, r_k}
4:	end if
5:	end for
6:	for any triplet (r_i, r_j, r_k) of black vertices such that r_i overlaps r, and r_j,r_k overlap r_i do
7:	if there are no edges (r, r_j), (r, r_k), or (r_j, r_k) in G then
8:	return {r_i, r, r_j, r_k}
9:	end if
10:	end for
11:	return “NO”

Algorithm 4: Check_III_4 (r, G) – O(m³)
Input:	a row r, the row–column intersection graph G.
Assumption:	r is not contained in an MCS of size 3.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} given by a forbidden induced subgraph of the form III containing r if such an MCS exists, otherwise returns “NO”.
1:	for any triplet (r_i, r_j, r_k) of black vertices such that r_i, r_j, r_k overlap r, and r − (r_i ∩ r_j ∩ r_k) ≠ ∅ do
2:	if there is no edge (r_i, r_k) in G, and (r_i ∩ r_j) − r ≠ ∅, and (r_j ∩ r_k) − r ≠ ∅ then
3:	return {r, r_i, r_j, r_k}
4:	end if
5:	end for
6:	for any triplet (r_i, r_j, r_k) of black vertices of such that r_i overlaps r, and r_j, r_k overlap r_i, and r_i − (r ∩ r_j ∩ r_k) ≠ ∅, and {r_i, r_j, r_k}is not an MCS do
7:	if there is no edge (r, r_k) in G, and (r ∩ r_j) − r_i ≠ ∅, and (r_j ∩ r_k) − r_i ≠ ∅ then
8:	return {r_i, r, r_j, r_k}
9:	end if
10:	end for
11:	for any triplet (r_i, r_j, r_k) of black vertices of such that r_i overlaps r, and r_j, r_k overlap r_i, and r_i − (r ∩ r_j ∩ r_k) ≠ ∅ do
12:	if there is no edge (r_j, r_k) in G, and (r_j ∩ r) − r_i ≠ ∅, and (r ∩ r_k) − r_i ≠ ∅ then
13:	return {r_i, r_j, r, r_k}
14:	end if
15:	end for
16:	return “NO”

Algorithm 5: Check_IV_4 (r, G) – O(m³)
Input:	a row r, the row–column intersection graph G.
Assumption:	r is not contained in an MCS of size 3.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size 4 given by a forbidden induced subgraph of the form IV containing r if such an MCS exists, otherwise returns “NO”.
1:	for any triplet (r_i, r_j, r_k) of black vertices such that r_i, r_j, r_k are connected to r, and r − (r_i ∩ r_j ∩ r_k) ≠ ∅ do
2:	if there is no edge (r_i, r_k) in G, and (r_i ∩ r_j) ≠ ∅, and (r_j ∩ r_k) ≠ ∅, and r_i − (r ∪ r_j) ≠ ∅, and r_k − (r ∪ r_j) ≠ ∅ then
3:	return {r, r_i, r_j, r_k}
4:	end if
5:	end for
6:	for any triplet (r_i, r_j, r_k) of black vertices of such that r_i is connected to r, and r_j, r_k are connected to r_i, and r_i −(r ∩ r_j ∩ r_k) ≠ ∅, and {r_i, r_j, r_k}is not an MCS do
7:	if there is no edge (r, r_k) in G, and (r ∩ r_j) ≠ ∅, and (r_j ∩ r_k) ≠ ∅, and r − (r_i ∪ r_j) ≠ ∅, and r_k −(r_i ∪ r_j) ≠ ∅ then
8:	return {r_i, r, r_j, r_k}
9:	end if
10:	end for
11:	for any triplet (r_i, r_j, r_k) of black vertices of such that r_i is connected to r, and r_j, r_k are connected to r_i, and r_i − (r ∩ r_j ∩ r_k) ≠ ∅ do
12:	if there is no edge (r_j, r_k) in G, and (r_j ∩ r) ≠ ∅, and (r ∩ r_k) ≠ ∅, and r_j − (r ∪ r_i) ≠ ∅, and r_k − (r ∪ r_i) ≠ ∅ then
13:	return {r_i, r_j, r, r_k}
14:	end if
15:	end for
16:	return “NO”

Algorithm 6: Check_IV_k (r, G) – O(nm²)
Input:	a row r, the row–column intersection graph G.
Assumption:	r is not contained in an MCS of size 3.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger that 4 given by a forbidden induced subgraph of the form IV whose kernel is r if such an MCS exists, otherwise returns “NO”.
1:	for any column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in r$$ \end{document} do
2:	H = G[N(r) − L(c)]
3:	for any connected component C of H do
4:	pick a couple (r_i, r_j) of black vertices in C that satisfies (1) r_i and r_j are not connected, and (2) r_i, r_j overlap r.
5:	find a chordless path P in C linking r_i and r_j
6:	pick the smallest subpath Q of P linking two vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_i^{ \prime}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_j^{ \prime}$$ \end{document} , such that the couple ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_i^{ \prime} , r_j^{ \prime}$$ \end{document} ) also satisfies (1) and (2)
7:	return {r} ∪ Q
8:	end for
9:	end for
10:	return “NO”

Algorithm 7: Check_IV_p (r, G) – O(nm⁶)
Input:	a row r, the row–column intersection graph G.
Assumption:	r is not contained in an MCS of size 3.
	r does not belong to an induced chordless cycle of G_R.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger than 4 given by a forbidden induced subgraph of the form IV containing r whose kernel is not r if such an MCS exists, otherwise returns “NO”.
1:	for any black vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a \in N ( r )$$ \end{document} do
2:	for any column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in a - r$$ \end{document} do
3:	return Check_IV(r, a, c, G)
4:	end for
5:	end for
6:	return “NO”

Algorithm 8: Check_IV (r, a, c, G) – O(m⁵)
Input:	two rows r and a, and a column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in a$$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in ( N ( a ) - L ( c ) )$$ \end{document} .
Assumption:	r is not contained in an MCS of size 3.
	r does not belong to an induced chordless cycle of G_R.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger than 4 given by a forbidden induced subgraph of the form IV containing r and a, whose kernel is a if such an MCS exists, otherwise returns “NO”.
1:	H = G[N(a) − L(c)]
2:	let C = (V_C, E_C) be the connected component of H to which r belongs.
3:	let V_a be the set of vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_a = \{ u \in V_C : u - a \neq \emptyset \} $$ \end{document} .
4:	let E_a be the set of edges \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$E_a = \{ ( u , v ) \in V_a^2 : u \cap v = \emptyset \} $$ \end{document} .
5:	let D = (V_D, E_D) be the graph such that V_D = V_C and E_D = E_C ∪ E_a.
6:	Q = Check_I (r, D)
7:	if Q ≠ “NO” then
8:	return {a} ∪ Q
9:	end if
10:	return “NO”

Algorithm 9: Check_V_4 (r, G) – O(m³)
Input:	a row r, the row–column intersection graph G.
Assumption:	r is not contained in an MCS of size 3.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size 4 given by a forbidden induced subgraph of the form V containing r if such an MCS exists, otherwise returns “NO”.
1:	for any triplet (r_i, r_j, r_k) of black vertices such that r_i, r_j, r_k are connected to r, and are pairwise connected do
2:	if (r_i, r_j, r_k) is not an MCS, and (r ∩ r_i) − (r_j ∪ r_k) ≠ ∅, and (r_j ∩ r_k) − (r ∪ r_i) ≠ ∅ then
3:	if (r_i ∩ r_j) − (r ∪ r_k) ≠ ∅ then
4:	return {r, r_i, r_j, r_k}
5:	end if
6:	if (r ∩ r_j) − (r_i ∪ r_k) ≠ ∅ then
7:	return {r_i, r, r_j, r_k}
8:	end if
9:	end if
10:	end for
11:	return “NO”

Algorithm 10: Check_V_5 (r, G) – O(m⁴)
Input:	a row r, the row–column intersection graph G.
Assumption:	r is not contained in an MCS of size 3 or 4.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size 5 given by a forbidden induced subgraph of the form V containing r if such an MCS exists, otherwise returns “NO”.
1:	for any quadruplet (r_i, r_j, r_k, r_l) of black vertices such that r, r_i, r_j, r_k, r_l are pairwise connected, except for one edge (r_a, r_b) in {r, r_i, r_j, r_k, r_l} × {r, r_i, r_j, r_k, r_l} missing do
2:	if {r_i, r_j, r_k, r_l}is C1P then
3:	for any pair (a, b) in ({r, r_i, r_j, r_k, r_l}−{r_a, r_b}) × ({r, r_i, r_j, r_k, r_l}−{r_a, r_b}) do
4:	if (a ∩ b) − ∪ {r, r_i, r_j, r_k, r_l}−{a, b} ≠ ∅, and (r_k ∩ a) − ∪ {r, r_i, r_j, r_k, r_l} − {r_k, a} ≠ ∅, and (r_l ∩ b) − ∪ {r, r_i, r_j, r_k, r_l}−{r_l, b} ≠ ∅ then
5:	return {r, r_i, r_j, r_k, r_l}
6:	end if
7:	end for
8:	end if
9:	end for
10:	return “NO”

Algorithm 11: Check_V_k (r, G) – O(n²m²)
Input:	a row r, the row–column intersection graph G.
Assumption:	r is not contained in an MCS of size 3 or 4.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger than 5 given by a forbidden induced subgraph of the form V such that r is one of its kernel, if such an MCS exists, otherwise returns “NO”.
1:	for any black vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a \in N ( r )$$ \end{document} do
2:	for any column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in ( r \cap a )$$ \end{document} do
3:	H = G[N(r, a) − L(c)]
4:	for any connected component C of H do
5:	pick a couple (r_i, r_j) of black vertices in C that satisfies (1) r_i and r_j are not connected, and (2) (r_i ∩ r) − a ≠ ∅, and (3) (r_j ∩ a) − r ≠ ∅.
6:	find a chordless path P in C linking r_i and r_j
7:	pick the smallest subpath Q of P linking two vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_i^{ \prime}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_j^{ \prime}$$ \end{document} , such that the couple ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r_i^{ \prime} , r_j^{ \prime}$$ \end{document} ) also satisfies (1) and (2) and (3)
8:	return {r} ∪ Q
9:	end for
10:	end for
11:	end for
12:	return “NO”

Algorithm 12: Check_V_p (r, G) – O(nm⁷)
Input:	a row r, the row–column intersection graph G.
Assumption:	r is not contained in an MCS of size 3 or 4.
	r does not belong to an induced chordless cycle of G_R.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger than 5 given by a forbidden induced subgraph of the form V containing r, but not as a kernel, if such an MCS exists, otherwise returns “NO”.
1:	for any couple of connected black vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( a , b ) \in N ( r ) ^2$$ \end{document} do
2:	for any column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in ( a \cap b ) - r$$ \end{document} do
3:	return Check_V (r, (a, b), c, G)
4:	end for
5:	end for
6:	return “NO”

Algorithm 13: Check_V (r, (a, b), c, G) – O(m⁵)
Input:	three rows r, a, and b, and a column \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \in a \cap b$$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in ( N ( a , b ) - L ( c ) )$$ \end{document} .
Assumption:	r is not contained in an MCS of size 3, 4, or 5.
	r is not contained in an MCS of type IV.
	r does not belong to an induced chordless cycle of G_R.
Output:	returns an MCS \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal S}$$ \end{document} of size larger than 5 given by a forbidden induced subgraph of the form V containing a, b, and r, and whose kernels are a and b, if such an MCS exists, otherwise returns “NO”.
1:	H = G[N(a, b) − L(c)]
2:	let C = (V_C, E_C) be the connected component of H to which r belongs.
3:	let V_A be the set of vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_A = \{ u \in V_C : ( u \cap a ) - b \neq \emptyset \} $$ \end{document} .
4:	let V_B be the set of vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_B = \{ v \in V_C : ( v \cap b ) - a \neq \emptyset \} $$ \end{document} .
5:	let E_AB be the set of edges \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$E_{AB} = \{ ( u , v ) , u \in V_A , v \in V_B : u \cap v = \emptyset \} $$ \end{document} .
6:	let V_a be the set of vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_a = \{ u \in V_C : u - a \neq \emptyset \} $$ \end{document} , and E_a be the set of edges \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$E_a = \{ ( u , v ) \in V_a^2 : u \cap v = \emptyset \} $$ \end{document} .
7:	let V_b be the set of vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V_b = \{ u \in V_C : u - b \neq \emptyset \} $$ \end{document} , and E_b be the set of edges \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$E_b = \{ ( u , v ) \in V_b^2 : u \cap v = \emptyset \} $$ \end{document} .
8:	let D = (V_D, E_D) be the graph such that V_D = V_C and E_D = E_C ∪ E_AB ∪ E_a ∪ E_b
9:	Q = Check_I (r, D)
10:	if Q ≠ “NO” then
11:	return {a, b} ∪ Q
12:	end if
13:	return “NO”

Steps	Algorithms	Comp.
Step 1	Check_I	O(m⁵)
Step 2	Check_IV_V_3	O(m²)
Step 3	Check_II_4	O(m³)
Step 4	Check_III_4	O(m³)
	Check_IV_4	O(m³)
	Check_IV _k	O(nm²)
Step 5	Check_IV _p	O(nm⁶)
	Check_V_4	O(m³)
	Check_V_5	O(m⁴)
	Check_V_k	O(n²m²)
Step 6	Check_V_p	O(nm⁷)

Footnotes

Acknowledgment

This work was partly supported by the French MAPPI project (ANR-2010-COSI-004). We would like to thank Nicolas Trotignon for his valuable comments on induced subgraphs and also Juraj Stacho for his participation in some meetings on the subject.

Disclosure Statement

The authors declare that no competing financial interests exist.

References

Bergeron

, Blanchette

, Chateau

, and Chauve

2004. Reconstructing ancestral gene orders using conserved intervals. In Workshop on Algorithms in Bioinformatics (WABI 2004), Lecture Notes in Computer Science, 3240, 14–25.

Bertrand

, Gagnon

, Blanchette

, and El-Mabrouk

2010. Reconstruction of ancestral genome subject to whole genome duplication, speciation, rearrangement and loss. In Workshop on Algorithms in Bioinformatics (WABI), Lecture Notes in Computer Science, 6293, 78–89.

Blin

, Rizzi

,and Vialette

2010. A faster algorithm for finding minimum Tucker submatrices. In 6th Conference on Computability in Europe (CiE), Lecture Notes in Computer Science, 6158, 69–77.

Blin

, Rizzi

, and Vialette

2011. A polynomial-time algorithm for finding a minimal conflicting set containing a given row. In CSR, Lecture Notes in Computer Science, 6651, 373–384.

Chauve

, and Tannier

2008. A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genomes. PLoS Comput. Biol., 4, e1000234.

Chauve

, Haus

U.-U.

, Stephen

, and You

2009. Minimal conflicting sets for the consecutive ones property in ancestral genome reconstruction. In Recomb-Comparative Genomics (Recomb-CG09), Lecture Notes in Computer Science, 5817, 48–58.

Dom

2009. Algorithmic aspects of the consecutive-ones property. Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS), 98, 27–59.

Lekkerkerker

, and Boland

1962. Representation of a finite graph by a set of intervals on the real line. Fundam. Math., 51, 45–64.

, Zhang

, Suh

, et al. 2006. Reconstructing contiguous regions of an ancestral genome. Genome Res., 16, 1557–1565.

10.

Muffato

, Louis

, Poisnel

, and Roest-Crollius

2010. Genomicus: a database and a browser to study gene synteny in modern and ancestral genomes. Bioinformatics, 26, 1119–1121.

11.

Nishizeki

, and Rahman

M.S.

2004. Planar Graph Drawing. World Scientific, Sinapore.

12.

Stoye

, and Wittler

2009. A unified approach for reconstructing ancient gene clusters. IEEE/ACM Trans. Comput. Biol. Bioinform., 6, 387–400.

13.

Tucker

1972. A structure theorem for the consecutive 1s property. J. Comb. Theory B, 12, 153–162.