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

Mathematical Informatics

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

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.

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	421-435
Number of pages	15
ISBN (Print)	9789819705658
DOIs	https://doi.org/10.1007/978-981-97-0566-5_30
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_30

Cite this

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 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. 421-435 (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, 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, Japan, 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 et al. 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 et al. / 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 -