\input epsf \documentstyle{article} \addtolength{\textheight}{4cm} \addtolength{\textwidth}{4cm} \setlength{\oddsidemargin}{1cm} \setlength{\evensidemargin}{1cm} \hoffset=-.5in \voffset=-.8in \newcounter{bean} \newcounter{bacon} \newcounter{cms} \def\Hom{{\mbox{Hom}}} \def\SPEC{{\mbox{SPEC}}} \def\SCH{{\mbox{SCH}}} \def\descriptionlabel#1{\hfil\bf[#1]\hfil} \def\C{{\cal C}} \def\O{{\cal O}} \def\A{{\cal A}} \def\proclaim #1. #2\par{\medbreak{\bf#1.\enspace}{\it#2}\par \ifdim\lastskip<\medskipamount \removelastskip\penalty55\medskip\fi} \parskip 5pt plus 1pt \setlength{\topmargin}{0cm} \newskip\Bigskipamount \Bigskipamount=20pt plus 5pt minus 4pt \def\Bigskip{\vskip\Bigskipamount} \begin{document} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 1 (1994), \#R5\hfill} \thispagestyle{empty} \large \centerline{\LARGE{\bf EVEN KERNELS}} \medskip \centerline{Aviezri Fraenkel\footnote{Permanent address:\ Dept.\ of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot 76100, Israel. The main part of this work was done at the University of Pennsylvania and later at the University of Calgary, during 1993.}} \centerline{Curtin University} \centerline{School of Mathematics and Statistics} \centerline{GPO Box U 1987, Perth, WA 6001, Australia} \vspace{0.5in} {\sc Abstract}. Given a graph $G = (V,E)$, an {\it even kernel} is a nonempty independent subset $V' \subseteq V$, such that every vertex of $G$ is adjacent to an even number (possibly $0$) of vertices in $V'$. It is proved that the question of whether a graph has an even kernel is {\rm NP}-complete. The motivation stems from combinatorial game theory. It is known that this question is polynomial if $G$ is bipartite. We also prove that the question of whether there is an even kernel whose size is between two given bounds, in a given bipartite graph, is {\rm NP}-complete. This result has applications in coding and set theory. \vspace{0.3in} \section{Introduction} \indent {\sc Even Kernel} (EVEK). Given an undirected graph $G = (V,E)$. Is there a nonempty independent subset $V' \subseteq V$ such that every $u \in V$ has even degree with respect to $V'$, i.e., $u$ has an even number (possibly $0$) of neighbors in $V'$? {\sc Example}. In the graph depicted in Fig.\ 1, the subset $\{u_1,u_3,u_7,u_9\}$ is an even kernel. So is its subset $\{u_1,u_3\}$; and also $\{u_2,u_4,u_5,u_6,u_8\}$ is an even kernel. Thus an even kernel may exist nonuniquely. A triangle has no even kernel. \epsfysize 1.5 true in $$\epsffile{fig1new.ps}$$ \centerline{{\sc Figure} 1. Even kernels in a graph $G = (V,E)$.} \vspace{0.2in} The notion of an even kernel was defined in Fraenkel, Scheinerman and Ullman [1993], with the motivation that the vertices of an even kernel are $P$-positions (second player win positions) in a game called ``Edge Geography''. It was shown there that EK is polynomially decidable if $G$ is bipartite. In \S 2 we prove \proclaim{Theorem 1}. {\rm EVEK} is {\rm NP}-complete even for graphs with maximum degree 3. \par This result is best possible, in the sense that for a graph with maximum degree $\leq 2$, the question can be decided in linear time, since a simple path or a simple circuit each have an even kernel if and only if the path or circuit has even length (an even number of edges). The notion of an even kernel is not all that new, though our terminology for it might be. Berlekamp, McEliece and van Tilborg [1978] showed that the problem of whether a binary matrix $A$ contains exactly $L$ rows such that each column of these $L$ rows has an even number of 1-bits (i.e., whether there is a binary vector $X$ such that $XA \equiv 0 \pmod{2}$) is {\rm NP}-complete, and asked about the status of the problem when ``exactly $L$'' is replaced by ``$\leq L$'' ($\leq {\rm DECOD}$). See also Garey and Johnson [1979, DECODING OF LINEAR CODES]. They also asked in ``OPEN5'' about the following EVEN SET (EVES) problem: ``Given a collection $C$ of subsets of a finite set $X$ and $L \in {\cal Z}^+$, is there a nonempty subcollection ${C'} \subseteq C$ with $|{C'}| \leq L$, such that each $x \in X$ belongs to an even number (possibly $0$) of sets in ${C'}$?''. They stated that EVES is equivalent to $\leq$ DECOD. It is easy to see that both EVES and $\leq$ DECOD are equivalent to asking whether a given bipartite graph $G=(V_1,V_2;E)$ with disjoint and independent parts $V_1$ and $V_2$ has an even kernel $K \subseteq V_1$ with $|K| \leq L$. Define the problem {\sc Even Single Bipartite Kernel} (ESBIK). Given $A,C \in {\cal Z}^+$ with $A \leq C$ and a bipartite graph $G=(V_1,V_2;E)$, where $V_1, V_2$ are disjoint independent subsets of vertices. Is there a subset $K \subseteq V_1$, with $A \leq |K| \leq C$ such that every vertex has an even number of neighbors (possibly $0$) in $K$? In \S 3 we prove \proclaim{Theorem 2}. {\rm ESBIK} is {\rm NP}-complete even for graphs with maximum degree 3. \par A related problem is {\sc Even Double Bipartite Kernel} (EDBIK). Given $A,C \in {\cal Z}^+$ with $A \leq B$ and a bipartite graph $G=(V_1,V_2;E)$, where $V_1, V_2$ are disjoint indpendent subsets of vertices. Is there a subset $K \subseteq V_1 \cup V_2$ with $A \leq |K| \leq C$, such that every vertex has an even number of neighbors (possibly $0$) in $K$? In \S 4 we prove \proclaim{Theorem 3}. {\rm EDBIK} is {\rm NP}-complete even for graphs with maximum degree 3. \par All our reductions are made from 1-3SAT, defined below. A Boolean formula is {\it positive} if it contains no negated variables. A Boolean formula is in 3CNF if it is a conjunction of clauses, where each clause is a disjunction of three literals. {\sc One-In-Three 3SAT} (1-3SAT). Given a positive Boolean 3CNF formula $B$. Is $B$ {\it 1-satisfiable}, i.e., is there a truth assignment for $B$ such that each clause in $B$ has precisely one true variable? Schaefer [1978] proved that 1-3SAT is {\rm NP}-complete. See also Garey and Johnson [1979]. For all the three proofs, we associate with any positive 3CNF-formula $B=c_1 \wedge \cdots \wedge~c_m$ with clauses $c_1, \ldots ,c_m$ and variables $x_1, \ldots, x_n$, a graph $G(B)$ whose vertex set is $\{c_1 \ldots c_m, x_1, \ldots, x_n \}$ and there is an edge $(x_j, c_i)$ if and only if $x_j \in c_i$, i.e., $x_j$ is in $c_i$ (Fig.\ 2). We shall make a standard modification on $G(B)$, so as to preserve the degree-at-most-3 requirement throughout the construction. \epsfysize 4 true in $$\epsffile{fig2new.ps}$$ \centerline{{\sc Figure} 2. The graph $G(B)$ for $B = (x_1 \vee x_2 \vee x_3) \wedge (x_3 \vee x_4 \vee x_5) \wedge (x_1 \vee x_2 \vee x_4)$.} \vspace{0.2in} \noindent \vspace{0.2in} It is clear that each of the problems EVEK, ESBIK and EDBIK is in {\it NP}. \vspace{0.2in} {\sc Notation}. A vertex belonging to a given fixed even kernel will be termed {\it marked}. Otherwise it is {\it unmarked}. In the figures below, we use asterisks to indicate marked vertices. The {\it length} of a simple path in a graph is the number of its edges, so it is 1 less than the number of its vertices. An $n$-{\it path} is a path of length $n$. \vspace{0.2in} \section{Proof of Theorem 1} \indent 1. {\sc Injectors}. An {\it injector} injects a mark onto a vertex. Typically, one end of an injector is a two-pronged ``or''-gate consisting of two adjacent vertices $u_1,u_2$, constituting one edge $e = (u_1,u_2)$ of a circuit in which alternate vertices are marked. Thus precisely one of $u_1,u_2$ is marked. The two vertices $u_1,u_2$ are both adjacent to the {\it focus} $v$ of the injector. The focus is adjacent to the other end of the injector, which is a single vertex $u$ (Fig.\ 3(i)), possibly joined to an or-gate of several vertices, an odd number of them being marked (Fig.\ 3 (ii),(iii)). The latter vertices may be adjacent to each other (implying further mark and adjacency restrictions) or not. Note that an injector injects a mark in either direction, and in fact may be completely symmetric relative to its mid-vertex (Fig.~\ 3(ii), if $u_3$ and $u_4$ are adjacent). \epsfysize 2.5true in $$\epsffile{fig3e.ps}$$ \begin{tabbing} xxxxxxx\= xxxxxxxxxxxxxxxxxxxxxxxx\= xxxxxxxxxxxxxxxxxxxxxxxx\= xxxxxxxxxxxxxxxxxxxxxxxx\= \kill \>(i)\ Simple injector \>(ii)\ Injector with \>(iii)\ Injector with\\ \> \>2-pronged or-gate \>3-pronged or-gate\\ \end{tabbing} \vspace{0.1in} \centerline{{\sc Figure} 3. Various manifestations of injectors.} \vspace{0.2in} We wish to make sure that the even kernel induced by our construction is a ``full'' even kernel, rather than only some subset of an even kernel, such as pointed out in Fig.\ 1. The injectors see to this. \vspace{0.2in} 2. {\sc Variable Circuits}. Let $m(j)$ be the total number of occurrences of the variable $x_j$ in $B$. Construct a simple circuit of $2(2m(j) + 2)$ vertices for $x_j$ $(1 \leq j \leq ~n)$, where alternate vertices are {\it labeled} $x_{1j},x_{2j},\ldots, x_{2m(j)+2,j}$; the vertices in-between are {\it unlabeled}. The circuits for $x_{j-1}$ and $x_j$ are joined by an injector with a $2$-pronged or-gate on both of its sides (Fig.\ 4), where, here and below, $x_{ij}$ is indicated by $ij$. The locations of the ends of the injector on any variable circuit are such that if the vertices of a variable circuit are traversed in clockwise direction, then the first vertex of the injector which is encountered in this traversal is labeled. (Note the distinction between marked and labeled vertices.) \epsfysize 1.5 true in $$\epsffile{fig4new.ps}$$ \centerline{{\sc Figure} 4. Two adjacent variable circuits joined via an injector.} \vspace{0.3in} \noindent \vspace{0.3in} 3. {\sc Clause Circuits}. A clause circuit $c_i$ $(1 \leq i \leq m)$ is a network consisting of $12$ vertices interconnected as shown in Fig.\ 5. (It would be more compact, if the degree constraint would be relaxed to $d \leq 4$.) It has four {\it terminals}, $a,b,d$ and $g$. \epsfysize 3 true in $$\epsffile{fig5new.ps}$$ \centerline{{\sc Figure} 5. A clause circuit $c_i$.} \epsfysize 4 true in $$\epsffile{fig6e.ps}$$ \centerline{{\sc Figure} 6. Joining variable circuits with a clause circuit.} \vspace{0.3in} In the global construction, $x_{ij}$ is joined via a $2$-path to precisely one of the terminals $a,b$ or $d$ of $c_i$, if and only if $x_j$ is in $c_i$. In addition, one injector, based on an $x_j$-variable circuit with $x_j$ in $c_i$ is joined, via a $2$-path, to terminal $g$ of $c_i$ (Fig.\ 6). Also here the location of the ends of the injector is such that if the vertices of a variable circuit are traversed in clockwise direction, then the first vertex of the injector encountered in this traversal is labeled. Since there are $m(j)$ $2$-paths between the variable circuit of $x_j$ and the $c_i$, and at most $m(j) + 2$ injectors on it, the $2(2m(j)+2)$ vertices on the variable circuit suffice to insure that the degrees on any variable circuit are at most $3$. The global construction (Fig.\ 7) is clearly polynomial. \epsfysize 5 true in $$\epsffile{fig7new.ps}$$ \centerline{{\sc Figure} 7. The global construction for $B = (x_1 \vee x_2 \vee x_3) \wedge (x_3 \vee x_4 \vee x_5) \wedge (x_1 \vee x_2 \vee x_4)$.} \vspace{0.3in} Now assume that 1-3SAT is $1$-satisfiable, i.e., each clause in $B$ has precisely one true variable. In the variable circuits, mark the $x_{ij}$ $(1 \leq i \leq 2m(j) + 2)$ if $x_j = 1$ for some truth assignment for which $B$ is 1-satisfiable, and the unlabeled vertices between the $x_{ij}$ $(1 \leq i \leq 2m(j)+2)$ if $x_j = 0$. Then precisely one of the $x_{ij}$ for $x_j$ in $c_i$ is marked for each $i$, and precisely one of $a,b,d$ is marked, namely, the one at the end of a $2$-path whose other end is a marked $x_{ij}$. Also the vertices $u$ (Figs.~\ 6 and~ 7) and the mid-vertices on the injectors connecting adjacent variable circuits get injected marks. If $d$ has been marked, no further vertex of $c_i$ is marked. But if $a$ or $b$ has been marked, then $h$ is marked; and so is $a_1$ and $a_2$ (if $a$ is marked) or $b_1$ and $b_2$ (if $b$ is marked). It is easily verified that the marked vertices constitute an even kernel of the constructed graph $G$. Conversely, assume that $G$ has an even kernel. We begin by collecting a few properties of $G$ and its even kernel. \proclaim{\bf Proposition 1}. If a labeled vertex of a variable circuit is marked, then all labeled vertices of that variable circuit are marked. \par {\bf Proof}. Proceed in clockwise direction from a marked vertex $x_{ij}$, and note that the mark necessarily ``propagates'' along the circuit at the labeled vertices, including those which impinge on $2$-paths joined to the $c_i$, and at the beginnings of injectors, all of which are labeled. $\Box$ \proclaim{\bf Proposition 2}. No focus $v$ of any injector can be marked. \par {\bf Proof}. Suppose $v$ is marked. Then both $x_{ij}$ in clockwise direction and the unlabeled vertex $w$ in counterclockwise direction of a variable circuit (Fig.\ 8) are marked. By Proposition 1, all labeled vertices are marked, in particular $x_{i-1,j}$. This is a contradiction, since $x_{i-1,j}$ is adjacent to both $v$ and $w$. $\Box$ \epsfysize 3 true in $$\epsffile{fig8e.ps}$$ \centerline{{\sc Figure} 8. An impossible situation.} \vspace{0.3in} \proclaim{\bf Proposition 3}. For every clause circuit $c_i$, none of the vertices $g$ and $v_j$ $(1 \leq j \leq 6)$ can be marked (Fig.\ 6).\par {\bf Proof}. For $g,v_1$ and $v_6$ this follows directly from Proposition 2. If $v_2$ were marked, then both $b_1$ and $b_2$ would be marked, so $a_1$ would have an odd number of marked neighbors, a contradiction. By symmetry, also $v_3$ cannot be marked. But then also neither $v_4$ nor $v_5$ can be marked. $\Box$ \proclaim{\bf Proposition 4}. If an unlabeled vertex $w$ of a variable circuit is marked, then all unlabeled vertices of that variable circuit are marked. \par {\bf Proof}. The only neighbors of the vertices of a variable circuit which lie outside that circuit, are vertices of the type $v,v_4,v_5$ and $v_6$ (Fig.\ 6). By Propositions 2 and 3, none of these is marked. Thus the mark at $w$ necessarily propagates along the variable circuit itself. $\Box$ \vspace{0.3in} Propositions 1 and 4 imply that if any vertex on any variable circuit is marked, then because of the injectors between adjacent variable circuits, all variable circuits are marked: \ either all $2m(j)+2$ labeled or all $2m(j)+2$ unlabeled vertices are marked in every variable circuit. Moreover, these two possible markings are independent of each other in the $n$ variable circuits. We now show that any even kernel of $G$ necessarily intersects a variable circuit. A mark on any of $a,b$ or $d$ injects a mark into a variable circuit via $v_4,v_5$ or $v_6$ respectively, a mark on $u$ does so via $v$, and a mark on $h$ via $d$ or $u$. Also a mark on $b_1$ or $b_2$ injects a mark into a variable circuit via $b$, and a mark on $a_1$ or $a_2$ does so via $a$. By Propositions~ 2 and 3, no other vertex outside the variable circuits and their interconnecting injectors can be marked. Since an even kernel is nonempty, some vertex of a variable circuit must be marked. Hence all the variable circuits are marked; in fact, each one has all its labeled or else all its unlabeled vertices marked. Each clause circuit $c_i$ receives a mark that is injected via some $u$. Then precisely one of $d$ and $h$ is marked, otherwise $g$ would have 3 marked neighbors. Assume first that $d$ is marked. Since $h$ is then unmarked, $a$ is marked if and only if $b$ is marked. But if both $a$ and $b$ are marked, then so are the adjacent vertices $a_1$ and $b_1$, a contradiction. Thus $a$ and $b$ are both unmarked. Secondly, assume that $h$ is marked. Then precisely one of $a$ and $b$ is marked ($a_1$ and $a_2$ are marked if $a$ is marked; $b_1$ and $b_2$ are marked if $b$ is marked). It follows that for every $c_i$, precisely one of the three terminals $a,b$ or $d$ is marked. Hence precisely one of the three variable circuits connecting to the terminals via $2$-paths has all its labeled vertices marked, and the other two have all their unlabeled vertices marked. Putting $x_j = 1$ if and only if the $j^{th}$ variable circuit has all its labeled vertices marked, thus constitutes a consistent truth assignment which $1$-satisfies the given instance of 1-3SAT. $\Box$ \section{Proof of Theorem 2} We make again a reduction from 1-3SAT. Since the construction is similar to that used for proving Theorem 1, we give less detail and refer the reader to Fig.\ 9, where the global construction is illustrated. We also use the same notation as in the proof of Theorem 1. The main difference between the two constructions is that in the present case the injector cannot be used, as it is not bipartite. Its function is emulated, in part, by long chains (paths) whose length may cause certain subgraphs to be marked or unmarked. \epsfysize 5 true in $$\epsffile{fig9e.ps}$$ \centerline{{\sc Figure 9}. The global construction for $B=(x_1 \vee x_2 \vee x_3) \wedge (x_3 \vee x_4 \vee x_5) \wedge (x_1 \vee x_2 \vee x_4).$} \vspace{0.3in} 1. {\sc Ignition Bus}. This is a path of length $4(7m+n)$, where alternate vertices, including the two end vertices, are numbered 1, \ldots, $14m+2n+1$. In a proper labeling, the numbered vertices are ``ignited'', i.e., marked. The vertices numbered 1, \ldots, $m$ feed into the $m$ clause circuits $c_1, \ldots, c_m$, and the vertices numbered $m+1, \ldots, m+n$ feed into the $n$ variable circuits via {\it ignitors} (see below). Each of the vertices $i\, (1 \leq i \leq m+n)$ appears twice in Fig.\ 9, but it is one and the same vertex. Its split into two was precipitated only by the desire to avoid the many intersecting edges which would otherwise clutter the drawing. 2. {\sc Ignitors}. The variable-ignitors are 2-paths feeding into the variable circuits, and the clause-ignitors are 3-paths feeding into the clause circuits. The vertices numbered $i$ are marked in proper operation ($i \in \{1, \ldots, m+n \}$). From each vertex labeled $p$ on each clause-ignitor, there emanates a simple path $L$ of length $2(22m+3n+1)$. In proper operation, all vertices of the paths $L$ remain unmarked. 3. {\sc Variable Circuits}. The variable circuit for $x_j$ contains $2(m(j)+1)$ vertices $(1 \leq j \leq n)$, and again alternate vertices are labeled. There is a {\it shunt} of length $2(m(j)+1)-1$ connected to the $j$\/th variable circuit. If the ignition bus is marked, then either the variable circuit or its shunt are marked, but not both. 4. {\sc Clause Circuits}. There are terminals $a, b, d, g$ as in the previous construction, but the clause circuits are now bipartite. The construction is complete by putting $A=14m+2n+1$ and $C=22m+3n+1$. It is clearly polynomial and produces a bipartite graph $G$ with degrees at most 3. Suppose $B$ is 1-satisfiable. Mark the numbered vertices on the ignition bus. Mark the labeled vertices in the variable circuit of $x_j$ if and only if $x_j=1$ in a truth assignment which makes $B$\/ 1-satisfiable. In all other variable circuits, alternate vertices on the shunts are marked. Since $B$ is 1-satisfiable, exactly one of $a, b, d$ gets an induced mark from a variable circuit. Three additional vertices on $c_i$ or on the path leading from $d$ to a variable circuit are then marked. The resulting set of marked vertices forms an even kernel $K$ of size \begin{eqnarray*} |K| = & 14m+2n+1 & ({\rm ignition\; bus})\\ + & 4m + m & ({\rm clause\;circuits\;and\;their\;ignitors})\\ + & \sum_{j=1}^{n}(m(j)+1) & ({\rm variable\;circuits/shunts})\\ & &= 22m + 3n+1 = C. \end{eqnarray*} Conversely, assume that $G$ has an even kernel $K$ of size $A \leq |K| \leq C$. First note that none of the vertices labeled $p$ can be marked: if any were marked, we would already have an entire path marked, contributing $22m+3n+2 > C$ marks. Secondly, suppose that the ignition bus is unmarked. The largest $K$ could then be is when each $c_i$ contributes 8 labels ($d$ is marked; so is precisely one of $a$ and $b$), and the labeled vertices on all the variable circuits and shunts are marked. Then \[|K| \leq 8m+\sum_{j=1}^{n} 2(m(j)+1) = 14m+2n < A. \] We could have unlabeled vertices in all the variable circuits and the two neighbors of $v$ in all the $c_i$ marked. But this clearly produces an even kernel of size $ < A$. Thus alternate vertices on the ignition bus have to be marked. It is easy to see that then in each $c_i$ either one or all three terminals $a,b,d$ are marked. If precisely one is marked, then $|K|=B$ as we saw in the first part of the proof. The marked terminal induces marks on the labeld vertices in the variable circuit it is connected to via a two-path. Putting $x_j=1$ if and only if the labeled vertices are marked in the $j$-th variable circuit, thus constitutes a 1-satisfable solution to $B$. If even one $c_i$ has 3 marked terminals, then $|K|>B$, so this is not possible. So the existence of an even kernel $K$ of size $A \leq |K| \leq |C|$ implies that $B$ is 1-satisfiable. $\Box$ \section{Proof of Theorem 3} The construction is similar to the constructions used for Theorems 1 and 2, especially to the latter. See Fig.~\ 10 for the global picture. On the variable circuits we now have two shunts. The one connected to a labeled vertex is termed shunt $s$, and the other, connected to an unlabeled vertex, is shunt $s'$. From each of the vertices labeled $p$ on the clause-ignitors, there emanates a path $L$ of length $2(39m+6n+2)$. There are two ignition buses, numbered 1 and 2, each of length $4(7m+n)$. We put $A=31m+5n+2$ and $C=39m+6n+2$, and note that the construction is polynomial and produces a bipartite graph. \epsfysize 5 true in $$\epsffile{fig10new.ps}$$ \centerline {{\sc Figure} 10. The global construction for $B=(x_1 \vee x_2 \vee x_3) \wedge (x_3 \vee x_4 \vee x_5) \wedge (x_1 \vee x_2 \vee x_4)$.} \vspace{0.3in} Suppose $B$ is 1-satisfiable. Mark the numbered vertices on the ignition buses. Mark the labeled vertices in a variable circuit of $x_j$ and alternate vertices on shunt $s'$ if $x_j=1$; the unlabeled vertices in the variable circuit or alternate vertices on $s'$ (but not both), and alternate vertices on shunt $s$ if $x_j=0$ for a given truth assignment that renders $B$\/ 1-satisfiable. Then exactly one of $a,b,d$ in each $c_i$ is marked, leading to a total of 4 marked vertices in each $c_i$. The result is an even kernel $K$ of size \[|K|= 28m+4n+2 +5m +2\sum_{j=1}^{n} (m(j)+1)=39m+6n+2=C.\] Conversely, assume that $G$ has an even kernel $K$ of size $A \leq |K| \leq C$. None of the vertices labeled $p$ can be labeled, for otherwise we would already have a kernel of size $\geq 39m+6n+3 > C$. Now suppose that at most one of the ignition buses is marked, say ignition bus 2. Then each $c_i$ can contribute at most 8 to $K$ and each variable circuit at most $3(m(j)+1)$, so \[|K| \leq 14m+2n+1+8m+3\sum_{j=1}^{n} (m(j)+1)=31m+5n+1