Cycle-connected mixed graphs and related problems

In this paper, motivated by applications of vertex connectivity of digraphs or graphs, we consider the cycle-connected mixed graph (CCMG, for short) problem, which is in essence different from the connected mixed graph (CMG, for short) problem, and it is modelled as follows. Given a mixed graph $$G=(V,A\cup E)$$ G = ( V , A ∪ E ) , for each pair $$ \{u, v\}$$ { u , v } of two distinct vertices in G, we are asked to determine whether there exists a mixed cycle C in G to contain such two vertices u and v, where C passes through its arc (x, y) along the direction only from x to y and its edge xy along one direction either from x to y or from y to x. Particularly, when the CCMG problem is specialized to either digraphs or graphs, we refer to the related version of the CCMG problem as either the cycle-connected digraph (CCD, for short) problem or the cycle-connected graph (CCG, for short) problem, respectively, where such a graph in the CCG problem is called as a cycle-connected graph. Similarly, we consider the weakly cycle-connected (in other words, circuit-connected) mixed graph (WCCMG, for short) problem, only substituting a mixed circuit for a mixed cycle in the CCMG problem. Moreover, given a graph $$G=(V,E)$$ G = ( V , E ) , we define the cycle-connectivity $$\kappa _c(G)$$ κ c ( G ) of G to be the smallest number of vertices (in G) whose deletion causes the reduced subgraph either not to be a cycle-connected graph or to become an isolated vertex; Furthermore, for each pair $$\{s, t\}$$ { s , t } of two distinct vertices in G, we denote by $$\kappa _{sc}(s,t)$$ κ sc ( s , t ) the maximum number of internally vertex-disjoint cycles in G to only contain such two vertices s and t in common, then we define the strong cycle-connectivity $$\kappa _{sc}(G)$$ κ sc ( G ) of G to be the smallest of these numbers $$\kappa _{sc}(s,t)$$ κ sc ( s , t ) among all pairs $$\{s, t\}$$ { s , t } of distinct vertices in G. We obtain the following three results. (1) Using a transformation from the directed 2-linkage problem, which is NP-complete, to the CCD problem, we prove that the CCD problem is NP-complete, implying that the CCMG problem still remains NP-complete, and however, we design a combinatorial algorithm in time $$O(n^2m)$$ O ( n 2 m ) to solve the CCG problem, where n is the number of vertices and m is the number of edges of a graph $$G=(V,E)$$ G = ( V , E ) ; (2) We provide a combinatorial algorithm in time O(m) to solve the WCCMG problem, where m is the number of edges of a mixed graph $$G=(V,A\cup E)$$ G = ( V , A ∪ E ) ; (3) Given a graph $$G=(V,E)$$ G = ( V , E ) , we present twin combinatorial algorithms to compute cycle-connectivity $$\kappa _c(G)$$ κ c ( G ) and strong cycle-connectivity $$\kappa _{sc}(G)$$ κ sc ( G ) , respectively.