A general approach to avoiding two by two submatrices

V.G. Deineko, R. Rudolf, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    4 Citations (Scopus)

    Abstract

    A matrixC is said to avoid a set of matrices, if no matrix of can be obtained by deleting some rows and columns ofC. In this paper we consider the decision problem whether the rows and columns of a given matrixC can be permuted in such a way that the permuted matrix avoids all matrices of a given class . At first an algorithm is stated for deciding whetherC can be permuted such that it avoids a set of 2×2 matrices. This approach leads to a polynomial time recognition algorithm for algebraic Monge matrices fulfilling special properties. As main result of the paper it is shown that permuted Supnick matrices can be recognized in polynomial time. Moreover, we prove that the decision problem can be solved in polynomial time, if the set is sufficiently dense, and a sparse set of 2×2 matrices is exhibited for which the decision problem is NP-complete. Eine MatrixC vermeidet eine Menge von Matrizen, wenn keine Matrix aus durch Streichen von Spalten und Zeilen vonC erhalten werden kann. In dieser Arbeit betrachten wir folgendes Entscheidungsproblem: Können die Zeilen bzw. Spalten einer MatrixC so vertauscht werden, daß die permutierte Matrix alle Matrizen aus einer gegebenen Menge vermeidet. Diese Arbeit enthält einen Algorithmus für den Fall, daß nur aus 2×2 Matrizen besteht. Dies führt zu einem polynomialen Erkennungsalgorithmus für spezielle algebraische Monge Matrizen. Als Hauptergebnis zeigen wir, daß permutierte Supnick Matrizen in polynomieller Zeit erkannt werden können. Zusätzlich wird bewiesen, daß im allgemeinen das Entscheidungsproblem NO-vollständig ist, es aber in polynomieller Zeit lösbar ist, wenn die Menge genügend dicht ist.
    Original languageEnglish
    Pages (from-to)371-388
    Number of pages18
    JournalComputing
    Volume52
    Issue number4
    DOIs
    Publication statusPublished - 1994

    Fingerprint

    Dive into the research topics of 'A general approach to avoiding two by two submatrices'. Together they form a unique fingerprint.

    Cite this