Combinatorics and Algorithms for Quasi-Chain Graphs

Bogdan Alecu, Aistis Atminas, Vadim Lozin*, Dmitriy Malyshev

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. This latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded in it. In the present paper, we show that the universe of quasi-chain graphs is at least as complex as the universe of permutations by establishing a bijection between the class of all permutations and a subclass of quasi-chain graphs. This implies, in particular, that the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs. On the other hand, we propose a decomposition theorem for quasi-chain graphs that implies an implicit representation for graphs in this class and efficient solutions for some algorithmic problems that are generally intractable.

Original languageEnglish
Pages (from-to)642-664
Number of pages23
JournalAlgorithmica
Volume85
Issue number3
DOIs
Publication statusPublished - Mar 2023

Keywords

  • Bipartite graphs
  • Implicit representation
  • Polynomial-time algorithm

Fingerprint

Dive into the research topics of 'Combinatorics and Algorithms for Quasi-Chain Graphs'. Together they form a unique fingerprint.

Cite this