| rev |
line source |
|
alpar@9
|
1 /* MFVSP, Minimum Feedback Vertex Set Problem */
|
|
alpar@9
|
2
|
|
alpar@9
|
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
|
|
alpar@9
|
4
|
|
alpar@9
|
5 /* The Minimum Feedback Vertex Set Problem for a given directed graph
|
|
alpar@9
|
6 G = (V, E), where V is a set of vertices and E is a set of arcs, is
|
|
alpar@9
|
7 to find a minimal subset of vertices, which being removed from the
|
|
alpar@9
|
8 graph make it acyclic.
|
|
alpar@9
|
9
|
|
alpar@9
|
10 Reference:
|
|
alpar@9
|
11 Garey, M.R., and Johnson, D.S. (1979), Computers and Intractability:
|
|
alpar@9
|
12 A guide to the theory of NP-completeness [Graph Theory, Covering and
|
|
alpar@9
|
13 Partitioning, Minimum Feedback Vertex Set, GT8]. */
|
|
alpar@9
|
14
|
|
alpar@9
|
15 param n, integer, >= 0;
|
|
alpar@9
|
16 /* number of vertices */
|
|
alpar@9
|
17
|
|
alpar@9
|
18 set V, default 1..n;
|
|
alpar@9
|
19 /* set of vertices */
|
|
alpar@9
|
20
|
|
alpar@9
|
21 set E, within V cross V,
|
|
alpar@9
|
22 default setof{i in V, j in V: i <> j and Uniform(0,1) <= 0.15} (i,j);
|
|
alpar@9
|
23 /* set of arcs */
|
|
alpar@9
|
24
|
|
alpar@9
|
25 printf "Graph has %d vertices and %d arcs\n", card(V), card(E);
|
|
alpar@9
|
26
|
|
alpar@9
|
27 var x{i in V}, binary;
|
|
alpar@9
|
28 /* x[i] = 1 means that i is a feedback vertex */
|
|
alpar@9
|
29
|
|
alpar@9
|
30 /* It is known that a digraph G = (V, E) is acyclic if and only if its
|
|
alpar@9
|
31 vertices can be assigned numbers from 1 to |V| in such a way that
|
|
alpar@9
|
32 k[i] + 1 <= k[j] for every arc (i->j) in E, where k[i] is a number
|
|
alpar@9
|
33 assigned to vertex i. We may use this condition to require that the
|
|
alpar@9
|
34 digraph G = (V, E \ E'), where E' is a subset of feedback arcs, is
|
|
alpar@9
|
35 acyclic. */
|
|
alpar@9
|
36
|
|
alpar@9
|
37 var k{i in V}, >= 1, <= card(V);
|
|
alpar@9
|
38 /* k[i] is a number assigned to vertex i */
|
|
alpar@9
|
39
|
|
alpar@9
|
40 s.t. r{(i,j) in E}: k[j] - k[i] >= 1 - card(V) * (x[i] + x[j]);
|
|
alpar@9
|
41 /* note that x[i] = 1 or x[j] = 1 leads to a redundant constraint */
|
|
alpar@9
|
42
|
|
alpar@9
|
43 minimize obj: sum{i in V} x[i];
|
|
alpar@9
|
44 /* the objective is to minimize the cardinality of a subset of feedback
|
|
alpar@9
|
45 vertices */
|
|
alpar@9
|
46
|
|
alpar@9
|
47 solve;
|
|
alpar@9
|
48
|
|
alpar@9
|
49 printf "Minimum feedback vertex set:\n";
|
|
alpar@9
|
50 printf{i in V: x[i]} "%d\n", i;
|
|
alpar@9
|
51
|
|
alpar@9
|
52 data;
|
|
alpar@9
|
53
|
|
alpar@9
|
54 /* The optimal solution is 3 */
|
|
alpar@9
|
55
|
|
alpar@9
|
56 param n := 15;
|
|
alpar@9
|
57
|
|
alpar@9
|
58 set E := 1 2, 2 3, 3 4, 3 8, 4 9, 5 1, 6 5, 7 5, 8 6, 8 7, 8 9, 9 10,
|
|
alpar@9
|
59 10 11, 10 14, 11 15, 12 7, 12 8, 12 13, 13 8, 13 12, 13 14,
|
|
alpar@9
|
60 14 9, 15 14;
|
|
alpar@9
|
61
|
|
alpar@9
|
62 end;
|
