Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem

Walter Didimo; Fedor V. Fomin; Petr A. Golovach; Tanmay Inamdar; Stephen Kobourov; Marie Diana Sieper

doi:10.1007/978-3-031-49275-4_13

Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem

Walter Didimo, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Stephen Kobourov, Marie Diana Sieper

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

Abstract

A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of graph layouts, such as upward drawings, level-planar drawings, and L-drawings. If the graph is not bimodal, the Maximum Bimodal Subgraph (MBS) problem asks for an embedding-preserving bimodal subgraph with the maximum number of edges. We initiate the study of the MBS problem from the parameterized complexity perspective with two main results: (i) we describe an FPT algorithm parameterized by the branchwidth (and hence by the treewidth) of the graph; (ii) we establish that MBS parameterized by the number of non-bimodal vertices admits a polynomial kernel. As the byproduct of these results, we obtain a subexponential FPT algorithm and an efficient polynomial-time approximation scheme for MBS.

Original language	English (US)
Title of host publication	Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers
Editors	Michael A. Bekos, Markus Chimani
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	189-202
Number of pages	14
ISBN (Print)	9783031492747
DOIs	https://doi.org/10.1007/978-3-031-49275-4_13
State	Published - 2023
Externally published	Yes
Event	31st International Symposium on Graph Drawing and Network Visualization, GD 2023 - Palermo, Italy Duration: Sep 20 2023 → Sep 22 2023

Publication series

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

Conference

Conference	31st International Symposium on Graph Drawing and Network Visualization, GD 2023
Country/Territory	Italy
City	Palermo
Period	9/20/23 → 9/22/23

Keywords

FPT algorithms
approximation scheme
bimodal graphs
maximum bimodal subgraph
parameterized complexity
polynomial kernel

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-49275-4_13

Cite this

Didimo, W., Fomin, F. V., Golovach, P. A., Inamdar, T., Kobourov, S., & Sieper, M. D. (2023). Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem. In M. A. Bekos, & M. Chimani (Eds.), Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers (pp. 189-202). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14466). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-49275-4_13

Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem. / Didimo, Walter; Fomin, Fedor V.; Golovach, Petr A. et al.
Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers. ed. / Michael A. Bekos; Markus Chimani. Springer Science and Business Media Deutschland GmbH, 2023. p. 189-202 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14466).

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

Didimo, W, Fomin, FV, Golovach, PA, Inamdar, T, Kobourov, S & Sieper, MD 2023, Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem. in MA Bekos & M Chimani (eds), Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14466, Springer Science and Business Media Deutschland GmbH, pp. 189-202, 31st International Symposium on Graph Drawing and Network Visualization, GD 2023, Palermo, Italy, 9/20/23. https://doi.org/10.1007/978-3-031-49275-4_13

Didimo W, Fomin FV, Golovach PA, Inamdar T, Kobourov S, Sieper MD. Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem. In Bekos MA, Chimani M, editors, Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2023. p. 189-202. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-49275-4_13

Didimo, Walter ; Fomin, Fedor V. ; Golovach, Petr A. et al. / Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem. Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers. editor / Michael A. Bekos ; Markus Chimani. Springer Science and Business Media Deutschland GmbH, 2023. pp. 189-202 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{cc62113bb82546798aa2fa4bda2a645a,

title = "Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem",

abstract = "A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of graph layouts, such as upward drawings, level-planar drawings, and L-drawings. If the graph is not bimodal, the Maximum Bimodal Subgraph (MBS) problem asks for an embedding-preserving bimodal subgraph with the maximum number of edges. We initiate the study of the MBS problem from the parameterized complexity perspective with two main results: (i) we describe an FPT algorithm parameterized by the branchwidth (and hence by the treewidth) of the graph; (ii) we establish that MBS parameterized by the number of non-bimodal vertices admits a polynomial kernel. As the byproduct of these results, we obtain a subexponential FPT algorithm and an efficient polynomial-time approximation scheme for MBS.",

keywords = "FPT algorithms, approximation scheme, bimodal graphs, maximum bimodal subgraph, parameterized complexity, polynomial kernel",

author = "Walter Didimo and Fomin, {Fedor V.} and Golovach, {Petr A.} and Tanmay Inamdar and Stephen Kobourov and Sieper, {Marie Diana}",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 31st International Symposium on Graph Drawing and Network Visualization, GD 2023 ; Conference date: 20-09-2023 Through 22-09-2023",

year = "2023",

doi = "10.1007/978-3-031-49275-4_13",

language = "English (US)",

isbn = "9783031492747",

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 = "189--202",

editor = "Bekos, {Michael A.} and Markus Chimani",

booktitle = "Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers",

address = "Germany",

}

TY - GEN

T1 - Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem

AU - Didimo, Walter

AU - Fomin, Fedor V.

AU - Golovach, Petr A.

AU - Inamdar, Tanmay

AU - Kobourov, Stephen

AU - Sieper, Marie Diana

PY - 2023

Y1 - 2023

N2 - A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of graph layouts, such as upward drawings, level-planar drawings, and L-drawings. If the graph is not bimodal, the Maximum Bimodal Subgraph (MBS) problem asks for an embedding-preserving bimodal subgraph with the maximum number of edges. We initiate the study of the MBS problem from the parameterized complexity perspective with two main results: (i) we describe an FPT algorithm parameterized by the branchwidth (and hence by the treewidth) of the graph; (ii) we establish that MBS parameterized by the number of non-bimodal vertices admits a polynomial kernel. As the byproduct of these results, we obtain a subexponential FPT algorithm and an efficient polynomial-time approximation scheme for MBS.

AB - A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of graph layouts, such as upward drawings, level-planar drawings, and L-drawings. If the graph is not bimodal, the Maximum Bimodal Subgraph (MBS) problem asks for an embedding-preserving bimodal subgraph with the maximum number of edges. We initiate the study of the MBS problem from the parameterized complexity perspective with two main results: (i) we describe an FPT algorithm parameterized by the branchwidth (and hence by the treewidth) of the graph; (ii) we establish that MBS parameterized by the number of non-bimodal vertices admits a polynomial kernel. As the byproduct of these results, we obtain a subexponential FPT algorithm and an efficient polynomial-time approximation scheme for MBS.

KW - FPT algorithms

KW - approximation scheme

KW - bimodal graphs

KW - maximum bimodal subgraph

KW - parameterized complexity

KW - polynomial kernel

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

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

U2 - 10.1007/978-3-031-49275-4_13

DO - 10.1007/978-3-031-49275-4_13

M3 - Conference contribution

AN - SCOPUS:85182604160

SN - 9783031492747

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

SP - 189

EP - 202

BT - Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers

A2 - Bekos, Michael A.

A2 - Chimani, Markus

PB - Springer Science and Business Media Deutschland GmbH

T2 - 31st International Symposium on Graph Drawing and Network Visualization, GD 2023

Y2 - 20 September 2023 through 22 September 2023

ER -