On the Complexity of List -Packing for Sparse Graph Classes

Tatsuya Gima; Tesshu Hanaka; Yasuaki Kobayashi; Yota Otachi; Tomohito Shirai; Akira Suzuki; Yuma Tamura; Xiao Zhou

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

On the Complexity of List -Packing for Sparse Graph Classes

Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou

数理情報

研究成果: 書籍/レポートタイプへの寄稿 › 会議への寄与

抄録

The problem of packing as many subgraphs isomorphic to as possible in a graph for a class of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for H that contains at least three vertices and at least three edges, respectively. In this paper, we consider “list variants” of these problems: Given a graph G, an integer k, and a collection of subgraphs of G isomorphic to some , the goal is to compute k subgraphs in that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.

本文言語	英語
ホスト出版物のタイトル	WALCOM
ホスト出版物のサブタイトル	Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Proceedings
編集者	Ryuhei Uehara, Katsuhisa Yamanaka, Hsu-Chun Yen
出版社	Springer Science and Business Media Deutschland GmbH
ページ	421-435
ページ数	15
ISBN（印刷版）	9789819705658
DOI	https://doi.org/10.1007/978-981-97-0566-5_30
出版ステータス	出版済み - 2024
イベント	18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024 - Kanazawa, 日本継続期間: 3月 18 2024 → 3月 20 2024

出版物シリーズ

名前	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
巻	14549 LNCS
ISSN（印刷版）	0302-9743
ISSN（電子版）	1611-3349

会議

会議	18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024
国/地域	日本
City	Kanazawa
Period	3/18/24 → 3/20/24

!!!All Science Journal Classification (ASJC) codes

理論的コンピュータサイエンス
コンピュータサイエンス一般

文献へのアクセス

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

他のファイルとリンク

引用スタイル

Gima, T., Hanaka, T., Kobayashi, Y., Otachi, Y., Shirai, T., Suzuki, A., Tamura, Y., & Zhou, X. (2024). On the Complexity of List -Packing for Sparse Graph Classes. 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. 421-435). (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_30

On the Complexity of List -Packing for Sparse Graph Classes. / Gima, Tatsuya; Hanaka, Tesshu; Kobayashi, Yasuaki その他.
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. 421-435 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14549 LNCS).

研究成果: 書籍/レポートタイプへの寄稿 › 会議への寄与

Gima, T, Hanaka, T, Kobayashi, Y, Otachi, Y, Shirai, T, Suzuki, A, Tamura, Y & Zhou, X 2024, On the Complexity of List -Packing for Sparse Graph Classes. 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. 421-435, 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Kanazawa, 日本, 3/18/24. https://doi.org/10.1007/978-981-97-0566-5_30

Gima T, Hanaka T, Kobayashi Y, Otachi Y, Shirai T, Suzuki A その他. On the Complexity of List -Packing for Sparse Graph Classes. 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. 421-435. (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_30

Gima, Tatsuya ; Hanaka, Tesshu ; Kobayashi, Yasuaki その他. / On the Complexity of List -Packing for Sparse Graph Classes. 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. 421-435 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c8704ab1d20d4ebdb6fee4ea66996f8c,

title = "On the Complexity of List -Packing for Sparse Graph Classes",

abstract = "The problem of packing as many subgraphs isomorphic to as possible in a graph for a class of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for H that contains at least three vertices and at least three edges, respectively. In this paper, we consider “list variants” of these problems: Given a graph G, an integer k, and a collection of subgraphs of G isomorphic to some , the goal is to compute k subgraphs in that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.",

author = "Tatsuya Gima and Tesshu Hanaka and Yasuaki Kobayashi and Yota Otachi and Tomohito Shirai and Akira Suzuki and Yuma Tamura and Xiao Zhou",

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_30",

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 = "421--435",

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

booktitle = "WALCOM",

address = "Germany",

}

TY - GEN

T1 - On the Complexity of List -Packing for Sparse Graph Classes

AU - Gima, Tatsuya

AU - Hanaka, Tesshu

AU - Kobayashi, Yasuaki

AU - Otachi, Yota

AU - Shirai, Tomohito

AU - Suzuki, Akira

AU - Tamura, Yuma

AU - Zhou, Xiao

PY - 2024

Y1 - 2024

N2 - The problem of packing as many subgraphs isomorphic to as possible in a graph for a class of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for H that contains at least three vertices and at least three edges, respectively. In this paper, we consider “list variants” of these problems: Given a graph G, an integer k, and a collection of subgraphs of G isomorphic to some , the goal is to compute k subgraphs in that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.

AB - The problem of packing as many subgraphs isomorphic to as possible in a graph for a class of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for H that contains at least three vertices and at least three edges, respectively. In this paper, we consider “list variants” of these problems: Given a graph G, an integer k, and a collection of subgraphs of G isomorphic to some , the goal is to compute k subgraphs in that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:85187777258

SN - 9789819705658

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

SP - 421

EP - 435

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 -