We study the standard-form ILP problem c^⊤ x → max Ax = b, x ∈ ℤ_{≥ 0}ⁿ, where A ∈ ℤ^{k× n} has full row rank. We obtain refined FPT algorithms parameterized by k and Δ, the maximum absolute value of a k× k minor of A. Our approach combines discrepancy-based dynamic programming with matrix discrepancy bounds in Komlós' setting. Let κ_k denote the maximum discrepancy over all matrices with k columns whose columns have Euclidean norm at most 1. Up to polynomial factors in the input size, the optimization problem can be solved in time O(κ_k)^{2k} Δ², and the corresponding feasibility problem in time O(κ_k)^kΔ. Using the best currently known bound κ_k = Õ(log^{1/4}k), this yields running times O(log k)^{k/2(1+o(1))} Δ² and O(log k)^{k/4(1+o(1))} Δ, respectively. Under the Komlós conjecture, the dependence on k in both running times reduces to 2^O(k).

Abstract The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. This latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded in it. In the present paper, we show that the universe of quasi-chain graphs is at least as complex as the universe of permutations by establishing a bijection between the class of all permutations and a subclass of quasi-chain graphs. This implies, in particular, that the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs. On the other hand, we propose a decomposition theorem for quasi-chain graphs that implies an implicit representation for graphs in this class and efficient solutions for some algorithmic problems that are generally intractable.