CSE 505: Computing with Logic

In this homework, you will solve a set of intractable problems using the most widely used ASP system clingo.

ASP:

ASP systems find stable models in two steps:

• Grounding: higher-level programs in subsets of predicate logic are converted to purely propositional normal logic programs by grounding clauses containing predicates (i.e. instantiating all variables to ground terms).
• Solving: a model of the resulting propositional program is compute by a stable model solver.

• Ranges: p(1..4). is equivalent to p(1). p(2). p(3). p(4).
• Aggregates #count {p(X)} finds the number of distinct values of X for which p(X) holds.
• (Bounded) Arithmetic: Arithmetic operators are interpreted (unlike Prolog which treats them as uninterpreted function symbols).

Example:

The problem of finding minimal vertex covers can be cast in terms of stable model finding using the following clingo specification:

% cover(X): X is in a minimal vertex cover.
cover(X) :- adj(X, Y), not cover(Y).

Here adj/2 is the relation such that adj(X,Y) holds iff there is an edge between vertices X and Y. in G.

Let there be another relation vertex/1 that is used to define the set of all vertices in G. If we want to find a vertex cover bounded by a given size limit, we can do add the following (Example uses a limit of 5).

limit(5).
solve :- limit(C), #count{ vertex(X): cover(X)} <= C.
:- not solve.

The first line above defines the limit. The second line defines the kind of solutions we're seeking. Specifically, those where the set of all vertices in the cover has a cardinality of C or less, where C is the predefined limit. The third line states an integrity constraint: specifying here that not solve would violate the integrity of the solution. (So we really want solve to hold).

The addition of cardinality constraint lets us look for not just minimal vertex covers, but also answer question regarding whether or not a vertex cover of a given size exists.

Finally, if we want to see a such a vertex cover, we can simply add,

#show cover/1.

The Homework Problems

1. Set Cover: Write a clingo specification for solving the minimal set cover problem: given a universe U and a collection S of subsets of U>, a cover C is a subset of S such that ⋃ C = U. A set cover is minimal if no proper subset of it is a set cover.

   For this problem,

   • the universe U is defined by a set of facts universe/1 (e.g. universe(1). universe(2). universe(3).).

   • the collection S is defined in two steps: a set of facts naming each set in the collection (e.g. collection(s1). collection(s2). collection(s3).). And a set of in/2 facts listing elements in each set of the collection (e.g. in(s1, 1). in(s2, 1). in(s2, 2). in(s3, 2). in(s3, 3).).

   For extra credit: given a specific integer limit (defined by a limit/1 fact as in vertex cover) find a set cover C such that |C| is no larger than the given limit.

2. Dominating Set: Write a clingo specification for solving the minimal dominating set problem: given a graph G=(V,E) S ⊆ V is a dominating set if every edge outside S (i.e. in V-S) has an edge to some vertex in S. A dominating set is minimal if no proper subset of it is a dominating set.

   For this problem, assume that the graph is specified by a set of vertex/1 facts listing its vertices, and a set of adj/2 facts listing its adjacency relation: adj(X,Y) iff there is an edge between X and Y.

   For extra credit: given a specific integer limit (defined by a limit/1 fact as in vertex cover) find a dominating set S such that |S| is no larger than the given limit.

3. Independent Set: Write a clingo specification for solving the maximal independent set problem: given a graph G=(V,E) R ⊆ V is an independent set if there is no edge between any two vertices in R. An independent set is maximal if no proper superset of it is an independent set.

   For extra credit: given a specific integer limit (defined by a limit/1 fact as in vertex cover) find an indpendent set S such that |S| is at least as large as the given limit.

Grading:

Submission: