  Deciding feasibility of large systems of linear equations and inequalities is
one of the most fundamental algorithmic tasks. However, due to data
inaccuracies or modeling errors, in practical applications one often faces
linear systems that are infeasible. Extensive theoretical and practical methods
have been proposed for post-infeasibility analysis of linear systems. This
generally amounts to detecting a feasibility blocker of small size $k$, which
is a set of equations and inequalities whose removal or perturbation from the
large system of size $m$ yields a feasible system. This motivates a
parameterized approach towards post-infeasibility analysis, where we aim to
find a feasibility blocker of size at most $k$ in fixed-parameter time $f(k)
\cdot m^{O(1)}$. We establish parameterized intractability ($W[1]$- and
$NP$-hardness) results already in very restricted settings for different
choices of the parameters maximum size of a deletion set, number of
positive/negative right-hand sides, treewidth, pathwidth and treedepth.
Additionally, we rule out a polynomial compression for MinFB parameterized by
the size of a deletion set and the number of negative right-hand sides.
Furthermore, we develop fixed-parameter algorithms parameterized by various
combinations of these parameters when every row of the system corresponds to a
difference constraint. Our algorithms capture the case of Directed Feedback Arc
Set, a fundamental parameterized problem whose fixed-parameter tractability was
shown by Chen et al. (STOC 2008).
