  We investigate the computational complexity of problems on toric ideals such
as normal forms, Gr\"obner bases, and Graver bases. We show that all these
problems are strongly NP-hard in the general case. Nonetheless, we can derive
efficient algorithms by taking advantage of the sparsity pattern of the matrix.
We describe this sparsity pattern with a graph, and study the parameterized
complexity of toric ideals in terms of graph parameters such as treewidth and
treedepth. In particular, we show that the normal form problem can be solved in
parameter-tractable time in terms of the treedepth. An important application of
this result is in multiway ideals arising in algebraic statistics. We also give
a parameter-tractable membership test to the reduced Gr\"obner basis. This test
leads to an efficient procedure for computing the reduced Gr\"obner basis.
Similar results hold for Graver bases computation.
