Abstract
Given a bipartite graph G = \((T\cup B,E)\), the problem bipartite 1-sided vertex explosion is to decide whether there exists a planar 2-layer embedding of G after exploding at most k vertices of B. For this problem, which is known to be NP-complete, parameterized algorithms have received increasing attention more recently. In this paper, we focus on the problem parameterized by the number k of allowed exploded vertices of B and develop a faster algorithm for it. More specifically, we show that this parameterized problem admits a kernel of at most 10.5k vertices, and present a fixed-parameter tractable algorithm running in time \(\mathcal O(2.31^k\cdot m)\), where m is the number of edges of G.
This research was supported in part by the National Natural Science Foundation of China under Grant (No.61572190), Hunan Provincial Science and Technology Program (No.2018TP1018), and Changsha Municipal Natural Science Foundation (Grant No. kq2202247).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For brevity, we only present this general rule, although there are some more refined rules for special subcases including \(|N^2(r_1)\cap N^2(r_2)| = i\), for i = 2 or i = 3.
References
Ahmed, R., Kobourov, S., Kryven, M.: An FPT algorithm for bipartite vertex splitting. In: Angelini P., Hanxleden R. von (eds.) Graph Drawing and Network Visualization. GD 2022. LNCS, vol. 13764. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-22203-0_19
Ahmed, R., et al.: Splitting vertices in 2-layer graph drawings. IEEE Comput. Graph. 43(3), 24–35 (2023)
Baumann, J., Pfretzschner, M., Rutter, I.: Parameterized complexity of vertex splitting to pathwidth at most 1. In: Paulusma, D., Ries, B. (eds.) Graph-Theoretic Concepts in Computer Science. WG 2023. LNCS, vol. 14093. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-43380-1_3
Bhore, S., Ganian, R., Montecchiani, F., Nöllenburg, M.: Parameterized algorithms for queue layouts. J. Graph Algorithms Appl. 26(3), 335–352 (2022)
Chaudhary, A., Chen, D.Z., Hu, X.S., Niemier, M.T., Ravichandran, R., Whitton, K.: Fabricatable interconnect and molecular QCA circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 26(11), 1978–1991 (2007)
Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-21275-3
Eades, P., McKay, B.D., Wormald, N.C.: On an edge crossing problem. In: ACSC 1986, pp. 327–334 (1986)
Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4), 379–403 (1994)
Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39(4), 321–347 (2004)
Liu, Y., Wang, J., Guo, J., Chen, J.: Complexity and parameterized algorithms for cograph editing. Theoret. Comput. Sci. 461, 45–54 (2012)
Liu, Y., Wang, J., You, J., Chen, J., Cao, Y.: Edge deletion problems: branching facilitated by modular decomposition. Theoret. Comput. Sci. 573, 63–70 (2015)
Liu, Y., Chen, J., Huang, J., Wang, J.: On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering. Theoret. Comput. Sci. 873, 16–24 (2021)
Liu, Y., Chen, J., Huang, J.: On book thickness parameterized by the vertex cover number. Sci. Chin. Inf. Sci. 65(4), 1–2 (2022). https://doi.org/10.1007/s11432-021-3405-x
Paul, H., Börner, K., Herr II, B.W., Quardokus, E.M.: ASCT+B REPORTER. https://hubmapconsortium.github.io/ccf-asct-reporter/. Accessed 06 June 2022
Pezzotti, N., Fekete, J.D., Höllt, T., Lelieveldt, B.P.F., Eisemann, E., Vilanova, A.: Multiscale visualization and exploration of large bipartite graphs. Comput. Graph. Forum 37(3), 549–560 (2018)
Scornavacca, C., Zickmann, F., Huson, D.H.: Tanglegrams for rooted phylogenetic trees and networks. Bioinformatics 27(13), i248–i256 (2011)
Acknowledgements
The authors thank the anonymous referees for their valuable comments and suggestions.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Liu, Y., Xiao, G., Liu, A., Wu, D., Huang, J. (2024). A Faster Parameterized Algorithm for Bipartite 1-Sided Vertex Explosion. In: Wu, W., Guo, J. (eds) Combinatorial Optimization and Applications. COCOA 2023. Lecture Notes in Computer Science, vol 14462. Springer, Cham. https://doi.org/10.1007/978-3-031-49614-1_19
Download citation
DOI: https://doi.org/10.1007/978-3-031-49614-1_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-49613-4
Online ISBN: 978-3-031-49614-1
eBook Packages: Computer ScienceComputer Science (R0)