| Abstract: | This paper focuses on combinatorial feasibility and optimization problems that arise in the context of parameter identification
of discrete dynamical systems. Given a candidate parametric model for a physical system and a set of experimental observations,
the objective of parameter identification is to provide estimates of the parameter values for which the model can reproduce
the experiments. To this end, we define a finite graph corresponding to the model, to each arc of which a set of parameters
is associated. Paths in this graph are regarded as feasible only if the sets of parameters corresponding to the arcs of the
path have nonempty intersection. We study feasibility and optimization problems on such feasible paths, focusing on computational
complexity. We show that, under certain restrictions on the sets of parameters, some of the problems become tractable, whereas
others are NP-hard. In a similar vein, we define and study some graph problems for experimental design, whose goal is to support
the scientist in optimally designing new experiments. |
