Combinatorics and Algorithms for Quasi-chain Graphs

Bogdan Alecu; Aistis Atminas; Vadim Lozin; Dmitriy Malyshev

doi:10.1007/978-3-030-79987-8_4

Combinatorics and Algorithms for Quasi-chain Graphs

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

^*Corresponding author for this work

University of Warwick
Higher School of Economics
Lobachevsky State University of Nizhni Novgorod

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

1 Citation (Scopus)

Abstract

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 language	English
Title of host publication	Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Proceedings
Editors	Paola Flocchini, Lucia Moura
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	49-62
Number of pages	14
ISBN (Print)	9783030799861
DOIs	https://doi.org/10.1007/978-3-030-79987-8_4
Publication status	Published - 2021
Event	32nd International Workshop on Combinatorial Algorithms, IWOCA 2021 - Virtual, Online Duration: 5 Jul 2021 → 7 Jul 2021

Publication series

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

Conference

Conference	32nd International Workshop on Combinatorial Algorithms, IWOCA 2021
City	Virtual, Online
Period	5/07/21 → 7/07/21

Keywords

Bipartite chain graphs
Implicit representation
Polynomial-time algorithm

Access to Document

10.1007/978-3-030-79987-8_4

Cite this

Alecu, B., Atminas, A., Lozin, V., & Malyshev, D. (2021). Combinatorics and Algorithms for Quasi-chain Graphs. In P. Flocchini, & L. Moura (Eds.), Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Proceedings (pp. 49-62). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12757 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-79987-8_4

Alecu, Bogdan ; Atminas, Aistis ; Lozin, Vadim et al. / Combinatorics and Algorithms for Quasi-chain Graphs. Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Proceedings. editor / Paola Flocchini ; Lucia Moura. Springer Science and Business Media Deutschland GmbH, 2021. pp. 49-62 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3fa250b46f3843fab37dd1ddcf86adb1,

title = "Combinatorics and Algorithms for Quasi-chain Graphs",

abstract = "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.",

keywords = "Bipartite chain graphs, Implicit representation, Polynomial-time algorithm",

author = "Bogdan Alecu and Aistis Atminas and Vadim Lozin and Dmitriy Malyshev",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021 ; Conference date: 05-07-2021 Through 07-07-2021",

year = "2021",

doi = "10.1007/978-3-030-79987-8\_4",

language = "English",

isbn = "9783030799861",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "49--62",

editor = "Paola Flocchini and Lucia Moura",

booktitle = "Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Proceedings",

}

Alecu, B, Atminas, A, Lozin, V & Malyshev, D 2021, Combinatorics and Algorithms for Quasi-chain Graphs. in P Flocchini & L Moura (eds), Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12757 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 49-62, 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021, Virtual, Online, 5/07/21. https://doi.org/10.1007/978-3-030-79987-8_4

Combinatorics and Algorithms for Quasi-chain Graphs. / Alecu, Bogdan; Atminas, Aistis; Lozin, Vadim et al.
Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Proceedings. ed. / Paola Flocchini; Lucia Moura. Springer Science and Business Media Deutschland GmbH, 2021. p. 49-62 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12757 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Combinatorics and Algorithms for Quasi-chain Graphs

AU - Alecu, Bogdan

AU - Atminas, Aistis

AU - Lozin, Vadim

AU - Malyshev, Dmitriy

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 - https://www.scopus.com/pages/publications/85112002794

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 -

Alecu B, Atminas A, Lozin V, Malyshev D. Combinatorics and Algorithms for Quasi-chain Graphs. In Flocchini P, Moura L, editors, Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 49-62. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-79987-8_4