A valid algorithm for the c-gap problem may answer anything if OPT is in the middle of the gap.
A simple example of a gap-producing reduction is the nonmetric Traveling Salesman problem (i.e. where the graph's edge costs need not satisfy the conditions of a metric).
[3] The MAX E3-X(N)OR-SAT problem is a form of SAT where each clause is the XOR of three distinct literals, exactly one of which is negated.
Note that this bound is tight, as a random assignment of variables gives an expected 7/8 fraction of satisfied clauses.
In the max-rep version of the problem, we are allowed to choose one vertex from each Ai and each Bi, and we aim to maximize the number of covered superedges.
In the min-rep version, we are required to cover every superedge in the graph, and want to minimize the number of vertices we choose.