TY - JOUR
T1 - Combinatorics and Algorithms for Quasi-Chain Graphs
AU - Alecu, Bogdan
AU - Atminas, Aistis
AU - Lozin, Vadim
AU - Malyshev, Dmitriy
N1 - Funding Information:
This work was supported by the Russian Science Foundation Grant No. 21-11-00194. Some results presented in this paper appeared in the extended abstract [] published in the proceedings of the 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021.
Publisher Copyright:
© 2022, The Author(s).
PY - 2023/3
Y1 - 2023/3
N2 - 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.
AB - 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.
KW - Bipartite graphs
KW - Implicit representation
KW - Polynomial-time algorithm
UR - http://www.scopus.com/inward/record.url?scp=85135742099&partnerID=8YFLogxK
U2 - 10.1007/s00453-022-01019-6
DO - 10.1007/s00453-022-01019-6
M3 - Article
AN - SCOPUS:85135742099
SN - 0178-4617
VL - 85
SP - 642
EP - 664
JO - Algorithmica
JF - Algorithmica
IS - 3
ER -