CISPA
Browse
2_conn_Appeared_version.pdf (744.81 kB)

The complexity of 2-vertex-connected orientation in mixed graphs

Download (744.81 kB)
journal contribution
posted on 2024-03-26, 08:54 authored by Florian Hörsch, Zoltán Szigeti

We consider two possible extensions of a theorem of Thomassen characterizing the graphs admitting a 2-vertex-connected orientation. First, we show that the problem of deciding whether a mixed graph has a 2-vertex-connected orientation is NP-hard. This answers a question of Bang-Jensen, Huang and Zhu. For the second part, we call a directed graph D = (V, A) 2T-connected for some T c V  if 

 is 2-arc-connected and D - v is strongly connected for all v E T. We deduce a characterization of the graphs admitting a 2T-connected orientation from the theorem of Thomassen.

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

Journal

Discrete Optimization

Volume

48

Page Range

100774-100774

Publisher

Elsevier

Open Access Type

  • Not Open Access

Sub Type

  • Article

BibTeX

@article{Hörsch:Szigeti:2023, title = "The complexity of 2-vertex-connected orientation in mixed graphs", author = "Hörsch, Florian" AND "Szigeti, Zoltán", year = 2023, month = 5, journal = "Discrete Optimization", pages = "100774--100774", publisher = "Elsevier", issn = "1572-5286", doi = "10.1016/j.disopt.2023.100774" }