The Complexity of Partial Function Extension for Coverage Functions

Gunjan Kumar; Umang Bhaskar

arxiv: 1907.07230 · v1 · pith:EXEXSTIInew · submitted 2019-07-16 · 💻 cs.DS · cs.GT

The Complexity of Partial Function Extension for Coverage Functions

Umang Bhaskar , Gunjan Kumar This is my paper

Pith reviewed 2026-05-24 20:23 UTC · model grok-4.3

classification 💻 cs.DS cs.GT

keywords coverage functionspartial function extensionNP-completenesssubmodular functionslearning lower boundsapproximate extension

0 comments

The pith

It is NP-complete to decide whether a partial function on subsets extends to a coverage function.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the decision problem of whether values given on some subsets of a ground set can be completed to a coverage function defined on every subset. Coverage functions form a subclass of submodular functions appearing in machine learning, game theory, and facility location. The central result establishes that this extendibility question is NP-complete, while simultaneously proving that yes-instances possess polynomial-sized certificates. The same hardness supplies a lower bound on learning coverage functions from data. The work further supplies upper and lower bounds on two natural notions of approximate extension, achieving nearly tight results for the additive L1 version.

Core claim

Given a family of subsets of [m] and a value at each point, deciding whether there exists a coverage function on all subsets that matches these values is NP-complete. When such an extension exists, a polynomial-sized certificate always exists. This hardness directly implies a computational lower bound for learning coverage functions. For approximate extensions the paper establishes upper and lower bounds on both multiplicative pointwise and additive L1 notions, with the latter nearly tight.

What carries the argument

The NP-completeness reduction establishing hardness of the partial function extension decision problem for coverage functions, together with the polynomial certificate for yes instances.

If this is right

Learning coverage functions from partial observations requires superpolynomial time under standard complexity assumptions.
Yes-instances of extendibility can be verified in nondeterministic polynomial time.
Algorithms exist for finding multiplicative or additive approximate extensions within the derived bounds.
The additive L1 approximate extension problem admits nearly matching upper and lower complexity bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar extension hardness may hold for broader classes such as all submodular functions.
The polynomial certificate could be turned into a practical verification procedure for modest ground-set sizes.
The techniques may adapt to related extension questions studied for convex or boolean functions.

Load-bearing premise

The partial function is presented explicitly as a collection of subsets together with their assigned values, and coverage functions are exactly those representable in the standard weighted-coverage form.

What would settle it

A concrete partial function on subsets for which extendibility holds yet no polynomial-sized certificate exists, or a polynomial-time algorithm that correctly answers the extendibility question on every input.

read the original abstract

Coverage functions are an important subclass of submodular functions, finding applications in machine learning, game theory, social networks, and facility location. We study the complexity of partial function extension to coverage functions. That is, given a partial function consisting of a family of subsets of $[m]$ and a value at each point, does there exist a coverage function defined on all subsets of $[m]$ that extends this partial function? Partial function extension is previously studied for other function classes, including boolean functions and convex functions, and is useful in many fields, such as obtaining bounds on learning these function classes. We show that determining extendibility of a partial function to a coverage function is NP-complete, establishing in the process that there is a polynomial-sized certificate of extendibility. The hardness also gives us a lower bound for learning coverage functions. We then study two natural notions of approximate extension, to account for errors in the data set. The two notions correspond roughly to multiplicative point-wise approximation and additive $L_1$ approximation. We show upper and lower bounds for both notions of approximation. In the second case we obtain nearly tight bounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

NP-completeness for partial extension to coverage functions plus nearly tight approximation bounds.

read the letter

The punchline here is that partial function extension to coverage functions is NP-complete, with a polynomial certificate, and the paper gives nearly tight bounds on two approximate extension problems. This extends previous complexity results from boolean and convex functions to coverage functions, which are monotone submodular functions defined by element weights. The hardness result immediately implies a lower bound on learning coverage functions from partial observations, as noted. The work does well on establishing both the hardness and the NP membership through the reduction, and the approximation section provides upper and lower bounds for multiplicative and additive error models, with the additive L1 case being nearly tight. The input is specified explicitly by subsets and values, which fits the standard model. A minor point is that the learning lower bound is a direct consequence rather than an independent result, so it doesn't add substantial new technical content. The reduction itself appears to be from a standard hard problem without any circularity. The paper is for theorists interested in submodular optimization and learning complexity. Readers working on function extension problems or approximation algorithms for coverage functions will get the most out of the reduction and the bound analysis. It deserves a serious referee because the claims are precise and the evidence from the reduction supports them. I would recommend sending this to peer review.

Referee Report

0 major / 3 minor

Summary. The paper claims that deciding whether a partial function (specified by values on an explicit family of subsets of [m]) can be extended to a coverage function is NP-complete, that the problem is in NP via a polynomial-sized certificate, that this yields a learning lower bound for coverage functions, and that two natural approximate-extension variants (multiplicative pointwise and additive L1) admit upper and lower bounds, with the additive case being nearly tight.

Significance. If the results hold, the work supplies fundamental complexity characterizations for an important subclass of submodular functions used across machine learning and combinatorial optimization. The explicit polynomial certificate for membership in NP and the nearly tight additive-L1 bounds are concrete strengths; the learning lower bound follows directly from the hardness result.

minor comments (3)

The abstract states that the additive-L1 bounds are 'nearly tight' but does not record the precise constants or the gap; adding these numbers would improve readability.
[Introduction] Notation for the ground set and the coverage representation (element weights) is introduced only after the problem statement; moving a short definition paragraph to the introduction would help readers unfamiliar with coverage functions.
The learning lower bound is mentioned in the abstract and presumably derived in the hardness section; a one-sentence pointer from the learning paragraph back to the specific reduction would clarify the implication.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. No major comments were listed in the report, so there are no specific points requiring point-by-point rebuttal or changes to the manuscript.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes NP-completeness of partial function extension to coverage functions via a standard many-one reduction from a known NP-complete problem, together with a direct argument that a polynomial-size certificate exists for membership in NP. No equations or claims reduce the target result to a fitted parameter, a self-citation chain, or a definitional renaming of the input; the hardness and certificate arguments are independent of the final statement and rely on external combinatorial constructions. The learning lower bound follows directly from the hardness result without circular reuse of the same data or parameters.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper builds on standard definitions and complexity theory without introducing new free parameters or entities.

axioms (2)

domain assumption Standard definition of coverage functions as a subclass of submodular functions
The result depends on the accepted definition of coverage functions in the literature.
standard math Standard notions of NP-completeness and polynomial-time reductions
The proof technique relies on these foundational concepts in complexity theory.

pith-pipeline@v0.9.0 · 5724 in / 1142 out tokens · 29455 ms · 2026-05-24T20:23:03.791501+00:00 · methodology

The Complexity of Partial Function Extension for Coverage Functions

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)