On the most imbalanced orientation of a graph

Abstract

We study the problem of orienting the edges of a graph such that the minimum over all the vertices of the absolute difference between the outdegree and the indegree of a vertex is maximized. We call this minimum the imbalance of the orientation, i.e. the higher it gets, the more imbalanced the orientation is. The studied problem is denoted by ${{\mathrm{\textsc {MaxIm}}}}$. We first characterize graphs for which the optimal objective value of ${{\mathrm{\textsc {MaxIm}}}}$ is zero. Next we show that ${{\mathrm{\textsc {MaxIm}}}}$ is generally NP-hard and cannot be approximated within a ratio of $\frac{1}{2}+\varepsilon$ for any constant $\varepsilon >0$ in polynomial time unless $\texttt {P}=\texttt {NP}$ even if the minimum degree of the graph $\delta$ equals 2. Then we describe a polynomial-time approximation algorithm whose ratio is almost equal to $\frac{1}{2}$. An exact polynomial-time algorithm is also derived for cacti. Finally, two mixed integer linear programming formulations are presented. Several valid inequalities are exhibited with the related separation algorithms. The performance of the strengthened formulations is assessed through several numerical experiments.

1 Introduction and notation

Let $G=(V,E)$ be an undirected simple graph (with node set V and edge set E), we denote by $\delta _G$ the minimum degree of the vertices of G. An orientation $\varLambda$ of G is an assignment of a direction to each undirected edge uv in E, i.e. any function on E of the form $\varLambda (uv)\in \{\overrightarrow{uv},\overrightarrow{vu}\}$, $\forall \{uv\}\in E$ where $\overrightarrow{uv}$ and $\overleftarrow{vu}$ denote the edge uv oriented from u to v. For each vertex v of G we denote by $d_G(v)$ or d(v) the unoriented degree of v in G and by $d^+_\varLambda (v)$ or $d^+(v)$ (resp. $d^-_\varLambda (v)$ or $d^-(v)$) the outdegree (resp. indegree) of v in G w.r.t. $\varLambda$. Graph orientation is a well studied area in graph theory and combinatorial optimization, a large variety of constrained orientations as well as objective functions have been considered so far.

Among those arise the popular degree-constrained orientation problems: in Frank and Gyárfás (1976) gave a simple characterization of the existence of an orientation such that the outdgree of every vertex is between a lower and an upper bound given for each vertex. Asahiro et al. (2007, 2008, 2014) proved the NP-hardness of the weighted version of the problem where the maximum outdegree is minimized, gave some inapproximability results, and studied similar problems for different classes of graphs. Chrobak and Eppstein (1991) proved that for every planar graph a 3-bounded outdegree orientation and a 5-bounded outdegree acyclic orientation can be constructed in linear time.

Other problems involving other criteria on the orientation have been studied such as acyclicity, diameter or connectivity. Robbins’ theorem (1939) for example states that the graphs that have strong orientations are exactly the 2-edge-connected graphs (Robbins 1939 and later 1985), Chung et al. (1985) provided a linear time algorithm for checking whether a graph has such an orientation and finding one if it does. Then in 1960, Nash-Williams generalized Robbin’s theorem showing that an undirected graph has a k-arc-connected orientation if and only if it is 2k-edge-connected (Nash-Williams 1960). The problem called oriented diameter that consists in finding a strongly connected orientation with minimum diameter was introduced in 1978 by Ch$\acute{\mathrm{v}}$atal and Thomassen: they proved that the problem is NP-hard for general graphs (Ch$\acute{\mathrm{v}}$atal and Thomassen 1978). It was then proven to be NP-hard even if the graph is restricted to a subset of chordal graphs by Fomin et al. 2004 who gave also approximability and inapproximability results.

For an orientation $\varLambda$ of $G=(V,E)$ and a vertex v we call $|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|$ the imbalance of v in G w.r.t $\varLambda$ and we call $\min _{v\in V}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|$ the imbalance of $\varLambda$. Biedl et al. studied the problem of finding an acyclic orientation of unweighted graphs minimizing the imbalance of each vertex: they proved that it is solvable in polynomial time for graphs with maximum degree at most three but NP-complete generally and for bipartite graphs with maximum degree six and gave a $\frac{13}{8}$-approximation algorithm (Biedl et al. 2005). Then Kára et al. closed the gap proving the NP-completeness for graphs with maximum degree four. Furthermore, they proved that the problem remains NP-complete for planar graphs with maximum degree four and for 5-regular graphs (Kára et al. 2005).

Landau’s (1953) famous theorem gives a condition for a sequence of non-negative integers to be the score sequence or outdegree sequence of some tournament (i.e. oriented complete graph) and later, Harary and Moser characterized score sequences of strongly connected tournaments (Harary et al. 1971). Analogous results for the “imbalance sequences” of directed graphs are given by Mubayi et al. (2001). In 1962, Ford and Fulkerson characterized the mixed graphs (i.e. partially oriented graphs) whose orientation can be completed in an eulerian orientation, that is to say, an orientation for which the imbalance of each vertex equals zero (Ford and Fulkerson 1962). Many other results related to orientation have been proposed. Some of them are reviewed in Bang-Jensen and Gutin (2009).

Let us denote by $\overrightarrow{O}(G)$ the set of all the orientations of G, we consider the problem of finding an orientation with maximized imbalance:

$$\begin{aligned} ({{\mathrm{\textsc {MaxIm}}}})~~{{\mathrm{\textsc {MaxIm}}}}(G)=\max _{\varLambda \in \overrightarrow{O}(G)}\min _{v\in V}{|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|} \end{aligned}$$

and we call ${{\mathrm{\textsc {MaxIm}}}}(G)$ the value of ${{\mathrm{\textsc {MaxIm}}}}$ for G. The minimum degree $\delta _G$ of a graph G is a trivial upper bound for ${{\mathrm{\textsc {MaxIm}}}}(G)$.

The rest of this paper is organized as follows. In the Sect. 2, we give several characterizations of the the graphs verifying ${{\mathrm{\textsc {MaxIm}}}}(G)=0$. In Sect. 3, we show that ${{\mathrm{\textsc {MaxIm}}}}$ is generally NP-complete even for graphs with minimum degree 2 and inapproximable within a ratio $\frac{1}{2}+\varepsilon$ for any constant $\varepsilon >0$ and then give an approximation algorithm whose ratio is almost equal to $\frac{1}{2}$. In Sect. 4, we present a polynomial-time exact algorithm for cactus. Section 5 is devoted to mixed integer linear programming formulations of ${{\mathrm{\textsc {MaxIm}}}}$ where families of valid inequalities are presented for the most promising formulation. These formulation have been implemented and the computational results are reported in Sect. 6.

Since the value of ${{\mathrm{\textsc {MaxIm}}}}$ for a graph is the minimum of the values of ${{\mathrm{\textsc {MaxIm}}}}$ on its connected components, from here on out, all the graphs we consider are assumed to be connected. For a graph G and H a subgraph of G, we will use the notations V(H) and E(H) to refer to the set of vertices of G and the set of edges of H, respectively.

2 Characterizing the graphs for which ${{\mathrm{\textsc {MaxIm}}}}(G)=0$

Now we characterize the graphs verifying ${{\mathrm{\textsc {MaxIm}}}}(G)=0$. We start by unveiling several necessary conditions and properties of such graphs. First we can show that concerning such a graph, we can find an orientation satisfying several additional properties.

Proposition 1

Let G be a graph such that ${{\mathrm{\textsc {MaxIm}}}}(G)=0$ and $u\in V$. Then there exists an orientation $\varLambda \in \overrightarrow{O}(G)$ such that u is the only vertex of G with imbalance equal to zero w.r.t. $\varLambda$.

Proof

Let $\varLambda \in \overrightarrow{O}(G)$ be an orientation minimizing $|\{v\in V/|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|=0\}|$. We suppose that $|\{v\in V/|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|=0\}|\ge 2$. We choose two distinct vertices v and w in $\{v\in V/|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|=0\}$ and a path $p=(v=u_0,\ldots ,u_n=w)$ between v and w. If we switch the orientation of the edge $u_0u_1$, then the imbalance of $u_0$ becomes positive and necessarily the imbalance of $u_1$ becomes zero otherwise the resulting orientation would contradict the minimality of $\varLambda$. Using the same reasoning, if we switch the orientation of all the edges $u_0u_1,\ldots ,u_{n-2}u_{n-1}$, we obtain an orientation where both $u_{n-1}$ and $u_n$ have an imbalance equal to zero while the imbalance is positive on all the vertices $u_0,\ldots ,u_{n-2}$ and unchanged on all other vertices. So now if we switch the orientation of the edge $u_{n-1}u_n$ as well, then the resulting orientation contradicts the minimality of $\varLambda$. Hence, $|\{v\in V/|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|=0\}|=1$.

Now let v be this unique vertex of G such that $|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|=0$. Let $u\ne v$ be an arbitrary vertex and let $p=(v=u_0,\ldots ,u_n=u)$ be a path between v and u. By switching the orientation of all the edges $u_0u_1,\ldots ,u_{n-2}u_{n-1}$, we obtain an orientation $\varLambda '$ where u has an imbalance equal to zero while the imbalance is positive for $u_0$ and unchanged on all other vertices. $\square$

This yields the following necessary condition: if G is a graph such that ${{\mathrm{\textsc {MaxIm}}}}(G)=0$, then G is eulerian. For let $u\in V$, we know there exists $\varLambda \in \overrightarrow{O}(G)$ such that $\{v\in V/|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|=0\}=\{u\}$. Then $d^+_\varLambda (u)=d^-_\varLambda (u)$, hence $d(u)=d^+_\varLambda (u)+d^-_\varLambda (u)=2d^+_\varLambda (u)$ is even. The following lemma about eulerian graphs will be useful for the proof of our characterization.

Lemma 2

If G is an eulerian graph, then there exists an elementary cycle (hereafter just called cycle) C of G such that $G-E(C)$ has at most one connected component that is not an isolated vertex.

Proof

Since G is eulerian and connected, it can be decomposed into edge-disjoint cycles that we can order $C_1,\ldots ,C_n$ according to the following condition: $\cup _{k=1}^iC_i$ is connected, $\forall i\in \llbracket 1,n\rrbracket$. Then $C_n$ is the cycle we are looking for. $\square$

Now let us define a certain family of graphs which will prove to be exactly the graphs for which the optimal objective value of ${{\mathrm{\textsc {MaxIm}}}}$ is zero. Intuitively they are the graphs for which every block is an odd cycle.

Definition 3

We define the class of graphs ${\mathscr {C}}^{odd}$ as follows: a simple graph G is in ${\mathscr {C}}^{odd}$ if there exists n odd cycles $C_1,\ldots ,C_n$ ($n\ge 1$) such that:

$$\begin{aligned}&\bullet ~ \cup _{i=1}^nC_i=G,\nonumber \\&\bullet ~|V(\cup _{k=1}^{i-1}C_k)\cap V(C_i)|=1,\quad \forall i\in \llbracket 2,n\rrbracket . \end{aligned}$$

(1)

Theorem 4

For any simple graph G, ${{\mathrm{\textsc {MaxIm}}}}(G)=0$ if and only if $G\in {\mathscr {C}}^{odd}$.

Proof

• $\Leftarrow$ We work by induction on the number n of cycles contained in the graph. Nothing is required for these cycles except that they must be elementary. If $n=1$, then our graph is an odd cycle which implies ${{\mathrm{\textsc {MaxIm}}}}(G)=0$. Let $n\ge 2$, we assume that all graphs of ${\mathscr {C}}^{odd}$ with $k\le n-1$ cycles verify ${{\mathrm{\textsc {MaxIm}}}}(G)=0$. Let $G\in {\mathscr {C}}^{odd}$ with n cycles $C_1,\ldots ,C_n$ as in (1). Suppose there exists $\varLambda \in \overrightarrow{O}(G)$ with strictly positive imbalance. Let us call $G'=\cup _{i=1}^{n-1}C_i$ the graph obtained from G after removing $C_n$ and let us take a look at $\varLambda _{|G'}$ : the orientation of the edges of $G'$ obtained from $\varLambda$ restricted to $E(G')$. As $G'$ is a graph of $n-1$ cycles in ${\mathscr {C}}^{odd}$, our inductive hypothesis implies that we have a vertex $u\in V(G')$ such that $|d^+_{\varLambda _{|G'}}(u)-d^-_{\varLambda _{|G'}}(u)|=0$. Necessarily, $u=V(G')\cap V(C_n)$. Thus $|d^+_{\varLambda }(u)-d^-_{\varLambda }(u)|=|d^+_{\varLambda _{|C_n}}(u)-d^-_{\varLambda _{|C_n}}(u)|>0$ implying that ${{\mathrm{\textsc {MaxIm}}}}(C_n)>0$, a contradiction because $C_n$ is an odd cycle.

• $\Rightarrow$ Since ${{\mathrm{\textsc {MaxIm}}}}(G)=0$, we know that G is eulerian. We work again by induction on the number of elementary cycles n. If $n=1$, then our graph is eulerian with a unique cycle, hence it is a cycle. Now as ${{\mathrm{\textsc {MaxIm}}}}(G)=0$, necessarily it is an odd cycle and is therefore in ${\mathscr {C}}^{odd}$. Let $n\ge 2$, we assume that all graphs with $k\le n-1$ cycles verifying ${{\mathrm{\textsc {MaxIm}}}}(G)=0$ are in ${\mathscr {C}}^{odd}$. Let G be a graph with n cycles such that ${{\mathrm{\textsc {MaxIm}}}}(G)=0$. Thanks to Lemma 2, there exists a cycle C of G such that $G-E(C)$ has at most one connected component $G'$ that is not an isolated vertex. Suppose that ${{\mathrm{\textsc {MaxIm}}}}(G')>0$, let $\varLambda \in \overrightarrow{O}(G')$ with strictly positive imbalance. Let $u_0\in V(G')\cap V(C)$, we name the vertices of C as follows: $u_0,u_1,\ldots ,u_k=u_0$. Without loss of generality, we can assume that $d^+_\varLambda (u_0)-d^-_\varLambda (u_0)>0$; if it was not the case, replace $\varLambda$ by its reverse. We complete $\varLambda$ in an orientation of G by orienting the edges of C: we orient $u_0u_1$ from $u_0$ to $u_1$ and go on as follows:

  $$\begin{aligned} \forall i\in \llbracket 1,k-1\rrbracket , {\left\{ \begin{array}{ll} \text {if } u_i\in V(G'), &{}\text { we orient }u_iu_{i+1}\text { as }u_{i-1}u_i,\\ \text {otherwise}, &{}\text { we orient } u_iu_{i+1} \text { as } u_iu_{i-1}. \end{array}\right. } \end{aligned}$$

  Where orienting an edge ab as another edge cd means orienting it from a to b if cd was oriented from c to d and from b to a otherwise. Let us have a look at the resulting orientation $\varLambda '$ (cf Fig. 1): when completing $\varLambda$ in $\varLambda '$, the imbalance of the vertices in $V(G')\backslash \{u_0\}$ was left unchanged, the imbalance of the vertices in $V(C)\backslash V(G')$ equals 2 and the imbalance of $u_0$ was either left unchanged or augmented by two. Hence $\varLambda '$ has strictly positive imbalance which contradicts ${{\mathrm{\textsc {MaxIm}}}}(G)=0$, therefore, ${{\mathrm{\textsc {MaxIm}}}}(G')=0$. Suppose $|V(G')\cap V(C)|\ge 2$ and let u and v be 2 distinct vertices in $V(G')\cap V(C)$ such that $u\ne v$. Thanks to Proposition 1, we know that there exists an orientation $\varLambda \in \overrightarrow{O}(G')$ such that $\{w\in V/|d^+_{\varLambda }(w)-d^-_{\varLambda }(w)|=0\}=\{v\}$ and without loss of generality, $d^+_\varLambda (u)-d^-_\varLambda (u)>0$. We name the vertices of C as follows: $u=u_0u_1\cdots u_k=u_0$, $v=u_l$ and we complete $\varLambda$ in an orientation of G by orienting the edges of C: we orient $u_0u_1$ from $u_0$ and $u_1$ and go on as follows:

  $$\begin{aligned} \forall i\in \llbracket 1,k-1\rrbracket \setminus \{l\}, {\left\{ \begin{array}{ll} \text {if } u_i\in V(G'), &{}\text { we orient } u_iu_{i+1} \text { as } u_{i-1}u_i,\\ \text {otherwise}, &{}\text { we orient } u_iu_{i+1} \text { as } u_iu_{i-1}. \end{array}\right. } \end{aligned}$$

  And we orient $u_lu_{l+1}$ as $u_lu_{l-1}$. In the resulting orientation $\varLambda '$, the imbalance of the vertices in $V(G')\backslash \{u,v\}$ was left unchanged, the imbalance of the vertices in $V(C)\backslash V(G')$ equals 2, the imbalance of v was augmented by two and the imbalance of u was either left unchanged or augmented by two. Hence $\varLambda '$ contradicts ${{\mathrm{\textsc {MaxIm}}}}(G)=0$, therefore, $|V(G')\cap V(C)|=1$. Suppose C is even. We call $u\in V(G')$ such that $V(G')\cap V(C)=\{u\}$, and $\varLambda \in \overrightarrow{O}(G')$ such that $\{v\in V/|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|=0\}=\{u\}$. We name the vertices of C as follows: $u=u_0u_1\cdots u_k=u_0$ and we complete $\varLambda$ in an orientation of G by orienting the edges of C: we orient $u_0u_1$ from $u_0$ to $u_1$ and $u_iu_{i+1}$ as $u_iu_{i-1},\quad \forall i\in \llbracket 1,k-1\rrbracket$. In the resulting orientation $\varLambda '$, the imbalance of the vertices in $V(G')\backslash \{u\}$ was left unchanged, the imbalance of the vertices in $V(C)\backslash V(G')$ equals 2 and, C being even, the imbalance of u was augmented by two. Hence $\varLambda '$ contradicts ${{\mathrm{\textsc {MaxIm}}}}(G)=0$, therefore, C is odd. As $G'$ is a graph with at most $n-1$ cycles verifying ${{\mathrm{\textsc {MaxIm}}}}(G)=0$, by the induction hypothesis, there exist $C_1,\ldots ,C_{n-1}$ odd cycles such that:

  • $\cup _{i=1}^{n-1}C_i=G'$,

  • $|V(\cup _{k=1}^{i-1}C_k)\cap V(C_i)|=1,\quad \forall i\in \llbracket 2,n-1\rrbracket$.

  Adding the odd cycle $C_n=C$, we obtain that $G\in {\mathscr {C}}^{odd}$.

$\square$

Fig. 1

The vertices of C in $G'$ are left unchanged imbalance-wise, the other vertices of C are set to 2 and in the end $|d^+_{\varLambda '}(u_0)-d^-_{\varLambda '}(u_0)|\ge |d^+_{\varLambda }(u_0)-d^-_{\varLambda }(u_0)|>0$

Fig. 2

The vertices of C in $G'$ are left unchanged imbalance-wise except for v which is set to 2, like the other vertices of C and in the end $|d^+_{\varLambda '}(u_0)-d^-_{\varLambda '}(u_0)|\ge |d^+_{\varLambda }(u_0)-d^-_{\varLambda }(u_0)|>0$

Now in order to widen our perception of those graphs, let us show another characterization (Fig. 2).

Theorem 5

For every simple graph G,

$$\begin{aligned} G\in {\mathscr {C}}^{odd}\Leftrightarrow G\text { is eulerian with no even cycle} \end{aligned}$$

Proof

• $\Rightarrow$ By construction, every graph in ${\mathscr {C}}^{odd}$ is eulerian with no even cycle.

• $\Leftarrow$ We will once again work by induction on the number of cycles n. If $n=1$, then our graph is eulerian with a unique odd cycle, hence it is an odd cycle and is therefore in ${\mathscr {C}}^{odd}$. Let $n\ge 2$, we assume that all eulerian graphs with no even cycle and $k\le n-1$ odd cycles are in ${\mathscr {C}}^{odd}$. Let G be a graph with no even cycle and n odd cycles. Thanks to Lemma 2, there exists an odd cycle C of G such that $G-E(C)$ has only one connected component $G'$ that is not an isolated vertex. As $G'$ is eulerian and even-cycle-free with $n-1$ odd cycles, by induction hypothesis, $G'\in {\mathscr {C}}^{odd}$, hence there exist $C_1,\ldots ,C_{n-1}$ odd cycles such that:

  • $\cup _{i=1}^{n-1}C_i=G'$,

  • $|V(\cup _{k=1}^{i-1}C_k)\cap V(C_i)|=1,\quad \forall i\in \llbracket 2,n-1\rrbracket$.

  Suppose there exist u and v ($u \ne v$) belonging to $V(\cup _{k=1}^{n-1}C_k) \cap V(C)$. Since $G'$ is connected, let p be an elementary path in $G'$ between u and v. We can assume that u and v are the only vertices of C contained in p, otherwise we could replace v by the first vertex of C encountered when traveling on p from u. C defines two other vertex-disjoint paths between u and v: one even that we will call $p_{even}$ and one odd that we will call $p_{odd}$. p being vertex disjoint with either $p_{even}$ or $p_{odd}$, by concatenating it with the one corresponding to its parity, we obtain an even cycle of G, contradicting our hypothesis on G (cf. Fig. 3a, b). This yields that $|V(C)\cap V(G')|=1$. From that we can conclude

  • $\cup _{i=1}^{n}C_i=G$,

  • $|V(\cup _{k=1}^{i-1}C_k)\cap V(C_i)|=1,\quad \forall i\in \llbracket 2,n\rrbracket$.

  Hence $G\in {\mathscr {C}}^{odd}$.

$\square$

Fig. 3

In both cases, concatenating p with $p_{even}$ or $p_{odd}$ yields an even cycle in G

3 Complexity and (in)approximability

In this section we prove the NP-completeness and inapproximability of our problem and give an approximation algorithm based on the special case of bipartite graphs.

Concerning the complexity of ${{\mathrm{\textsc {MaxIm}}}}$, we show that the problem is NP-complete. More precisely, that answering if ${{\mathrm{\textsc {MaxIm}}}}(G)$ equals 2 for a graph G such that $\delta _G=2$ is NP-complete. For that purpose, we introduce a variant of the satisfiability problem that we reduce to a ${{\mathrm{\textsc {MaxIm}}}}$ instance: the not-all-equal at most 3-SAT(3V).

Not-all-equal at most 3-SAT(3V) is a restriction of not-all-equal at most 3-SAT which is itself a restriction of 3-SAT known to be NP-complete (Schaefer 1978), where each clause contains at most three literals and in each clause, not all the literals can be true. Since 2-SAT can be solved in polynomial time, we hereafter deal only with formulas having at least one three-literals clause. The added restriction of not-all-equal at most 3-SAT(3V) is that each variable (not literal) appears at most three times in a formula. The resulting problem is still $\texttt {NP}$-complete.

Lemma 6

The not-all-equal at most 3-SAT(3V) problem is NP-complete.

Proof

See ‘Appendix’. $\square$

Now we associate to a not-all-equal at most 3-SAT(3V) instance $\varphi$ with n variables $\{x_1,\ldots ,x_n\}$ and m clauses $\{c_1,\ldots ,c_m\}$ a graph $G_\varphi$ for which the value w.r.t. ${{\mathrm{\textsc {MaxIm}}}}$ will give the answer to whether $\varphi$ is satisfiable or not. If a variable $x_i$ occurs only in positive literals (resp. only in negative literals), it follows that a satisfying assignment of the variables of $\varphi$ must necssarily give the value ${{\mathrm{{\text {TRUE}}}}}$ (resp. ${{\mathrm{{\text {FALSE}}}}}$) to $x_i$, therefore $x_i$ can be removed from $\varphi$ with conservation of the satisfiability. Thus, without loss of generality, we can assume that in any not-all-equal at most 3-SAT(3V) formula, every variable occurs at least once as a positive literal and at least once as a negative literal. $G_\varphi$ consists of gadgets that mimic the variables and the clauses of $\varphi$ and additional edges that connect them together:

• the gadget corresponding to a variable $x_i$ consists of two vertices labeled $x_i$ and $\lnot x_i$ and one edge connecting them;

• the gadget corresponding to a two-literals clause $c_j=(l^1\vee l^2)$, where $l^1$ and $l^2$ are its literals, consists in two vertices labeled $a^j_{l^1}$ and $b^j_{l^2}$ corresponding to $l^1$ and $l^2$ respectively (the index ”$l^k$” of the vertices labels stands for the literal it represents, i.e. $x_i$ if $l^k$ is the variable $x_i$ and $\lnot x_i$ if $l^k$ is the negation of the variable $x_i$) and one edge connecting them;

• the gadget corresponding to a three-literals clause gadget consists in six vertices and six edges. For a clause $c_j=(l^1\vee l^2\vee l^3)$, where $l^1$, $l^2$ and $l^3$ are its literals (the order is arbitrary), three vertices labeled $a^j_{l^1}$, $b^j_{l^2}$ and $b'^j_{l^3}$ correspond to $l^1$, $l^2$ and $l^3$ respectively. Three additional vertices are labeled $u^j$, $v^j$ and $w^j$ and the gadgets’ edges are $a^j_{l^1}u_j$, $a^j_{l^1}v_j$, $u_jw_j$, $v_jw_j$, $w_jb^j_{l^2}$ and $w_jb'^j_{l^3}$;

• $\forall i\in \llbracket 1,n\rrbracket$, the vertex labeled $x_i$ (resp. $\lnot x_i$) is connected to all the vertices labeled $a^j_{x_i}$, $b^j_{x_i}$ or $b'^j_{x_i}$ (resp. $a^j_{\lnot x_i}$, $b^j_{\lnot x_i}$ or $b'^j_{\lnot x_i}$), $\forall j\in \llbracket 1,m\rrbracket$.

As an example, for a formula

$$\begin{aligned} \varphi =(x_1\vee \lnot x_2\vee x_3)\wedge (\lnot x_1\vee \lnot x_3\vee x_4)\wedge (x_1\vee \lnot x_2\vee x_4)\wedge (x_2\vee \lnot x_4), \end{aligned}$$

(2)

the corresponding graph $G_\varphi$ is represented in Fig. 4.

Fig. 4

$G_\varphi$ for $\varphi =(x_1\vee \lnot x_2\vee x_3)\wedge (\lnot x_1\vee \lnot x_3\vee x_4)\wedge (x_1\vee \lnot x_2\vee x_4)\wedge (x_2\vee \lnot x_4)$

Theorem 7

A not-all-equal at most 3-SAT(3V) formula $\varphi$ is satisfiable if and only if ${{\mathrm{\textsc {MaxIm}}}}(G_\varphi )=2$.

Proof

• $\Rightarrow$ Suppose $\varphi$ is satisfiable and let $v: \{x_1,\ldots ,x_n\}\rightarrow \{{{\mathrm{{\text {TRUE}}}}},{{\mathrm{{\text {FALSE}}}}}\}$ be a satisfying assignment of $x_1,\ldots ,x_n$. We know that $\delta _{G_\varphi }=2$ which yields ${{\mathrm{\textsc {MaxIm}}}}(G_\varphi )\le 2$. So let us build an orientation $\varLambda \in \overrightarrow{O}(G_\varphi )$ for which the imbalance is greater than or equal to 2. First, we assign an orientation to the edges of the variable gadget:

  $$\begin{aligned} \varLambda (x_i\lnot x_i)={\left\{ \begin{array}{ll} \overrightarrow{x_i\lnot x_i}&{}\text { if }v(x_i)={{\mathrm{{\text {TRUE}}}}};\\ \overrightarrow{\lnot x_ix_i}&{}\text { otherwise}. \end{array}\right. } \end{aligned}$$

  For example, for the formula $\varphi =(x_1\vee \lnot x_2\vee x_3)\wedge (\lnot x_1\vee \lnot x_3\vee x_4)\wedge (x_1\vee \lnot x_2\vee x_4)\wedge (x_2\vee \lnot x_4)$ satisfied by the assignment $v(x_1,x_2,x_3,x_4)=({{\mathrm{{\text {FALSE}}}}},{{\mathrm{{\text {TRUE}}}}},$ ${{\mathrm{{\text {TRUE}}}}},{{\mathrm{{\text {TRUE}}}}})$, the edges of the variable gadgets of graph $G_\varphi$ are oriented as in Fig. 5a. Since each variable $x_i$ occurs at least once as a positive literal and at least once as a negative literal, $2\le d_{G_\varphi }(x_i)\le 3$ and $2\le d_{G_\varphi }(\lnot x_i)\le 3,\quad \forall i\in \llbracket 1,n\rrbracket$. Then to ensure our objective on the imbalance of $\varLambda$, the orientation of the edges connecting vertex gadgets and clause gadgets must be such that $\forall i\in \llbracket 1,n\rrbracket ,~|d^+_{\varLambda }(x_i)-d^-_{\varLambda }(x_i)|=d_{G_\varphi }(x_i)$ and $|d^+_{\varLambda }(\lnot x_i)-d^-_{\varLambda }(\lnot x_i)|=d_{G_\varphi }(\lnot x_i)$. In other words, for $i\in \llbracket 1,n\rrbracket$, if $v(x_i)={{\mathrm{{\text {TRUE}}}}}$ (resp. $v(x_i)={{\mathrm{{\text {FALSE}}}}}$), then the edges adjacent to the vertex $x_i$ are oriented from $x_i$ (resp. to $x_i$) and the edges adjacent to the vertex $\lnot x_i$ are oriented to $\lnot x_i$ (resp. from $\lnot x_i$), e.g. Fig. 5b.

  So far, all the edges in the variables gadgets and the edges connecting the vertex gadgets and the clause gadgets have been oriented and the vertices in the variables gadgets have imbalance greater than or equal to 2. In order to complete our orientation $\varLambda$ we have to orient the edges in the clause gadgets.

  Let $c_j=(l^1\vee l^2)$ be a two-literals clause. Since v satisfies $\varphi$, we know that exactly one of the two literals is true w.r.t. v. Which, according to the way we oriented edges so far, means that exactly one of $a^j_{l^1}$ and $b^j_{l^2}$ has one incoming arc from a variable gadget and the other has one outgoing arc to a variable gadget. If $a^j_{l^1}$ is the one with the incoming arc from a variable gadget (meaning that $v(l^1)={{\mathrm{{\text {TRUE}}}}}$), then we assign $\varLambda (a^j_{l^1}b^j_{l^2})=\overrightarrow{b^j_{l^2}a^j_{l^1}}$, otherwise the opposite. We obtain $|d^+_{\varLambda }(a^j_{l^1})-d^-_{\varLambda }(a^j_{l^1})|=|d^+_{\varLambda }(b^j_{l^2})-d^-_{\varLambda }(b^j_{l^2})|=2$.

  Let $c_j=(l^1\vee l^2\vee l^3)$ (the order is identical to the one chosen to build the clause gadget, i.e. $d_{G_\varphi }(a^j_{l^1})=3$ and $d_{G_\varphi }(b^j_{l^2})=d_{G_\varphi }(b'^j_{l^3})=2$) be at three-literals clause. If the edge connecting $a^j_{l^1}$ to a variable gadget is oriented to $a^j_{l^1}$ (meaning that $v(l^1)={{\mathrm{{\text {TRUE}}}}}$), then we assign $\varLambda (a^j_{l^1}u_j)=\overrightarrow{u_ja^j_{l^1}}$, $\varLambda (a^j_{l^1}v_j)=\overrightarrow{v_ja^j_{l^1}}$, $\varLambda (u_jw_j)=\overrightarrow{u_jw_j}$ and $\varLambda (v_jw_j)=\overrightarrow{v_jw_j}$. Since $v(l^1)={{\mathrm{{\text {TRUE}}}}}$, either both $v(l^2)$ and $v(l^3)$ are ${{\mathrm{{\text {FALSE}}}}}$ or exactly one of $v(l^2)$ and $v(l^3)$ is ${{\mathrm{{\text {TRUE}}}}}$ and one is ${{\mathrm{{\text {FALSE}}}}}$. If both are ${{\mathrm{{\text {FALSE}}}}}$ then $b^j_{l^2}$ and $b'^j_{l^3}$ have an outgoing arc to a variable gadget. In that case, we orient $w_jb^j_{l^2}$ and $w_jb'^j_{l^3}$ to $w_j$ and we obtain $|d^+_{\varLambda }(a^j_{l^1})-d^-_{\varLambda }(a^j_{l^1})|=3$, $|d^+_{\varLambda }(b^j_{l^2})-d^-_{\varLambda }(b^j_{l^2})|=|d^+_{\varLambda }((b'^j_{l^3})-d^-_{\varLambda }((b'^j_{l^3})|=|d^+_{\varLambda }(u_j)-d^-_{\varLambda }(u_j)|=|d^+_{\varLambda }(v_j)-d^-_{\varLambda }(v_j)|=2$ and $|d^+_{\varLambda }(w_j)-d^-_{\varLambda }(w_j)|=4$. If exactly one of $v(l^2)$ and $v(l^3)$ is ${{\mathrm{{\text {TRUE}}}}}$ and one is ${{\mathrm{{\text {FALSE}}}}}$, then exactly one of $b^j_{l^2}$ and $b'^j_{l^3}$ has an incoming arc from a variable gadget and the other an outgoing arc to a variable gadget. If $b^j_{l^2}$ is the one with the incoming arc from a variable gadget (meanings that $v(l^2)={{\mathrm{{\text {TRUE}}}}}$ and $v(l^3)={{\mathrm{{\text {FALSE}}}}}$), then we assign $\varLambda (w_jb^j_{l^2})=\overrightarrow{w_jb^j_{l^2}}$ and $\varLambda (w_jb'^j_{l^3})=\overrightarrow{b'^j_{l^3}w_j}$, otherwise the opposite. We obtain $|d^+_{\varLambda }(a^j_{l^1})-d^-_{\varLambda }(a^j_{l^1})|=3$ and $|d^+_{\varLambda }(b^j_{l^2})-d^-_{\varLambda }(b^j_{l^2})|=|d^+_{\varLambda }(b'^j_{l^3})-d^-_{\varLambda }(b'^j_{l^3})|=|d^+_{\varLambda }(u_j)-d^-_{\varLambda }(u_j)|=|d^+_{\varLambda }(v_j)-d^-_{\varLambda }(v_j)|=|d^+_{\varLambda }(w_j)-d^-_{\varLambda }(w_j)|=2$.

  If, on the other hand, the edge connecting $a^j_{l^1}$ to a variable gadget is oriented from $a^j_{l^1}$ (meanings that $v(l^1)={{\mathrm{{\text {FALSE}}}}}$), then we assign $\varLambda (a^j_{l^1}u_j)=\overrightarrow{a^j_{l^1}u_j}$, $\varLambda (a^j_{l^1}v_j)=\overrightarrow{a^j_{l^1}v_j}$, $\varLambda (u_jw_j)=\overrightarrow{w_ju_j}$ and $\varLambda (v_jw_j)=\overrightarrow{w_jv_j}$. By symmetry, we conclude in the same way that $|d^+_{\varLambda }(a^j_{l^1})-d^-_{\varLambda }(a^j_{l^1})|=3$ and $|d^+_{\varLambda }(b^j_{l^2})-d^-_{\varLambda }(b^j_{l^2})|=|d^+_{\varLambda }(b'^j_{l^3})-d^-_{\varLambda }(b'^j_{l^3})|=|d^+_{\varLambda }(u_j)-d^-_{\varLambda }(u_j)|=|d^+_{\varLambda }(v_j)-d^-_{\varLambda }(v_j)|=|d^+_{\varLambda }(w_j)-d^-_{\varLambda }(w_j)|=2$.

  Consequently, the imbalance of the resulting orientation $\varLambda$ is greater than or equal to 2, e.g. Fig. 5c.

• $\Leftarrow$ Now we assume that ${{\mathrm{\textsc {MaxIm}}}}(G_\varphi )=2$, let $\varLambda \in \overrightarrow{O}(G_\varphi )$ with optimal imbalance. Since all the vertices in the variable gadgets have degree at most 3, each vertex $x_i$ (or $\lnot x_i$) is necessarily adjacent to only incoming arcs or only outgoing arcs w.r.t. $\varLambda$. We will show that the assignment $v:\{x_1,\ldots ,x_n\}\rightarrow \{{{\mathrm{{\text {TRUE}}}}},{{\mathrm{{\text {FALSE}}}}}\}$ of $x_1,\ldots ,x_n$ defined by

  $$\begin{aligned} v(x_i)={\left\{ \begin{array}{ll} {{\mathrm{{\text {TRUE}}}}}&{}\text { if }d^+_\varLambda (x_i)>d^-_\varLambda (x_i);\\ {{\mathrm{{\text {FALSE}}}}}&{}\text { otherwise}; \end{array}\right. } \end{aligned}$$

  satisfies $\varphi$. Suppose $\varphi$ does not satisfy a clause $c_j,~j\in \llbracket 1,m\rrbracket$. If $c_j$ is a two-literals clause $(l^1\vee l^2)$ then either $v(l^1)=v(l^2)= {{\mathrm{{\text {TRUE}}}}}$ or $v(l^1)=v(l^2)= {{\mathrm{{\text {FALSE}}}}}$, i.e. either both $a^j_{l^1}$ and $b^j_{l^2}$ have an incoming arc from a variable gadget or both have an outgoing arc to a variable gadget and in both cases, whichever is the orientation assigned to $a^j_{l^1}b^j_{l^2}$ by $\varLambda$, either $a^j_{l^1}$ or $b^j_{l^2}$ has a zero imbalance which contradicts our assumption. So $c_j$ is a three-literals clause $(l^1\vee l^2\vee l^3)$ (the order is identical to the one chosen to build the clause gadget, i.e. $d_{G_\varphi }(a^j_{l^1})=3$ and $d_{G_\varphi }(b^j_{l^2})=d_{G_\varphi }(b'^j_{l^3})=2$). Then either $v(l^1)=v(l^2)=v(l^3)= {{\mathrm{{\text {TRUE}}}}}$ or $v(l^1)=v(l^2)=v(l^3)= {{\mathrm{{\text {FALSE}}}}}$, i.e. either all $a^j_{l^1}$, $b^j_{l^2}$ and $b'^j_{l^3}$ have an incoming arc from a variable gadget or they all have an outgoing arc to a variable gadget. In the first case, it implies $\varLambda (a^j_{l^1}u_j)=\overrightarrow{u_ja^j_{l^1}}$, $\varLambda (a^j_{l^1}v_j)=\overrightarrow{v_ja^j_{l^1}}$, $\varLambda (u_jw_j)=\overrightarrow{u_jw_j}$, $\varLambda (v_jw_j)=\overrightarrow{v_jw_j}$, $\varLambda (w_jb^j_{l^2})=\overrightarrow{w_jb^j_{l^2}}$ and $\varLambda (w_jb'^j_{l^3})=\overrightarrow{w_jb'^j_{l^3}}$, and we obtain $|d^+_{\varLambda }(w_j)-d^-_{\varLambda }(w_j)|=0$ which contradicts the optimality of $\varLambda$. Similarly, in the second case it implies that the orientations assigned to the edges of the clause gadgets are the opposite from the previous ones and we obtain the same contradiction. So we can conclude that v does satisfy $\varphi$.$\square$

Fig. 5

$G_\varphi$ corresponding to $\varphi =(x_1\vee \lnot x_2\vee x_3)\wedge (\lnot x_1\vee \lnot x_3\vee x_4)\wedge (x_1\vee \lnot x_2\vee x_4)\wedge (x_2\vee \lnot x_4)$ satisfied by $v(x_1,x_2,x_3,x_4)= ({{\mathrm{{\text {FALSE}}}}},{{\mathrm{{\text {TRUE}}}}}, {{\mathrm{{\text {TRUE}}}}},{{\mathrm{{\text {TRUE}}}}})$

Corollary 8

${{\mathrm{\textsc {MaxIm}}}}$ is NP-complete and inapproximable within $\frac{1}{2}+\varepsilon$ where $\varepsilon \in \mathbb {R}_+^*$, unless $\texttt {P}=\texttt {NP}$.

Proof

Let $\varepsilon \in \mathbb {R}_+^*$, suppose that there exists a polynomial approximation algorithm giving $val\ge (\frac{1}{2}+\varepsilon ){{\mathrm{\textsc {MaxIm}}}}(G)$ for an input graph G. Let $\varphi$ be a not-all-equal at most 3-SAT(3V) formula and $G_\varphi$ its associated graph. Since $G_\varphi$ contains at least one three-literals clause gadget, we know that $G_\varphi$ contains an even cycle and $\delta _{G_\varphi }=2$. This leads to ${{\mathrm{\textsc {MaxIm}}}}(G_\varphi )\in \{1,2\}$ and since $(\frac{1}{2}+\varepsilon ){{\mathrm{\textsc {MaxIm}}}}(G_\varphi )\le val\le {{\mathrm{\textsc {MaxIm}}}}(G_\varphi )$, if the polynomial approximation algorithm returns a value less than or equal to 1 then

$$\begin{aligned} \left( \frac{1}{2}+\varepsilon \right) {{\mathrm{\textsc {MaxIm}}}}(G_\varphi )\le 1\Rightarrow {{\mathrm{\textsc {MaxIm}}}}(G_\varphi )<2\Rightarrow {{\mathrm{\textsc {MaxIm}}}}(G_\varphi )=1; \end{aligned}$$

and if it returns a value greater than 1, then ${{\mathrm{\textsc {MaxIm}}}}(G_\varphi )$ is greater than 1 hence equal to 2. In other words the polynomial approximation algorithm output answers whether $\varphi$ is satisfiable or not which implies $\texttt {P}=\texttt {NP}$. $\square$

Let us use cut(A) to denote the set of edges having only one endpoint in A. Now we consider the case of bipartite graphs: if is a bipartite graph, the orientation that consists in assigning to each edge in E the orientation from its endpoint in $V_1$ to its endpoint in $V_2$ has an imbalance equal to $\delta _G$, i.e. optimal. This simple case permits us to obtain the following lower bound:

Theorem 9

For every graph G,

$$\begin{aligned} {{\mathrm{\textsc {MaxIm}}}}(G)\ge \lceil \frac{\delta _G}{2}\rceil -1. \end{aligned}$$

Proof

Let $(V_1,V_2)$ be a partition of V corresponding to a cut $C = cut (V_1) \subset E$ such that we have $|cut(\{v\}) \cap C|\ge \lceil \frac{d(v)}{2}\rceil ,\quad \forall v\in V$. Such a cut exists: for example a maximum cardinality cut verifies this property, otherwise we could find a higher cardinality cut by switching a vertex $v\in V$ s.t. $|cut(\{v\})\cap C|<\lceil \frac{d(v)}{2}\rceil$ from $V_1$ to $V_2$ (or the contrary). Moreover, if we iterated this process starting from a random k, we would converge in polynomial time to such a cut. Now we define $\varLambda \in \overrightarrow{O}(G)$ as follows. We begin by orienting all edges in C from $V_1$ to $V_2$. Then for any $i\in \{1,2\}$, we orient the edges of the induced subgraph $G[V_i]$. We add a new vertex $v_0$ and an edge between $v_0$ and each vertex with an odd degree in $G[V_i]$ if it is not eulerian and we consider a decomposition of its edges into edge-disjoint cycles. We orient each of these cycles as a directed cycle. Removing $v_0$ if necessary, the imbalance of each vertex in $G[V_i]$ is now in $\{-1,0,1\}$ which implies that $\forall v\in V$ we have $|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|\ge \lceil \frac{d(v)}{2}\rceil -1$, hence, ${{\mathrm{\textsc {MaxIm}}}}(G)\ge \lceil \frac{\delta _G}{2}\rceil -1$. $\square$

From the proof proposed above, it is easy to see that when $\delta _G \equiv 0 [4]$ then ${{\mathrm{\textsc {MaxIm}}}}(G)\ge \frac{\delta _G}{2}$ while ${{\mathrm{\textsc {MaxIm}}}}(G)\ge \frac{\delta _G - 1}{2}$ when $\delta _G$ is odd and ${{\mathrm{\textsc {MaxIm}}}}(G)\ge \frac{\delta _G}{2} - 1$ when $\delta _G \equiv 2 [4]$. This leads to an approximation algorithm whose ratio is $\frac{1}{2}$ (resp. $\frac{1}{2} - \frac{1}{2 \delta }$, $\frac{1}{2} - \frac{1}{\delta }$ ) when $\delta _G \equiv 0 [4]$, (resp. $\delta _G$ is odd, $\delta _G \equiv 2 [4]$).

4 Exact algorithm for cacti

The class of graphs defined in the previous section is a special case of cacti. A cactus is a connected simple graph for which every edge belongs to at most one simple cycle. Equivalently, a cactus is a connected graph for which every block, or maximal subgraph with no cut-vertex, is a single edge or a cycle. We will start by recalling the structure induced by the blocks of a graph.

Definition 10

Let $G=(V,E)$ be a graph, $V_B$ the set of its blocks and $V_C$ the set of its cutvertices. The block tree of G is the graph where $E'=\{Zu|Z\in V_B,~u\in V_C\text { and }u\in V(Z)\}$.

Fig. 6

Building the block tree

Observe that the block tree of a connected graph is a tree (Diestel 2010).

In Fig. 6 we have an example of a cactus graph G (a), the isolation of its blocks (b) and finally its block tree T (c).

The next lemma is related to the minimum degree of a cactus.

Lemma 11

Let G be a cactus graph,

$$\begin{aligned} \delta _G\le 2. \end{aligned}$$

Proof

Let G be a cactus graph and T its block tree. Let $u\in V(T)$ be a leaf of T. By the definition of a cut vertex, u corresponds necessarily to a block of G. If u corresponds to a bridge of G, then one of its endpoint (the one that is not a cutvertex) is a leaf of G which implies $\delta _G$=1. If u corresponds to a cycle of G, being a leaf of T, it contains only one cutvertex of G and therefore the degree of its other vertices equals 2. $\square$

The previous lemma automatically provides an upper bound for ${{\mathrm{\textsc {MaxIm}}}}(G)$.

Proposition 12

Let G be a cactus,

$$\begin{aligned} {{\mathrm{\textsc {MaxIm}}}}(G)\le 2. \end{aligned}$$

Note that an edge of a cactus is a single edge block if and only if it is a bridge. We have already characterized which of the cacti verify ${{\mathrm{\textsc {MaxIm}}}}(G)=0$, and the previous result states that the only two other possibilities are 1 or 2. The following will permit us to determine which. Let $G=(V,E)$ be a cactus and its block tree, a subset $A\in V_B$ will hereafter refer to a subset of vertices of T as well as the subgraph consisting in the union of the blocks of G corresponding to these vertices. We define for a cactus G the smallest subset $S\subseteq V_B$ containing all even cycles of G in addition to all vertices of T satisfying one the following conditions:

• If $Y\in V_B$ corresponds to an odd cycle of G that shares a cut-vertex with a cycle or with two bridges contained in S, then $Y\in S$,

• if $Y\in V_B$ corresponds to a bridge of G that shares a cut-vertex with a block contained in S, then $Y\in S$.

In Figs. 6a and 7 are examples of two cacti along with their subsets S.

Fig. 7

A graph G such that $\delta _G=2$ and $S=V_B$

Theorem 13

Let G be a cactus,

$$\begin{aligned} {{\mathrm{\textsc {MaxIm}}}}(G)=2\Longleftrightarrow S=V_B\text {~and~}\delta _G=2. \end{aligned}$$

The idea of this result and its proof is that if we have a cactus G, we consider the subgraph $S_0$ of G consisting in the union of all the even cycles of G and that can be oriented with imbalance at least 2. Then we can extend the orientation of $S_0$ into an orientation of S, keeping an imbalance of at least two for each vertex with at least two oriented edges. Now if $\delta _G=2$ and $S=V_B$, we obtain an orientation of G with imbalance at least 2. Moreover, for a cactus G, the subset S can be computed in polynomial time by a basic search on the block tree of G which means that we can derive a polynomial time algorithm solving ${{\mathrm{\textsc {MaxIm}}}}$ for any input cactus.

In order to prove Theorem 13, we first show two lemmas that will be useful in the proof of our theorem.

Fig. 8

A graph G and a bridge $cc'$

Lemma 14

Let $G=(V,E)$ be a graph, $cc'\in E$ a bridge of G. Let us call $G_c$ the connected component of $G\backslash cc'$ containing c and $G_{c'c}$ the graph obtained by adding c and $cc'$ to the connected component of $G\backslash cc'$ containing $c'$ (see Fig. 8). Then

$$\begin{aligned} {{\mathrm{\textsc {MaxIm}}}}(G)\le \max _{\varLambda \in \overrightarrow{O}(G_c)}\min (\min _{v\in V(G_c)\backslash \{c\}}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|,|d^+_{\varLambda }(c)-d^-_{\varLambda }(c)|+1). \end{aligned}$$

Proof

Let $\varLambda \in \overrightarrow{O}(G)$ be an optimal orientation of G w.r.t. ${{\mathrm{\textsc {MaxIm}}}}$. If $d^+_{\varLambda _{|G_{c'c}}}(c)-d^-_{\varLambda _{|G_{c'c}}}(c)$ and $d^+_{\varLambda _{|G_c}}(c)-d^-_{\varLambda _{|G_c}}(c)$ do not have the same sign, then we switch the assignment of $\varLambda$ of the edges of $G_{c'c}$. Doing so, the imbalance of all the vertices of G is unchanged except for that of c which got risen by 2 hence $\varLambda$ is still optimal and $|d^+_{\varLambda }(c)-d^-_{\varLambda }(c)|\le |d^+_{\varLambda _{|G_c}}(c)-d^-_{\varLambda _{|G_c}}(c)|+1$. Moreover,

$$\begin{aligned} {{\mathrm{\textsc {MaxIm}}}}(G)=\min _{v\in V}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|\le \min _{v\in V(G_c)\backslash \{c\}}|d^+_{\varLambda _{|G_c}}(v)-d^-_{\varLambda _{|G_c}}(v)| \end{aligned}$$

which yields

$$\begin{aligned} {{\mathrm{\textsc {MaxIm}}}}(G)\le & {} \min (\min _{v\in V(G_c)\backslash \{c\}}|d^+_{\varLambda _{|G_c}}(v)-d^-_{\varLambda _{|G_c}}(v)|,|d^+_{\varLambda _{|G_c}}(c)-d^-_{\varLambda _{|G_c}}(c)|+1)\\\le & {} \max _{\varLambda \in \overrightarrow{O}(G_c)}\min (\min _{v\in V(G_c)\backslash \{c\}}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|,|d^+_{\varLambda }(c)-d^-_{\varLambda }(c)|+1). \end{aligned}$$

$\square$

Lemma 15

Let G be a cactus such that $\delta _G=2$. Then there exists a cycle of G with at most one gate (vertex adjacent to any vertex not belonging to the cycle).

Proof

Let T be the block tree of G. If T has no leaf, then it is a vertex graph, hence G is a cycle which necessarily has no gate. If T has a leaf l, it necessarily corresponds to a block of G. If l was a bridge, the degree of its endpoint in G which is not a cutvertex would be 1, hence l is a cycle of G. And being a leaf in T, it has at most one gate in G. $\square$

Proof of Theorem 13

• $\Leftarrow$ We assume that $S=V_B$ and $\delta _G\ge 2$. From Proposition 12, we know that ${{\mathrm{\textsc {MaxIm}}}}(G)\le 2$. We will build an orientation $\varLambda \in \overrightarrow{O}(G)$ such that $\min _{v\in V}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|=2$. We start by orienting the edges of the subgraph $S_0$ consisting in the union of all the even cycles of G. $S_0$ having no odd cycles, it is bipartite and we can therefore choose an orientation of the edges of $S_0$ such that $|d^+_{\varLambda _{|S_0}}(v)-d^-_{\varLambda _{|S_0}}(v)|=d_{S_0}(v)\ge 2,\quad \forall v\in V(S_0)$. We now recursively extend $\varLambda$ to the rest of the blocks in S ensuring an imbalance of at least 2 for each vertex adjacent to at least two oriented edges. Let $Z\in V_B$ be an unoriented block of G that is either:

  • an odd cycle of G sharing a cut-vertex with an oriented cycle or two oriented bridges,

  • a bridge sharing a cut vertex with an oriented block.

  If there was no such block and the graph G was not totally oriented, the set of oriented blocks of G denoted by $\overrightarrow{S}$ would contradict the minimality of S.

  If Z is an odd cycle, we choose a cut vertex c of Z adjacent to oriented edges and name the vertices of B $c=v_1v_2\cdots v_k=c$. We assign:

  • $\varLambda (v_iv_{i+1})= {\left\{ \begin{array}{ll} \overrightarrow{v_iv_{i+1}} &{}\text { if }i\text { is odd};\\ \overrightarrow{v_{i+1}v_i} &{}\text {otherwise} \end{array}\right. } ,\quad \forall i\in \llbracket 1,k-1\rrbracket$.

  Let us now consider the imbalance of the vertices of Z. Since c is adjacent to either a cycle or two bridges in $\overrightarrow{S}$, it is adjacent to at least two edges in $\overrightarrow{S}$ and therefore $|d^+_{\varLambda _{|\overrightarrow{S}}}(c)-d^-_{\varLambda _{|\overrightarrow{S}}}(c)|\ge 2$ according to our inductive hypothesis. Since $|d^+_{\varLambda _{|Z}}(c)-d^-_{\varLambda _{|Z}}(c)|=0$, $|d^+_{\varLambda }(c)-d^-_{\varLambda }(c)|=|d^+_{\varLambda _{|\overrightarrow{S}}}(c)-d^-_{\varLambda _{|\overrightarrow{S}}}(c)|\ge 2$. If there is another cut-vertex $c'$ of Z that is adjacent to a block in $\overrightarrow{S}$ such that $d^+_{\varLambda _{|\overrightarrow{S}}}(c')-d^-_{\varLambda _{|\overrightarrow{S}}}(c')$ and $d^+_{\varLambda _{|Z}}(c')-d^-_{\varLambda _{|Z}}(c')$ do not have the same sign, then we switch the assignment of $\varLambda$ of the edges of the whole connected component of $\overrightarrow{S}$ containing $c'$ for its opposite. Necessarily, $c'$ is the only vertex this connected component shares with Z otherwise Z would be contained in a bigger block of G. Then doing so, the imbalance of all vertices is left unchanged except for that of $c'$ which is now equal to $|d^+_{\varLambda _{|\overrightarrow{S}}}(c')-d^-_{\varLambda _{|\overrightarrow{S}}}(c')|+|d^+_{\varLambda _{|Z}}(c')-d^-_{\varLambda _{|Z}}(c')|=|d^+_{\varLambda _{|\overrightarrow{S}}}(c')-d^-_{\varLambda _{|\overrightarrow{S}}}(c')|+2$.

  This process is repeated for all the cut-vertices $c'$ of Z different from c adjacent to a block in $\overrightarrow{S}$ to be such that $|d^+_{\varLambda }(c')-d^-_{\varLambda }(c')| \ge 2$. If $u\in V(Z)$ is not a cut-vertex, then $|d^+_{\varLambda }(u)-d^-_{\varLambda }(u)|=|d^+_{\varLambda _{|Z]}}(u)-d^-_{\varLambda _{|Z]}}(u)|=2$ and $\varLambda$ becomes an orientation of $\overrightarrow{S}\cup \{Z\}$ with imbalance at least two for all the vertices of G adjacent to at least two oriented edges.

  If Z is a bridge, we take c one of its endpoints adjacent to an oriented edge, we call u the other one and assign

  $$\begin{aligned} \varLambda (cu)={\left\{ \begin{array}{ll} \overrightarrow{cu} &{}\text { if } d^+_{\varLambda _{|\overrightarrow{S}}}(c)>d^-_{\varLambda _{|\overrightarrow{S}}}(c);\\ \overrightarrow{uc} &{}\text { otherwise}. \end{array}\right. } \end{aligned}$$

  Concerning the imbalance of c, by inductive hypothesis, $|d^+_{\varLambda _{\overrightarrow{S}}}(c)-d^-_{\varLambda _{\overrightarrow{S}}}(c)|\ge 1$, then $|d^+_{\varLambda }(c)-d^-_{\varLambda }(c)|=|d^+_{\varLambda _{|\overrightarrow{S}}}(c)-d^-_{\varLambda _{|\overrightarrow{S}}}(c)|+|d^+_{\varLambda _{|Z}}(c)-d^-_{\varLambda _{|Z}}(c)|\ge 2$. If u is adjacent to a block in $\overrightarrow{S}$ as well and $d^+_{\varLambda _{|\overrightarrow{S}}}(u)-d^-_{\varLambda _{|\overrightarrow{S}}}(u)$ and $d^+_{\varLambda _{|Z}}(u)-d^-_{\varLambda _{|Z}}(u)$ do not have the same sign then we switch the assignment of $\varLambda$ of the edges of the whole connected component of $\overrightarrow{S}$ containing u for its opposite. This connected component necessarily doesn’t contain c otherwise z would be contained in a bigger block of G. Then doing so, the imbalance of all vertices is left unchanged except for that of u which is now equal to $|d^+_{\varLambda _{|\overrightarrow{S}}}(u)-d^-_{\varLambda _{|\overrightarrow{S}}}(u)|+|d^+_{\varLambda _{|Z}}(u)-d^-_{\varLambda _{|Z}}(u)|=|d^+_{\varLambda _{|\overrightarrow{S}}}(u)-d^-_{\varLambda _{|\overrightarrow{S}}}(u)|+1\ge 2$. $\varLambda$ thus becomes an orientation of $\overrightarrow{S}\cup \{Z\}$ with imbalance at least two for all the vertices of G adjacent to at least two oriented edges.

  We now add Z to $\overrightarrow{S}$ and proceed like this for all blocks Z in $S\backslash \overrightarrow{S}$ until $\overrightarrow{S}=S$. Now since $V_B=S$ and $\delta _G=2$, we conclude that $\varLambda$ is an orientation of all the edges of G with an imbalance equal to 2. In Fig. 9 can be found the orienting process of the cactus presented in Fig. 7. First, the even cycles are oriented (Fig. 9a), then the blocks adjacent to the even cycles (Fig. 9b) and then iteratively the unoriented blocks adjacent to oriented blocks (Fig. 9c–f). In Fig. 9c, e, the vertices with imbalance zero are circled in red, and in the next step, the orientation is reversed on one of the subtree where the circled vertex is the root in order to ensure an orientation imbalance of at least 2.

• $\Rightarrow$ If $\delta _G<2$ then ${{\mathrm{\textsc {MaxIm}}}}(G)<2$. So we assume that $\delta _G=2$ and $S\varsubsetneq V_B$. Let $c\in V(\bar{S})\cap V(S)$. Belonging to both V(S) and $V(\bar{S})$, c must belong to at least two different blocks of G and is therefore a cutvertex of G. Let Z be a block in S adjacent to c, Z is necessarily a bridge of G otherwise all the blocks adjacent to Z would be in S thus contradicting $c\in V(\bar{S})$, and for the same reason, Z is the only bridge in S adjacent to c. Calling $c'$ the endpoint of Z that is not c and $G_c$ the subgraph of G obtained by taking the connected component of $G\backslash cc'$ containing c, we are in the conditions of Lemma 14 and thus we obtain

  $$\begin{aligned} {{\mathrm{\textsc {MaxIm}}}}(G)\le \max _{\varLambda \in \overrightarrow{O}(G_c)}\min \left( \min _{v\in V(G_c)\backslash \{c\}}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|,|d^+_{\varLambda }(c)-d^-_{\varLambda }(c)|\!+\!1\!\right) \!. \end{aligned}$$

  Proceeding like this for all $c\in V(\bar{S})\cap V(S)$ yields that ${{\mathrm{\textsc {MaxIm}}}}(G)$ is smaller than

  $$\begin{aligned} \max _{\varLambda \in \overrightarrow{O}(\bar{S})}\min \left( \min _{v\in V(\bar{S})\backslash V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|,\min _{v\in V(\bar{S})\cap V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|+1\right) . \end{aligned}$$

  Now if we choose a connected component $\bar{S}_0$ of $\bar{S}$ we get that ${{\mathrm{\textsc {MaxIm}}}}(G)$ is smaller than

  $$\begin{aligned} \max _{\varLambda \in \overrightarrow{O}(\bar{S}_0)}\min \left( \min _{v\in V(\bar{S}_0)\backslash V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|,\min _{v\in V(\bar{S}_0)\cap V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|+1\right) . \end{aligned}$$

  Now we show that the right-hand part of the previous inequality is lower than or equal to 1. Suppose it equals 2 and let $\varLambda \in \overrightarrow{O}(\bar{S}_0)$ satisfying

  $$\begin{aligned} \min \left( \min _{v\in V(\bar{S}_0)\backslash V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|,\min _{v\in V(\bar{S}_0)\cap V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|+1\right) \ge 2. \end{aligned}$$

  (3)

  Thus we have $d_{\bar{S}_0}(v)\ge 2,\quad \forall v\in V(\bar{S}_0)\backslash V(S)$ and we know that for any $v\in V(\bar{S}_0)\cap V(S)$, all the blocks in $\bar{S}_0$ adjacent to v are odd cycles, hence $d_{\bar{S}_0}(v)\ge 2$. So $\delta _{\bar{S}_0}\ge 2$ and according to Lemma 15, there is a cycle C of $\bar{S}_0$ with at most one gate. If C has no gate then it means that $\bar{S}_0$ consists only of C and since we know that all the cycles of $\bar{S}_0$ are odd, it directly contradicts the existence of $\varLambda$. Hence C has exactly one gate g. So for all $v\in V(C)\backslash \{g\}$, $|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|=|d^+_{\varLambda _{|C}}(v)-d^-_{\varLambda _{|C}}(v)|$ and if we name the vertices of C $g=v_1v_2\cdots v_k=g$ the assignment of $\varLambda$ must be

  • $\varLambda (v_iv_{i+1})= {\left\{ \begin{array}{ll} \overrightarrow{v_iv_{i+1}} &{}\text { if }i\text { is odd};\\ \overrightarrow{v_{i+1}v_i} &{}\text {otherwise} \end{array}\right. } ,\quad \forall i\in \llbracket 1,k-1\rrbracket$.

  or its reverse so that $\varLambda$ satisfies our assumption. Thus we have

  $$\begin{aligned}&\max _{\varLambda \in \overrightarrow{O}(\bar{S}_0)}\min \left( \min _{v\in V(\bar{S}_0)\backslash V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|,\min _{v\in V(\bar{S}_0)\!\cap \! V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|\!+\!1\!\right) \\&\quad =\max _{\varLambda \in \overrightarrow{O}(\bar{S}_0\backslash C)}\min \left( \min _{v\in V(\bar{S}_0\backslash C)\backslash V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|,\right. \\&\qquad \left. \min _{v\in V(\bar{S}_0\backslash C)\cap V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|+1\right) . \end{aligned}$$

  If there exists a vertex of degree one in $\bar{S}_0\backslash C$ then it is adjacent to a bridge in $\bar{S}_0$ and is thereofre in $V(\bar{S}\backslash C)\backslash V(S)$, thus contradicting (3). So we assume that $\delta _{\bar{S}_0\backslash C}=2$ and we can reiterate the same process with another odd cycle with exactly one gate until we are left with an odd cycle $C_{end}$ with no gates and conclude that

  $$\begin{aligned}&\max _{\varLambda \in \overrightarrow{O}(C_{end})}\min \left( \min _{v\in V(C_{end})\backslash V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|,\right. \\&\quad \left. \min _{v\in V(C_{end})\cap V(S)}|d^+_{\varLambda }(v)-d^-_{\varLambda }(v)|+1\right) \ge 2; \end{aligned}$$

  Since this is impossible for an odd cycle, we deduce that (3) is wrong. Hence, ${{\mathrm{\textsc {MaxIm}}}}(G)\le 1$. $\square$

Fig. 9

Orienting the edges of G verifying $\delta _G=2$ and $S=V_B$ in such a way that ${{\mathrm{\textsc {MaxIm}}}}(G)=2$

As already mentioned, Theorem 13 leads to a simple polynomial-time algorithm to compute ${{\mathrm{\textsc {MaxIm}}}}(G)$ for cacti. Starting from the set $S_0$ of even cycles, we add blocks to S using the two operations defined above: bridges sharing a cut-vertex with a block in S, and odd cycles sharing a cut-vertex with either a cycle or two bridges that are already in S, are added to S.

5 Mixed integer linear programming formulations

In this section, we gradually introduce two formulations for the ${{\mathrm{\textsc {MaxIm}}}}$ problem. For our purposes, we shall consider the original graph $G=(V,E)$ is directed (consider any arbitrary orientation) and let $B\in \{-1,0,1\}^{|V|\times |E|}$ stand for its incidence matrix, i.e., the column corresponding to the arc uv (or, equivalently, to the edge uv directed from node u to node v), has only nonzero entries in the rows corresponding to the nodes u and v: $B_{u, uv}=1$ and $B_{v, uv}=-1$, respectively.

In order to describe an orientation of the graph G, we take orientation variables $x\in \{-1,1\}^{|E|}$ interpreted as follows. For each edge $uv\in E$ which is originally directed from node u to node v: if $x_{ uv}=1$ then uv is directed from u to v (i.e., the orientation is the same as the original one) and is directed from v to u otherwise (i.e., the edge is “reversed” with respect to the original orientation). Then if we look at the product of B with an orientation vector $x\in \{-1,1\}^{|E|}$ we obtain $B_vx=d^+_x(v)-d^-_x(v),\quad \forall v\in V$, where $d^+_x(v)$ (resp. $d^-_x(v)$) is the outdegree (resp. indegree) of $v\in V$ in G w.r.t. the orientation described by x and $B_v$ denotes the row of the matrix B which corresponds to node v. Hence the ${{\mathrm{\textsc {MaxIm}}}}$ problem can be expressed as the following non-linear formulation.

$$\begin{aligned}\left\{ \begin{array}{l} \max h\\ \text {s.t. }\\ h\le |B_vx|,\quad \forall v\in V\\ x\in \{-1,1\}^{|E|}. \end{array} \right. \end{aligned}$$

Let us derive from the preceding non-linear formulation an equivalent linear formulation. To that purpose, we remove the absolute value of the constraint by squaring it : $h^2\le (B_vx)^2,\quad \forall v\in V$. Since it still is not linear, we have to consider variables representing the product of two variables and for that we substitute the x variables by their 0-1 version. So developing, we obtain

$$\begin{aligned} (B_v(2x-\mathbf {1}))^2= & {} \left( \sum _{ uv\in E}B_{v, uv}(2x_{ uv}-1)\right) ^2\\= & {} \sum _{ uv\in E}B_{v, uv}^2(2x_{ uv}\!-\!1)^2\!+\! 2\sum _{\begin{array}{c} uv, wv\in E\\ uv\ne wv \end{array}}B_{v, uv}B_{v, wv}(2x_{ uv}\!-\!1)(2x_{ wv}\!-\!1)\\= & {} \sum _{ uv\in E}(4x_{ uv}^2-4x_{ uv}+1)\\&+2\sum _{\begin{array}{c} uv, wv\in E\\ uv\ne wv \end{array}}B_{v, uv}B_{v, wv}(4x_{ uv}x_{ wv}-2x_{ uv}-2x_{ wv}+1)\\= & {} d(v)+2\sum _{\begin{array}{c} uv, wv\in E\\ uv\ne wv \end{array}}B_{v, uv}B_{v, wv}(4x_{ uv}x_{ wv}-2x_{ uv}-2x_{ wv}+1). \end{aligned}$$

Furthermore, since maximizing h is equivalent to maximizing its square root, substituting $h^2$ by h, we obtain the following formulation.

$$\begin{aligned} \left\{ \begin{array}{l} \max h\\ \text {s.t. }\\ h\le d(v)+2\sum _{\begin{array}{c} uv, wv\in E\\ uv\ne wv \end{array}}B_{v, uv}B_{v, wv}(4x_{ uv}x_{ wv}-2x_{ uv}-2x_{ wv}+1),\quad \forall v\in V\\ x\in \{0,1\}^{|E|}. \end{array} \right. \end{aligned}$$

In order to linearize it, we introduce product variables $z_{ uv, wp}\in \{0,1\},~ uv, wp\in E,~ uv\ne wp$ representing the variables product $x_{ uv}x_{ wp}$. For a pair of edges $(uv, wp)\in E^2,~ uv\ne wp$, we add the constraints $z_{ uv, wp}\le x_{ uv},~z_{ uv, wp}\le x_{ wp}$ and $z_{ uv, wp}\ge x_{ uv}+x_{ wp}-1$ so as to force $z_{ uv, wp}=x_{ uv}x_{ wp}$. We can relax the integer constraint on the z variables and we obtain the following mixed integer linear programming formulation.

$$\begin{aligned} ({{\mathrm{{\text {MIP1}}}}})\left\{ \begin{array}{l} \max h\\ \text {s.t. }\\ h\!\le \!d(v)\!+\!2\sum _{\begin{array}{c} uv, wv\in E\\ uv\ne wv \end{array}}B_{v, uv}B_{v, wv}(4z_{ uv, wv}\!-\!2x_{ uv}-2x_{ wv}+1),\quad \forall v\in V\\ \begin{array}{l} z_{ uv, wp}\le x_{ uv}\\ z_{ uv, wp}\le x_{ wp}\\ z_{ uv, wp}\ge x_{ uv}+x_{ wp}-1\\ \end{array} ,\quad \forall uv, wp\in E,~ uv\ne wp\\ x\in \{0,1\}^{|E|},~z_{ uv, wp}\ge 0,~ uv, wp\in E,~ uv\ne wp,~h\in \mathbb {R}. \end{array} \right. \end{aligned}$$

Theorem 16

For any graph G,

$$\begin{aligned} {{\mathrm{{\text {MIP1}}}}}(G)={{\mathrm{\textsc {MaxIm}}}}(G), \end{aligned}$$

Where ${{\mathrm{{\text {MIP1}}}}}(G)$ is the square root optimal of the objective value of ${{\mathrm{{\text {MIP1}}}}}$ for G.

Proof

$x\in \{0,1\}^{|E|}$ covers all the possible orientations of G and for every vertex $v\in V$, the first constraint is equivalent to $h\le (d^+_x(v)-d^-_x(v))^2$. $\square$

Thus we have a first mixed integer linear programming formulation for our problems with $O(m^2)$ variables, O(m) of which are integer variables and $O(m^2)$ constraints.

Let us take a look at the linear program obtained by relaxing the integer constraint of ${{\mathrm{{\text {MIP1}}}}}$ on an input graph $G=(V,E)$, and let us consider the triplet $(x^{lp},z^{lp},h^{lp})$ where $x^{lp}_{ uv}=\frac{1}{2},\quad \forall uv\in E$; $z^{lp}_{ uv, wp}=0$ for all pairs of edges $uv, wp\in E$ that share no endpoint; $z^{lp}_{ uv, wv}=\frac{1+B_{v, uv}B_{v, wv}}{4}$ for all pairs of edges $uv, wv\in E$ (i.e. all pairs of edges in E that share an endpoint), and $h^{lp}=\delta _G^2$.

Lemma 17

$(x^{lp},z^{lp},h^{lp})$ is a feasible solution of the linear relaxation of $\texttt {MIP1}$ whith objective value $\delta _G^2$.

Proof

Observe that $\forall uv, wp\in E$,

$$\begin{aligned}0=x^{lp}_{ uv}+x^{lp}_{ wp}-1\le z^{lp}_{ uv, wp}\le x^{lp}_{ uv}=x^{lp}_{ wv}=\frac{1}{2}. \end{aligned}$$

Moreover, $\forall v\in V$,

$$\begin{aligned}&d(v)+2\sum _{\begin{array}{c} uv, wv\in E\\ uv\ne wv \end{array}}B_{v, uv}B_{v, wv}(4z^{lp}_{ uv, wv}-2x^{lp}_{ uv}-2x^{lp}_{ wv}+1)\\&=d(v)+2\sum _{\begin{array}{c} uv, wv\in E\\ uv\ne wv \end{array}}B_{v, uv}B_{v, wv}(1+B_{v, uv}B_{v, wv}-1-1+1)\\&=d(v)+2\sum _{\begin{array}{c} uv, wv\in E\\ uv\ne wv \end{array}}(B_{v, uv}B_{v, wv})^2\\&=d(v)+2\sum _{\begin{array}{c} uv, wv\in E\\ uv\ne wv \end{array}}1\\&=d(v)+(d(v)-1)d(v)\\&=d(v)^2\ge \delta _G^2. \end{aligned}$$

$\square$

The previous lemma proves that the optimal value of the linear relaxation of $\texttt {MIP1}$ is at least the minimum degree of the input graph squared, which corresponds to the trivial upper bound of ${{\mathrm{\textsc {MaxIm}}}}(G)$.

We present a second formulation with reduced number of variables and constraints. This second formulation involves the same orientation variables $x\in \{-1,1\}^{|E|}$ we described earlier and a second type of variables that are binary: indicator variables $y_k^v$ with $v\in V$ a vertex of G and $k\in \llbracket -d(v),d(v)\rrbracket$. They have the following interpretation: $y^v_k=1$ if and only if $B_vx=d^+_x(v)-d^-_x(v)=k$, so that the following equation trivially holds

$$\begin{aligned} {\sum }_{\begin{array}{c} k\in \llbracket -d(v),d(v)\rrbracket \end{array}}ky^v_k=B_vx,\forall v\in V. \end{aligned}$$

Given the interpretation for the variables y, among those of the form $y^v_k$, for some fixed node $v\in V$, exactly one of them has value 1. Thus, the following constraints are satisfied

$$\begin{aligned} {\sum }_{\begin{array}{c} k\in \llbracket -d(v),d(v)\rrbracket \end{array}}y^v_k=1,\quad \forall v\in V. \end{aligned}$$

Notice that for a vertex $v\in V$, the difference between its oudegree and indegree w.r.t. any orientation and its degree have the same parity. Thus instead of running k through $\llbracket -d(v),d(v)\rrbracket$, we can limit to $k\in \llbracket -d(v),d(v)\rrbracket ,~\text {s.t. }k\equiv d(v)[2]$, i.e. the only possible values of $d^+_x(v)-d^-_x(v)$ when x runs through $\{-1,1\}^{|E|}$. Then we can show the ${{\mathrm{\textsc {MaxIm}}}}$ problem may be formulated as the mixed integer program

$$\begin{aligned} ({{\mathrm{{\text {MIP2}}}}})\left\{ \begin{array}{l} \max h\\ \text {s.t. }\\ h\le \sum _{\begin{array}{c} k\in \llbracket -d(v),d(v)\rrbracket \\ k\equiv d(v)[2] \end{array}}\min (|k|, \delta _G)y_k^v,\quad \forall v\in V\\ \sum _{\begin{array}{c} k\in \llbracket -d(v),d(v)\rrbracket \\ k\equiv d(v)[2] \end{array}}y^v_k=1,\quad \forall v\in V\\ \sum _{\begin{array}{c} k\in \llbracket -d(v),d(v)\rrbracket \\ k\equiv d(v)[2] \end{array}}ky^v_k=B_v x,\quad \forall v\in V\\ x\in [-1;1]^{|E|},y^v_k\in \{0,1\},\forall (v,k)\in V\times \llbracket -d(v),d(v)\rrbracket ,\text { s.t. }k\equiv d(v)[2],h\in \mathbb {R}. \end{array} \right. \end{aligned}$$

Theorem 18

For any graph G,

$$\begin{aligned} {{\mathrm{{\text {MIP2}}}}}(G)={{\mathrm{\textsc {MaxIm}}}}(G), \end{aligned}$$

Where ${{\mathrm{{\text {MIP2}}}}}(G)$ is the optimal objective value of ${{\mathrm{{\text {MIP2}}}}}$ for G.

Proof

First, if the orientation variables x were constrained to be integers, since $y^v_k=1$ if and only if $B_v x=d^+_x(v)-d^-_x(v)=k$ and $x\in \{0,1\}^{|E|}$ covers all the possible orientations of G and for every vertex $v\in V$, the first and third constraints lead to $h\le |d^+_x(v)-d^-_x(v)|$ and the optimal objective value of the resulting formulation would equal ${{\mathrm{\textsc {MaxIm}}}}(G)$.

Now we know that the incidence matrix B is totally unimodular. Hence, there exists an integer optimal solution $(x^\star ,y^\star ,h^\star )$ of ${{\mathrm{{\text {MIP2}}}}}$. If $x^\star \in \{-1,1\}^{|E|}$ then $(x^\star ,y^\star ,h^\star )$ is solution of the all-integer version of ${{\mathrm{{\text {MIP2}}}}}$ mentioned above and therefore optimal, i.e. its objective value is ${{\mathrm{\textsc {MaxIm}}}}(G)$. Otherwise $x^\star$ describes a partial orientation of G, i.e. for an edge $uv\in E$, if $x^\star _{ uv}=1$ then the original orientation of the edge is preserved, if $x^\star _{ uv}=-1$ then it is reversed and if $x^\star _{ uv}=0$ then the edge is left unoriented. We know that for each vertex $v\in V$, $B_vx^\star \equiv d(v)[2]$. So the number of edges adjacent to v on which $x^\star$ is non-zero must have the same parity as the degree of v. In other words, the number of edges adjacent to v on which $x^\star$ is zero must be even. That is to say, let $E'=\{ uv\in E|x^\star _{ uv}=0\}$ and $G'=(V,E')$, $d_{G'}(v)\equiv 0[2]$ for each vertex $v\in V$. Since $G'$ is eulerian, we can take a cycle of $G'$, orient it in a way that does not change the imbalance of any vertex, remove it and proceed like this until there are no more edges in $G'$. The resulting (complete) orientation can be described by an orientation vector $x'\in \{-1,1\}^{|E|}$ and the triplet $(x',y^\star ,h^\star )$ is a solution of the all-integer version of ${{\mathrm{{\text {MIP2}}}}}$ having the same objective value as $(x^\star ,y^\star ,h^\star )$, hence it is optimal and therefore equal to ${{\mathrm{\textsc {MaxIm}}}}(G)$. $\square$

We now have a second mixed integer linear programming formulation of ${{\mathrm{\textsc {MaxIm}}}}$ with $O(m+n)$ variables, O(m) of which are integer variable and O(n) constraints.

Let us consider the triplet $(x^{lp},y^{lp},h^{lp})$ where $x^{lp}_{ uv}=0,\quad \forall uv\in E$; $y_k^{v,lp}=0,\quad \forall (v,k)\in V\times \llbracket -d(v)+1,d(v)-1\rrbracket ,$ s.t. $k\equiv d(v)[2]$; and $y_{-d(v)}^{v,lp}=y_{d(v)}^{v,lp}=\frac{1}{2},\quad \forall v\in V$. Observe that $(x^{lp},y^{lp},h^{lp})$ is a feasible solution of the linear relaxation of ${{\mathrm{{\text {MIP2}}}}}$ whith objective value $\delta _G$. In other words, the linear relaxation ${{\mathrm{{\text {MIP2}}}}}$ is generally weak. Let us then try to strengthen it using some valid inequalities.

Remember from Sect. 2 that it is easy to check whether ${{\mathrm{\textsc {MaxIm}}}}(G) =0$. One can then set variables $y^v_0$ to 0 when ${{\mathrm{\textsc {MaxIm}}}}(G) >0$. We also know from the discussion at the end of Sect. 3 that ${{\mathrm{\textsc {MaxIm}}}}(G)$ can almost not be less than $\frac{\delta _G}{2}$. More precisely, if $\delta _G \equiv 0 [4]$ then ${{\mathrm{\textsc {MaxIm}}}}(G)\ge \frac{\delta _G}{2}$ while ${{\mathrm{\textsc {MaxIm}}}}(G) \ge \frac{\delta _G - 1}{2}$ when $\delta _G$ is odd and ${{\mathrm{\textsc {MaxIm}}}}(G)\ge \frac{\delta _G}{2} - 1$ when $\delta _G \equiv 2 [4]$.

More generally, if l is a known lower bound for ${{\mathrm{\textsc {MaxIm}}}}(G)$, then all variables $y^v_k$ for $|k| < l$ can be fixed to 0. To find such a lower bound, we use a standard greedy algorithm to find a locally maximum cut and orient edges as described in the proof of Theorem 9.

Let u be an upper bound for ${{\mathrm{\textsc {MaxIm}}}}(G)$. We already know that ${{\mathrm{\textsc {MaxIm}}}}(G) \le \delta _G$, so we can assume that $u \le \delta _G$. Consider the following inequality

$$\begin{aligned} h\le u-\sum _{v=1}^n\sum _{\begin{array}{c} k\in \llbracket 0,u-1\rrbracket \\ k\equiv d(v)[2] \end{array}}\lambda _k^v (y_k^v+y^v_{-k}),\quad \forall \lambda \in \varLambda _u \end{aligned}$$

(4)

where the vertices of G are numbered from 1 to $|V|=n$, and

$$\begin{aligned}&\varLambda _u\\&=\left\{ \lambda =(\lambda ^v_k)_{(v,k)\in \llbracket 1,n\rrbracket \times \llbracket 0,u-1\rrbracket } \in \mathbb {N}^{n u}\left| \begin{array}{l} \lambda ^v_{k+1}\le \lambda ^v_k,\quad \forall (v,k)\in \llbracket 1,n\rrbracket \times \llbracket 0, u-2\rrbracket \\ \sum _{v=1}^n\lambda ^v_k=u-k,\quad \forall k\in \llbracket 0,u-1\rrbracket \end{array}\right. \right\} . \end{aligned}$$

Observe that coefficients $\lambda ^v_k$ are non-negative integer numbers and are non increasing in k. For each k, there exists only one v such that $\lambda ^v_{k+1} = \lambda ^v_{k}-1$ while $\lambda ^w_{k+1} = \lambda ^w_{k}$ for any $w \ne v$. Let us prove that inequalities (4) are valid inequalities for the convex hull of feasible solutions of ${{\mathrm{{\text {MIP2}}}}}$ denoted by ${\mathscr {P}}_2$.

Proposition 19

Inequalities (4) are valid for ${\mathscr {P}}_2$.

Proof

Consider a feasible solution (x, y, h) of ${\mathscr {P}}_2$. If $y^v_k = 0$ and $y^v_{-k} = 0$ for any $v \in \llbracket 1,n\rrbracket$ and any $k \in \llbracket 0,u-1\rrbracket$, then $\sum _{v=1}^n\sum _{\begin{array}{c} k\in \llbracket 0,u-1\rrbracket \\ k\equiv d(v)[2] \end{array}}\lambda _k^v (y_k^v+y^v_{-k})=0$ and inequality (4) becomes $h \le u$. The last is valid since u is an upper bound for ${{\mathrm{\textsc {MaxIm}}}}(G)$.

Let us now assume that $h \le u - 1$, then there exist $v \in \llbracket 1,n\rrbracket$ and $k \le u - 1$ such that either $y^v_{k}$ or $y^v_{-k}$ is equal to 1 while $y^{w}_{k'} = 0$ for any $w \in \llbracket 1,n\rrbracket$ and $k'$ such that $|k'| <k$.

Using the fact that $y^w_k$ is non increasing, we deduce that $\sum _{\begin{array}{c} k'\in \llbracket 0,u-1\rrbracket \\ k'\equiv d(w)[2] \end{array}}\lambda _{k'}^w (y_{k'}^w+y^w_{-k'}) \le \lambda _k^w \sum _{\begin{array}{c} k'\in \llbracket k,u-1\rrbracket \\ k'\equiv d(w)[2] \end{array}} (y_{k'}^w+y^w_{-k'}) \le \lambda _k^w$. Summing up these inequalities for all w and using the fact that $\sum _{v=1}^n\lambda ^v_k=u-k$ leads to $h \le k$ which is valid by k definition. $\square$

Observe that the first family of inequalities included in ${{\mathrm{{\text {MIP2}}}}}$ can be seen as a special case of inequalities (4).

Let us now study the separation problem of inequalities (4).

Proposition 20

Inequalities (4) can be separated in polynomial time.

Proof

Given a fractional solution (x, y, h), one can check whether an inequality of type (4) is violated by looking for coefficients $\lambda \in \varLambda _u$ maximizing $\sum _{v=1}^n\sum _{\begin{array}{c} k\in \llbracket 0,u-1\rrbracket \\ k\equiv d(v)[2] \end{array}}\lambda _k^v (y_k^v+y^v_{-k})$. Remember that for each k, there exists only one v such that $\lambda ^v_{k+1} = \lambda ^v_{k}-1$ while $\lambda ^w_{k+1} = \lambda ^w_{k}$ for any $w \ne v$. Let $v_{k}$ be such v. Then $\sum _{v=1}^n\sum _{\begin{array}{c} k\in \llbracket 0,u-1\rrbracket \\ k\equiv d(v)[2] \end{array}}\lambda _k^v (y_k^v+y^v_{-k})$ can be written as $\sum _{\begin{array}{c} k\in \llbracket 0,u-1\rrbracket \end{array}} \sum _{\begin{array}{c} k'\in \llbracket 0,k\rrbracket \end{array}} (y_{k'}^{v_k}+y^{v_k}_{-k'})$. This immediately leads to the following algorithm. First, all $\lambda ^v_k$ are initially set to 0. Then, we select $v_{u-1}$ maximizing $\sum _{\begin{array}{c} k\in \llbracket 0,u-1\rrbracket \\ k\equiv d(v)[2] \end{array}} (y_k^v+y^v_{-k})$ and we increment by 1 all $\lambda ^{v_{u-1}}_{k}$: $\lambda ^{v_{u-1}}_k = \lambda ^{v_{u-1}}_k + 1$ for any $k \le u-1$. More generally, for each $w \in \llbracket 0,u-1\rrbracket$, we select $v_w$ maximizing $\sum _{\begin{array}{c} k\in \llbracket 0,w\rrbracket \\ k\equiv d(v)[2] \end{array}} (y_k^v+y^v_{-k})$ and we increment by 1 all $\lambda ^{v_{w}}_{k}$ for $k \le w$. The algorithm has clearly a polynomial-time complexity. $\square$

A second family of valid inequalities is defined for each vertex v, each integer number $p \in \llbracket 1,d(v)\rrbracket$ and each subset of p edges incident to v.

$$\begin{aligned} \sum _{ \{ \{v j_1\}, \ldots , \{v j_i\}, \ldots ,\{v j_p\}\} \subset cut(\{v \})} B_{v, \{v j_i \}}x_{\{v j_i\}} + \sum _{k \in \llbracket 0,p-1\rrbracket } 2(p-k) y^v_{2k-d(v)} \le p. \end{aligned}$$

(5)

Proposition 21

Inequalities (5) are valid for ${\mathscr {P}}_2$.

Proof

If all variables $y^v_{2k-d(v)}$ are equal to 0 for $k \in \llbracket 0,p-1\rrbracket$, then inequality (5) is implied by the fact that $x \in [ -1;1]^{|E|}$.

Assume that $y^v_{2k_0-d(v)} = 1$ for some $k_0 \in \llbracket 0,p-1\rrbracket$. This requires that among all edges of $cut(\{v\})$ there are exactly $k_0$ (resp. $d(v) - k_0$) edges $\{v j \}$ such that $B_{v, \{v j \}}x_{\{v j\}}= 1$ (resp. $B_{v, \{v j \}}x_{\{v j\}}= -1$). Consequently $\sum _{ \{ \{v j_1\}, \ldots , \{v j_i\}, \ldots ,\{v j_p\}\} \subset cut(\{v \})} B_{v, \{v j_i \}}x_{\{v j_i\}}$ is upper bounded by $k_0 - (p-k_0) = 2k_0 -p$. Moreover, we have $\sum _{k \in \llbracket 0,p-1\rrbracket } 2(p-k) y^v_{2k-d(v)} = 2(p - k_0)$. Inequality (5) immediately follows. $\square$

The separation problem of inequalities (5) is also easy to solve.

Proposition 22

Inequalities (5) can be separated in polynomial time.

Proof

Given a fractional solution (x, y, h), for each vertex v and any $p \in \llbracket 1,d(v)\rrbracket$, we order the edges of $cut(\{v\})$ in descending order according to $B_{v, \{v j \}}x_{\{v j\}}$ and we select the first p edges. Then a violated inequality can be detected by comparison of $\sum _{ \{ \{v j_1\}, \ldots , \{v j_i\}, \ldots ,\{v j_p\}\} \subset cut(\{v \})} B_{v, \{v j_i \}}x_{\{v j_i\}} + \sum _{k \in \llbracket 0,p-1\rrbracket } 2(p-k) y^v_{2k-d(v)}$ with p. $\square$

Let us now consider any cycle ${\mathscr {C}}$ and the two following inequalities.

$$\begin{aligned} \sum _{v \in {\mathscr {C}}}(2y^v_{d(v)}+y^v_{d(v)-2})\le & {} |{\mathscr {C}}|, \end{aligned}$$

(6)

$$\begin{aligned} \sum _{v \in {\mathscr {C}}}(2y^v_{-d(v)}+y^v_{-d(v) + 2})\le & {} |{\mathscr {C}}|. \end{aligned}$$

(7)

Proposition 23

Inequalities (6) and (7) are valid for ${\mathscr {P}}_2$.

Proof

Let us focus on the validity of inequalities (6) [inequalities (7) being provable in the same way]. After orientation of the edges of the cycle ${\mathscr {C}}$, let ${\mathscr {C}}^{+}$ be the set of vertices of ${\mathscr {C}}$ for which their two incident edges are oriented outward from these vertices to their neighbours. We also define ${\mathscr {C}}^{-}$ in the same way be considering vertices having two edges of the cycle oriented from their neighbours to them. The remaining set of vertices of the cycle is denoted by ${\mathscr {C}}^{*}$ (they have an incoming incident edge and an outgoing incident edge). These definitions are illustrated on Fig. 10. It is now easy to see that we always have $|{\mathscr {C}}^{+}| = |{\mathscr {C}}^{-}|$.

Suppose that $y^v_{d(v)} = 1$, then $v \in {\mathscr {C}}^{+}$. Observe also that $y^v_{d(v)-2} = 1$ requires v to be in ${\mathscr {C}}^+ \cup {\mathscr {C}}^*$. Consequently, $\sum _{v \in {\mathscr {C}}}(y^v_{d(v)}+y^v_{d(v)-2}) \le |{\mathscr {C}}^{+}| + |{\mathscr {C}}^{*}|$ and $\sum _{v \in {\mathscr {C}}} y^v_{d(v)} \le |{\mathscr {C}}^{+}|$. Summing up both inequalities leads to $\sum _{v \in {\mathscr {C}}}(2y^v_{d(v)}+y^v_{d(v)-2}) \le 2 |{\mathscr {C}}^{+}| + |{\mathscr {C}}^{*}| = |{\mathscr {C}}^{+}| + |{\mathscr {C}}^{-}|+ |{\mathscr {C}}^{*}| = |{\mathscr {C}}|$. $\square$

Proposition 24

Inequalities (6) and (7) can be separated in polynomial time.

Fig. 10

A vertex of a cycle ${\mathscr {C}}$ is respectively in ${\mathscr {C}}^+$, ${\mathscr {C}}^-$ or ${\mathscr {C}}^*$ if it has two, zero or one outgoing incident edge(s) in ${\mathscr {C}}$

Proof

Let us again focus on inequalities (6) since (7) can be separated in a similar way. Given a fractional solution (x, y, h), we need an algorithm to either compute a cycle ${\mathscr {C}}$ such that $|{\mathscr {C}}| - \sum _{v \in {\mathscr {C}}}(2y^v_{d(v)}+y^v_{d(v)-2}) < 0$ or to certify that such a cycle does not exist. For each edge uv, let us consider a weight $c_{ uv} = 1 - (y^v_{d(v)}+ \frac{1}{2} y^v_{d(v)-2}) - (y^u_{d(u)}+ \frac{1}{2} y^u_{d(u)-2})$. Then we clearly have

$$\begin{aligned} |{\mathscr {C}}| - \sum _{v \in {\mathscr {C}}}(2y^v_{d(v)}+y^v_{d(v)-2}) = \sum _{\{uv \} \in {\mathscr {C}}} c_{ uv}. \end{aligned}$$

We are then looking for an undirected cycle having a negative total weight. This can be done, for example, by computing a minimum weight $\emptyset$-join, where the last is a set of edge disjoint cycles. This can be done using the algorithm of Edmonds and Johnson (1973). Notice that this algorithm can provide many negative weight cycles with some 0 weight cycles. If the total weight of the $\emptyset$-join is strictly negative, a negative weight cycle can be easily extracted. A different algorithm can also be found in Ben-Ameur and Hadji (2010) (see Sect. 6 of the reference). $\square$

Given any clique ${\mathscr {K}}$ and any number $p\in \llbracket 1,|{\mathscr {K}}|\rrbracket$, we consider the two following inequalities.

$$\begin{aligned} \sum _{v \in {\mathscr {K}}} \sum _{k=0}^{\min (p-1, d(v))} (p-k) y_{d(v)-2k}^v\le & {} \frac{p(p+1)}{2},\quad \forall p\in \llbracket 1,|{\mathscr {K}}|\rrbracket , \end{aligned}$$

(8)

$$\begin{aligned} \sum _{v \in {\mathscr {K}}}\sum _{k=0}^{\min (p-1, d(v))}(p-k)y_{2k-d(v)}^v\le & {} \frac{p(p+1)}{2},\quad \forall p\in \llbracket 1,|{\mathscr {K}}|\rrbracket . \end{aligned}$$

(9)

Inequalities (8) can be seen as a generalization of the obvious inequalities $\sum _{v \in {\mathscr {K}}} y^v_{d(v)}\le 1$ obtained when $p = 1$.

Proposition 25

Inequalities (8) and (9) are valid for ${\mathscr {P}}_2$.

Proof

We can focus on inequalities (8). To maximize the left hand side of (8), we can assume that all edges in $cut({\mathscr {K}})$ are oriented from ${\mathscr {K}}$ to outside (this is due to the fact that the coefficient $p-k$ increases when k decreases). Then, $y^v_{d(v) - 2k} = 1$ is equivalent to say that exactly k edges, inside ${\mathscr {K}}$ and incident to v, are oriented from v to outside.

Observe that inequality (8) is equivalent to

$$\begin{aligned} p \sum _{v \in \mathscr {K}} \sum _{k=0}^{\min (p-1, d(v))} y_{d(v)-2k}^v \le \sum _{v \in \mathscr {K}} \sum _{k=0}^{\min (p-1, d(v))} k y_{d(v)-2k}^v + \frac{p(p+1)}{2}. \end{aligned}$$

(10)

Let q be the number of vertices of ${\mathscr {K}}$ whose outdegree (in the graph induced by ${\mathscr {K}}$) is at most $p-1$ after orientation. The left hand side of (10) is given by pq. The sum of the q lowest outdegrees is exactly given by $\sum _{v \in \mathscr {K}} \sum _{k=0}^{\min (p-1, d(v))} k y_{d(v)-2k}^v$. Using landau’s theorem for tournaments (Landau 1953), we can write that $\sum _{v \in \mathscr {K}} \sum _{k=0}^{\min (p-1, d(v))} k y_{d(v)-2k}^v \ge \frac{q(q-1)}{2}$. Adding $\frac{p(p+1)}{2}$ to both sides, we get $\sum _{v \in \mathscr {K}} \sum _{k=0}^{\min (p-1, d(v))} k y_{d(v)-2k}^v +\frac{p(p+1)}{2} \ge \frac{p^2 + q^2 + p - q}{2}$. Moreover, from $(q-p)^2 \ge q -p$, we get that $\frac{p^2 + q^2 + p - q}{2} \ge pq$ proving (10). $\square$

To separate inequalities (8), the following heuristic is used. Given a fractional solution (x, y, h), for each vertex v and any $p \in \llbracket 1,d(v)+1\rrbracket$, we use a greedy approach to find a locally maximum-weight clique where the weight of any vertex $u\in V$ is $\sum _{k=0}^{\min (p-1, d(u))} (p-k) y_{d(u)-2k}^u$. We start with ${\mathscr {K}}\, := \{v\}$ and then recursively find $u={{\mathrm{arg\,max}}}\{\sum _{k=0}^{\min (p-1, d(w))} (p-k) y_{d(w)-2k}^w|w\in \cap _{v'\in {\mathscr {K}}}N_G(v')\}$, where $N_G(v)$ denotes the set of the neighbours of v in G, and add it to ${\mathscr {K}}$ until $\cap _{v'\in {\mathscr {K}}}N_G(v')=\emptyset$. Then if $|{\mathscr {K}}|\ge p$ we can derive the inequality (8) corresponding to ${\mathscr {K}}$.

6 Computational results

In order to assess the performance of formulations ${{\mathrm{{\text {MIP1}}}}}$ and ${{\mathrm{{\text {MIP2}}}}}$, we present some computational results related to a wide variety of graphs. All algorithms were written in C++ calling IBM’s ILOG CPLEX optimizer©and experiments have been performed using a processor 1.9GHzx4, 15.6GB RAM with four cores.

While the implementation of ${{\mathrm{{\text {MIP1}}}}}$ is pretty straightforward: the model is created with all inequalities described in Sect. 5 and then the mixed-integer-linear-programming solver of CPLEX is run with default parameters, the implementation of ${{\mathrm{{\text {MIP2}}}}}$ needs to be detailed.

First of all, an initial solution is determined by computing a locally maximum cut using the standard greedy algorithm described in the proof of Theorem 9. A starting integer solution is then known for both formulations ${{\mathrm{{\text {MIP1}}}}}$ and ${{\mathrm{{\text {MIP2}}}}}$.

For both formulations and each instance, we set a limited total processing time of 15 min (900 s). If this limit is reached, then the process is interrupted and returns both the objective value of the current best integer solution $L_{{{\mathrm{{\text {MIP1}}}}}}$ or $L_{{{\mathrm{{\text {MIP2}}}}}}$ and the current best upper bound $U_{{{\mathrm{{\text {MIP1}}}}}}$ or $U_{{{\mathrm{{\text {MIP2}}}}}}$.

For formulation ${{\mathrm{{\text {MIP2}}}}}$, a cutting-plane algorithm is implemented based on the inequalities of Sect. 5. Inequalities are generated in the following order:

• We look for a violated inequality of the type (4) according to the proof of Proposition 20.

• We generate cliques using the heuristic described in the end of Sect. 5 and check for a violated inequalities of the types (8) and (9).

• We search for a cycle with minimum weight with a simple flow formulation solved as mixed integer program where each edge $vw\in E$ has weight $\frac{1}{2}(2y^v_{d(v)}+y^v_{d(v)-2}+y^w_{d(w)}+y^w_{d(w)-2})$. If we find a negative weighted cycle, then corresponding inequality of the type (6) is violated. We do the same with the weight $\frac{1}{2}(2y^v_{-d(v)}+y^v_{2-d(v)}+y^w_{-d(w)}+y^w_{2-d(w)})$ for an edge vw to find a violated inequality of the type (7). For the sake of simplicity, inequalities (6) and (7) are not separated using the algorithms of Edmonds and Johnson (1973) and Ben-Ameur and Hadji (2010) but using a simple integer linear program computing a minimum-weight cycle.

Table 1 Numerical results

After various experimentations, we chose not to put the inequalities of type (5) in the cutting-plane phase because when included, while the number of generated inequalities increases excessively with the size of the graph, the optimal objective value of the linear program is left unimproved.

After the addition of violated inequalities, the linear relaxation is solved to get a fractional (x, y, h) solution and the process is repeated until no more violated inequalities can be found. The optimal objective value of the last LP is denoted by $v_{{{\mathrm{{\text {LP2}}}}}}$. Notice that the cutting-plane phase is intentionally limited to less than 10 min (600 s). Thus, if either no more valid inequalities can be generated or the time spent in the cutting-plane phase reaches 10 min, we switch to branch and bound. The time spent in the cutting-plane phase us denoted by $t_{{{\mathrm{{\text {LP2}}}}}}$.

CPLEX’s mixed integer programming solver is used with default parameters to solve ${{\mathrm{\textsc {MaxIm}}}}$. Notice that some automatic internal cuts are generated by the solver to accelerate the branch and bound. As already mentioned, the total running time is limited to 15 min. The time spent in the branch and bound phase is denoted by $t_{{{\mathrm{{\text {MIP2}}}}}}$ while the best lower and upper bounds are respectively denoted by $L_{{{\mathrm{{\text {MIP2}}}}}}$ and $U_{{{\mathrm{{\text {MIP2}}}}}}$.

For each of the instances we report $L_{{{\mathrm{{\text {MIP1}}}}}}$, $U_{{{\mathrm{{\text {MIP1}}}}}}$, $t_{{{\mathrm{{\text {MIP1}}}}}}$, $v_{{{\mathrm{{\text {LP2}}}}}}$, $t_{{{\mathrm{{\text {LP2}}}}}}$, $L_{{{\mathrm{{\text {MIP2}}}}}}$, $U_{{{\mathrm{{\text {MIP2}}}}}}$, and $t_ {{{\mathrm{{\text {MIP2}}}}}}$, where $t_{{{\mathrm{{\text {LP2}}}}}}$, $t_{{{\mathrm{{\text {MIP1}}}}}}$ and $t_ {{{\mathrm{{\text {MIP2}}}}}}$ are expressed in seconds. We also report $\text {nb}_{(4)}$, $\text {nb}_{(8,9)}$ and $\text {nb}_{(6,7)}$, respectively the number of inequalities of the type (4), (8) and (9) and (6) and (7) generated for each instance $G=(V,E)$ along with |V|,|E| and $\delta _G$.

The graph instances used for the computations are denoted as follows:

• $K_n$: the complete graph with n vertices,

• $G^n_k$: the n-dimensional grid of length k, i.e. the cartesian product of n paths graphs of length k: $\bullet _{i=1}^nL_k$, where $L_k$ is a path graph of length k,

• $G^2_{n_1,n_2}$: the 2-dimensional grid, i.e. the cartesian product of two path graphs of length $n_1$ and $n_2$: $L_{n_1}\bullet L_{n_2}$,

• $tG^n_k$: the n-dimensional toroidal grid of length k, i.e. the cartesian product of n cycless of length k: $\bullet _{i=1}^nC_k$, where $C_k$ is a cycle of length k,

• $tG^2_{n_1,n_2}$: the 2-dimensional toroidal grid, i.e. the cartesian product of cycles of length $n_1$ and $n_2$: $C_{n_1}\bullet C_{n_2}$,

• $P_{n,m}$: a randomly generated planar graph with n vertices and m edges,

• $R_{n,m}$: a randomly generated graph with n vertices and m edges.

More about the toroidal grids can be found in Degraaf and Schrijver (1994).

Table 1 shows that formulation ${{\mathrm{{\text {MIP2}}}}}$ has a significantly better performance than ${{\mathrm{{\text {MIP1}}}}}$. On many instances we can observe that the cutting plane algorithm of ${{\mathrm{{\text {MIP2}}}}}$ drastically improved the upper bound $\delta _G$, sometimes so far as to the optimal objective value as can be seen for example on the complete graphs, the planar graphs or most of the n-dimensional toroidal grids. while the number and nature of the generated inequalities varies a lot, it seems to never grow excessively. We can see that as soon as the size of the instance becomes substantial, formulation ${{\mathrm{{\text {MIP1}}}}}$ seems to degenerate, needing too much time and/or memory to be processed, while ${{\mathrm{{\text {MIP2}}}}}$ shows its ability to handle large size graphs.

7 Further research

While computing the most imbalanced orientation of a graph is generally difficult, the problem turns out to be easy for cacti. It may be the same for other graph classes. Characterizing such graph classes would be interesting.

Two mixed integer linear programming formulations of ${{\mathrm{\textsc {MaxIm}}}}$ have been presented. Several families of valid inequalities have been presented to strengthen one of the two formulations. Exhibition of other families of valid inequalities might be helpful to solve larger size problems.

Finally, one can also the study the weighted version of the most imbalanced orientation problem.

Appendix 1: Proof of Lemma 6

Let $\varphi$ be a not-all-equal at most 3-SAT formula with n variables $\{x_1,\ldots ,x_n\}$ and m clauses $\{c_1,\ldots ,c_m\}$ and for all $i\in \llbracket 1,n\rrbracket$, let $k_i\in \mathbb {N}$ be the number of occurences of $x_i$ in $\varphi$. We assume that there is at least one variable $x_i$ that has at least 4 occurences in $\varphi$ (otherwise $\varphi$ is already a not-all-equal at most 3-SAT(3V) formula) and we will build from $\varphi$ a not-all-equal at most 3-SAT(3V) $\varphi '$ such that $\varphi$ and $\varphi '$ are equisatisfiable as follows.

• For all $i\in \llbracket 1,n\rrbracket$, if $k_i\ge 4$ then we introduce $k_i$ new variables $\{x_i^1,\ldots ,x_i^{k_i}\}$ and for $l\in \llbracket 1,k_i\rrbracket$ we replace the l-th occurence of $x_i$ in $\varphi$ with $x_i^l$.

• For all $i\in \llbracket 1,n\rrbracket$, if $k_i\ge 4$ then we add $k_i$ new clauses $\{c_{x_i}^1,\ldots ,c_{x_i}^{k_i}\}$ where for $l\in \llbracket 1,k_i-1\rrbracket$, $c_{x_i}^l=(x_i^l\vee \lnot x_i^{l+1})$ and $c_{x_i}^l=(x_i^l\vee \lnot x_i^1)$.

Suppose there exists an assignment $v:\{x_1,\ldots ,x_n\}\rightarrow \{{{\mathrm{{\text {TRUE}}}}},{{\mathrm{{\text {FALSE}}}}}\}$ of $x_1,\ldots ,x_n$ satisfying $\varphi$. Then

$$\begin{aligned}v':\begin{array}{ll} x_i\mapsto v(x_i)~&{}\quad \forall i\in \llbracket 1,n\rrbracket \text { s.t. }k_i\le 3;\\ x_i^l\mapsto v(x_i)~&{}\quad \forall i\in \llbracket 1,n\rrbracket \text { s.t. }k_i \ge 4\text { and }\forall l\in \llbracket 1,k_i\rrbracket ; \end{array} \end{aligned}$$

is an assignment of the variables $x_i$ and $x_i^l$ satisfying $\varphi '$ for

• $\forall j\in \llbracket 1,m\rrbracket$, the values of the literals of $c_j$ w.r.t. v and $v'$ are piecewise equal so $v'(c_j)=v(c_j)={{\mathrm{{\text {TRUE}}}}}$ and $v'$ is not-all-equal for $c_j$ as well as v is;

• $\forall i\in \llbracket 1,n\rrbracket \text { s.t. }k_i\ge 4$, $\forall l\in \llbracket 1,k_i-1\rrbracket$, $v'(x_i^l)=v'(x_i^{l+1})=v(x_i)$ and $v'(x_i^{k_i})=v'(x_i^{1})=v(x_i)$ so we directly have $\forall l\in \llbracket 1,k_i-1\rrbracket$, $v'(c_{x_i}^l)={{\mathrm{{\text {TRUE}}}}}$ and $v'(c_{x_i}^{k_i})={{\mathrm{{\text {TRUE}}}}}$ and $v'$ is not-all-equal for each of these clauses since they all consist of two literals having opposite values w.r.t. $v'$.

As an example, for a formula

$$\begin{aligned} \varphi= & {} (x_1\vee \lnot x_2\vee x_3)\wedge (\lnot x_1\vee \lnot x_3\vee x_4)\wedge (x_1\vee \lnot x_2)\wedge (\lnot x_1\vee \lnot x_3\vee \lnot x_4)\\&\wedge (x_1\vee x_3), \end{aligned}$$

where $x_1$ occurs five times and $x_3$ four so we add nine new variables $x_1^1$, $x_1^2$, $x_1^3$, $x_1^4$, $x_1^5$, $x_3^1$, $x_3^2$, $x_3^3$ and $x_3^4$ and nine new clauses:

$$\begin{aligned} \varphi '=&(x_1^1\vee \lnot x_2\vee x_3^1)\wedge (\lnot x_1^2\vee \lnot x_3^2\vee x_4)\wedge (x_1^3\vee \lnot x_2)\wedge (\lnot x_1^4\vee \lnot x_3^3\vee \lnot x_4)\\&\wedge (x_1^5\vee x_3^4)\wedge (x_1^1\vee \lnot x_1^2)\wedge (x_1^2\vee \lnot x_1^3)\wedge (x_1^3\vee \lnot x_1^4)\wedge (x_1^4\vee \lnot x_1^5)\\&\wedge (x_1^5\vee \lnot x_1^1)\wedge (x_3^1\vee \lnot x_3^2)\wedge (x_3^2\vee \lnot x_3^3)\wedge (x_3^3\vee \lnot x_3^4)\wedge (x_3^4\vee \lnot x_3^1). \end{aligned}$$

Now suppose there exists an assignment $v'$ of the $x_i$ and $x_i^l$ satisfying $\varphi '$ and let $i\in \llbracket 1,n\rrbracket$ such that $k_i \ge 4$. If we take a look at the clauses $c_{x_i}^1,\ldots ,c_{x_i}^{k_i}$, we notice that if $v'(x_i^1)={{\mathrm{{\text {FALSE}}}}}$ then for $c_{x_i}^1$ to be satisfied, $v'(\lnot x_i^2)={{\mathrm{{\text {TRUE}}}}}$, i.e. $v'(x_i^2)={{\mathrm{{\text {FALSE}}}}}$, then for $c_{x_i}^2$ to be satisfied, $v'(\lnot x_i^3)={{\mathrm{{\text {TRUE}}}}}$ ...etc. Repeating this argument, we obtain that if $v'(x_i^1)={{\mathrm{{\text {FALSE}}}}}$ then $v'(x_i^1)=v'(x_i^2)=\cdots =v'(x_i^{k_i})={{\mathrm{{\text {FALSE}}}}}$. Similarly, if $v'(x_i^{k_i})={{\mathrm{{\text {TRUE}}}}}$ then for $c_{x_i}^{k_i}$ to be satisfied, $v'(\lnot x_i^{k_i-1})={{\mathrm{{\text {FALSE}}}}}$, i.e. $v'(x_i^{k_i-1})={{\mathrm{{\text {TRUE}}}}}$, then for $c_{x_i}^{k_i-1}$ to be satisfied, $v'(\lnot x_i^{k_i-2})={{\mathrm{{\text {FALSE}}}}}$ ...etc. Hence if $v'(x_i^{k_i})={{\mathrm{{\text {TRUE}}}}}$ then $v'(x_i^{k_i})=v'(x_i^{k_i-1})=\cdots =v'(x_i^1)={{\mathrm{{\text {TRUE}}}}}$. This yields that

$$\begin{aligned} \forall i\in \llbracket 1,n\rrbracket \text { s.t. }k_i \ge 4,~v'(x_i^1)=v'(x_i^2)=\cdots =v'(x_i^{k_i}). \end{aligned}$$

Hence for all $i\in \llbracket 1,n\rrbracket$ such that $k_i\ge 4$, we can replace $x_i^1,\ldots ,x_i^{k_i}$ by a unique variable $x_i$ and doing so the clauses $c_{x_i}^1,\ldots ,c_{x_i}^{k_i}$ become trivial and can be removed and only $\varphi$ remains. So the following assignment of $x_1,\ldots ,x_n$:

$$\begin{aligned} v:\begin{array}{ll} x_i\mapsto v'(x_i)~&{}\quad \forall i\in \llbracket 1,n\rrbracket \text { s.t. }k_i\le 3;\\ x_i\mapsto v'(x_i^1)~&{}\quad \forall i\in \llbracket 1,n\rrbracket \text { s.t. }k_i \ge 4; \end{array} \end{aligned}$$

satisfies $\varphi$. We have just shown that $\varphi$ and $\varphi '$ are equisatisfiable.