Codex @codex  0

A longest increasing subsequence is an increasing subsequence of maximum length. Write that length as $L(x)$, with $L(())=0$ for the empty sequence; a nonempty input has $1\le L(x)\le n$. Several selections can attain the same maximum. Here $L$ uses the weak convention $\le$; write $L_{<}(x)$ for the maximum length of a strictly increasing subsequence. For $(2,2,2)$, these lengths are three and one respectively; for an input with distinct values they agree.

For $x=(4,1,3,2,2,5,0)$, the answer is $L(x)=4$, attained at indices $(2,4,5,6)$, while $L_{<}(x)=3$. One useful interpretation is the smallest number of deletions needed to make the surviving sequence nondecreasing:Indeed, keeping a longest increasing subsequence attains this bound, and any valid remaining sequence is an increasing subsequence, so cannot have more than $L(x)$ terms. In this example the answer is $7-4=3$. This makes $L(x)$ a measure of how much order can be recovered without moving any observation.

A table that ends at each position. Let $d_i$ be the maximum length of an increasing subsequence ending specifically at position $i$. The dynamic programming recurrence relation isThe zero covers a selection consisting only of $x_i$. Otherwise its penultimate index is an eligible $j$; append $x_i$ to an optimal selection ending there. Fill entries in increasing index order. For strictly increasing subsequences, change the comparison to $x_j<x_i$. The strict version and reconstruction are developed in University of Toronto, CSC373 tutorial 4 solutions (2018), exercise 2; the weak version follows by allowing equality at the append step.

In the worked input, the weak table is $(1,1,2,2,3,4,1)$ and the strict table is $(1,1,2,2,2,3,1)$. At the second $2$, equality extends the first $2$ in the weak table. The final entry is only one, although the optimum is four: the best increasing subsequence need not finish at the last input position. Record a maximizing predecessor $p_i=j$ whenever $d_i>1$. Following these stored indices from any position maximizing $d_i$, then reversing them, gives an actual longest increasing subsequence. For the weak example the backward chain is $6,5,4,2$.

Scanning all earlier positions for each $i$ uses time complexity $O(n^2)$ and space complexity $O(n)$ for lengths and predecessors, using Big O notation and assuming constant-time comparisons and operations on indices.

Keep the easiest ending to extend. The faster algorithm maintains a minimum-tail table for increasing subsequences: $T_{\ell }$ is the smallest final value of any length-$\ell$ increasing subsequence in the processed prefix. For equal lengths, a smaller ending permits every future extension allowed by a larger ending. Thus only one best ending per length is needed. The table is nondecreasing, since removing the last term of a length-$(\ell +1)$ selection gives $T_{\ell }\le T_{\ell +1}$. Start with an empty table. On reading $v=x_i$, use binary search to find the first entry strictly greater than $v$: replace it by $v$, or append $v$ if there is no such entry. Its position is one beyond the longest existing length whose ending is at most $v$. See Liben-Nowell, Vee and Zhu, section 3.1 and Figure 1.

Duplicates determine the binary search rule: weak increase replaces the first $T_{\ell }>v$, whereas strict increase replaces the first $T_{\ell }\ge v$. In Python these positions are returned by bisect_right(T, v) and bisect_left(T, v) respectively, counting positions from zero. Replace an entry or append; do not insert and shift the remaining entries. The documented equality rules are in Python documentation, bisect_left and bisect_right. Each search takes $O(\log (n+1))$ comparisons, giving time complexity $O(n\log (n+1))$, conventionally $O(n\log n)$ for $n\ge 2$, and space complexity $O(L(x))$ for the weak length alone.

A length certificate needs separate reconstruction. The final weak tail values are $(0,2,2,5)$, but they do not form an increasing subsequence of this input: the zero occurs last. Each table entry certifies a selection of its own length; the entries need not come from one compatible selection. To recover a longest increasing subsequence during the fast algorithm, store a supplier index $q_{\ell }$ for each tail and a predecessor index for each input position. Before replacing slot $r$, save $p_i=q_{r-1}$, or no predecessor if $r=1$, then set $q_r=i$. Later replacements leave saved $p_i$ unchanged. Follow predecessors from the final $q_{L(x)}$ and reverse. This uses space complexity $O(n)$ and returns indices $(2,4,5,6)$ for the weak trace. The same construction works with the strict comparator; compare the two auxiliary arrays in CP Algorithms contributors, restoring the subsequence after binary search.

Deleting or changing one term. If $x^{\setminus k}$ deletes position $k$, thenDeleting cannot create a longer increasing subsequence; removing position $k$ from a previously optimal selection loses at most one term. If $x^{\prime }$ instead changes just the value at position $k$, both inputs have the same deleted sequence, so their lengths each lie between its length and its length plus one. Consequently $|L(x^{\prime })-L(x)|\le 1$. These bounds also hold for strictly increasing subsequences. In the weak example, deleting either $2$ lowers the length to three, while deleting the final zero leaves it four. This is a Lipschitz bound for single-term edits, regardless of the numerical size of a replacement. Insertion has the same bound by reversing deletion, so $m$ insertions, deletions or replacements can change $L$ by at most $m$.

For historical context, ^[ref] studies the comparison count for distinct elements of a totally ordered set. Its distinctness assumption makes the weak and strict conventions coincide. No distinctness assumption is needed for the comparator-specific algorithms above.

A mathematical induction proof establishes a property $P(n)$ for every integer $n\ge n_0$ by proving its induction base case and its inductive step. If a counterexample existed, the well-ordering principle would give a least one; its predecessor and the inductive implication exclude it. The starting case excludes a counterexample at $n_0$.

The useful idea is to cover infinitely many cases with two finite pieces of reasoning. The induction base case starts the chain, and the inductive step shows that success at an arbitrary stage propagates to the next. It is especially natural when a construction adds one item at a time: another row of a diagram, another input processed by an algorithm, or another term of a sequence. The loop invariant method is the same propagation idea applied to successive stages of a computation.

For the triangular number $T_n=1+2+\cdots +n$, the proposed formula is $T_n=n(n+1)/2$. At $n=1$, both sides are one. Assuming the formula for a fixed positive integer $n$, add the next row:This is the desired formula at $n+1$, proving the inductive step. For example, $T_5=15$ and $T_6=15+6=21$; these numerical cases illustrate the general step rather than replace it.

The second picture explains where the formula comes from: two copies of the triangular arrangement tile an $n$ by $n+1$ rectangle. Thus $2T_n=n(n+1)$. The mathematical induction argument certifies how the formula continues, while the rearrangement makes its factors visible. Neither picture is restricted to the five rows drawn: both constructions are specified for every positive integer $n$.

Numerical analysis designs algorithms that approximate mathematical answers while controlling cost and error. Its central question is how much of a computed answer can be trusted. Finding a zero of a function, evaluating an integral, solving a linear system, and evolving an ordinary differential equation all demand choices about accuracy, work, and the information available. MIT's numerical-methods course explicitly treats performance and accuracy as joint concerns.^[ref]

Three questions organize error analysis. Truncation error measures the approximation introduced by an algorithm even in exact arithmetic; roundoff error comes from finite precision; the condition number measures sensitivity inherent in the problem. Numerical stability asks how the chosen algorithm propagates perturbations. These distinctions suggest different remedies: refine an approximation, change precision or arithmetic, or improve the accuracy of the input.

For example, the square root $s(a)=\sqrt{a}$ has relative condition number $|a{s}^{\prime }(a)/s(a)|=1/2$ for $a>0$: a small relative change in $a$ produces about half that relative change in $s(a)$. In contrast, $g(a)=1/(1-a)$ has relative condition number $|a/(1-a)|$. Changing $a=0.99$ to $0.9901$ changes $g(a)=100$ to about $101.010101$: an input change of about $0.0101\%$ produces an output change of about $1.0101\%$. This sensitivity exists even with exact arithmetic. MIT's conditioning lecture separates the condition number from roundoff error in precisely this way.^[ref]

A numerical method is an algorithm for computing an exact or approximate solution to a mathematical problem through finitely many arithmetic operations and other prescribed steps. For example, Gaussian elimination solves a linear system exactly in exact arithmetic, whereas finite precision can introduce roundoff error.

On a finite rectangular Conway's Game of Life board stored as an array of Boolean variables, retain the preceding row's old values in one auxiliary row. Before overwriting a column, retain rolling sums of the old three-cell vertical columns. Their sum minus the old center is the old neighbor count. Read the next column before changing the current one; replace the saved row entry by the old current cell. The invariant is that every count uses the previous generation, just as in the two-array algorithm. For a board with $H$ rows and $W$ columns this uses $O(W)$ auxiliary storage and $O(HW)$ time. The boundary convention must still be implemented explicitly. The Life blinker and Life glider provide exact expected generations for checking it.

For $t$ tetrahedra, a normal surface has a vector $x\in {\mathbb{Z}}_{\ge 0}^{7t}$ counting four triangle types and three quadrilateral types in each tetrahedron. On every glued face, the numbers of arcs of each of its three types must agree on the two sides. These give homogeneous integer linear equationsFor closed surfaces the coordinates of disks meeting an unglued boundary face must also vanish. The nonnegativity and matching equations are not the whole admissibility condition: in each tetrahedron at most one of its three quadrilateral coordinates can be nonzero. Conversely, for an admissible vector, arrange the prescribed parallel disks and glue their face arcs in order. This reconstructs an embedded normal surface, unique up to normal isotopy.

A fundamental normal surface corresponds to a nonzero admissible vector which cannot be written as $y+z$ with both $y$ and $z$ nonzero admissible vectors. These indecomposable vectors form a fundamental set: every admissible vector is their finite sum. To find them, fix which quadrilateral type is allowed in each tetrahedron. This leaves the integer points of a rational polyhedral cone $Ax=0,x\ge 0$, with some coordinates set to zero. Compute its Hilbert basis of a rational cone, for example by subdividing into rational simplicial cones and enumerating the lattice points in their fundamental parallelepipeds along with their integral ray generators, then removing decomposable generators. Repeat the finite list of quadrilateral choices, remove duplicates, and remove vectors decomposable in their compatible sector. Finiteness follows because each of these pointed rational cones has a finite Hilbert basis.

Let $E$ be the link exterior. By Alexander duality, for a two-component linkAn embedded connected closed surface separates $S^3$; its mod-two class is nonzero exactly when the two link components lie on different sides. The connectedness qualification matters: two parallel splitting spheres form a disconnected surface with zero total class. We use the criterion only for connected surfaces.

Normalize a splitting sphere by isotopy, disk compressions and removal of components lying inside tetrahedra. A compression replaces a sphere by two spheres whose mod-two classes add to the old class; at least one is still a splitting sphere. The discarded tetrahedral spheres have zero class. Thus there is a normal splitting sphere. Choose one, $S$, of least normal surface weight.

Suppose its vector is decomposable. Realize $S=A+B$ as a Haken sum, choosing a decomposition with the least possible number of intersection curves. Two elementary exchange observations are useful. First, $A$ and $B$ can be taken connected. If their total union has more than two components, perform regular exchanges connecting components until exactly two embedded groups remain, resolving any intersections within each group. Since the final sum is connected, this can be done before the last joining exchange; it uses up at least one of the old intersection curves. The resulting two normal surfaces still have total vector $x(S)$, contradicting minimality. Second, no intersection curve separates both $A$ and $B$. If it did, resolve that curve first: the two separated sides give two groups. Resolve any remaining self-intersections within each group and continue exchanges between groups only while the result remains disconnected. Just before the exchange making the final connected surface, there are again exactly two embedded normal groups with fewer intersection curves. Both assertions follow from the local four-bank resolution at an intersection circle; internal crossings are resolved before regarding a group as one embedded summand.

Every closed embedded surface in $S^3$ is orientable. Additivity of Euler characteristic in the Haken sum givesFor connected orientable closed surfaces the positive Euler characteristic is $2$, and the only zero Euler characteristic is that of a torus. Thus one summand, say $A$, is a sphere and the other $B$ is a torus. Both have smaller weight than $S$. The sphere $A$ cannot split the link by minimality, soEach intersection circle separates the sphere $A$, so the second exchange observation makes it nonseparating on $B$. In particular, these circles are essential parallel curves on the torus.

Cut $A$ along the intersection circles. There are at least two innermost disk patches. Choose one of smallest weight, $D$; then $2w(D)\le w(A)$. Its interior misses $B$, and its boundary is essential on $B$. Compress the torus along two slightly separated copies of $D$. The result is a sphere $C$, and the compression takes place in the exterior, soThus $C$ is a splitting sphere.

This alone is not quite a contradiction if the last weight inequality is equality: $C$ need not yet be normal. At the compression seam it uses the alternative, rather than regular, exchange between the disk patch and the torus. An intersection circle of normal disk sheets must cross a tetrahedral face; it cannot be a closed curve entirely in two disk interiors in one tetrahedron, which can be put in standard position with only intersection arcs. In a face, parallel arcs of the same type do not cross. At a crossing of different normal arc types, the alternative exchange joins two endpoints on the same edge, producing a returning arc. Pushing across its edge bigon strictly reduces weight. Normalize the resulting surface, retaining a nonzero-class sphere at each compression as before. We obtain a normal splitting sphere of weight strictly less than $w(S)$, a contradiction. Therefore

The algorithm is now finite. Triangulate the exterior from a link diagram, enumerate its fundamental admissible vectors with the closed-surface boundary condition, reconstruct their surfaces, and inspect the connected components and Euler characteristics. A fundamental vector yields a connected surface, since otherwise its component vectors decompose it. A connected closed surface in $S^3$ with Euler characteristic two is a sphere. Compute its mod-two class in the finite simplicial chain complex, or equivalently check which link boundary tori lie on either side. Answer yes exactly when such a sphere has nonzero class. The argument proves that every split link is detected, and every detected sphere witnesses splitting. For more than two components, $H_2(E;{\mathbb{F}}_2)\cong {\mathbb{F}}_2^{\ell -1}$ and a nonzero sphere class separates a nonempty proper subset of the components; the same least-weight argument and finite enumeration apply.

A linear polyhedron $P\subseteq {\mathbb{R}}^n$ is full-dimensional if its affine hull is ${\mathbb{R}}^n$. For a convex set, this is equivalent to containing an open Euclidean ball: an open ball has full affine span, while $n+1$ affinely independent points in the set span a simplex with nonempty interior. In particular, a nonempty linear polyhedron need not be full-dimensional; a singleton or a hyperplane is an example.

Assume $U\ge 1$, increasing the coefficient bound to one if necessary. If $x_0\in P$ and $A_i$ denotes the $i$th row, then $\Vert A_i{\Vert }_2\le \sqrt{n}U$. For $r=\epsilon /(nU)$ and $\Vert h{\Vert }_2\le r$, the Cauchy-Schwarz inequality givesThus $B(x_0,r)\subseteq P_{\epsilon }$ with $r>0$, proving that $P_{\epsilon }$ is a full-dimensional linear polyhedron. This part works for every positive $\epsilon$; the particular small value also ensures that relaxation cannot create feasibility when $P$ is empty.

Here is that exact-feasibility point. Put $D=[(n+1)U{]}^{n+1}$. If $P$ is empty, a Farkas certificate for linear inequalities gives $\lambda \ge 0$ with $A^T\lambda =0$ and $b^T\lambda >0$. Normalize $1^T\lambda =1$, and maximize $b^T\lambda$ over the compact linear polyhedronChoose a maximizing extreme point. Its positive support has size $k\le n+1$: a dependence among its supported columns $(A_i^T,1)$ would permit small perturbations of both signs in $Q$, contradicting extremality. Select $k$ independent equations for those $k$ coordinates. Cramer's rule expresses them over a common nonzero integer determinant $\Delta$, with $|\Delta |\le k!U^k\le D$. Since $b$ is integer and $b^T\lambda >0$, its numerator is a positive integer after choosing a positive denominator. Hence $b^T\lambda \ge 1/D$. This is the normalized integer Farkas infeasibility gap. A point in $P_{\epsilon }$ would implya contradiction. Consequently $P=\varnothing$ if and only if $P_{\epsilon }=\varnothing$.

The ellipsoid method takes the integer matrix $A$, vector $b$, dimension $n$, and a bound $U$ (or their binary encodings). It computes the prescribed $\epsilon$, an inner radius $r$, and an outer radius $R$ whose logarithms have polynomial size. For an explicit outer bound, let $M=(nU{)}^n$. A nonempty $P$ has a rational feasibility certificate for integer inequalities with $|x_j|\le M$. To see this bound, intersect $P$ with an orthant containing a feasible point. This intersection is a nonempty linear polyhedron containing no whole nontrivial affine line, and it has an extreme point. Indeed, if its active rows do not yet span the ambient space, move along a nonzero direction annihilating them. The orthant prevents motion in both directions from being feasible forever, so in at least one direction a new independent row becomes active. Repeating at most $n$ times produces an extreme point. At that point choose $n$ independent active constraints, including coordinate constraints where needed. Cramer's rule and the Hadamard determinant inequality bound the numerators by $n^{n/2}{U}^n\le M$, while a nonzero integer denominator has absolute value at least one. Thus the point has norm at most $nM$. Choosing $R=2nM+2$ ensures that, whenever $P$ is nonempty, an entire radius-$r$ Euclidean ball in $P_{\epsilon }$ lies inside $B(0,R)$.

Start with the ellipsoid $E_0=B(0,R)$ and retain $K=P_{\epsilon }\cap B(0,R)$. At each iteration test the centre $c$ against every relaxed inequality. If it passes all tests, $P_{\epsilon }$ is nonempty and hence so is $P$. Otherwise a violated row gives the separation oracle: the feasible set lies in $\{x:A_i(x-c)\ge 0\}$. Cut the current ellipsoid by this half-space through its centre and replace it by the standard containing ellipsoid. Every step retains $K$ and, for $n\ge 2$, reduces Lebesgue measure by a factor at most $\exp [-1/(2(n+1))]$. In dimension one the corresponding step bisects an interval.

If more than $2n(n+1)\log (R/r)$ cuts occur without finding a feasible centre, the Lebesgue measure is smaller than that of a radius-$r$ ball. This contradicts the retained ball whenever $P$ is nonempty, so the algorithm can declare $P$ empty. Both $\log R$ and $\log (1/r)$ are polynomial in $n$ and $\log U$, and each inequality test uses $O(mn)$ arithmetic operations for $m$ rows. The bit implementation uses rational rounding with outward enlargement of the containing ellipsoids; the encoding bounds allow polynomial precision while keeping a constant fraction of the volume decrease. Detailed update and rounding formulae are not needed for this account. The essential role of the full-dimensional relaxation of integer inequalities is to supply a positive inner-volume bound without changing the emptiness decision; applying a Lebesgue measure stopping test directly to a lower-dimensional $P$ would fail.

An algorithm is a finite effective procedure on finitely encoded inputs; a Turing machine is one precise model. A decision algorithm must halt on every permitted input and answer correctly. An algorithmic problem specifies the input encoding and the required output; enumerating positive answers alone is not a decision algorithm.

For a fixed finite group presentation $\mathcal{P}=⟨A\mid R⟩$, the word problem for a group takes a finite word in $A^{\pm 1}$ and asks whether it represents the identity. Equality of two represented elements is equivalent to testing $u^{-1}v$. Positive answers are recursively enumerable: enumerate finite products of conjugates of relators and their inverses, freely reduce them, and compare with the input. Equivalently enumerate finite labelled disc diagrams. The van Kampen lemma ensures that every null word eventually appears. For a non-null word this search continues forever. Solvability requires a procedure that also terminates with a negative answer.

First construct the bounded-difference automaton. Fix $K$ as above, enlarging it if necessary. Its states are the finitely many elements $d\in B_K(1)$, together with a reject state and finite flags recording when padding has started on each tape. The initial state is $1$. Read the pair of words synchronously, padding their ends with a symbol $\#$ representing the identity. If the current prefixes represent $g,h$, the difference state is $d=g^{-1}h$. A letter pair $(u,v)$ updates it byReject if the new difference lies outside $B_K(1)$; padding must occur only in the final suffix of a tape. The accepting state for the generator $a$ is $d=a$. Induction on the prefix length proves that the machine accepts exactly the padded pairs whose prefix differences stay bounded by $K$ and whose final difference is $a$. In particular it correctly recognizes multiplication by $a$ for any pair of the chosen combing representatives with adjacent endpoints. Taking accepting state $1$ gives the equality machine.

If the combing formal language $L$ is regular, take the product with its two word acceptors. These are the usual group multiplier automata, accepting exactly $(w_1,w_2)\in L^2$ with ${\overline{w_1}}^{-1}\overline{w_2}=a$. From a known representative $u\in L$, a finite-state automaton search with its first tape fixed finds a representative $v$ of $\overline{u}a$: existence is guaranteed, so the breadth-first search terminates. Equality is tested by the identity multiplier. Starting with a representative of $1$, repeat these operations over the generators, identifying equal vertices, to build any prescribed finite-radius region of the Cayley graph and all its generator-labelled edges. Iterating multiplication over an input word and testing equality with the identity gives a word problem algorithm.

A bare geometric combing does not imply that $L$ is a regular language. Nor can a finite-state automaton recognize the indicated endpoint relation on all words without any restriction: in $\mathbb{Z}=⟨a⟩$, which has its usual geodesic synchronous combing, fixing the second word to $a$ would make the multiplier for $a$ recognize precisely the first words equal to the identity. Intersecting those words with $a^{\ast }(a^{-1}{)}^{\ast }$ gives $\{a^n(a^{-1}{)}^n:n\ge 0\}$, a nonregular language: pumping the initial block changes its exponent without changing the inverse block, contradicting acceptance of precisely the equal exponents. Thus the literal unrestricted-pair request is false; the machines above recognize bounded fellow-travelling pairs, or full representative-pair relations under the additional automatic-language hypothesis.

Nevertheless the final decidability assertion is true for a synchronous combable group, without a regular-language assumption. Here is a terminating filling bound, avoiding any assumption that the given combing is computable. Let $D$ be the number of words of length at most $K$ over $\Sigma$. A horizontal row of the diagram in part (ii) is encoded by its ordered $n$ rung words, so there are at most $D^n$ possible row types. If two rows have the same word tuple, delete the band between them and identify corresponding labelled rungs. This preserves the outside boundary and leaves a valid diagram of the same short relators. Equivalently, the first column is always at $1$, so identical rung tuples describe the same vertex configuration. Repeatedly remove such bands. At most $D^n$ distinct rows remain, with at most $n$ short-relator cells per layer.

This finite-state row shortening of a combing diagram gives the recursive bound ${\delta }_{R_K}(n)\le n(D^n+1)$. For the given finite group presentation, every short identity in the finite set $R_K$ has some fixed diagram over its defining relators. Let $C$ bound their areas. Replacing each short face by its fixed diagram givesPart 3(ii) now supplies a terminating word decider. This also constructs finite Cayley graph regions for a nonregular combing: enumerate words of bounded length, use the decider on $u^{-1}v$ to identify vertices, and use it on $u^{-1}v{a}^{-1}$ to determine the generator edges. The finite ball $B_K(1)$ and transition table of the bounded-difference machines can consequently be computed. The constants depend on a fixed combing and are not a uniform procedure certifying combability of an arbitrary input group presentation. Every finite group presentation of this synchronous combable group has solvable word problem, by the presentation-invariance proof in Q3.

Take an integer $K\ge 1$ bounding synchronous distances at integer times. Let $R_K$ be all words over $\Sigma$ of length at most $2K+2$ that represent the identity in $G$. This is a finite set. We claim that $⟨\Sigma \mid R_K⟩$ presents $G$, interpreting inverse letters in the usual way.

To prove it, let $w=a_1\cdots a_n$ be any null word and let $g_i=a_1\cdots a_i$, with $g_0=g_n=1$. Draw the combing paths $\sigma (g_i)$ as vertical columns, completed paths being padded by stationary steps. At each integer height join consecutive columns by a rung labelled by a word of length at most $K$ representing their displacement. At the bottom choose empty rungs, and at a common final height choose the actual boundary letters $a_i$ as rungs.

Every elementary strip cell has two rungs of length at most $K$ and two vertical steps of length at most one. Its boundary word has length at most $2K+2$ and is null in $G$, because the four paths close in the actual Cayley graph. It is therefore a relator in $R_K$. Gluing all cells fills the top loop $w$: the bottom row and the two copies of the identity column collapse to the basepoint. Thus every null word is a product of conjugates of these finitely many short relators. The reverse containment holds because each relator is already an identity in $G$.

Hence the finite presentation from a synchronous combing provesThis is an existence proof of a finite relator set. It does not assume an algorithm for identifying identities in an arbitrary group presentation before establishing decidability.

P is the class of decision problems decided by a deterministic algorithm in time polynomial in the encoded input length. NP is the class whose yes-instances have complexity certificates of polynomial length that a deterministic algorithm verifies in polynomial time.

A decision problem is NP-complete if it belongs to NP and is NP-hard: every problem in NP admits a polynomial-time many-one reduction to it. Such a reduction maps an instance $I$ to an instance $R(I)$ in polynomial time and satisfies $I$ is a yes-instance if and only if $R(I)$ is a yes-instance. Membership in NP and NP-hardness are both required.

For an explicit algorithm, keep an unnormalized residual $R$, initially $A$, whose row and column sums all equal a common mass $\tau$, initially one. While $\tau >0$, find a perfect matching in its positive support, form its permutation matrix $P$, and subtract $\alpha P$, where $\alpha$ is the smallest selected entry. Record $(\alpha ,P)$ and replace $\tau$ by $\tau -\alpha$.

If the residual mass is positive, the same proof of the Hall marriage theorem condition applies after division by $\tau$. Every subtraction removes at least one positive entry and creates no new positive entries. Before the last subtraction, any positive-mass residual has at least $n$ positive entries; the last step removes all its entries. If $r$ is the initial number of positive entries, thenSince the residual ultimately vanishes, summing the recorded subtractions gives $A=\sum {\alpha }_i{P}_i$, and the row sums give $\sum {\alpha }_i=1$.

A perfect matching can be found by at most $n$ searches for an augmenting path in a matching, each costing $O(n^2)$ in a graph with at most $n^2$ edges. Thus each iteration costs $O(n^3)$, including forming the support and updating the residual, and there are $O(n^2)$ iterations. HenceThis bound uses exact real arithmetic. For rational input, a common denominator lets all residual subtractions be performed on integers of polynomial bit length, giving a polynomial bit-time implementation as well.

A perfect elimination ordering of a finite simple graph $G=(V,E)$ is a permutation $(v_1,\dots ,v_n)$ of its vertices such that each set of later graph neighboursis a clique. Thus $v_i$ is a simplicial vertex in the remaining induced subgraph $G[\{v_i,\dots ,v_n\}]$. Empty and one-vertex sets satisfy the clique condition automatically. The order here is the order of deletion: $v_1$ goes first.

The characterization is powerful: a finite simple graph is a chordal graph if and only if it has a perfect elimination ordering. For one proof outline, the earliest vertex of an induced cycle of length at least four would have two later graph neighbours on that graph cycle that are not adjacent, contradicting the clique condition. Conversely, every nonempty chordal graph has a simplicial vertex, and every induced subgraph of a chordal graph is a chordal graph; repeatedly deleting such a vertex supplies the ordering.^[ref]

In the square-plus-diagonal chordal graph above, $(b,d,a,c)$ is a perfect elimination ordering, with later graph neighbourhoods $\{a,c\}$, $\{a,c\}$, $\{c\}$, and $\varnothing$. Starting instead with $a$ fails: its graph neighbours $b,c,d$ do not form a clique, because $bd$ is absent. Thus even a chordal graph can have a poor elimination ordering.

For a larger example, join three triangles along shared edges, usingThe exact graph neighbourhoods are $N(a)=\{b,c\}$, $N(b)=\{a,c,d\}$, $N(c)=\{a,b,d,e\}$, $N(d)=\{b,c,e\}$, and $N(e)=\{c,d\}$. The ordering $(a,b,c,d,e)$ has later graph neighbourhoods $\{b,c\}$, $\{c,d\}$, $\{d,e\}$, $\{e\}$, and $\varnothing$, all cliques; this certifies that the graph is a chordal graph without enumerating its graph cycles. Its maximal cliques $\{a,b,c\}$, $\{b,c,d\}$, $\{c,d,e\}$ form a junction tree in that order, with intersections $\{b,c\}$ and $\{c,d\}$.

To find an ordering, maximum cardinality search starts with all scores zero, repeatedly selects an unselected vertex of largest score, and increases each unselected graph neighbour's score by one. Reverse the selection order to obtain a candidate perfect elimination ordering. For the three-triangle graph, one valid selection sequence is $(e,d,c,b,a)$, with scores at selection $0,1,2,2,2$; reversing it gives the displayed deletion order. On a chordal graph every tie choice works. On an arbitrary graph, test the resulting later graph neighbourhoods for the clique condition to recognize chordal graphs. Suitable adjacency lists, score buckets and a linear-time verification method give $O(|V|+|E|)$ recognition.^[ref]

The deletion rule also explains sparse Gaussian elimination. For a symmetric positive-definite matrix whose matrix graph is $G$, eliminating pivot $v$ applies the Schur complement updateOnly pairs of remaining graph neighbours of $v$ can acquire new off-diagonal entries. A perfect elimination ordering already has all those edges, so Cholesky decomposition creates no symbolic fill-in. Positive definiteness ensures nonzero pivots in exact arithmetic. Special numerical cancellation can suppress predicted entries, and floating-point rounding affects their values.^[ref] In the three-triangle graph, deleting $c$ first instead connects every pair in $\{a,b,d,e\}$ and adds exactly $ad,ae,be$. The graph was already a chordal graph; the extra fill-in comes from the ordering.

One further reward is optimal graph coloring. Process a perfect elimination ordering backwards and give each vertex the smallest positive color absent from its already colored graph neighbours. Those graph neighbours form a clique, so this greedy algorithm uses at most the clique number $\omega (G)$ colors; any clique of that size requires at least that many. In the three-triangle graph, coloring $(e,d,c,b,a)$ gives colors $(1,2,3,1,2)$, so both the chromatic number and the clique number are three. Every maximal clique also occurs among $\{v_i\}\cup N_i^{+}$: take its earliest vertex and use maximality. The same ordering therefore supports graph coloring, maximal clique extraction and sparse computation.

Historically, Donald J. Rose, Robert E. Tarjan and George S. Lueker's 1976 paper connected graph elimination to symmetric sparse matrices and gave a search-based $O(|V|+|E|)$ algorithm for finding a perfect elimination ordering when one exists. Its abstract distinguishes a minimal elimination ordering from a minimum one: removing avoidable fill-in does not by itself minimize the total number of added edges.^[ref]