Hardness of Path-Cost Arborescence Optimization

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

$P^v$ is the unique directed path from the root to $v$ in the arborescence, and $c^v(P^v)$ sums its arc costs under the destination-specific vector $c^v$.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The supplied registry flags this extraction as unrecoverable. It is displayed as a literal source fragment; the definitions provide context rather than a replacement formal statement.

Source-record limitation: Source flags the statement as unrecoverable: The official problem session contains one path-cost arborescence hardness problem, represented canonically by OWR-16633-014. This extraction repeats it verbatim. No separate clean statement is promoted; the original record remains publicly visible and retained for provenance.

Related catalogue records: 30003997. Separate source IDs are preserved for their provenance. The source text below is rendered literally where necessary; damaged formulas and composite extracts are not silently repaired into a new mathematical claim. The supplied catalogue marks this record as unrecoverable. Its extract and terminology are documented, but a complete original problem has not been reconstructed.

Statement recorded in the supplied source.

Why is the following optimization problem NP-hard: given a directed graph D=(V,A), a root r, and a cost vector c^v for each v

\textbackslash{}

ne r, find an arborescence T minimizing the sum over v

\textbackslash{}

ne r of c^v(P^v), where P^v is the r-to-v path in T? [S2]

Source status.

The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

The supplied fragment concerns duplicate Path-Cost Arborescence Problem. Its complete mathematical target is not recovered.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003998 (OWR-16633-015). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2019$, Oberwolfach Reports, DOI 10.4171/owr/2018/50, pp. 2969--3023 https://doi.org/10.4171/owr/2018/50.
• S3 Oberwolfach Report 50/2018 https://ems.press/content/serial-article-files/46772.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Preparation and review.

The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30003998 and code OWR-16633-015 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Related canonical identities: 30003997. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Literature and context check

The primary report, pp. 3014--3015, asks for NP-hardness with real cost vectors and does not impose nonnegative-cost restrictions. The proof below uses only nonnegative integers, hence falls within that original scope. The single external complexity theorem used is the Cook--Levin theorem: Boolean formula satisfiability is NP-complete under polynomial-time many-one reductions. Karp's author-written introduction to the consulted reprint explicitly records this theorem and attributes it to Cook's 1971 paper. The original Cook paper was not retrieved; no claim of checking its proof is made. The reduction to the needed bounded-clause form and every graph-gadget assertion are proved here. No exhaustive novelty search was performed, and this proof is not claimed new.

Research attempt: A standalone proof for the duplicate path-cost hardness record

This source ID repeats the preceding mathematical question. It is preserved as a separate record, not claimed to be an independent new conjecture. The full proof is repeated here so that this manuscript is standalone.

Starting problem and normal form.

Use Boolean formula satisfiability, with variables and binary AND, OR and unary NOT gates. This is the standard NP-complete decision problem just identified. It can be transformed in polynomial time to a conjunction of nonempty clauses of at most three literals while preserving satisfiability. Introduce a new variable $z$ for each gate with input variables $a,b$. For an AND gate use \[ (\neg z\vee a)\wedge(\neg z\vee b)\wedge(z\vee\neg a\vee\neg b). \] If $z=1$, the first two clauses force $a=b=1$; if $z=0$, the last clause forbids $a=b=1$. Thus these clauses are equivalent to $z=a\wedge b$. For OR use \[ (z\vee\neg a)\wedge(z\vee\neg b)\wedge(\neg z\vee a\vee b). \] If $z=0$, the first two force $a=b=0$; if $z=1$, the last requires at least one input to be one. For NOT use $(\neg z\vee\neg a)\wedge(z\vee a)$, which says exactly that $z$ and $a$ differ. Add the unit clause requiring the output variable to be one. Assigning the gates their actual values extends every satisfying original assignment to the clause system; conversely the clauses force all gate values, so every satisfying clause assignment satisfies the original formula. The number of new variables and clauses is linear in the formula size. Delete tautological clauses and repeated literals without changing satisfiability. Each retained clause contains at most one sign of each variable and is nonempty. A detected empty clause can be mapped to a fixed negative target instance; an empty conjunction to a fixed positive one. These trivial cases do not affect hardness. Write the remaining variables as $x_1,\ldots,x_k$ and clauses as $C_1,\ldots,C_m$.

The directed graph and its costs.

Create a root $r$; for each variable create vertices $t_i,f_i,v_i$; and create a clause vertex $q_j$ for each clause. Add arcs \[ r\to t_i,\quad r\to f_i,\quad t_i\to v_i,\quad f_i\to v_i, \quad v_i\to q_j\ \text{when variable }x_i\text{ occurs in }C_j. \] The graph is acyclic, with four layers: root, truth selectors, variable vertices, and clauses. Every nonroot vertex is reachable because clauses are nonempty. An outward spanning arborescence must use both root-selector arcs for every variable, must choose exactly one of $t_i\to v_i,f_i\to v_i$, and must choose exactly one incoming variable arc for each clause. Conversely any such choices give an arborescence: every nonroot vertex has one parent, and following parents strictly decreases the layer until it reaches $r$. This proves reachability and excludes cycles.

Give every non-clause destination the identically zero cost vector. For destination $q_j$, give cost zero to all arcs except that a selector arc into $v_i$ has cost one exactly when its chosen truth value falsifies the literal of $x_i$ in $C_j$. A positive literal therefore makes $f_i\to v_i$ cost one and $t_i\to v_i$ cost zero; a negative literal reverses those costs. For variables absent from $C_j$, both are zero. These are destination-specific vectors with entries in $\{0,1\}$.

Read an assignment from a tree by $x_i=1$ when its parent arc is $t_i\to v_i$, and $x_i=0$ otherwise. If clause $q_j$ chooses parent $v_i$, its unique root path is $r\to t_i\to v_i\to q_j$ or the corresponding path through $f_i$. Its cost under $c^{q_j}$ is exactly one if that literal is false and zero if it is true; the other two arcs have zero cost. Since the available clause parents are precisely its variables, the minimum possible clause cost for a fixed assignment is zero when the clause is satisfied and one when it is not. Choices at distinct clause vertices are independent and never affect any variable parent. Consequently \[ \min_T\sum_{v\ne r}c^v(P^v) =\min_{\text{assignments}}\#\{\text{unsatisfied clauses}\}. \] In particular the optimum is zero if and only if the formula is satisfiable. The graph has $1+3k+m$ vertices and $4k$ plus the number of variable-clause incidences many arcs. Even explicitly listing a cost for every destination and arc takes polynomial space and time. Thus an exact optimizer for the original problem would decide satisfiability in polynomial time. This proves NP-hardness, already on these layered acyclic graphs with nonnegative binary costs.

Verification and adversarial audit

The audit checked that all selector vertices must be spanned, not chosen as optional vertices; the assignment is encoded only by the unique parent of each variable vertex. No clause can select a variable absent from itself. Every root-to-clause path has exactly one cost-bearing selector arc under that clause's own vector. Tautological clauses and duplicate literals are explicitly removed, and the normal-form conversion preserves satisfiability in both directions. The problem asks for an optimization hardness proof, so hardness of distinguishing optimum zero suffices. Finite checks support but do not replace the proof.

Audit corrections.

The starting NP-completeness theorem is explicitly identified as an external classical dependency; no guessed theorem number or unchecked novelty claim is used. Every gadget and orientation implication is proved. Completion is measured against the full original hardness target.

External computation.

Executed check_arborescence_reduction.py under Python 3.14.2. For every ordered one- or two-clause formula over two variables, with each variable absent, positive, or negative in a nonempty clause, the script checked all 72 formulas. It enumerated 5696 undirected spanning trees in total and compared exact directed and root-dependent optima with the minimum unsatisfied-clause count. All equalities passed. This is finite falsification testing, not a general proof or a novelty test.

Scope and remaining gaps

The exact duplicate hardness target is fully covered by the standalone reduction. The retained duplicate identity and original source status are unchanged. No second independent novelty claim, approximation result, or different problem is introduced.

Full-solution scope declaration

The original target is an NP-hardness proof for the stated optimization problem. The reduction above maps a Boolean formula to a polynomial-size instance with optimum zero exactly when the formula is satisfiable, and therefore covers the entire requested hardness claim. Hardness of the restricted nonnegative-integer instances implies hardness when arbitrary real cost vectors are permitted. Every gadget vertex is mandatory, and both directions of the objective correspondence are proved. The sole external complexity dependency is Cook--Levin NP-completeness of Boolean formula satisfiability, whose statement was checked in Karp's author introduction; its proof was not rederived. The normal-form reduction and all graph claims are proved in the manuscript. No independent human or formal proof checking occurred. No novelty claim is made and no exhaustive novelty search was performed.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 100% The complete polynomial-time reduction establishes the original NP-hardness target. This estimate concerns target coverage, not novelty or independent verification.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46772 (consulted 2026-10-11).
• https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and adversarial mathematical review of the written argument; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Solved: the original NP-hardness target is proved. This is a fully written reduction with an explicit classical complexity dependency, without a novelty claim or independent human or formal verification.

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

$P^v$ is the unique directed path from the root to $v$ in the arborescence, and $c^v(P^v)$ sums its arc costs under the destination-specific vector $c^v$.

Polynomial time means a number of elementary steps bounded by a polynomial in the encoded input length. A decision problem is in $\mathrm{NP}$ if yes-instances have polynomial-length certificates verifiable in polynomial time; NP-hardness is under polynomial-time reductions.

An arborescence rooted at $r$ is a directed spanning tree with a unique directed path from $r$ to every other vertex; reversing all arcs gives the inward-rooted convention. The source question fixes the orientation convention.

Statement recorded in the supplied source.

Given a directed graph $D=(V,A)$, a root $r\in V$, and a cost vector $c^v$ for every $v\neq r$, prove that it is NP-hard to find an arborescence $T$ minimizing

$$\sum_{v\in V\setminus\{r\}}c^v(P^v),$$

where $P^v$ is the path from $r$ to $v$ in $T$. [S2]

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Prove hardness of minimizing all root-to-vertex path costs when each destination has its own cost vector.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003997 (OWR-16633-014). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2019$, Oberwolfach Reports, DOI 10.4171/owr/2018/50, pp. 2969--3023 https://doi.org/10.4171/owr/2018/50.
• S3 Oberwolfach Report 50/2018 https://ems.press/content/serial-article-files/46772. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30003997 and source code OWR-16633-014 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The primary report, pp. 3014--3015, asks for NP-hardness with real cost vectors and does not impose nonnegative-cost restrictions. The proof below uses only nonnegative integers, hence falls within that original scope. The single external complexity theorem used is the Cook--Levin theorem: Boolean formula satisfiability is NP-complete under polynomial-time many-one reductions. Karp's author-written introduction to the consulted reprint explicitly records this theorem and attributes it to Cook's 1971 paper. The original Cook paper was not retrieved; no claim of checking its proof is made. The reduction to the needed bounded-clause form and every graph-gadget assertion are proved here. No exhaustive novelty search was performed, and this proof is not claimed new.

Research attempt: A satisfiability reduction for destination-dependent path costs

Starting problem and normal form.

Use Boolean formula satisfiability, with variables and binary AND, OR and unary NOT gates. This is the standard NP-complete decision problem just identified. It can be transformed in polynomial time to a conjunction of nonempty clauses of at most three literals while preserving satisfiability. Introduce a new variable $z$ for each gate with input variables $a,b$. For an AND gate use \[ (\neg z\vee a)\wedge(\neg z\vee b)\wedge(z\vee\neg a\vee\neg b). \] If $z=1$, the first two clauses force $a=b=1$; if $z=0$, the last clause forbids $a=b=1$. Thus these clauses are equivalent to $z=a\wedge b$. For OR use \[ (z\vee\neg a)\wedge(z\vee\neg b)\wedge(\neg z\vee a\vee b). \] If $z=0$, the first two force $a=b=0$; if $z=1$, the last requires at least one input to be one. For NOT use $(\neg z\vee\neg a)\wedge(z\vee a)$, which says exactly that $z$ and $a$ differ. Add the unit clause requiring the output variable to be one. Assigning the gates their actual values extends every satisfying original assignment to the clause system; conversely the clauses force all gate values, so every satisfying clause assignment satisfies the original formula. The number of new variables and clauses is linear in the formula size. Delete tautological clauses and repeated literals without changing satisfiability. Each retained clause contains at most one sign of each variable and is nonempty. A detected empty clause can be mapped to a fixed negative target instance; an empty conjunction to a fixed positive one. These trivial cases do not affect hardness. Write the remaining variables as $x_1,\ldots,x_k$ and clauses as $C_1,\ldots,C_m$.

The directed graph and its costs.

Create a root $r$; for each variable create vertices $t_i,f_i,v_i$; and create a clause vertex $q_j$ for each clause. Add arcs \[ r\to t_i,\quad r\to f_i,\quad t_i\to v_i,\quad f_i\to v_i, \quad v_i\to q_j\ \text{when variable }x_i\text{ occurs in }C_j. \] The graph is acyclic, with four layers: root, truth selectors, variable vertices, and clauses. Every nonroot vertex is reachable because clauses are nonempty. An outward spanning arborescence must use both root-selector arcs for every variable, must choose exactly one of $t_i\to v_i,f_i\to v_i$, and must choose exactly one incoming variable arc for each clause. Conversely any such choices give an arborescence: every nonroot vertex has one parent, and following parents strictly decreases the layer until it reaches $r$. This proves reachability and excludes cycles.

Give every non-clause destination the identically zero cost vector. For destination $q_j$, give cost zero to all arcs except that a selector arc into $v_i$ has cost one exactly when its chosen truth value falsifies the literal of $x_i$ in $C_j$. A positive literal therefore makes $f_i\to v_i$ cost one and $t_i\to v_i$ cost zero; a negative literal reverses those costs. For variables absent from $C_j$, both are zero. These are destination-specific vectors with entries in $\{0,1\}$.

Read an assignment from a tree by $x_i=1$ when its parent arc is $t_i\to v_i$, and $x_i=0$ otherwise. If clause $q_j$ chooses parent $v_i$, its unique root path is $r\to t_i\to v_i\to q_j$ or the corresponding path through $f_i$. Its cost under $c^{q_j}$ is exactly one if that literal is false and zero if it is true; the other two arcs have zero cost. Since the available clause parents are precisely its variables, the minimum possible clause cost for a fixed assignment is zero when the clause is satisfied and one when it is not. Choices at distinct clause vertices are independent and never affect any variable parent. Consequently \[ \min_T\sum_{v\ne r}c^v(P^v) =\min_{\text{assignments}}\#\{\text{unsatisfied clauses}\}. \] In particular the optimum is zero if and only if the formula is satisfiable. The graph has $1+3k+m$ vertices and $4k$ plus the number of variable-clause incidences many arcs. Even explicitly listing a cost for every destination and arc takes polynomial space and time. Thus an exact optimizer for the original problem would decide satisfiability in polynomial time. This proves NP-hardness, already on these layered acyclic graphs with nonnegative binary costs.

Verification and adversarial audit

The audit checked that all selector vertices must be spanned, not chosen as optional vertices; the assignment is encoded only by the unique parent of each variable vertex. No clause can select a variable absent from itself. Every root-to-clause path has exactly one cost-bearing selector arc under that clause's own vector. Tautological clauses and duplicate literals are explicitly removed, and the normal-form conversion preserves satisfiability in both directions. The problem asks for an optimization hardness proof, so hardness of distinguishing optimum zero suffices. Finite checks support but do not replace the proof.

Audit corrections.

The starting NP-completeness theorem is explicitly identified as an external classical dependency; no guessed theorem number or unchecked novelty claim is used. Every gadget and orientation implication is proved. Completion is measured against the full original hardness target.

External computation.

Executed check_arborescence_reduction.py under Python 3.14.2. For every ordered one- or two-clause formula over two variables, with each variable absent, positive, or negative in a nonempty clause, the script checked all 72 formulas. It enumerated 5696 undirected spanning trees in total and compared exact directed and root-dependent optima with the minimum unsatisfied-clause count. All equalities passed. This is finite falsification testing, not a general proof or a novelty test.

Scope and remaining gaps

The original NP-hardness target is fully covered. The reduction uses outward arborescences as in the retained r-to-v path statement and only nonnegative binary costs. It does not claim a new hardness theorem or characterize approximation ratios. The classical satisfiability theorem is the sole external complexity dependency.

Full-solution scope declaration

The original target is an NP-hardness proof for the stated optimization problem. The reduction above maps a Boolean formula to a polynomial-size instance with optimum zero exactly when the formula is satisfiable, and therefore covers the entire requested hardness claim. Hardness of the restricted nonnegative-integer instances implies hardness when arbitrary real cost vectors are permitted. Every gadget vertex is mandatory, and both directions of the objective correspondence are proved. The sole external complexity dependency is Cook--Levin NP-completeness of Boolean formula satisfiability, whose statement was checked in Karp's author introduction; its proof was not rederived. The normal-form reduction and all graph claims are proved in the manuscript. No independent human or formal proof checking occurred. No novelty claim is made and no exhaustive novelty search was performed.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 100% The complete polynomial-time reduction establishes the original NP-hardness target. This estimate concerns target coverage, not novelty or independent verification.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46772 (consulted 2026-10-11).
• https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and adversarial mathematical review of the written argument; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Solved: the original NP-hardness target is proved. This is a fully written reduction with an explicit classical complexity dependency, without a novelty claim or independent human or formal verification.