Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs

Suguru Yamada; Tesshu Hanaka

doi:10.1007/978-3-031-60924-4_17

Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs

Suguru Yamada, Tesshu Hanaka

Mathematical Informatics

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

Abstract

For an undirected and edge-weighted graph G=(V,E) and a vertex subset S⊆V, we define a function φ_G(formula presented), where (formula presented) is a real number, w(S) is the sum of weights of edges having two endpoints in S, and w(S,V\S) is the sum of weights of edges having one endpoint in S and the other in V\S. Then, given a graph G=(V,E) and a positive integer k, Max (Min) α-Fixed Cardinality Graph Partitioning (Max (Min) α-FCGP) is the problem to find a vertex subset (formula presented) of size k that maximizes (minimizes) φ_G(S). In this paper, we first show that Max α-FCGP with (formula presented) and Minα-FCGP with (formula presented) can be solved in time (formula presented)-time algorithm on general graphs and a (formula presented)-time randomized algorithm on apex-minor-free graphs. Moreover, for Max α-FCGP with (formula presented) and Min (formula presented), we propose an (1+d)^k2^o(kd)+O(k)n^O(1)-time algorithm. Finally, we show that they admit FPT-ASs when edge weights are constant.

Original language	English
Title of host publication	Combinatorial Optimization - 8th International Symposium, ISCO 2024, Revised Selected Papers
Editors	Amitabh Basu, Ali Ridha Mahjoub, Ali Ridha Mahjoub, Juan José Salazar González
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	220-232
Number of pages	13
ISBN (Print)	9783031609237
DOIs	https://doi.org/10.1007/978-3-031-60924-4_17
Publication status	Published - 2024
Event	8th International Symposium on Combinatorial Optimization, ISCO 2024 - La Laguna, Spain Duration: May 22 2024 → May 24 2024

Publication series

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

Conference

Conference	8th International Symposium on Combinatorial Optimization, ISCO 2024
Country/Territory	Spain
City	La Laguna
Period	5/22/24 → 5/24/24

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-60924-4_17

Cite this

Yamada, S., & Hanaka, T. (2024). Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs. In A. Basu, A. R. Mahjoub, A. R. Mahjoub, & J. J. Salazar González (Eds.), Combinatorial Optimization - 8th International Symposium, ISCO 2024, Revised Selected Papers (pp. 220-232). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14594 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-60924-4_17

Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs. / Yamada, Suguru; Hanaka, Tesshu.
Combinatorial Optimization - 8th International Symposium, ISCO 2024, Revised Selected Papers. ed. / Amitabh Basu; Ali Ridha Mahjoub; Ali Ridha Mahjoub; Juan José Salazar González. Springer Science and Business Media Deutschland GmbH, 2024. p. 220-232 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14594 LNCS).

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

Yamada, S & Hanaka, T 2024, Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs. in A Basu, AR Mahjoub, AR Mahjoub & JJ Salazar González (eds), Combinatorial Optimization - 8th International Symposium, ISCO 2024, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14594 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 220-232, 8th International Symposium on Combinatorial Optimization, ISCO 2024, La Laguna, Spain, 5/22/24. https://doi.org/10.1007/978-3-031-60924-4_17

Yamada S, Hanaka T. Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs. In Basu A, Mahjoub AR, Mahjoub AR, Salazar González JJ, editors, Combinatorial Optimization - 8th International Symposium, ISCO 2024, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2024. p. 220-232. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-60924-4_17

Yamada, Suguru ; Hanaka, Tesshu. / Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs. Combinatorial Optimization - 8th International Symposium, ISCO 2024, Revised Selected Papers. editor / Amitabh Basu ; Ali Ridha Mahjoub ; Ali Ridha Mahjoub ; Juan José Salazar González. Springer Science and Business Media Deutschland GmbH, 2024. pp. 220-232 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{524e79fe6a984b0d8bc7e5caab9379d0,

title = "Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs",

abstract = "For an undirected and edge-weighted graph G=(V,E) and a vertex subset S⊆V, we define a function φG(formula presented), where (formula presented) is a real number, w(S) is the sum of weights of edges having two endpoints in S, and w(S,V\S) is the sum of weights of edges having one endpoint in S and the other in V\S. Then, given a graph G=(V,E) and a positive integer k, Max (Min) α-Fixed Cardinality Graph Partitioning (Max (Min) α-FCGP) is the problem to find a vertex subset (formula presented) of size k that maximizes (minimizes) φG(S). In this paper, we first show that Max α-FCGP with (formula presented) and Minα-FCGP with (formula presented) can be solved in time (formula presented)-time algorithm on general graphs and a (formula presented)-time randomized algorithm on apex-minor-free graphs. Moreover, for Max α-FCGP with (formula presented) and Min (formula presented), we propose an (1+d)k2o(kd)+O(k)nO(1)-time algorithm. Finally, we show that they admit FPT-ASs when edge weights are constant.",

author = "Suguru Yamada and Tesshu Hanaka",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 8th International Symposium on Combinatorial Optimization, ISCO 2024 ; Conference date: 22-05-2024 Through 24-05-2024",

year = "2024",

doi = "10.1007/978-3-031-60924-4_17",

language = "English",

isbn = "9783031609237",

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 = "220--232",

editor = "Amitabh Basu and Mahjoub, {Ali Ridha} and Mahjoub, {Ali Ridha} and {Salazar Gonz{\'a}lez}, {Juan Jos{\'e}}",

booktitle = "Combinatorial Optimization - 8th International Symposium, ISCO 2024, Revised Selected Papers",

address = "Germany",

}

TY - GEN

T1 - Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs

AU - Yamada, Suguru

AU - Hanaka, Tesshu

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

PY - 2024

Y1 - 2024

N2 - For an undirected and edge-weighted graph G=(V,E) and a vertex subset S⊆V, we define a function φG(formula presented), where (formula presented) is a real number, w(S) is the sum of weights of edges having two endpoints in S, and w(S,V\S) is the sum of weights of edges having one endpoint in S and the other in V\S. Then, given a graph G=(V,E) and a positive integer k, Max (Min) α-Fixed Cardinality Graph Partitioning (Max (Min) α-FCGP) is the problem to find a vertex subset (formula presented) of size k that maximizes (minimizes) φG(S). In this paper, we first show that Max α-FCGP with (formula presented) and Minα-FCGP with (formula presented) can be solved in time (formula presented)-time algorithm on general graphs and a (formula presented)-time randomized algorithm on apex-minor-free graphs. Moreover, for Max α-FCGP with (formula presented) and Min (formula presented), we propose an (1+d)k2o(kd)+O(k)nO(1)-time algorithm. Finally, we show that they admit FPT-ASs when edge weights are constant.

AB - For an undirected and edge-weighted graph G=(V,E) and a vertex subset S⊆V, we define a function φG(formula presented), where (formula presented) is a real number, w(S) is the sum of weights of edges having two endpoints in S, and w(S,V\S) is the sum of weights of edges having one endpoint in S and the other in V\S. Then, given a graph G=(V,E) and a positive integer k, Max (Min) α-Fixed Cardinality Graph Partitioning (Max (Min) α-FCGP) is the problem to find a vertex subset (formula presented) of size k that maximizes (minimizes) φG(S). In this paper, we first show that Max α-FCGP with (formula presented) and Minα-FCGP with (formula presented) can be solved in time (formula presented)-time algorithm on general graphs and a (formula presented)-time randomized algorithm on apex-minor-free graphs. Moreover, for Max α-FCGP with (formula presented) and Min (formula presented), we propose an (1+d)k2o(kd)+O(k)nO(1)-time algorithm. Finally, we show that they admit FPT-ASs when edge weights are constant.

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

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

U2 - 10.1007/978-3-031-60924-4_17

DO - 10.1007/978-3-031-60924-4_17

M3 - Conference contribution

AN - SCOPUS:85195483526

SN - 9783031609237

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

SP - 220

EP - 232

BT - Combinatorial Optimization - 8th International Symposium, ISCO 2024, Revised Selected Papers

A2 - Basu, Amitabh

A2 - Mahjoub, Ali Ridha

A2 - Salazar González, Juan José

PB - Springer Science and Business Media Deutschland GmbH

T2 - 8th International Symposium on Combinatorial Optimization, ISCO 2024

Y2 - 22 May 2024 through 24 May 2024

ER -