Unary Integer Linear Programming with Structural Restrictions

1 Introduction

Integer Linear Programming (ILP) is the archetypical NPcomplete optimization problem and is used in a multitude of applications in diverse areas of artificial intelligence. In particular, a wide range of problems in artificial intelligence can be efficiently solved in practice via a translation into an ILP instance, including problems from areas such as process scheduling [Floudas and Lin, 2005], planning [Vossen et al., 1999; van den Briel et al., 2005], vehicle routing [Toth and Vigo, 2001], packing [Lodi et al., 2002], and network hub location [Alumur and Kara, 2008].

Recently, a number of papers have explored the complexity of ILP instances where the interactions between variables have specific forms of structure, captured in terms of structural parameters such as primal treewidth [Jansen and Kratsch, 2015], primal treedepth [Ganian and Ordyniak, 2018], torso-width [Ganian et al., 2017], and fracture backdoors [Dvoˇr´ak et al., 2017]. All of these parameters give rise to polynomial (and also fixed-parameter [Downey and Fellows, 2013; Cygan et al., 2015]) algorithms for solving ILP, under the condition that either the domain of variables (primal treewidth, torso-width) or the size of the coefficients (fracture backdoors, primal treedepth) in the ILP are bounded.

In this paper, we turn our attention to the significantly less explored case of using the structure of variable interactions for solving ILPs where neither the domain nor the coefficients are bounded by a fixed constant or a parameter (as per the parameterized complexity setting). On the other hand, due to the trivial structure of ILP instances which encode weakly NP-hard problems such as SUBSET SUM, one cannot hope to obtain polynomial algorithms even for very simple ILPs encoded in binary. Hence in this paper we consider variants of ILP where both the domain and the coefficients are not bounded to only a fixed number of options, but where either one or both of these components are encoded in unary. We note that such ILPs arise naturally, e.g., when encoding combinatorial problems as ILPs (consider for instance VERTEX COVER or vehicle routing problems). To this end, we distinguish UNARY ILP (coefficients and domains are encoded in unary and bounded by the input size), UNARYCOEFFICIENT ILP (coefficients are encoded in unary), and UNARY-DOMAIN ILP (domains are encoded in unary and bounded by the input size).

The first series of results focus on solving ILP using the structural parameter clique-width. Unlike parameters such as treewidth and treedepth, clique-width can remain bounded even on well-structured instances that are very dense, i.e., have a high number of variable-constraint interactions. Clique-width (and in particular its "signed" variant) has been successfully applied in areas such as Boolean Satisfiability [Fischer et al., 2008], Answer Set Programming [Bliem et al., 2016], and Graph Algorithms [Courcelle et al., 2000]. Since clique-width originates from the graph setting, one needs to specify the graph representation of ILPs where clique-width will be measured: two graph representations of ILP instances are used in this context, namely the primal graph (which captures variable-variable interactions) and the incidence graph (which captures variable-constraint interactions) [Ganian et al., 2017; Samer and Szeider, 2010]. Our main result involving clique-width is a polynomialtime algorithm for UNARY ILP on instances of bounded signed clique-width of the incidence graph representation. The algorithm is based on dynamic programming, but requires careful introduction of data records tailored to ILP which are fundamentally different from those used, e.g., for Boolean Satisfiability [Fischer et al., 2008]. We complement the algorithm with lower bounds which show that the result is essentially tight. In particular, we show that UNARY ILP remains NP-hard when the clique-width of the primal graph is used (Lemma 4), UNARY ILP remains NP-hard when the unsigned clique-width 1 of the incidence graph is used (Lemma 4), and finally both UNARY-COEFFICIENT ILP and UNARY-DOMAIN ILP are NP-hard when the signed incidence clique-width is bounded (Lemma 2).

In the second part of the paper, we turn our attention to acyclic ILP instances, i.e., ILP instances whose primal and/or incidence graph is a forest. In this context, we obtain new algorithms and hardness results in order to complete the complexity landscape for UNARY ILP, UNARY-COEFFICIENT ILP and UNARY-DOMAIN ILP on acyclic instances. We present a summary of our results in Table 1.

We note that the NP-hardness proof for UNARYCOEFFICIENT ILP presented in Theorem 5 is of particular interest-surprisingly, it shows that already deciding feasibility on instances whose primal graph is a star is NP-hard. The proof uses a nontrivial reduction from 3-SAT which uses unary-encoded coefficients to force very high domain values in a way which encodes variable assignments of the SAT instance. Another interesting observation is that in some cases, having an acyclic primal graph allows for a polynomial-time algorithm even though an acyclic incidence graph does not, while in other cases the situation is reversed. Finally, we note that Lemma 7 shows an even stronger result: deciding whether an ILP is feasible is polynomial-time solvable whenever the incidence graph is acyclic, even if the instance is encoded in binary.

Related Work and Technical Remarks. Two of the structural parameters studied in previous works give rise to polynomial-time algorithms even when the original restrictions to bounded domain and/or coefficients are relaxed to weaker restrictions in terms of the encoding. In particular, UNARY-DOMAIN ILP instances of bounded primal treewidth can be solved in polynomial-time [Jansen and Kratsch, 2015] and UNARY ILP is polynomial-time tractable on instances of bounded incidence treewidth [Ganian et al., 2017]. On the other hand, UNARY-COEFFICIENT ILP remains NP-hard even on instances of bounded primal/incidence treewidth [Ganian et al., 2017; Ganian and Ordyniak, 2018] and UNARY-DOMAIN ILP is NP-hard on instances of bounded incidence treewidth [Ganian et al., 2017].

1 Unlike signed clique-width, unsigned clique-width does not capture information about how variables interact with constraints.

Clique-width and the associated k-expressions used for dynamic programming are NP-hard to compute [Fellows et al., 2009], which might be considered as an obstacle towards practical applications. Furthermore, while it is possible to check in polynomial time whether the clique-width of a graph is bounded by a fixed k, these algorithms are infeasible in practice and involve an approximation error that is exponential in k [Oum and Seymour, 2006]. Recently, SAT solvers have been used to compute the clique-width of graphs [Heule and Szeider, 2015]. In some cases, a suitable k-expression witnessing a bound on the clique-width might already be part of the input (this is the case, e.g., for certain applications in the area of verification [Fischer et al., 2008, Section1.4]). In line with previous work on clique-width [Fischer et al., 2008; Bliem et al., 2016; Courcelle et al., 2000], we will generally assume in our theorems that a suitable k-expression is provided as part of the input.

We note that the paper considers ILP instances in inequality form, i.e., each instance consists of a set of inequalities (see Subsection 2.1). Other definitions of the ILP problem exist, and the transformations necessary to convert an instance from one definition to another can affect the structural properties of the instance; this is particularly true for determining whether an ILP instance is acyclic. For example, an instance of ILP in equality form (i.e., all constraints are equalities) containing a single equality has an acyclic incidence graph representation, but would no longer be acyclic if we convert it to an inequality form. On the other hand, the property of having bounded (signed) clique-width is preserved regardless of the used formulation.

2 Preliminaries

We will use standard graph terminology, see for instance the handbook by Diestel [Diestel, 2012]. An undirected graph G is a tuple (V, E), where V or V (G) is the vertex set and E or E(G) is the edge set. All our graphs are simple and loopless. For natural numbers i < j, we set [i, j] = {i, . . . , j}, [i] = [1, i] and ±[i] = [-i, i].

2.1 Integer Linear Programming

It will be useful to view an ILP instance as a set of linear inequalities (constraints) rather than using the constraint matrix. Formally, let an ILP instance I be a tuple (X, dom, F, ϵ) where X is a set of variables, dom : X → [Z ∪ {-∞}, Z ∪ {∞}] is a function which maps each variable to an interval, F is a set of linear inequalities over X = x1, . . . , xn and ϵ is a linear function over X of the form ϵ(X) = s1x1+· · ·+snxn. Each inequality A ∈ F is assumed to be of the form cA,1xA,1 + · · · + cA,jxA,j ≤ bA where the coefficients cA,i are non-zero; the set of variables which occur in A is denoted var(A), and we let var(I) = X. We call dom(x) the domain of x, elements of F are the constraints, and the numbers si, cA,i and bA are called the coefficients.

A (partial) assignment α: X → Z is a (partial) mapping such that α(x) ∈ dom(x) for all x to which α assigns a value. For a (partial) assignment α and an inequality A, we denote by A(α) the left-side value of A obtained by applying α (specifically, the part of α which intersects with A); for instance, if α is a partial assignment which only maps a single variable x to the value 3 and A is the inequality 2x - y - z ≤ 7, then A(α) = 6. Formally, A(α) = cA,1α(xA,1) + · · · + cA,nα(xA,n), where undefined values of α are treated as 0; this means that if var(A) has an empty intersection with the domain of α, then A(α) = 0. Similarly, we set ϵ(α) to be the value of ϵ obtained by applying α, i.e., ϵ(α) = s1α(x1) + · · · + snα(xn).

An assignment α is called a feasible assignment or a solution if it satisfies every A ∈ F, i.e., if A(α) ≤ bA for each A ∈ F. Furthermore, α is called an optimal solution if the value of ϵ(α) is maximized over all solutions. Given an instance I, the task in the ILP problem is to compute an optimal solution for I if one exists, and otherwise to decide whether there exists a feasible assignment.

In this paper, we focus on ILP instances which are either completely or partially encoded in unary. We distinguish:

• UNARY ILP, where both the domain and the coefficients are bounded by the input size and encoded in unary.
• UNARY-COEFFICIENT ILP, where the coefficients are encoded in unary; the domain is encoded in binary and can be unbounded.
• UNARY-DOMAIN ILP, where the domain is bounded by the input size and encoded in unary; coefficients are encoded in binary.

For example, consider an instance I of UNARY ILP and let the unary encoding size |A| of an inequality A of the form cA,1xA,1 + · · · + cA,qxA,q ≤ bA be defined as |A| = |bA| + ∑i∈[q] (|cA,i| + 1). Then the input size of I is |I| = (∑i∈|var(I)| |si|+(maxd∈dom(i) |d|)+1)+(∑A∈F |A|). For each of the above problems, the FEASIBILITY variant is the restriction of the chosen problem to inputs where ϵ is empty.

There are several ways of naturally representing (the variable interactions in) ILP instances as graphs. Given an ILP instance I = (X, dom,F, ϵ), the (simplified) primal graph [Ganian et al., 2017] of I is the graph whose vertex set is the set var(I), and two vertices a, b are adjacent iff there exists some A ∈ F containing both a and b. The incidence graph [Ganian et al., 2017] of I is the graph whose vertex set is var(I)∪F and two vertices a, b are adjacent iff a ∈ var(I), b ∈ F and a ∈ var(b). Finally, the signed incidence graph of I is the incidence graph of I where an edge between constraint A and variable xA,j carries the sign cA,j; observe that each edge e in the signed incidence graph carries precisely one sign. We call graphs where all edges carry a sign signed Figure 1: An example of a graph with clique-width 2 and signed clique-width 4.

graphs. Given an ILP instance I, let GI, HI denote the primal graph and the signed incidence graph of I, respectively.

2.2 Clique-width

Let k be a positive integer. A k-graph is a graph whose vertices are labeled by [k]; formally, the graph is equipped with a labeling function γ : V (G) → [k], and we also use γ-1 (i) to denote the set of vertices labeled i for i ∈ [k]. We consider an arbitrary graph as a k-graph with all vertices labeled by 1. We call the k-graph consisting of exactly one vertex v (say, labeled by i) an initial k-graph and denote it by i(v). The clique-width of a graph G is the smallest integer k such that G can be constructed from initial k-graphs by means of repeated application of the following three operations:

1. Disjoint union (denoted by ⊕);
2. Relabeling: changing all labels i to j (denoted by pi→j);
3. Edge insertion: adding an edge between each vertex labeled by i and each vertex labeled by j, where i ̸= j (denoted by ηi,j or ηj,i).

A construction of a k-graph G using the above operations can be represented by an algebraic term composed of ⊕, pi→j and ηi,j (where i ̸= j and i, j ∈ [k]). Such a term is called a k-expression defining G, and the clique-width of G is the smallest integer k such that G can be defined by a kexpression. Many graph classes are known to have bounded clique-width; examples include all graph classes of bounded treewidth [Courcelle and Olariu, 2000] and co-graphs [Courcelle and Olariu, 2000].

A k-expression tree (also called parse trees in the literature [Courcelle et al., 2000]) is a rooted tree representation of a k-expression; specifically, the k-expression tree can be built from a k-expression in a leaves-to-root fashion by using a leaf to represent each i(v), each ⊕ operator is represented by an ⊕ node with two children, and each pi→j and ηj,i operator is represented by a corresponding node with a single child.

If the edges of G have signs, then one can define two different variants of clique-width for G. The unsigned clique-width of G is simply the clique-width of the graph G′ obtained by removing all signs on the edges of G. On the other hand, the signed clique-width of G is the minimum k such that G can be defined by a signed k-expression, which is analogous to a k-expression with the sole distinction that the operation ηi,j is replaced by ηℓ i,j which adds an edge with sign ℓ between all vertices labeled i and j.

We list some known facts about clique-width below:

• The difference between the signed clique-width (scw) and unsigned clique-width (cw) of a signed graph G can be arbitrarily large [Bliem et al., 2016].

• A signed k-expression of a bipartite signed graph G with bi-partition V1, V2 can be converted to a signed (k + 1)- expression of G such that the labels used for V1 are completely disjoint from those used for V2 (this is because any label that was originally used for V1 and V2 cannot be used to create new edges).

As per the above observation, from now on we will assume that, at each node of a signed k-expression tree, a label is either a variable-label (i.e., used exclusively by variables) or a constraint-label (i.e., used exclusively by constraints).

3 ILP on Graphs of Bounded Signed Clique-width

In this section, we obtain our polynomial-time algorithm for solving UNARY ILP using signed incidence clique-width. We then turn our attention to providing lower bounds which complement the algorithmic result.

Theorem 1. There exists an algorithm which takes as input an instance I of UNARY ILP and a signed k-expression tree T of HI , runs in time O(|I|4k · |T |), and solves UNARY ILP.

At its core, the algorithm performs dynamic programming along T . Let t be a node of T , and recall that t could be one of the following four types of nodes: i(v), ⊕, ηi,j or pi→j. Let Tt be the subtree of T rooted at t, and let G(t) be signed graph defined by the signed k-expression tree Tt; furthermore, let Xt and Ft denote the variable set and set of constraints of G(t), respectively, and let ω(Xt) and ω(Ft) denote the set of variable-labels and the set of constraint-labels. For instance, if r is the root of T then G(r) = HI, and for each leaf t in T it holds that G(t) is a graph with a single labeled vertex (which may be either a variable or a constraint).

3.1 Towards a Proof of Theorem 1

The high-level idea of the algorithm is to compute certain information (a data table) about our graph G(t) in a leaf-to-root fashion, and once we reach the root this information allows us to output an optimal solution to the ILP instance. Let us first provide an informal description of the data table before giving the formal definition. Consider a graph G(t) defined by the k-expression tree Tt. Our data table will remember a set of signatures, where each signature will contain all the information we need to store about one possible set of partial assignments of Xt.

Let ϱ = |I|. We can now formally define the notion of signature: a signature φ is a tuple (P, Q) where P : ω(Xt) → ±[ϱ] maps each variable-label to an integer, and Q : ω(Ft) → [-∞, ±[ϱ2 ]] maps each constraint-label to an interval whose left endpoint is -∞ and right endpoint is an integer. Observe that since the number of labels is upper-bounded by k and each label is either a variable-label or constraint-label, the total number of possible signatures is upper-bounded by ϱ2k . Let Φt be the set of all possible signatures at node t.

Our next step is to link signatures with partial assignments; this will also define the semantics behind the definition of a signature. Informally, an assignment α of Xt matches the signature φ = (P,Q) (α |= φ) if P captures the sum of all variables for each individual variable-label and Q specifies the "offset" under which each constraint of a given constraintlabel is satisfied. Formally, an assignment α of Xt matches the signature φ = (P, Q) if the following holds:

1. ∀j ∈ ω(Ft) ∀A ∈ γ-1 (j) ∀h ∈ Q(j) : A(α) +h ≤ bA, and

The first condition ensures that P(i) captures the sum of the variables with variable-label i, the second condition ensures that Q(j) captures how much each constraint with constraintlabel j can change while being satisfied, and the third condition ensures that Q(j) is the maximum interval with the desired property. If a variable-label i is empty then we let P(i) = 0, and if a constraint-label j is empty then we let Q(j) = [-∞, ϱ2 ]. Note that the restriction to [-∞, ϱ2 ] is justified by the fact that |A(α)| is upper-bounded by ϱ2 .

It follows from the definition that an assignment of Xt cannot have more than one signature. However, it is not difficult to show that each assignment of Xt has precisely one signature, i.e., that the bounds on P and Q can never be exceeded. Observation 1. Let α be an assignment of Xt. Then there exists a signature φ such that α |= φ.

Having established the notion of a signature, we can now define the data table used in the dynamic programming algorithm. For a node t of T, we let DTt be a mapping from each signature φ in Φt to a partial assignment which matches φ and maximizes ϵ; formally, DTt(φ ∈ Φt) = α : (α |= φ) ∧ (∀α′ |= φ : ϵ(α′ ) ≤ ϵ(α)). If there is no partial assignment α which matches φ, then we set DTt(φ) = ∅.

Proof of Theorem 1. We compute the data table DTt in a leafto-root fashion along the signed k-expression tree T of HI. Once we reach the root r of T , then we can output an optimal solution to I as follows. Let a signature φ = (P,Q) be good if for all constraint-labels i, 0 ∈ Q(i). If DTr(φ) = ∅ for every good signature φ, then there exists no feasible assignment for I. Otherwise, we loop over all good signatures φ, compute the value of ϵ(DTr(φ)), and output an assignment αopt = DTr(φopt) with maximum ϵ(DTr(φopt)).

For completeness, we remark that such an assignment can be obtained fromDTr in time ϱ2k and that correctness follows fromObservation 1. Indeed, we are outputting an assignment which maximizes ϵ over all assignments which match a signature in Φt, and Observation 1 establishes that each assignment has a signature in Φt. So, all that remains is to show how to compute DTt for each node t in T. We note that computing DTt for i(v) nodes and pi→j nodes is straightforward, and so here we only focus on the remaining two cases.

If t is a ⊕ node: Let u and w be the two children of t. For each pair of signatures φu = (Pu,Qu) ∈ Φu and φw = (Pw,Qw) ∈ Φw we construct a signature φuw = (P,Q) ∈ Φt as follows:

• for each variable-label i, P(i) = Pu(i) +Pw(i), and
• for each constraint-label j, Q(j) = Qu(j) ∩Qw(j).

Intuitively, the signature φuw is the signature of assignments of Xt which can be obtained by taking the disjoint union of partial assignments matching φu and φw. To avoid confusion, we remark that a signature φ ∈ Φt can be constructed in the above manner from more than a single tuple of signature φu and φw; in other words, there may exist u′ ̸= u and/or w′ ̸= w such that φ = φuw = φu′w′ . In this case, we will proceed by keeping the assignment compatible with φ which optimizes ϵ, regardless of how φ was constructed.

We start with an empty data table DTt. Then, for each φuw constructed as above, we compare the assignment that is currently stored in DTt(φuw) with the one obtained by merging φu and φw and store the better one in DTt. More precisely, if ϵ(DTt(φuw)) ≥ ϵ(DTu(φu)) + ϵ(DTw(φw)) then DTt(φuw) remains unchanged, and otherwise (or if DTt(φuw) = ∅) we set DTt(φuw) = DTu(φu) ∪ DTw(φw).

If t is a ηℓ i,j node: Let u be the child of t, and assume w.l.o.g. that i is a variable-label and j is a constraint-label. For each φ′ = (P ′ ,Q′ ) ∈ Φu, we construct a signature φ = (P ′ ,Q) by retaining all entries except for Q′ (j); to obtain the value of Q(j), we alter the interval Q′ (j) by subtracting the value ℓ · P ′ (i) (from the right side of the interval), i.e., Q(j) = (Q′ (j) - ℓ · P ′ (i)). To populate the data table DTt, we proceed similarly as in the case of ⊕ nodes. We begin with an empty DTt, and for each φ′ ∈ Φu we compute φ as above and compare ϵ(DTu(φ′ )) with ϵ(DTt(φ)): if ϵ(DTu(φ′ )) ≥ ϵ(DTt(φ)) or if DTt(φ) is undefined then we set DTt(φ) = DTu(φ′ ), and otherwise we leave DTt(φ) unchanged.

Running time: Each of the operations carried out at the nodes of T can be completed in time ϱ2k with the exception of the operations for ⊕ nodes, which take time at most ϱ4k . The running time of the algorithm follows.

3.2 Lower Bounds

We begin by noting that the algorithm cannot be extended to work on either UNARY-COEFFICIENT ILP or UNARYDOMAIN ILP-in other words, signed incidence cliquewidth does not give rise to a polynomial-time algorithm if either the domain or the constraints are encoded in binary.

Lemma 2. UNARY-DOMAIN ILP FEASIBILITY and UNARY-COEFFICIENT ILP FEASIBILITY are both NP-hard when restricted to instances of signed incidence clique-width at most 5, even if a signed 5-expression is given in the input.

Proof Sketch. For the first claim, we give a simple polynomial reduction from the SUBSET SUM problem, which is well known to be weakly NP-complete. The resulting instance I of UNARY-DOMAIN ILP FEASIBILITY has two constraints which model the desired equality, and it is easy to verify that HI has signed clique-width at most 4. In order to establish the second claim, it suffices to observe that the instances produced by the NP-hardness proof presented in the recent work by Ganian and Ordyniak (2018, Theorem 13) have signed clique-width at most 5.

Next, we rule out the existence of algorithms with a uniformly polynomial running time for UNARY ILP on instances of bounded signed clique-width; in the language of parameterized complexity theory [Downey and Fellows, 2013; Cygan et al., 2015], we show that the problem is W[1]-hard.

Lemma 3. UNARY ILP FEASIBILITY is W[1]-hard parameterized by signed incidence clique-width, even if an optimal signed k-expression is given as part of the input.

Proof Sketch. One can observe that the ILP instances obtained in the W[1]-hardness proof by Ganian and Ordyniak (2016) have bounded signed incidence clique-width.

Our final result rules out the use of unsigned clique-width.

Lemma 4. UNARY ILP is NP-hard when restricted to instances of unsigned incidence clique-width at most 2, even if a 2-expression is given as part of the input. Furthermore, UNARY ILP is NP-hard when restricted to instances of primal clique-width at most 2, even if a 2-expression is given as part of the input.

Proof. We reduce from the well-known VERTEX COVER problem. Given an m-vertex graph G and an upper bound ℓ on the size of the vertex cover, we construct an ILP instance I as follows. For each vertex vi we create a variable xi where dom(xi) = [0, 1]. For each edge vivj, we create the constraint m · xi +m · xj + ∑xp∈var(I)\{xi,xj} xp ≥ m. Finally, we set ϵ = ∑xp∈X -xp. Since each constraint can only be satisfied if at least one of xi, xj is set to 1, it follows that (G, ℓ) is a YES-instance if and only if there exists a solution α for I such that ϵ(α) ≥ -ℓ. To conclude the proof, observe that HI is a complete bipartite graph, GI is a complete graph, and the size of the unary encoding of I is upper-bounded by a polynomial of |V (G)| + ℓ.

4 Results for Acyclic ILPs

This section is dedicated to obtaining a complexity classification for ILPs with an acyclic graph representation.

4.1 ILPs with an Acyclic Primal Graph

First, observe that UNARY-DOMAIN ILP (and hence also UNARY ILP) can be solved in polynomial time if the primal graph is a tree by applying the dynamic programming algorithm of Jansen and Kratsch (2015). We now proceed to our main lower-bound result for this section, Theorem 5.

Theorem 5. UNARY-COEFFICIENT ILP FEASIBILITY is NP-complete even on instances whose primal graph is a star.

Proof Sketch. Clearly, UNARY-COEFFICIENT ILP FEASIBILITY is in NP, since ILP FEASIBILITY is in NP. To prove NP-hardness, we will give a polynomial time reduction from the well-known NP-complete problem 3-SAT.

Let F be an instance of 3-SAT with n variables u1, . . . , un and m clauses C1, . . . , Cm. We will define an instance I of UNARY ILP with 1+n+m variables and 2(n+m) inequalities, whose primal graph is the star Sn+m such that there exists a feasible assignment for I if and only if F is a satisfiable instance of 3-SAT. Note that we can assume that none of the clauses Ci contains a variable along with its negation.

The reduced instance I = (X, dom, F, ∅) is defined as follows. We set X = {y} ∪ {x1, . . . , xn} ∪ {z1, . . . , zm} and dom(x) = [-∞,∞] for every variable x ∈ X. In what follows let pi be the i-th prime number. Then, F contains the following inequalities (variables marked in bold):

• ∀i ∈ [n], F contains y - pixi ≤ 1 and pixi - y ≤ 0.

Note that since these are the only inequalities containing xi, there exists a feasible assignment for xi if and only if y is assigned a number that has a remainder of 0 or 1 modulo pi.

• ∀i ∈ [m], F contains y - prpsptzi ≤ di + prpspt - 1 and prpsptzi - y ≤ -di - 1, where
• r, s, t are such that Cm is a clause over the variables ur, us, ut, and
• let ur ↦→ br, us ↦→ bs, ut ↦→ bt be the assignment which falsifies Cm. Then di is the unique integer in [0, prpspt -1] such that di ≡ br mod pr, di ≡ bs mod ps, di ≡ bt mod pt.

We note that the existence and uniqueness of di follows directly from the Chinese Remainder Theorem. Observe that for any partial assignment α such that α(y) ̸≡ di mod prpspt, it is easy to compute a value of α(zi) such that the two inequalities where zi appears are satisfied.

It follows from the Prime Number Theorem that pi = O(i log(i)). Hence, the absolute value of the largest coefficient in I is upper-bounded by 2p3n = O(n4 ), and in particular I is an instance of UNARY-COEFFICIENT ILP FEASIBILITY whose size is polynomial in |F|. The primal graph of I is a star with center y and leaves x1, . . . , xn, z1, . . . , zm. Now, it suffices to show that there is a satisfying assignment for F iff there is a feasible assignment for I.

The reduction provided in Theorem 5 immediately yields the following lower bound based on the Exponential Time Hypothesis (ETH) [Impagliazzo et al., 2001].

Corollary 6. Unless the Exponential Time Hypothesis fails, there is no 2o(n+m) algorithm solving UNARY-COEFFICIENT ILP FEASIBILITY with n variables and m inequalities, even on instances whose primal graph is a star.

4.2 ILP on Tree-like Incidence Graph

Theorem 7. ILP FEASIBILITY restricted to instances with an acyclic incidence graph is polynomial-time solvable.

Proof Sketch. Let I = (X, dom,F, ∅) be the input instance, and recall that HI is the incidence graph of I, i.e., a tree. Let us set an arbitrary variable as the root r of HI. The algorithm works as follows: It takes an inequality A that is furthest from r, computes the domain restrictions imposed by A on the unique variable x ∈ var(A) that lies on the path between A and r (i.e., x is the parent of A), and then it removes A and all variables in var(A) \ {x} from HI . The algorithm proceeds in this manner until only r is left. If the domain of r is not empty, the algorithm outputs yes, otherwise it outputs no. The proof of correctness and the step of simplifying an instance by removing an inequality can be handled by induction on the number of inequalities.

Lemma 8. UNARY-COEFFICIENT ILP is NP-complete on instances whose incidence graph is a tree of depth 2.

Proof Sketch. The proof follows a similar strategy as the proof of Theorem 5. As before, we will reduce from a 3SAT instance F with n variables u1, . . . , un and m clauses C1, . . . , Cm and we will have a central variable y in the ILP instance I such that ui ↦→ y mod pi should satisfy F.

However, here we are not allowed to specify both lower and upper bounds for the same pair of variables of ILP, as this would introduce cycles in the incidence graph. So instead of specifying both bounds, we introduce new variables x01 , . . . , x0n , z0 1 , . . . , z 0m, which represent the remainder of y after dividing, respectively, by pi's for variables (x1, . . . , xn) and by pr · ps · pt for clauses (z1, . . . , zm) with variables ur, us, ut. Furthermore, to achieve equality, we will set ϵ so that it maximizes the sum of all left sides of the inequalities in I. Observe that while a feasible assignment of I can satisfy an inequality without having the left side equal to its right side, the optimization function only achieves the value ∑A∈F bA if and only if all inequalities are tight, i.e., their left side equals the right side; in all other cases, the optimization function will achieve a value lower than ∑A∈F bA. In the end, we get an ILP instance I that has a solution α such that ϵ(α) ≥ ∑A∈F bA if and only if F is a YES-instance.

Lemma 9. UNARY-DOMAIN ILP is NP-complete, even on instances with incidence graph isomorphic to a star.

Proof Sketch. We employ a reduction from SUBSET SUM similar to the one used in Lemma 2; however, here we use a single inequality constraint together with ϵ applied on the left side of the inequality to model the desired.

5 Concluding Remarks

We have presented new algorithms and lower bounds for ILP in the case where rather mild restrictions on the formulation of the instance (unary encoding of the coefficients or domain) are combined with structural restrictions on variableconstraint interactions. The results naturally complement recent works on ILPs [Jansen and Kratsch, 2015; Ganian and Ordyniak, 2018; Ganian et al., 2017; Dvoˇr´ak et al., 2017].

We believe that the algorithm using signed incidence clique-width (Theorem 1) is of particular interest; since, unlike previously considered parameters, it can deal with ILP instances which are "dense". We also consider the nontrivial reduction presented in Theorem 5 to be surprising.

Acknowledgments

Eduard Eiben was supported by Pareto-Optimal Parameterized Algorithms (ERC Starting Grant 715744). Robert Ganian is also affiliated with FI MU, Brno, Czech Republic. Duˇsan Knop is also affiliated with MFF UK, Praha, Czech Republic and was supported by projects NFR MULTIVAL and P202/12/G061 of GA ˇCR.