In the above formulation, condition 2 became a cubic expression. Here, we consider expressing
condition 2
in a quadratic form by adding a new binary variable.
As mentioned earlier, the condition 2 is the following condition.
For an edge $u\rightarrow v$ of $G$, if $u\rightarrow v$ is not contained in the feedback edge set
$F$,
then the number of $u$ is less than the number of $v$.
For the binary variables $y$ and $x$, assume as defined above.
If we know that the number of vertex $u$ is $i$, then the constraint "the number of $u$ is less than
the
number of $v$" is expressed by
a first-order expression as:
$$
\sum_{j>i} x_{v, j} = 1.
$$
Therefore, if we can obtain the first-order formula for each edge for whether the feedback edge set
$F$
includes the edge. For the number of the starting point, we can express condition 2 by taking these
formulae and OR.
We introduce a binary variable table $z$ of $M \times N$ to express whether $F$ contains $M$ and the
number of the starting point. Here $M$ is the number of edges in $G$, and $N$ is the number of
vertices in
$G$. The rows corresponding to $u\rightarrow v$ in $z$ are all $0$ if the edge $u\rightarrow v$ is
contained in $F$; otherwise, only the $i$ column is $1$, with $i$ as the number of $u$ (starting
point).
For example, for the following feedback edge selection/numbering scheme, $z$ will be as in the table
below.
| $z$ |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| $a\rightarrow b$ |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
| $a\rightarrow g$ |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| $b\rightarrow c$ |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| $c\rightarrow d$ |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| $d\rightarrow b$ |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
| $d\rightarrow e$ |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
| $d\rightarrow f$ |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
| $e\rightarrow f$ |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
| $f\rightarrow g$ |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
| $g\rightarrow h$ |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
| $h\rightarrow a$ |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
For condition 2, $z$ must satisfy the following. We write $z_{u\rightarrow v}$ for the $z$ row
corresponding to edge $u\rightarrow v$
-
Condition 2-1: Each row of $z$ represents whether the corresponding edge is included in the
feedback
edge set $F$. That is, each row of $z$ is all $0$ if the corresponding edge is part of in $F$, and
one
colum of the row has $1$ otherwise.
-
Condition 2-2: Each row of $z$ represents the starting number of the edge if the feedback edge
set
$F$ does not include the corresponding edge. That is, $z_{u\rightarrow v, i} = 1$ means that
$u\rightarrow v$ is not contained in $F$ and the number of $u$ is $i$.
-
Condition 2-3: If edge $u\rightarrow v$ is not contained in $F$ and the number of vertex $u$ is
$i$,
then the number of vertex $v$ is greater than $i$.
Condition 2-1 is written as
$$
\sum_{i = 0}^{N - 1} z_{e, i} = y_e \quad \text{for} \quad e \in E.
$$
Please recall that $y_e$ is a binary variable $0$ if the edge $e$ is contained in $F$.
For conditions 2-2, it is sufficient to impose the condition that "if $z_{u\rightarrow v, i} = 1$,
then
the number of $u$ is $i$". This is because it is clear from Condition 2-1 that "if $z_{u\rightarrow v,
i}
= 1$, then $u\rightarrow v$ is not contained in $F$". Therefore, condition 2-2 is satisfied by the
following equation.
$$
z_{u\rightarrow v, i}(1 - x_{u, i}) = 0 \quad \text{for} \quad (u\rightarrow v) \in E, \ i \in \{0, 1,
\ldots, N-1\}.
$$
From the condition 2-2, the presumption of condition 2-3 is equivalent to $z_{u\rightarrow v, i} =
1$.
Also, as mentioned earlier, the condition "the number of vertices $v$ is greater than $i$" is
expressed by
$\sum_{j>i} x_{v, j} = 1$, so condition 2-3 is:
$$
z_{u\rightarrow v, i} (1 - \sum_{j>i} x_{v, j}) = 0 \quad \text{for} \quad (u\rightarrow v) \in E,
\ i
\in \{0, 1, \ldots, N-1\}
$$
Condition 2-1, 2-2, and 2-3 can now be formulated in the first- and second-order manners. It is easy
to
see that constraint 2 is satisfied if all these conditions are satisfied.
