The problem: Given an undirected graph, the dominating set problem is to select a subset of vertices such that each remaining vertex is adjacent to some selected vertex, where the number of selected vertices must not exceed a given threshold.
An example: The graph $(\{1,2,3,4,5,6\},\{\{1,2\},\{1,3\},\{2,4\},\{3,5\},\{4,5\},\{4,6\}\})$ has two dominating sets with at most $2$ vertices: $\{1,4\}$ and $\{3,4\}$.
Instance format: We represent such a problem instance by facts as follows.
%%file instances/instance-dominating.lp
vertex(1). vertex(2). vertex(3). vertex(4). vertex(5). vertex(6).
edge(1,2). edge(1,3). edge(2,4). edge(3,5). edge(4,5). edge(4,6).
threshold(2).
The task: Specify a uniform problem encoding such that atoms over the predicate select/1 within the stable models correspond to dominating sets for arbitrary instances (see the output under Help below).
%%clingo 0 instances/instance-dominating.lp -
% your encoding goes here...
% show
#show select/1.
The symbol - in the command call tells clingo to read the instance file and the content of the cell.
Help: The next cell contains a hard to read encoding for the problem that
you can use for testing your solution.
A readable version of it can be found in the solutions directory.
%%clingo 0 instances/instance-dominating.lp -
#show select/1.ssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-select(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).sodjhoinfeorfioejoi2423onjnfeiooi454onro3jfo34oi43o43nfo34oi34iofj43(R0JER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-threshold(R0JER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).:-vertex(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43),not ssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).ssdfefcerverversodjhoinfeorfioejoi2423onjnfeiooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43,RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-edge(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43,RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).scerverversodjhoinfeorfioejoi2423onjnfeiooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-vertex(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).ssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-select(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43),edge(RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43,RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).ssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-select(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43),edge(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43,RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).select(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-ssdfefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).{ssdfefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):vertex(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43)}R0JER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43:-threshold(R0JER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).
clingo version 5.4.0 Reading from instances/instance-dominating.lp ... Solving... Answer: 1 select(1) select(4) Answer: 2 select(3) select(4) SATISFIABLE Models : 2 Calls : 1 Time : 0.002s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s) CPU Time : 0.002s