20.2. Feedback Vertex Set

The high-level approach we take to find a feedback vertex set of size at most \(k\) is identical to the one we took to find a vertex cover in the previous section:

PROCEDURE \(\boldsymbol{\textbf{FVS}(G, k)}\):

INPUT:

  • An undirected \(G = (V,E)\)
  • A non-negative integer \(k\)

OUTPUT:

  • A feedback vertex set of \(G\) of size at most \(k\), if there is such a set; None otherwise

Let \(\langle v_1, \ldots, v_n \rangle\) be the sequence of vertices in \(G\), in an arbitrary order.
\(F_1 = \emptyset\)
FOR \(i = 1\) TO \(n-1\) DO
    Let \(V_i = \{ v_1, \ldots, v_i \}\) and \(G_i = G[V_i]\)
    \(F_{i+1}' = F_i \cup \{v_{i+1}\}\)
    \(F_{i+1} = \boldsymbol{\textbf{CompressFVS}(G_{i+1}, F_{i+1}', k)}\)
    IF \(F_{i+1} = \textbf{None}\) THEN
        RETURN None
RETURN \(F_n\)

There are two important difference to the solution to the vertex cover problem. First, we do not insist on finding a minimum feedback vertex set: We will be content with finding a feedback vertex set of size at most \(k\), if such a set exists. Second, the compression procedure implemented by CompressFVS is significantly more complicated than its counterpart CompressVertexCover.

Given a feedback vertex set \(F_i\) of \(G_i\) of size at most \(k\), the set \(F_{i+1}' = F_i \cup \{v_{i+1}\}\) is clearly a feedback vertex set of \(G_{i+1}\) and has size at most \(k+1\). Procedure CompressFVS tries to replace \(F_{i+1}'\) with a feedback vertex set \(F_{i+1}\) of \(G_{i+1}\) of size at most \(k\). If \(|F_{i+1}'| \le k\), we can set \(F_{i+1} = F_{i+1}'\). If \(|F_{i+1}'| = k+1\), we use a strategy similar to the one used by CompressVertexCover: For every subset \(I \subseteq F_{i+1}'\), we try to find a feedback vertex set \(F\) of \(G_{i+1}\) such that \(|F| = k\) and \(F \cap F_{i+1}' = I\). If this succeeds, we return \(F\). Otherwise, we proceed to the next possible choice of \(I\) or return None if this was the last possible choice of \(I\):

PROCEDURE \(\boldsymbol{\textbf{CompressFVS}(G_{i+1}, F_{i+1}', k)}\):

INPUT:

  • A subgraph \(G_{i+1} \subseteq G\)
  • A feedback vertex set \(F_{i+1}'\) of \(G_{i+1}\) of size at most \(k + 1\)
  • A parameter \(k\)

OUTPUT:

  • A feedback vertex set of \(G_{i+1}\) of size at most \(k\); None if no such feedback vertex set exists

IF \(|F_{i+1}'| \le k\) THEN
    RETURN \(F_{i+1}'\)
FOR ALL \(\emptyset \subseteq I \subseteq F_{i+1}'\) DO
    \(D = F_{i+1}' \setminus I\)
    \(F' = \boldsymbol{\textbf{CompressD}(G_{i+1} - I, D, k - |I|)}\)
    IF \(F' \ne \textbf{None}\) THEN
        RETURN \(F' \cup I\)
RETURN NONE

Note that any feedback vertex set \(F\) of \(G_{i+1}\) such that \(F \cap F_{i+1}' = I\) can be written as \(F = F' \cup I\), where \(F'\) is a feedback vertex set of the graph \(G' = G_{i+1} - I\) and \(F' \cap D = \emptyset\). \(F\) has size \(k\) if and only if \(F'\) has size \(k - |I|\). The search for the set \(F'\) is implemented by the procedure CompressD below.

What makes the feedback vertex set problem more interesting is that finding a feedback vertex set \(F'\) of \(G'\) with \(F' \cap D = \emptyset\) is not merely a matter of taking the neighbourhood \(N(D)\) of \(D\) as for the vertex cover problem; \(F'\) may be any subset of \(V(G') \setminus D\) of size \(k - |I|\). Checking whether any such subset of \(V(G') \setminus D\) is a feedback vertex set of \(G'\) would be prohibitively expensive since \(V(G') \setminus D\) can have size linear in \(n\) and there are \(\binom{|V(G') \setminus D|}{k - |I|}\) candidate sets to be inspected.

Procedure CompressD takes a more sophisticated approach to limit the cost of searching for \(F'\). First, it tests whether the induced subgraph \(G'[D] \subseteq G'\) contains a cycle; if so, no vertex set \(F'\) with \(F' \cap D = \emptyset\) can be a feedback vertex set of \(G'\), so we can immediately return None. Otherwise, procedure CompressD constructs a reduced version \(G''\) of \(G'\) and a subset of vertices \(I'' \subseteq V(G') \setminus D\). This graph \(G''\) has the property that it has size at most \(12|D|\) or there is no feedback vertex set \(F'\) of \(G'\) of size \(k - |I|\) and such that \(F' \cap D = \emptyset\). The other important property is that \(G'\) has a feedback vertex set \(F'\) of size \(k - |I|\) and such that \(F' \cap D = \emptyset\) if and only if \(G''\) has a feedback vertex set \(F''\) of size \(k - |I \cup I''|\) and such that \(F'' \cap D = \emptyset\). If \(G''\) has such a feedback vertex set \(F''\), then \(F'' \cup I''\) is a feedback vertex set of \(G'\), of size \(k - |I \cup I''| + |I''| = k - |I|\).

By the above property, if \(|G''| > 12|D|\), we can immediately report that \(G'\) has no feedback vertex set \(F'\) of size \(k - |I|\) and such that \(F' \cap D = \emptyset\). Similarly, if \(|I''| > k' = k - |I|\), then \(k - |I \cup I''|\) is negative, so \(G''\) has no feedback vertex set of size \(k' = k - |I \cup I''|\), which implies that \(G'\) has no feedback vertex set \(F'\) of size \(k - |I|\) and such that \(F' \cap D = \emptyset\). If \(|G''| \le 12|D|\) and \(|I''| \le k'\), then since \(|D| \le k + 1\), it takes \(O^*\Bigl(\binom{12|D|}{k - |I \cup I''|}\Bigr) = O^*\Bigl(\binom{12(k+1)}{k+1}\Bigr)\) time to check for every subset of \(k - |I \cup I''|\) vertices of \(G''\) whether it is disjoint from \(D\) and whether it is a feedback vertex set of \(G''\). If we find such a set, it is the desired feedback vertex set \(F''\) and we return the set \(F' = F'' \cup I''\).

PROCEDURE \(\boldsymbol{\textbf{CompressD}(G', D, k')}\):

INPUT:

  • The graph \(G' = G_{i+1}\)
  • A feedback vertex set \(D\) of \(G'\) of size at most \(k + 1\)
  • A parameter \(k' = k - |I|\)

OUTPUT:

  • A feedback vertex set \(F'\) of \(G'\) of size at most \(k'\) and such that \(F' \cap D = \emptyset\), if such a set exists; None otherwise

IF \(G'[D]\) contains a cycle THEN
    RETURN None
\((G'', I'') = \boldsymbol{\textbf{ReduceGraphFVS}(G', D)}\)
IF \(|G''| > 12|D|\) or \(|I''| > k'\) THEN
    RETURN None
FOR ALL \(\emptyset \subseteq F'' \subseteq V(G') \setminus D\) with \(|F''| = k' - |I''|\) DO
    IF \(G'' - F''\) is acyclic THEN
        RETURN \(F'' \cup I''\)
RETURN None

It remains to discuss the reduction procedure ReduceGraphFVS. This procedure sets \(G'' = G'\) and \(I'' = \emptyset\) and then applies three reduction rules until none of them is applicable anymore:

FVS-1: Remove vertices of degree less than \(2\) from \(G''\).

FVS-2: If \(G''\) has a vertex \(v\) with exactly two neighbours \(u\) and \(w\) such that \(u \notin D\), then remove \(v\) and its incident edges from \(G''\) and add the edge \((u, w)\). If the edge \((u, w)\) already exists in \(G''\), then keep both copies.

FVS-3: If \(G''\) contains two parallel edges \((u, v)\), then we will prove below that w.l.o.g., \(u \notin D\) and \(v \in D\). In this case, remove \(u\) and its incident edges from \(G''\) and add \(u\) to \(I''\).

Once none of these three rules is applicable, we call \(G''\) fully reduced.

Initially, \(G'' = G'\) and \(I'' = \emptyset\). Thus, \(G''\) and \(I''\) have the following properties:

  1. \(G'\) has a feedback vertex set \(F'\) of size \(k'\) and such that \(F' \cap D = \emptyset\) if and only if \(G''\) has a feedback vertex set \(F''\) of size \(k' - |I''|\) and such that \(F'' \cap D = \emptyset\).
  2. For every feedback vertex set \(F''\) of \(G''\) of size \(k' - |I''|\) and such that \(F'' \cap D = \emptyset\), the set \(F' = F'' \cup D''\) is a feedback vertex set of \(G'\) of size \(k'\) and such that \(F' \cap D = \emptyset\).
  3. \(V(G'') \cap D\) is a feedback vertex set of \(G''\).

Next we prove that each of the three rules above preserves these two properties and that the final fully reduced graph \(G''\) has size less than \(12|D|\) or there is no feedback vertex set \(F'\) of \(G'\) of size at most \(k'\) and such that \(F' \cap D = \emptyset\).

The following lemma makes this task computationally feasible. Specifically, it states that there is no such feedback vertex set if \(|V(G'') \setminus D| > 12|D|\). If \(|V(G'') \setminus D| \le 12|D|\), then there are only \(\binom{12|D|}{k - |I|} \le \binom{12|D|}{|D|} \le \binom{12(k+1)}{k+1}\) candidate sets of size \(k - |I|\) to inspect. If one of these sets \(F'\) is a feedback vertex set of \(G''\), then \(F' \cup I\) is a feedback vertex set of \(G_{i+1}\) of size \(k\). Otherwise, \(G_{i+1}\) has no feedback vertex set of size \(k\).

Lemma 20.3: Reduction rule FVS-1 preserves properties (1)–(3) above.

Proof: Let \(v\) be a vertex of degree less than \(2\) in \(G''\). Then \(v\) is not part of any cycle in \(G''\). Thus, any minimum feedback vertex set \(F''\) of \(G'' - v\) such that \(F'' \cap D = \emptyset\) is a minimum feedback vertex set of \(G''\) such that \(F'' \cap D = \emptyset\). Thus, both properties (1)) and (2) are preserved. Property (3) is preserved because \(G'' - v\) is a subgraph of \(G''\). ▨

Lemma 20.4: Reduction rule FVS-2 preserves properties (1)–(3) above.

Proof: Let \(v\) be a vertex with exactly two neighbours \(u\) and \(w\) and such that \(u \notin D\). Then observe that every cycle in \(G''\) that contains \(v\) also contains \(u\). Thus, for any feedback vertex set \(F''\) of \(G''\) such that \(v \in F''\) and \(F'' \cap D = \emptyset\), the set \(F''' = F'' \setminus {v} \cup {u}\) is a feedback vertex set of \(G''\) of size \(|F'''| = |F''|\) and such that \(F''' \cap D = \emptyset\).

Next observe that any vertex set \(F'''\) with \(v \notin F'''\) is a feedback vertex set of \(G''\) if and only if it is a feedback vertex set of the graph \(G'''\) obtained by replacing the path \(\langle u, v, w \rangle\) with the edge \((u, w)\). Thus, since \(v \notin D\), replacing \(G''\) with \(G'''\) preserves properties (i)--(iii). ▨

Lemma 20.5: Reduction rule FVS-3 preserves properties (1)–(3) above.

Proof: Let \(u\) and \(v\) be two vertices connected by a pair of parallel edges \((u, v)\). Since \(\langle u, v \rangle\) is a cycle of length two in \(G''\) and \(D\) is a feedback vertex set of \(G''\), at least one of the vertices in this cycle is in \(D\), say \(v \in D\). Since \(G''[D] \subseteq G'[D]\) is acyclic, this implies that \(u \notin D\).

Any feedback vertex set \(F''\) of \(G''\) with \(F'' \cap D = \emptyset\) must contain one vertex in \(\langle u, v \rangle\) but cannot contain \(v\). Thus, \(u \in F''\). ▨

% ----------------------------------------------------------------------------- \begin{lem}\label{lem:fvs-compression} If \(G'\) has a feedback vertex set \(F'\) of size \(k' = k - |I|\) and \(G''\) is a fully reduced version of \(G'\), then \(|G''| < 12|D|\). \end{lem} % -----------------------------------------------------------------------------

\begin{proof} Let \(U = V(G'') \setminus D\). We start by partitioning \(U\) into three subsets: \begin{itemize}[noitemsep] \item \(U_1\) contains all vertices in \(U\) with at least two neighbours in \(D\). \item \(U_2\) contains all vertices not in \(U_1\) with at least three neighbours in \(U\). \item \(U_3 = U \setminus (U_1 \cup U_2)\) contains all remaining vertices in \(U\). \end{itemize} We prove that \(|U_1| < 2|D|\), \(|U_2| < 2|D|\), and \(|U_3| < 8|D|\), which proves the lemma.

% ----------------------------------------------------------------------------- \paragraph{\boldmath\)U_1\).} % -----------------------------------------------------------------------------

Let \(U_1' = U_1 \setminus F'\). Then \(U_1 \subseteq U_1' \cup F'\), that is, \(|U_1| \le |U_1'| + |F'|\). Since \(|F'| < |D|\), it thus suffices to prove that \(|U_1'| \le |D|\). Since \(U_1' \subseteq V(G'') \setminus F'\) and \(F'\) is a feedback vertex set of \(G''\), \(G[U_1']\) is acyclic.

% ----------------------------------------------------------------------------- \paragraph{\boldmath\)U_2\).} % -----------------------------------------------------------------------------

TODO.

% ----------------------------------------------------------------------------- \paragraph{\boldmath\)U_3\).} % -----------------------------------------------------------------------------

TODO. ▨

To try to find such a subset \(F' \subseteq V_{i+1} \setminus (I \cup D)\), we essentially apply kernelization and then inspect every possible subset of the kernel of the desired size. Specifically, we will either determine that \(G'\) has no feedback vertex set of size at most \(k - |I|\) or obtain a reduced graph \(G''\) such that \(|V(G'') \setminus D| \le 11|D|\) and any optimal feedback vertex set of \(G''\) is an optimal feedback vertex set of \(G'\). Thus, we inspect all subsets \(F' \subseteq V(G'')\) such that \(|F'| = k - |I| = |D| - 1\) and \(F' \cap D = \emptyset\). If any such set is a feedback vertex set of \(G''\), we return \(F_{i+1} = F' \cup I\). Otherwise, we move on to the next choice of \(I\).

We will show that the construction of \(G''\) from \(G'\) takes polynomial time. Given~\)G''\), the number of subsets of \(V(G'')\) to consider is at most \(\binom{11|D|}{|D|-1}\) because \(|V(G'') \setminus D| \le 11|D|\) and we only consider subsets \(F'\) of size \(|D|- 1\) such that \(F' \cap D = \emptyset\). For each such subset, it is easy to check in linear time whether it is a feedback vertex set of~\)G''\). Thus, the cost for each choice of \(I\) is \(O^\bigl(\binom{11|D|}{|D|-1}\bigr) = O^\bigl(\binom{11(k - |I| + 1)}{k - |I| + 1}\bigr)\). There are \(\binom{k+1}{i}\) choices of \(I\) of size \(|I| = i\). Thus, the entire compression step takes \begin{equation*} \sum_{i=0}^k \binom{k+1}{i} \cdot O^\left(\binom{11(k-i+1)}{k-i+1}\right) \end{equation} time. Using Stirling's formula, we can bound \(O^\bigl(\binom{11(k-i+1)}{k-i+1}\bigr)\) by \(O^(28.6^{k-i+1})\). Thus, the running time of the algorithm is bounded by \begin{equation*} O^\left(\sum_{i=0}^{k+1}28.6^{k-i+1}\right) = O^\bigl(29.6^{k+1}\bigr) = O^\bigl(29.6^k\bigr). \end{equation}

It remains to describe the construction \(G''\) from \(G'\). The construction may add more vertices to \(I\). This can only decrease the size of the feedback vertex set \(F'\) of \(G''\) to be found and thus can only improve the running time of the compression procedure. We set \(G'' = G'\) and apply the following reduction rules until \(G''\) is fully reduced:

\begin{itemize} \item If \(G''\) has a vertex \(v\) of degree \(0\) or \(1\), then we remove it from \(G''\) because \(v\) cannot be part of any cycle and thus is not a part of any optimal feedback vertex set of \(G''\). \item If \(G''\) has a degree-\)2\) vertex \(v\) whose two neighbours \(u\) and \(w\) do not both belong to \(D\), then assume w.l.o.g.\ that \(u \notin D\). Any cycle that includes \(v\) also includes \(u\). Thus, for any feedback vertex set \(F'\) of \(G''\) such that \(v \in F'\) and \(F' \cap D = \emptyset\), \(F'' = F' \setminus {v} \cup {u}\) is also a feedback vertex set of \(G''\) such that \(F'' \cap D = \emptyset\), its size is \(|F''| \le |F'|\), and it does not include \(v\). Thus, we remove \(v\) and its two incident edges from \(G''\) and add the edge \((u,w)\) to preserve all cycles that \(v\) may have been part of. \item The previous step may produce parallel edges. Consider any two vertices \(u,w\) connected by a pair of parallel edges \((u,w)\). Since there is no cycle containing only vertices in \(D\), we must w.l.o.g.
have \(u \notin D\). Since \(D\) is a feedback vertex set of \(G''\), it must contain at least one vertex in this cycle. Since \(u \notin D\), we thus have \(w \in D\). Any feedback vertex set \(F'\) of \(G''\) must break this cycle. Since we are looking for a feedback vertex set \(F'\) with \(F' \cap D = \emptyset\), we must have \(u \in F'\). Thus, we add \(u\) to \(I\) and remove \(u\) and its incident edges from~\)G''\). \end{itemize} Once \(G''\) is fully reduced with respect to these three rules, the next lemma shows that we either have \(|V(G'') \setminus D| \le 11|D|\) or we can conclude that there is no feedback vertex set of \(G''\) of size at most \(k - |I|\) and such that \(F' \cap D = \emptyset\).

% ----------------------------------------------------------------------------- \begin{lem} \label{lem:fvs-iterative-compression} If \(G''\) is fully reduced with respect to the above reduction rules and \(G''\) has a feedback vertex set \(F'\) of size at most \(k - |I|\) and such that \(F' \cap D = \emptyset\), then \(|V(G'') \setminus D| \le 11|D|\). \end{lem} % -----------------------------------------------------------------------------

\begin{proof} We divide the vertex set of \(G''\) into two subsets \(U = V(G'') \setminus D\) and \(D\). We further partition \(U\) into three subsets \(U_1\), \(U_2\), and \(U_3\). \(U_1\) is the set of all vertices in \(U\) that have at least two neighbours in \(D\). \(U_2\) is the set of all vertices in \(U \setminus U_1\) that have at least three neighbours in \(U\). Finally, \(U_3 = U \setminus (U_1 \cup U_2)\). We prove that \(|U_1| \le 2|D|\), \(|U_2| \le 2|D|\), and \(|U_3| \le 7|D|\). Thus, \(|U| \le 11|D|\).

To bound the size of \(U_1\), consider the subset \(U_1' = U_1 \setminus F'\). Since \(F'\) is a feedback vertex set of \(G''\), the induced bipartite subgraph \(G''[U_1', D]\) is acyclic. Thus, if \(E_1\) is the set of edges of \(G''[U_1', D]\), then \(|E_1| \le |U_1'| + |D| - 1\). Since every vertex in \(U_1'\) has at least two neighbours in \(D\), it has at least two incident edges in \(E_1\), so \(|E_1| \ge 2|U_1'|\). Together, these two inequalities show that \(2|U_1'| \le |U_1'| + |D| - 1\), that is, \(|U_1'| \le |D| - 1\). Since \(|F'| \le |D| - 1\) and \(U_1 \subseteq U_1' \cup F'\), this shows that \(|U_1| < 2|D|\).

To bound the size of \(U_2\), recall that \(D\) is a feedback vertex set of \(G''\). Thus, the graph \(G''[U]\) is acyclic. Every leaf \(v\) of this forest is in \(U_1\). Indeed, if \(v \notin U_1\), then \(v\) has at most one neighbour in \(D\). If \(v\) has no neighbours in \(U\), then its degree in \(G''\) is at most \(1\) and thus would be removed by the first reduction rule. If \(v\) has one neighbour \(u \in U\), then we either remove \(v\) from \(G''\) because its degree is \(1\) (if \(v\) has no neighbours in \(D\)) or because it has degree \(2\) and one of its neighbours is not in~\)D\).

Since every leaf of \(G''[U]\) is in \(|U_1|\), the number of vertices of degree at least \(3\) in \(G''[U]\) is less than \(|U_1|\), that is, \(|U_2| < |U_1| < 2|D|\).

Finally, consider the vertices in \(U_3\) and let \(U_3' = U_3 \setminus F'\). Since \(|U_3| \le |U_3'| + |F'|\) and \(|F'| < |D|\), it suffices to prove that \(|U_3'| \le 6|D|\).

Since \(U_2\) contains all vertices with at least \(3\) neighbours in \(U\) and \(U_1\) contains all vertices with at most one neighbour in \(U\), every vertex in \(U_3'\) has exactly two neighbours in~\)U\). Similarly, since every vertex in \(U\) with at least two neighbours in \(D\) is in~\)U_1\), every vertex in \(U_3'\) has at most one neighbour in \(D\). If it has no neighbour in \(D\), it has exactly two neighbours in \(G''\) neither of which is in \(D\). Thus, it would have been removed by the second reduction rule. This shows that every vertex in \(U_3'\) has exactly one neighbour in \(W\).

Since every vertex in \(U_3'\) has two neighbours in \(U\), the subgraph \(G''[U_3']\) is a collection of paths. Let \(U_3''\) be the set of isolated vertices of \(G''[U_3']\) and let \(U_3''' = U_3' \setminus U_3''\).

To bound the size of \(U_3''\), we construct an auxiliary graph \(H\) with vertex set \(U_1 \cup U_2 \cup F'\). For each vertex \(u \in U_3''\), its two neighbours \(v\) and \(w\) in \(U\) belong to \(U_1 \cup U_2 \cup F'\). We add the edge \((v,w)\) to \(H\). If the graph \(H\) contains a cycle, then so does \(G''[U]\), a contradiction because \(D\) is a feedback vertex set of \(G''\). Thus, \(H\) is acyclic and therefore has at most \(|U_1| + |U_2| - |F'| - 1\) edges. Since every vertex in \(U_3''\) adds an edge to \(H\), this shows that \(|U_3''| < |U_1| + |U_2| + |F'| < 5|D|\).

To bound the size of \(U_3'''\), let \(E_3\) be the edge set of \(G''[U_3''']\). Since \(G''[U]\) is acyclic, so is \(G''[U_3''']\), that is, \(|U_3'''| \le |E_3| + 1\). Thus, it suffices to prove that \(|E_3| < |D|\). For every edge \((u,v) \in E_3\), \(u\) and \(v\) have unique neighbours \(u'\) and \(v'\) in \(W\). Thus, the edge \((u,v)\) defines a path \(P_{u,v}\) from \(u'\) to \(v'\). Let \(H\) be a graph with vertex set \(W\) and with an edge \((u',v')\) between two vertices \(u',v' \in W\) if there exists a path \(P_{u,v}\) between them. If \(|E_3| \ge |D|\), then \(H\) contains a cycle \(C\). Each edge \((u',v') \in C\) corresponds to a path \(P_{u,v}\) in \(G''[U_3''' \cup W]\). The union of these paths forms a closed walk \(C'\) in \(G''[U_3''' \cup W]\) that visits all vertices in \(C\) and has \(3|C|\) edges. Only edges incident to vertices in \(C\) can occur more than once in \(C'\) and occur at most twice. By removing such edges that occur twice in \(C'\), we obtain a cycle \(C''\) in \(G''[U_3''' \cup W]\) of size at least \(3|C| - 2|C| = |C|\). This is a contradiction because \(F'\) is a feedback vertex set of \(G''\), that is, \(G''[U_3''' \cup W]\) is acyclic. This shows that \(|E_3| < |D|\) and thus \(|U_3'''| \le |D|\) and \(|U_3| < 7|D|\). \end{proof}

The discussion in this section proves the following theorem.

% ----------------------------------------------------------------------------- \begin{thm} It takes \(O^*(29.6^k)\) time to decide whether a graph \(G\) has a feedback vertex set of size at most \(k\) and, if so, compute such a set. \end{thm} % -----------------------------------------------------------------------------

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.