Structural Parameterizations of Vertex Integrity [Best Paper]

Tatsuya Gima; Tesshu Hanaka; Yasuaki Kobayashi; Ryota Murai; Hirotaka Ono; Yota Otachi

doi:10.1007/978-981-97-0566-5_29

Structural Parameterizations of Vertex Integrity [Best Paper]

Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, Yota Otachi

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected components small. In this paper, we initiate a systematic study of structural parameterizations of the problem of computing the unweighted/weighted vertex integrity. As structural graph parameters, we consider well-known parameters such as clique-width, treewidth, pathwidth, treedepth, modular-width, neighborhood diversity, twin cover number, and cluster vertex deletion number. We show several positive and negative results and present sharp complexity contrasts.

Original language	English
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Proceedings
Editors	Ryuhei Uehara, Katsuhisa Yamanaka, Hsu-Chun Yen
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	406-420
Number of pages	15
ISBN (Print)	9789819705658
DOIs	https://doi.org/10.1007/978-981-97-0566-5_29
Publication status	Published - 2024
Event	18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024 - Kanazawa, Japan Duration: Mar 18 2024 → Mar 20 2024

Publication series

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

Conference

Conference	18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024
Country/Territory	Japan
City	Kanazawa
Period	3/18/24 → 3/20/24

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-981-97-0566-5_29

Cite this

Gima, T., Hanaka, T., Kobayashi, Y., Murai, R., Ono, H., & Otachi, Y. (2024). Structural Parameterizations of Vertex Integrity [Best Paper]. In R. Uehara, K. Yamanaka, & H.-C. Yen (Eds.), WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Proceedings (pp. 406-420). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14549 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-981-97-0566-5_29

Structural Parameterizations of Vertex Integrity [Best Paper]. / Gima, Tatsuya; Hanaka, Tesshu; Kobayashi, Yasuaki et al.
WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Proceedings. ed. / Ryuhei Uehara; Katsuhisa Yamanaka; Hsu-Chun Yen. Springer Science and Business Media Deutschland GmbH, 2024. p. 406-420 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14549 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Gima, T, Hanaka, T, Kobayashi, Y, Murai, R, Ono, H & Otachi, Y 2024, Structural Parameterizations of Vertex Integrity [Best Paper]. in R Uehara, K Yamanaka & H-C Yen (eds), WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14549 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 406-420, 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Kanazawa, Japan, 3/18/24. https://doi.org/10.1007/978-981-97-0566-5_29

Gima T, Hanaka T, Kobayashi Y, Murai R, Ono H, Otachi Y. Structural Parameterizations of Vertex Integrity [Best Paper]. In Uehara R, Yamanaka K, Yen HC, editors, WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2024. p. 406-420. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-981-97-0566-5_29

Gima, Tatsuya ; Hanaka, Tesshu ; Kobayashi, Yasuaki et al. / Structural Parameterizations of Vertex Integrity [Best Paper]. WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Proceedings. editor / Ryuhei Uehara ; Katsuhisa Yamanaka ; Hsu-Chun Yen. Springer Science and Business Media Deutschland GmbH, 2024. pp. 406-420 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4e9fae1ab1fb47b98cc5d836d21b0b99,

title = "Structural Parameterizations of Vertex Integrity [Best Paper]",

abstract = "The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected components small. In this paper, we initiate a systematic study of structural parameterizations of the problem of computing the unweighted/weighted vertex integrity. As structural graph parameters, we consider well-known parameters such as clique-width, treewidth, pathwidth, treedepth, modular-width, neighborhood diversity, twin cover number, and cluster vertex deletion number. We show several positive and negative results and present sharp complexity contrasts.",

keywords = "Parameterized complexity, Structural graph parameter, Vertex integrity, Vulnerability of graphs",

author = "Tatsuya Gima and Tesshu Hanaka and Yasuaki Kobayashi and Ryota Murai and Hirotaka Ono and Yota Otachi",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.; 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024 ; Conference date: 18-03-2024 Through 20-03-2024",

year = "2024",

doi = "10.1007/978-981-97-0566-5_29",

language = "English",

isbn = "9789819705658",

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 = "406--420",

editor = "Ryuhei Uehara and Katsuhisa Yamanaka and Hsu-Chun Yen",

booktitle = "WALCOM",

address = "Germany",

}

TY - GEN

T1 - Structural Parameterizations of Vertex Integrity [Best Paper]

AU - Gima, Tatsuya

AU - Hanaka, Tesshu

AU - Kobayashi, Yasuaki

AU - Murai, Ryota

AU - Ono, Hirotaka

AU - Otachi, Yota

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.

PY - 2024

Y1 - 2024

N2 - The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected components small. In this paper, we initiate a systematic study of structural parameterizations of the problem of computing the unweighted/weighted vertex integrity. As structural graph parameters, we consider well-known parameters such as clique-width, treewidth, pathwidth, treedepth, modular-width, neighborhood diversity, twin cover number, and cluster vertex deletion number. We show several positive and negative results and present sharp complexity contrasts.

AB - The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected components small. In this paper, we initiate a systematic study of structural parameterizations of the problem of computing the unweighted/weighted vertex integrity. As structural graph parameters, we consider well-known parameters such as clique-width, treewidth, pathwidth, treedepth, modular-width, neighborhood diversity, twin cover number, and cluster vertex deletion number. We show several positive and negative results and present sharp complexity contrasts.

KW - Parameterized complexity

KW - Structural graph parameter

KW - Vertex integrity

KW - Vulnerability of graphs

UR - http://www.scopus.com/inward/record.url?scp=85187790060&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85187790060&partnerID=8YFLogxK

U2 - 10.1007/978-981-97-0566-5_29

DO - 10.1007/978-981-97-0566-5_29

M3 - Conference contribution

AN - SCOPUS:85187790060

SN - 9789819705658

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 406

EP - 420

BT - WALCOM

A2 - Uehara, Ryuhei

A2 - Yamanaka, Katsuhisa

A2 - Yen, Hsu-Chun

PB - Springer Science and Business Media Deutschland GmbH

T2 - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024

Y2 - 18 March 2024 through 20 March 2024

ER -