The Minimum Rooted-Cycle Cover Problem

Abstract

Given an undirected rooted graph, a cycle containing the root vertex is called a rooted cycle. We study the combinatorial duality between vertex-covers of rooted-cycles, which generalize classical vertex-covers, and packing of disjoint rooted cycles, where two rooted cycles are vertex-disjoint if their only common vertex is the root node. We use Menger’s theorem to provide a characterization of all rooted graphs such that the maximum number of vertex-disjoint rooted cycles equals the minimum size of a subset of non-root vertices intersecting all rooted cycles, for all subgraphs.

1 Introduction

Throughout $G=(V,E)$ is a simple undirected graph. The minimum vertex-cover problem amounts to find a vertex-cover (that is, a set $T\subseteq V$ so that every edge of G has at least one vertex in T) minimizing |T|. This is a very well studied NP-hard problem, equivalent to finding a maximum stable set (equivalently, the complement of a vertex-cover, or a clique in the complementary graph) [6]. In this paper, we introduce the minimum rooted-cycle cover problem which contains the vertex-cover problem, and which is, given a root vertex r of G, to remove a minimum size subset of $V\setminus \{r\}$ so that r is contained in no cycle anymore. The minimum vertex-cover problem is the particular case where r is adjacent with all other vertices.

If we are given a set of terminal vertices of G, with at least two vertices, the minimum multi-terminal vertex-cut problem is to remove a minimum number of vertices, so that no path connects two terminal vertices anymore, see [1, 2]. The weighted version of the minimum rooted-cycle cover problem contains the minimum multi-terminal vertex-cut problem which is the particular case where the neighborhood N(r) of r is the set of terminal vertices with infinite weight. In turn, if we replace r by |N(r)| terminal vertices $t_1,\ldots ,t_{k}$ where $N(r)=\{v_1,\ldots ,v_k\}$ and link $t_i$ to $v_i$, then we obtain an instance of the minimum multi-terminal vertex-cut problem the solution of which is a solution for the original instance of the minimum rooted cycle cover problem.

Our main motivation to introduce the minimum rooted cycle cover problem is that it allows us to give short proofs of some min-max theorems, such results being fundamental in combinatorial optimization and linear programming [5]. Jost and Naves gave such results for the minimum multi-terminal vertex-cut problem in an unpublished manuscript [2] (actually we found independently this result).

The paper is organized as follows. In Sect. 2, we recall two classical theorems and give formal definitions. In Sect. 3, we give a characterization of all rooted graphs (G, r) so that the minimum number of non-root vertices intersecting all rooted cycles equals the maximum number of rooted cycles having only the root as common node, for all partial subgraphs. In Sect. 4, we revisit a result by Jost and Naves [2] in terms of rooted cycles. (We found the equivalent result independently.) This is a structural characterization in terms of excluded minors of pseudo-bipartite rooted graphs, that is, rooted graphs satisfying the min-max equality for all rooted minors.

2 Background

Let us recall two fundamental min-max theorems.

Given a graph, a matching is a subset of pairwise vertex-disjoint edges.

Kőnig’s Theorem [3]. Let G be a bipartite graph. The minimum size of a vertex-cover of G is equal to the maximum size of a matching of G.

Take a graph G and fix distinct vertices s, t. A st-path of G is subset $P\subseteq V$ of vertices of G which can be ordered into a sequence $s=v_0,v_1,\ldots ,v_k=t$ where $v_iv_{i+1}$ is an edge of G. The vertices $v_0,v_k$ are the extremities of P, the other vertices are the internal vertices of P. Two st-paths P, Q are internally vertex-disjoint if $P\cap Q=\{s,t\}$. A subset D of vertices of G is an st-vertex cut if neither s nor t belongs to D, and D intersects every st-path.

Menger’s Theorem [4]. Let G be a graph and let s and t be two nonadjacent vertices of G. The minimum size of a st-vertex cut is equal to the maximum number of internally vertex-disjoint st-paths.

A subset $C\subseteq V$ containing r and so that $C\setminus \{r\}$ is a path the extremities of which are adjacent with r is called a rooted cycle of (G, r). Two rooted cycles are internally vertex-disjoint if r is their only common vertex. A rooted-cycle cover of (G, r) is a subset of $T\subseteq V\setminus \{r\}$ of non-root vertices so that $C\cap T\ne \emptyset$ for all rooted cycle C. A rooted-cycle cover is minimum if |T| is minimum. A rooted-cycle packing of (G, r) is a collection $C_1,\ldots ,C_k$ of rooted cycles so that $C_i\cap C_j= \{r\}$ for all distinct $i,j=1,\ldots ,k$. A rooted-cycle packing is maximum if k is maximum. Clearly the minimum of the cover is at least the maximum of the packing.

We call $G'$ a subgraph of G if it is obtained from G by deleting vertices, and $G'$ is a partial subgraph of G if it is obtained by deleting vertices and/or edges.

3 Packing and Covering Rooted Cycles

The following consequence of Menger’s theorem is useful to characterize rooted graphs for which the minimum equals the maximum.

Corollary 1

Let G be a graph with a vertex t and a subset S, of at least k vertices, not containing t. If there are k internally vertex-disjoint vt-paths for every $v\in S$, then there are k distinct vertices $s_1,\ldots ,s_k$ of S, with $s_it$-paths $P_i$ for each $i=1,\ldots ,k$, so that t is the only vertex belonging both to distinct $P_i,P_j$.

Proof

Add a new vertex s to G and link it to every vertex in S. We only need to prove that there are k internally vertex-disjoint st-paths. If it is not the case, then, by Menger’s theorem, there is a st-vertex cut D of size $|D|<k$. Let $v\in S\setminus D$. Clearly v is not adjacent with t. Thus D is a vt-vertex cut which is impossible since (again by Menger’s theorem) there are k internally vertex-disjoint vt-paths.    $\square$

Let $K_4$ be the complete graph on four vertices and r one of its vertices. The rooted graph $(\hat{G},r)$ is a subdivision of $(K_4,r)$ if it is obtained from $(K_4,r)$ by inserting vertices in edges. Note that in any such subdivision, the vertex r has degree three. A rooted partial subgraph of (G, r) is a rooted graph $(G',r)$ where $G'$ is a partial subgraph of G.

Theorem 1

The minimum size of a subset of non-root vertices intersecting all rooted cycles is equal to the maximum number of internally vertex-disjoint rooted cycles, for all partial rooted subgraphs of (G, r), if and only if no partial rooted subgraph of (G, r) is a subdivision of $(K_4,r)$.

Proof

$(\Rightarrow )$ It suffices to see that, for any subdivision of $(K_4,r)$, any two rooted cycles must have a non-root vertex in common while any rooted cycle cover needs at least two non-root vertices.

$(\Leftarrow )$ Let (G, r) be a minimum graph, that is, with a minimum number of edges, such that the minimum rooted cycle cover is strictly greater than the maximum packing of rooted cycles. Minimality implies that G has no vertices of degree $<3$. It follows that the graph $G-r$ obtained from G by removing r has a cycle C with at least three distinct vertices $s_1,s_2,s_3$ (since G is a simple graph). Hence, by Corollary 1, it suffices to prove (1) below, since it implies that there are three internally vertex-disjoint $s_ir$-paths which form with C a subdivision of $(K_4,r)$.

$$\begin{aligned} \text {There are three internally vertex-disjoint} \,vr\,\text {-paths for every vertex}\, v\in V\setminus \{r\} \end{aligned}$$

(1)

Assume that (1) is not true, and let v be a counter-example. Remark that, for any vertex s nonadjacent with r, the minimality of G implies that no sr-vertex cut is a clique, in particular, it has at least two vertices (indeed otherwise v belongs to no inclusion wise minimal rooted cycle). Furthermore, no vertex-cut has only one vertex. We build a graph $\hat{G}$ from G as follows:

• (a): If v is nonadjacent with r, then (by Menger’s theorem) there is a vr-vertex cut with size 2, say $D=\{u,w\}$. Let $V'\ni v$ be the subset of vertices in the component, containing v, of the graph obtained from G by removing D. We let $\hat{G}$ be the graph obtained by removing $V'$ and adding the edge $e=uw$.

• (b): If v is adjacent with r, then, in the graph $G-vr$ (obtained from G by removing the edge vr), there is a vr-vertex cut $D=\{u\}$. Let $V'\ni v$ be the subset of vertices in the component, containing v, of the graph obtained by removing u from $G-vr$. We let $\hat{G}$ be the graph obtained by removing $V'$ and adding the edge $e=ur$.

Observe now, that if there are $\nu$ vertex-disjoint rooted cycles in $\hat{G}$, then there are also $\nu$ vertex-disjoint rooted cycles in G. Indeed, if some rooted cycle of $\hat{G}$ contains the additional edge e, then e can be replaced by a path of G with all internal vertices in $V'$. Moreover, if there are $\tau$ vertices intersecting every rooted cycles of $\hat{G}$, then these $\tau$ vertices intersect also every rooted cycles of G. We have a contradiction, since the minimality of G implies $\tau =\nu$.    $\square$

Finally, since series-parallel graphs are those with no minor $K_4$, one has:

Corollary 2

Given a graph G, the minimum rooted cycle cover equals the maximum rooted cycle packing, for all partial subgraphs and every choice of a root r, if and only if G is series-parallel.

4 Pseudo-bipartite Rooted Graphs

The closed neighborhood of r is the set of $N[r]=N(r)\cup \{r\}$.

A rooted graph is pseudo-bipartite if it is obtained from a bipartite graph $(V_1,V_2;E)$ by creating a root vertex linked to every vertex of $V_1\cup V_2$, and then, by replacing some original edges $uv\in E$ by any graph $G_{uv}$, on new vertices, with edges between some new vertices and u (or v), more precisely:

Definition 1

A rooted graph (G, r) is pseudo-bipartite if

• (a) The subgraph G[N(r)] induced by the neighbors of r is a bipartite graph $G_B$;

• (b) There is a bipartition of $G_B$, so that every component of the graph $G\setminus N[r]$, that we obtain if we remove the closed neighborhood of r, has at most one neighbour in each side of $G_B.$

Contracting a vertex v is to delete v, and to add edges so that its neighborhood N(v) forms a clique. A rooted minor of (G, r) is a rooted graph $(\hat{G},r)$ obtained from (G, r) by deleting vertices different from r, or by contracting vertices $v\in V\setminus N[r]$ outside the closed neighborhood of the root.

An odd wheel is a graph composed of an odd cycle together with one vertex, called the center of the wheel, to which all the vertices of the odd cycle are linked. A rooted odd wheel is a rooted graph (G, r) so that G is an odd wheel the center of which is the root r.

Theorem 2

[2]. A rooted graph (G, r) is pseudo-bipartite if and only if it has no rooted minor which is a rooted odd wheel.

Proof

Necessity holds since $G[N(r)]=G_B$ has no odd cycle and since every edge which appears in G[N(r)] by contracting some vertex outside N[r] necessarily links two vertices in different side of the bipartition of $G_B$.

To see sufficiency, suppose that no rooted-minor of (G, r) is a rooted odd-wheel. Condition (a) of Definition 1 is indeed satisfied since deleting all vertices but those of an odd cycle in the neighborhood of r leaves a rooted odd wheel. Assume that condition (b) is not satisfied. Let $U_1,\ldots ,U_p$ be the components of the graph obtained by removing r and all its neighbors. If $U_i$ has at least three neighbors x, y, z (in $G_B$), then contracting all the vertices in $U_i$ and deleting all vertices but x, y, z (and r) leaves $(K_4,r)$ which is a rooted odd wheel. It follows that $U_i$ has at most two neighbors. Chose a bipartition $V_1,V_2$ of $G_B$ so that the number of components $U_1,\ldots ,U_p$ having two neighbors in the same side is minimum. There is a component $U_i$ with two neighbors x, y in the same side, say $x,y\in V_1$ (otherwise the proof is done). Let $V_1^x$ (resp. $V_2^x$) be the set of vertices in $V_1$ (resp. in $V_2$) reachable, from x, by a path of $G_B$. Similarly, define $V_1^y$ and $V_2^y$. If either $V_1^x\cap V_1^y$ or $V_2^x\cap V_2^y$ is nonempty, then there exists a xy-path P in $G_B$. Yet contracting $U_i$ and deleting all vertices but those of P (and r) leaves a rooted odd wheel. It follows that $V_1^x,V_2^x,V_1^y,V_2^y$ are pairwise disjoint, and hence $(V_1\setminus V_1^x)\cup V_2^x, (V_2\setminus V_2^x)\cup V_1^x$ is a possible bipartition for $G_B$. The way the bipartition $V_1,V_2$ was chosen implies that there is another component, say $U_j$, with either one neighbor in $V_1^x$ and the other in $V_2^y$, or one neighbor in $V_1^y$ and the other in $V_2^x$. Anyway, contracting both $U_i$ and $U_j$ creates an odd cycle in the neighborhood of r. Now deleting the vertices outside this odd cycle leaves a rooted odd wheel; contradiction.    $\square$

Given a pseudo-bipartite rooted graph (G, r) with bipartite graph $G_B=G[N(v)]$, we let $\hat{G}$ be the graph obtained by removing r from (G, r), and then by creating two new vertices s and t, so that s is linked to every vertex of one side of $G_B$, and t is linked similarly to every vertex in the other side of $G_B$. Observe that:

$$\begin{aligned} \text {A subset}\,P\subseteq V\,\text {is a}\,st\text {-path of}\,\hat{G}\,\text {if and only if}\,P\setminus \{s,t\}\cup \{r\}\,\text {is a rooted cycle of}\,(G,r). \end{aligned}$$

(2)

Since (2) holds, Menger’s theorem implies that, for pseudo-bipartite rooted graphs, the minimum rooted cycle cover equals the maximum rooted cycle packing.

Observe, moreover, that for any rooted odd wheel with an odd cycle having $2k+1$ vertices, the minimum size of a cover is $k+1$ while the maximum packing is k. It follows that Theorem 2 implies Corollary 3 below, which is also a consequence of a result in [2] (namely Lemma 9).

Corollary 3

[2]. The minimum size of a subset of non-root vertices intersecting all rooted cycles is equal to the maximum number of internally vertex-disjoint rooted cycles, for all rooted minor of (G, r), if and only if no rooted minor of (G, r) is a rooted odd wheel.    $\square$

Observe that, if every vertex is linked to r, then (G, r) is pseudo-bipartite if and only if the graph induced by $V\setminus \{r\}$ is bipartite. Hence by Theorem 2:

Remark 1

Corollary 3 contains Kőnig’s theorem as particular case.

Note also that recognizing if (G, r) is pseudo-bipartite or not, it suffices to contract all vertices outside the closed neighborhood of r, to remove r, and to check if the remaining graph is bipartite or not. So one has:

Remark 2

In can be checked in polynomial time if (G, r) is pseudo-bipartite or not.