TY - GEN
T1 - Combinatorics and Algorithms for Quasi-chain Graphs
AU - Alecu, Bogdan
AU - Atminas, Aistis
AU - Lozin, Vadim
AU - Malyshev, Dmitriy
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Bipartite chain graphs
KW - Implicit representation
KW - Polynomial-time algorithm
UR - http://www.scopus.com/inward/record.url?scp=85112002794&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-79987-8_4
DO - 10.1007/978-3-030-79987-8_4
M3 - Conference Proceeding
AN - SCOPUS:85112002794
SN - 9783030799861
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 49
EP - 62
BT - Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Proceedings
A2 - Flocchini, Paola
A2 - Moura, Lucia
PB - Springer Science and Business Media Deutschland GmbH
T2 - 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021
Y2 - 5 July 2021 through 7 July 2021
ER -