Combinatorics and Algorithms for Quasi-chain Graphs

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

*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceedingConference Proceedingpeer-review

1 Citation (Scopus)


The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. The 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
Title of host publicationCombinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Proceedings
EditorsPaola Flocchini, Lucia Moura
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages14
ISBN (Print)9783030799861
Publication statusPublished - 2021
Event32nd International Workshop on Combinatorial Algorithms, IWOCA 2021 - Virtual, Online
Duration: 5 Jul 20217 Jul 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12757 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference32nd International Workshop on Combinatorial Algorithms, IWOCA 2021
CityVirtual, Online


  • Bipartite chain graphs
  • Implicit representation
  • Polynomial-time algorithm


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

Cite this