# Minimum d-Transversals of Maximum-Weight Stable Sets in Trees

Christophe Picouleau, Cédric Bentz, Marie-Christine Costa, Dominique de Werra, Bernard Ries

► To cite this version:

Christophe Picouleau, Cédric Bentz, Marie-Christine Costa, Dominique de Werra, Bernard Ries. Minimum d-Transversals of Maximum-Weight Stable Sets in Trees. European conference on combinatorics, graph theory and applications. EuroComb'11, Aug 2011, Budapest, Hungary. pp.129-134, 10.1016/j.endm.2011.09.022. hal-01125892

HAL Id: hal-01125892

https://hal.science/hal-01125892

Submitted on 28 Nov 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Minimum *d*-Transversals of Maximum-Weight Stable Sets in Trees

Cédric Bentz<sup>1,2</sup>

LRI, Université Paris-Sud & CNRS, Orsay, France

Marie-Christine Costa<sup>3</sup>

ENSTA UMA-CEDRIC, Paris, France

Dominique de Werra<sup>4</sup>

Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

Christophe Picouleau<sup>1,5</sup>

CNAM, Laboratoire CEDRIC, Paris, France

Bernard Ries<sup>6</sup>

LAMSADE - Université Paris-Dauphine, Paris, France

## Abstract

Given an integer $d$ and a weighted tree $T$, we show how to find in polynomial time a minimum $d$-transversal of all maximum-weight stable sets in $T$, i.e., a set of vertices of minimum size having at least $d$ vertices in common with every maximum-weight stable set. Our proof relies on new structural results for maximum-weight stable sets on trees.

**Keywords:** Transversals, Maximum-weight stable sets, Trees.
# 1 Definitions and previous results

Given an undirected simple loopless graph $G = (V, E)$ and a positive weight function $w$ on its vertices, a **stable set** $S$ of $G$ is a set of pairwise non adjacent vertices. The weight of a stable set is the sum of the weights of its vertices. A stable set $S$ is a **maximum-weight stable set** if no other stable set has a strictly larger weight. We will denote by $\alpha_w(G)$ the **weighted stability number**, i.e., the weight of a maximum-weight stable set in $G$.

A subset $T' \subseteq V$ is a **d-transversal** of $G$ if for every maximum-weight stable set $S$ we have $|S \cap T'| \ge d$. Thus, a $d$-transversal is a subset of vertices which intersects every maximum-weight stable set in at least $d$ vertices.

We denote by $\tau_d(G)$ the minimum cardinality of a $d$-transversal in $G$. A $d$-transversal will be *minimum* if it is of minimum size.

Some properties and results concerning $d$-transversals of maximum matchings (i.e., subsets of edges intersecting every maximum matching in at least $d$ edges) were given in [2,5] where the following is proved (here $\nu(G)$ denotes the size of a maximum matching):

**Theorem 1.1** For every fixed $d \in \{1, 2, \dots, \nu(G)\}$, finding a minimum $d$-transversal of maximum matchings is $\mathcal{NP}$-hard even if $G$ is bipartite.

This result implies that finding minimum $d$-transversals of maximum stable sets (i.e., stable sets with maximum cardinality) is $\mathcal{NP}$-hard (matchings in $G$ are stable sets in the line-graph $L(G)$). In [1] it is shown how to find such minimum $d$-transversals of maximum-cardinality stable sets in polynomial time when $G$ is bipartite. $\mathcal{NP}$-hard results concerning maximum-weight stable sets in bipartite graphs can be found in [3,4].

Here we are interested in *maximum-weight* stable sets: we show how to find minimum *d*-transversals of maximum-weight stable sets in polynomial

<footnote n="1">¹ The research work of these two authors was supported by the French ANR project *DOPAGE* (ANR-09-JCJC-0068).</footnote>

<footnote n="2">² Email: bentz@lri.fr</footnote>

<footnote n="3">³ Email: marie-christine.costa@ensta.fr</footnote>

<footnote n="4">⁴ Email: dominique.dewerra@epfl.ch</footnote>

<footnote n="5">⁵ Email: chp@cnam.fr</footnote>

<footnote n="6">⁶ Email: bernard.ries@dauphine.fr</footnote>
time in trees. Our proof mainly relies on the definition of a partition of the given tree having useful properties, and on new structural results concerning maximum-weight stable sets in trees, which allow us to reduce the minimum *d*-transversal problem in weighted trees to a matching problem.

## 2 Structural results concerning maximum-weight stable sets in trees

Let $T = (V, E)$ be a weighted tree. We first give some preliminary properties.

Given an arbitrary vertex $r$ of $T$, we denote by $T_r$ the tree rooted at vertex $r$ and by $T^r(v)$ the subtree of $T^r$ rooted at vertex $v$, for every $v \in T$. We also define the following function: for every vertex $v \in T$, $p^r(v, \delta)$ is the weight of a maximum-weight stable set in $T^r$ that contains $v$ if $\delta = 1$, and that does not contain $v$ if $\delta = 0$. Note that we have $\alpha_w(T^r(v)) = \max\{p^r(v, 0), p^r(v, 1)\}$, and that all values $p^r(v, \delta)$ can be easily computed by dynamic programming formulas, starting from the leaves of $T^r$. This also allows us to find **forced**, **excluded**, and **free** vertices.

**Definition 2.1** A vertex of a tree $T$ is:

* **forced** if it belongs to all the maximum-weight stable sets of $T$,

* **excluded** if it does not belong to any maximum-weight stable set of $T$,

* **free** otherwise.

The sets of **forced**, **excluded** and **free** vertices can be easily computed using the following property:

**Proposition 2.2** A vertex $v$ of a tree $T$ is:

* **forced** iff $p^v(v, 1) > p^v(v, 0)$,

* **excluded** iff $p^v(v, 1) < p^v(v, 0)$,

* **free** iff $p^v(v, 1) = p^v(v, 0)$.

Note that **excluded** vertices belong neither to maximum-weight stable sets nor to minimal inclusionwise transversals: hence, they can be removed from the tree. Moreover, when looking for a minimum *d*-transversal $T'$, we include $\min\{d, f\}$ forced vertices in $T'$ (and possibly other vertices if needed), where $f$ is the total number of forced vertices. So, when $d \le f$, we can trivially solve the problem by using only forced vertices. As a consequence, we can assume without loss of generality that $d > f$, and that we look for a *d'*-transversal in a forest having only free vertices, where $d' = d - f$. Since vertices of weight 0
do not belong to minimal inclusionwise transversals, they can be removed as
well. Finally, any maximum-weight stable set in a forest is the disjoint union
of maximum-weight stable sets in each one of the trees of the forest, so it is
sufficient to focus on maximum-weight stable sets in trees having only free
vertices and positive weights. We define the following partition of the tree,
that will allow us to establish the structure of such stable sets.

**Definition 2.3** Let $v_{i_1}, \dots, v_{i_q}$ be the vertices in $T^r$ such that $p^r(v_{i_j}, 0) = p^r(v_{i_j}, 1)$ for each $j \in \{1, \dots, q\}$. We define the following partition $\mathcal{V}^r = \{V_1^r, \dots, V_q^r\}$ of $V$: for every $j \in \{1, \dots, q\}$, $V_j^r = V(T^r(v_{i_j})) \cup \bigcup_{v_{i_k} \in T^r(v_{i_j})} V(T^r(v_{i_k}))$ for $k \in \{1, \dots, q\}$ and $k \neq j$, where $V(T^r(v_{i_l}))$ is the set of vertices of $T^r(v_{i_l})$ for $l \in \{j, k\}$.

We give some useful results.

**Proposition 2.4** For any vertex $v \in T^r$, if $p^r(v, 0) > p^r(v, 1)$, then $v$ is excluded.

This property implies that, in a tree containing only free vertices, we have
$p^r(v, 0) \leq p^r(v, 1)$ for any vertex $v$ and any root $r$.

**Lemma 2.5** $|V_j^r| \ge 2$ for every $j \in \{1, \dots, q\}$.

**Lemma 2.6** $\forall r, r' \in T$ we have $\mathcal{V}^r = \mathcal{V}^{r'}$.

In other words, the partition of $V$ is unique, and does not depend on the
choice of the root. From now on we will denote by $\mathcal{V} = \{V_1, \dots, V_q\}$ this
unique partition.

**Remark 2.7** Lemma 2.6 and the uniqueness of the partition $\mathcal{V}$ imply that, given any two adjacent vertices $u$ and $v$ of $V$ with $u \in V_i$ and $v \in V_j$ for some $i$ and $j \neq i$, we have $p^v(u, 0) = p^v(u, 1)$ (since $\mathcal{V}^v = \mathcal{V}$) and $p^u(v, 0) = p^u(v, 1)$ (since $\mathcal{V}^u = \mathcal{V}$).

Let $(B, W)$ denote the bipartition of $V$.

**Lemma 2.8** Let $T$ be a weighted tree containing only free vertices, and let $u, v$ be two adjacent vertices in $T$ with $u \in V_i$ and $v \in V_j$ for some $i$ and $j \neq i$. Then, a stable set $S$ of $T$ has maximum weight in $T$ if and only if $w(S \cap T_1) = \alpha_w(T_1)$ and $w(S \cap T_2) = \alpha_w(T_2)$, where $T_1 = T^v(u)$ and $T_2 = T^u(v)$.

**Proof (Sketch.)** Actually, it is sufficient to show that $\alpha_w(T_1) + \alpha_w(T_2) = \alpha_w(T)$. The inequality $\alpha_w(T) \le \alpha_w(T_1) + \alpha_w(T_2)$ simply comes from the fact
that any stable set in $T$ is the union of a stable set in $T_1$ and of a stable set in $T_2$. The inequality $\alpha_w(T) \ge \alpha_w(T_1) + \alpha_w(T_2)$ comes from the fact that $p^v(u, 0) = p^v(u, 1)$ implies that there exist two maximum-weight stable sets $S_1$ and $S_2$ of $T_1$ and $T_2$ respectively that are compatible (i.e., $S_1 \cup S_2$ is a stable set for $T$). $\square$

**Lemma 2.9** Let $T$ be a weighted tree containing only free vertices. Then, a vertex set $S$ is a maximum-weight stable set if and only if $S$ is stable and for any $j \in \{1, \dots, q\}$ either $S \cap V_j = B \cap V_j$ or $S \cap V_j = W \cap V_j$.

**Proof (Sketch.)** To show that any maximum-weight stable set $S$ satisfies $S \cap V_j = B \cap V_j$ or $S \cap V_j = W \cap V_j$ for each $j \in \{1, \dots, q\}$, we only need to use the uniqueness of the partition $\mathcal{V}$ and the fact that for every $j \in \{1, \dots, q\}$ and $v \in V_j$, we have by definition $p^v(u, 0) < p^v(u, 1)$ for every $u \in V_j \setminus \{v\}$.

We use induction to show that any stable set $S$ satisfying $S \cap V_j = B \cap V_j$ or $S \cap V_j = W \cap V_j$ for each $j \in \{1, \dots, q\}$ has maximum weight. When $q=1$, this trivially follows from the above argument. Assume now that $q > 1$. We consider two vertices $u \in V_i$ and $v \in V_j$ for $i \ne j$, and apply induction on $T^v(u)$ and $T^u(v)$ (this is possible since a straightforward consequence of Lemma 2.8 is that any vertex in $T^v(u)$ or $T^u(v)$ is free): finally, we conclude the proof by using Lemma 2.8. $\square$

### 3 Finding minimal $d$-transversals in weighted trees

From the partition $\mathcal{V}$, we define the following auxiliary digraph $T^* = (V^*, A^*)$: $V^* = \{V_1, \dots, V_q\}$ and $A^* = \{(V_i, V_j) | \exists v u \in E, v \in V_i \cap B, u \in V_j \cap W\}$. (Notice that $T^*$ is a directed tree.) From $T^*$ we define the following partial order $(V, \preceq)$: for $u \in W$ and $v \in B$, $u \preceq v$ if and only if either $u, v \in V_j$ for some $j \in \{1, \dots, q\}$ or $u \in V_i$, $v \in V_j$, $i \ne j$, and there exists a (directed) path from $V_i$ to $V_j$ in $T^*$. Let $d_{\max}$ be the minimum size of a maximum-weight stable set in $T$. Then, our main result is the following:

**Lemma 3.1** Let $T$ be a weighted tree containing only free vertices. Then for any $0 \le d \le d_{\max}$, a set $T'$ is a minimum $d$-transversal in $T$ iff it consists of $d$ disjoint pairs of vertices $(u, v)$ such that $u \in W, v \in B$ and $u \preceq v$.

**Proof (Sketch.)** First we show that a set $T'$ consisting of $d$ disjoint pairs of vertices $(u, v)$ with $u \in W, v \in B$ and $u \preceq v$ is a $d$-transversal. Each of these pairs $(u, v)$ with $u \in V_i$ and $v \in V_j$ has at least one vertex in common with any maximum-weight stable set $S$, because of Lemma 2.9: either $S \cap V_i = W \cap V_i$
and so $u \in S$, or $S \cap V_i = B \cap V_i$ and then we have $S \cap V_j = B \cap V_j$ (because of the definition of $T^*$), and so $v \in S$.

Then we have to show that at least 2d vertices are needed in any d-transversal $T'$ (which is obvious, since from Lemma 2.9 we must have $|B \cap T'| \ge d$ and $|W \cap T'| \ge d$), and that there always exist $d_{\max}$ such pairs. We consider a maximum matching $M$ in the bipartite graph $\tilde{G} = (W, B, \tilde{E})$ with edge set $\tilde{E} = \{uv : u \in W, v \in B, u \preceq v\}$, and show how to construct, using the structure of $M$, a maximum-weight stable set with the same size. Finally, we assume by contradiction that it exists a d-transversal $T'$ not containing $d$ such pairs, and show how to construct, using the structure of $T'$, a maximum-weight stable set having at most $d-1$ vertices in common with $T'$. $\square$

We observe that, from Lemma 3.1, there is a bijection between matchings of size $d$ in $\tilde{G}$ and $d$-transversals in $T$. This yields:

**Theorem 3.2** Let $T = (V, E)$ be a weighted tree. Then, finding a minimum $d$-transversal in $T$ can be done in polynomial time, by solving a maximum matching problem in $\tilde{G}$.

# 4 Open problems

It would be interesting to study this problem in chordal graphs, or in other classes of bipartite graphs: for instance, in [2], minimum $d$-transversals of maximum matchings were studied in grids.

# References

[1] Costa, M.-C., D. de Werra and C. Picouleau, *Minimum d-blockers and d-transversals in graphs*, to appear in J. of Combinatorial Optimization (2011).

[2] Ries, B., C. Bentz, C. Picouleau, D. de Werra, M.-C. Costa and R. Zenklusen, *Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid*, Discrete Mathematics **310** (2010), 132–146.

[3] Toubaline, S., “Détermination des éléments les plus vitaux pour des problèmes de graphes”, Ph.D. thesis, Univ. Paris Dauphine, France, 2010.

[4] Zenklusen, R., *Matching Interdiction*, Discrete Applied Mathematics **158** (2010), 1441–1455.

[5] Zenklusen, R., B. Ries, C. Picouleau, D. de Werra, M.-C. Costa and C. Bentz, *Blockers and transversals*, Discrete Mathematics **309** (2009), 4306–4314.