Nothing Special   »   [go: up one dir, main page]

Skip to main content

A Faster Parameterized Algorithm for Bipartite 1-Sided Vertex Explosion

  • Conference paper
  • First Online:
Combinatorial Optimization and Applications (COCOA 2023)

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).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 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

  1. 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

  2. Ahmed, R., et al.: Splitting vertices in 2-layer graph drawings. IEEE Comput. Graph. 43(3), 24–35 (2023)

    Article  Google Scholar 

  3. 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

  4. Bhore, S., Ganian, R., Montecchiani, F., Nöllenburg, M.: Parameterized algorithms for queue layouts. J. Graph Algorithms Appl. 26(3), 335–352 (2022)

    Article  MathSciNet  Google Scholar 

  5. 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)

    Google Scholar 

  6. Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-21275-3

    Book  Google Scholar 

  7. Eades, P., McKay, B.D., Wormald, N.C.: On an edge crossing problem. In: ACSC 1986, pp. 327–334 (1986)

    Google Scholar 

  8. Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4), 379–403 (1994)

    Article  MathSciNet  Google Scholar 

  9. 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)

    Article  MathSciNet  Google Scholar 

  10. Liu, Y., Wang, J., Guo, J., Chen, J.: Complexity and parameterized algorithms for cograph editing. Theoret. Comput. Sci. 461, 45–54 (2012)

    Google Scholar 

  11. 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)

    Article  MathSciNet  Google Scholar 

  12. 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)

    Article  MathSciNet  Google Scholar 

  13. 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

    Article  Google Scholar 

  14. 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

  15. 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)

    Article  Google Scholar 

  16. Scornavacca, C., Zickmann, F., Huson, D.H.: Tanglegrams for rooted phylogenetic trees and networks. Bioinformatics 27(13), i248–i256 (2011)

    Article  Google Scholar 

Download references

Acknowledgements

The authors thank the anonymous referees for their valuable comments and suggestions.

Author information

Authors and Affiliations

Authors

Corresponding authors

Correspondence to Yunlong Liu or Jingui Huang .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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)

Publish with us

Policies and ethics