  Consider a distributed system with $n$ processors out of which $f$ can be
Byzantine faulty. In the approximate agreement task, each processor $i$
receives an input value $x_i$ and has to decide on an output value $y_i$ such
that
  - the output values are in the convex hull of the non-faulty processors'
input values,
  - the output values are within distance $d$ of each other.
  Classically, the values are assumed to be from an $m$-dimensional Euclidean
space, where $m \ge 1$.
  In this work, we study the task in a discrete setting, where input values
with some structure expressible as a graph. Namely, the input values are
vertices of a finite graph $G$ and the goal is to output vertices that are
within distance $d$ of each other in $G$, but still remain in the graph-induced
convex hull of the input values. For $d=0$, the task reduces to consensus and
cannot be solved with a deterministic algorithm in an asynchronous system even
with a single crash fault. For any $d \ge 1$, we show that the task is solvable
in asynchronous systems when $G$ is chordal and $n > (\omega+1)f$, where
$\omega$ is the clique number of~$G$. In addition, we give the first
Byzantine-tolerant algorithm for a variant of lattice agreement. For
synchronous systems, we show tight resilience bounds for the exact variants of
these and related tasks over a large class of combinatorial structures.
