Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid

Diwan, Haya; Hellerstein, Lisa; Megow, Nicole; Schlöter, Jens

doi:10.4230/LIPIcs.STACS.2026.32

Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid

Haya Diwan

Department of Computer Science and Engineering, New York University, NY, USA Lisa Hellerstein

Department of Computer Science and Engineering, New York University, NY, USA Nicole Megow

Faculty of Mathematics and Computer Science, University of Bremen, Germany Jens Schlöter

Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands

Abstract

Research in explorable uncertainty addresses combinatorial optimization problems where there is partial information about the values of numeric input parameters, and exact values of these parameters can be determined by performing costly queries. The goal is to design an adaptive query strategy that minimizes the query cost incurred in computing an optimal solution. Solving such problems generally requires that we be able to solve the associated verification problem: given the answers to all queries in advance, find a minimum-cost set of queries that certifies an optimal solution to the combinatorial optimization problem. We present a polynomial-time algorithm for verifying a minimum-weight basis of a matroid, where each weight lies in a given uncertainty area. These areas may be finite sets, real intervals, or unions of open and closed intervals, strictly generalizing previous work by Erlebach and Hoffman which only handled the special case of open intervals. Our algorithm introduces new techniques to address the resulting challenges.

Verification problems are of particular importance in the area of explorable uncertainty, as the structural insights and techniques used to solve the verification problem often heavily influence work on the corresponding online problem and its stochastic variant. In our case, we use structural results from the verification problem to give a best-possible algorithm for a promise variant of the corresponding adaptive online problem. Finally, we show that our algorithms can be applied to two learning-augmented variants of the minimum-weight basis problem under explorable uncertainty.

Keywords and phrases:

Matroid verification, minimum-weight basis, query strategy, uncertainty matroid, explorable uncertainty

Funding:

Haya Diwan: Partially supported by National Science Foundation (NSF) Grant no. 1909335.

Lisa Hellerstein: Partially supported by National Science Foundation (NSF) Grant no. 1909335.

Nicole Megow: Supported by the Deutsche Forschungsgemeinschaft (DFG) Grant no. 547924951.

Jens Schlöter: Supported by the research project Optimization for and with Machine Learning (OPTIMAL), funded by the Dutch Research Council (NWO), Grant no. OCENW.GROOT.2019.015.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Design and analysis of algorithms

Editors:

Meena Mahajan, Florin Manea, Annabelle McIver, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Consider the problem of finding a minimum-weight basis (MWB) of a matroid, under uncertainty. We consider a weighted matroid $M=(E,\mathcal{I},w)$ , where each element $e\in E$ has a weight $w_{e}$ that is known to be contained within a given range, called an uncertainty area $A_{e}$ . The exact value of $w_{e}$ can be obtained by performing a query on element $e$ that incurs a non-negative cost of $c_{e}$ . The problem is to determine an MWB while minimizing the total query cost. In the special case where $M$ is the graphic matroid of a connected graph, so the bases of $M$ correspond to spanning trees, this is the minimum spanning tree (MST) problem under uncertain edge weights. This was one of the earliest studied problems in explorable uncertainty, motivated by network design: spanning trees capture fundamental connectivity tasks, and uncertainty areas naturally model edge weights known only within ranges, such as costs, latencies, or capacities.

The verification version of the MWB problem under uncertainty is an offline problem that, given access to both the uncertainty areas $A_{e}$ and the exact weights $w_{e}$ , seeks a minimum-cost set of queries for verifying some minimum-weight basis of $M$ . More particularly, these queries and their answers, together with the uncertainty areas for all elements $e\in E$ not queried, would be sufficient to determine an MWB of $M$ .

To illustrate the MWB verification problem, consider the special case of a graphic matroid of a connected graph $G$ . The elements of this matroid are the edges in $G$ , the independent sets are the cycle-free edge sets, and an MWB is an MST. Figure 1 shows three uncertainty graphs with different types of intervals as their uncertainty areas, and their corresponding minimum-cost query sets, assuming unit query cost per edge.

Figure 1: Let

T

(blue) be an MST of the given graph. The figure shows the minimum-cost query sets for instances with different types of uncertainty intervals: open

(0,1)

, closed

[0,1]

, or mixed. Edge labels indicate (name, interval, weight), and each query has unit cost. The corresponding minimum-cost query sets are

Q=\{e_{1},e_{2},e_{3}\}

(open),

Q=\{e_{2},e_{3}\}

(closed), and

Q=\emptyset

(mixed).

Our main result is a polynomial-time algorithm for this verification problem, producing both a minimum-cost verification set (we also say certificate), and an associated MWB $B$ , for uncertainty areas that are a finite union of intervals. Each of these intervals can be open or closed. Note that this includes the case where each uncertainty area is a finite set of discrete values. For example, $\{0,1\}$ is equivalent to $[0,0]\cup[1,1]$ .

In addition to being an interesting combinatorial problem in its own right, the verification problem is fundamental to solving variants of the online MWB problem in settings beyond the worst-case, such as stochastic settings and adversarial learning-augmented variants. In the stochastic setting, each weight $w_{e}$ is assumed to be drawn from a known probability distribution, and the goal is to minimize the expected query cost. The verification problem can be viewed as either an analog or a special case of such a stochastic formulation, where each distribution has support of size 1, but an element $e$ still must be queried in order to “use” the value $w_{e}$ . At the same time, our results have direct consequences for variants of the adversarial adaptive online problem: in Section 5 we use insights from the verification problem to obtain new results for a variant of the online adaptive MWB problem, and show how it provides a foundation for learning-augmented algorithms. Thus, verification serves both as a crucial first step toward stochastic formulations and as a direct tool for online problems under uncertainty.

A special case (in two senses) of our verification problem was studied before by Erlebach and Hoffman [8]. They considered finding the MST of a graph under weight uncertainty, with uncertainty areas that are either open intervals, i.e., $A_{e}=(L_{e},U_{e})$ , or trivial, i.e., $A_{e}=\{w_{e}\}$ (meaning the weight of $e$ is given). They gave an efficient algorithm that computes an optimal solution.

From a technical standpoint, handling uncertainty areas that are closed intervals and finite sets, as we do in our work, posed new challenges and required new techniques as well as structural insights. We discuss differences and challenges in more detail below.

1.1 Related Work

Verification problems.

In the context of verifying optimal structures under uncertainty, the above-mentioned polynomial-time algorithm of Erlebach and Hoffman [8], for MST verification with open and trivial uncertainty areas, stands out as a notable exception in terms of computational complexity. In contrast, other verification problems are known to be NP-hard and even inapproximable. For instance, verification is NP-hard for identifying the set of maximal points under geometric uncertainty [3], and for selecting the cheapest set from a collection of sets with elements of uncertain weight [9]. The latter is even NP-hard to approximate within a factor of $o(\log m)$ , where $m$ is the number of sets [19]. Recently, verification for knapsack under explorable uncertainty was shown to be $\Sigma_{2}^{p}$ -complete [23].

Online algorithms.

The line of research on exploring uncertain numerical values under query costs was initiated by Kahan [14], who studied problems such as identifying the minimum or $k$ -th smallest value from a set of uncertain values. Since then, many problems have been investigated [5], mainly in an adaptive online setting, where queries can be performed sequentially based on prior outcomes. The goal is to minimize the worst-case competitive ratio, comparing the total cost of an online algorithm to the minimum-cost of a verification set. Favorable constant (and often matching) upper and lower bounds are known for selection-type problems [14, 10], MST and matroid bases [13, 18, 21] and sorting [12]. However, strong lower bounds have been shown for more complex problems such as cheapest set [9], knapsack, matchings, linear programming [20], which rule out any constant competitive ratio.

The online adaptive MWB problem under uncertainty was studied by Erlebach et al. [9] for open and trivial intervals. They gave a deterministic algorithm with a best-possible competitive ratio of 2. This result extended earlier work [13] on finding the MST in a graph with the same types of uncertainty areas. Subsequently, Megow et al. gave a randomized algorithm with an improved bound of $1.707$ for the online versions of both MST and MWB problems, again with open and trivial intervals [18]. In [17], Mathwieser and Çela gave improved randomized algorithms for special cases of the problem. Note that it is crucial to omit closed intervals in this online setting as otherwise no constant competitive ratio is possible [13].

In contrast to the above, non-adaptive online variants have received little attention, with the notable exception of the work of Merino and Soto [21]. They gave an algorithm that computes a minimum-cost ‘universal’ set of queries that can be used to find an MWB of an uncertainty matroid, assuming no prior knowledge of any of the actual element weights. Their algorithm, like ours, allows for uncertainty areas that are finite unions of bounded real intervals that can be either open or closed. However, they require a query set to be a certificate for every weight vector $w^{\prime}$ such that $w^{\prime}_{e}\in A_{e}$ for all elements $e$ , while the verification problem requires that it be a certificate only for the given weights $w_{e}$ . Because of the stronger requirements, the minimum-cost certificate for their problem can have significantly higher cost. In fact, using their algorithm for the verification problem (ignoring access to the weights $w_{e}$ ) only yields an $n$ -approximation for uniform query costs and an unbounded approximation factor for general query costs (cf. discussion in full version [4]). Thus using the given weights $w_{e}$ is crucial to optimally solving the verification problem.

Beyond-worst-case models and the relevance of verification methods.

The strong lower bounds for more complex problems suggest that the adversarial online model may be overly pessimistic. This has motivated the study of beyond-worst-case approaches in the context of explorable uncertainty, such as stochastic models [1, 2, 19], where query outcomes are drawn from (possibly unknown) probability distributions, and learning-augmented frameworks [6, 7], where algorithms have access to imperfect predictions of the actual weights. In all of these works, a solid understanding of the corresponding verification problem was fundamental to the design and analysis of algorithms.

1.2 Our Results

We give a polynomial-time algorithm that solves the MWB verification problem, producing both a minimum-cost verification set (a certificate) and an associated MWB, for uncertainty areas that are a finite union of bounded intervals. Each interval can be either open or closed.

Figure 2: Let

T

(blue) and

T^{\prime}

(red) be MSTs of the same uncertainty graph. Edge labels show (name, interval, weight), and all queries have unit cost. While both are MSTs,

T

has a cheaper minimum-cost query set,

Q=\{e_{3},e_{4}\}

, compared to

T^{\prime}

with

Q=\{e_{1},e_{3},e_{4}\}

.

Our algorithm has two phases, motivated by a key difference from the verification problem for open intervals: If uncertainty areas contain closed intervals, the cost of verification may vary across MWBs; see Figure 2. In contrast, for open intervals, all MWBs have the same minimum verification cost¹¹1This fact is only implicit in previous works [8, 7]. However, it is also a corollary of our results in Section 3.. This raises a natural question for general uncertainty areas: Can we efficiently identify an MWB whose minimum verification cost is as small as possible? (We make the standard assumption that the matroid is given by an independence oracle, and that oracle queries are answered in time polynomial in the number of matroid elements.)

Our first main result answers this question in the affirmative. The first phase of our algorithm is a polynomial-time procedure that identifies an MWB which has minimum possible verification cost (Section 3). Our algorithm is based on carefully designed contraction and deletion rules that allow us to delete and contract extreme case elements, i.e., elements $e$ with $w_{e}=\inf A_{e}$ or $w_{e}=\sup A_{e}$ , while maintaining the invariant that there exists an MWB consistent with the deletions and contractions having minimum possible verification cost. As a corollary, we show that, for uniform query costs and uniform areas $A_{e}=\{L,U\}$ with $L<U$ (i.e., each $w_{e}$ is either equal to $L$ or $U$ ), all MWBs have the same minimum verification cost.

In the second phase (Section 4), our algorithm efficiently computes a minimum-cost certificate to verify a given MWB. Together, the two phases of our algorithm yield a polynomial-time algorithm for our MWB verification problem.

Motivating the second phase, we give a full structural characterization of certificates for verifying an MWB. In contrast to previous work, we have to carefully handle extreme case elements. Intuitively, the presence or absence of such elements can make a huge difference for the certificates. For example, if we want to find an element of maximum weight in a set of elements with identical uncertainty areas, then querying a single element $e$ with $w_{e}=\sup A_{e}$ is sufficient to identify an element of maximum weight, whereas the absence of extreme case elements forces us to query all elements. Based on our certificate characterization, we compute a minimum-cost certificate by solving a minimum-weight vertex cover problem in a bipartite auxiliary graph; this technique has also been used in previous work [8, 18, 7, 6, 1]. We remark that our results imply an alternative, arguably simpler, algorithm for the verification problem with open intervals (and other special cases where all MWBs have the same verification cost): Fix any MWB and run the algorithm’s second phase.

Finally, in Section 5, we use insights from the second phase of our verification algorithm to give new results for the online adaptive MWB problem with general uncertainty areas. For open uncertainty intervals, the competitive ratio of the online adaptive MWB problem is $2$ [13]. If closed uncertainty areas are allowed, the competitive ratio increases to $n$ [11]. We show that the competitive ratio of $2$ can be recovered in a promise variant of the online MWB problem with general uncertainty areas, where the algorithm is given an MWB and only has to verify this MWB. This shows that the increase in the competitive ratio from open to general uncertainty areas stems from the algorithm’s task of finding rather than merely verifying an MWB $B$ . Based on this insight, we design a learning-augmented algorithm for a setting where algorithms have access to an untrusted prediction of an MWB.

2 Preliminaries

We assume familiarity with matroids and only briefly define basic concepts and notation. For a comprehensive introduction, see Schrijver’s book [24]. Readers might find it helpful to keep the graphic matroid and the MST problem on a connected graph in mind. For a set $X$ and an element $e$ , we use the short notation $X+e\coloneqq X\cup\{e\}$ and $X-e\coloneqq X\setminus{\{e\}}$ .

2.1 Matroid Basics

A matroid is a non-empty, downward-closed set system $(E,\mathcal{I})$ with element set $E$ and a family of subsets $\mathcal{I}\subseteq 2^{E}$ , which satisfies the augmentation property: if $I,J\in\mathcal{I}$ and $|I|<|J|$ , then $I+e\in\mathcal{I}$ for some $e\in J\setminus{I}$ .

Given a matroid $M=(E,\mathcal{I})$ , a set $I\subseteq E$ is called independent if $I\in\mathcal{I}$ , and dependent otherwise. We refer to the elements of $M$ by $E(M)$ . An inclusion-wise maximal independent subset is called a basis of $M$ . With a matroid $M$ , we associate a rank function $r:2^{E}\rightarrow\mathbb{Z}_{\geq 0}$ , where $r(X)$ describes the maximal cardinality of an independent subset of $X$ .

The span of some $X\subseteq E$ contains all elements that do not increase the rank when added to $X$ , i.e., $\textrm{span}_{M}(X)=\{e\in E\mid r(X)=r(X+e)\}$ . If $X$ is a basis and $e^{\prime}\not\in\textrm{span}_{M}(X-e)$ for some $e\in X$ , then the definition of the span implies that $X-e+e^{\prime}$ is a basis.

A circuit $C$ in a matroid $M=(E,\mathcal{I})$ is a minimally dependent set, that is, $C\not\in I$ whereas $C\setminus\{e\}\in I$ for each $e\in C$ . Any independent set $I\in\mathcal{I}$ of $M$ and an $e\in E$ such that $I+e$ is dependent, form a unique circuit $C_{e}^{I}\subseteq I+e$ . This circuit is called the fundamental circuit of $e$ with respect to $I$ . If $B$ is a basis and $e\in C_{e^{\prime}}^{B}$ for some $e^{\prime}\not\in B$ , then the definition of fundamental circuits implies that $B^{\prime}=B-e+e^{\prime}$ is also a basis of $M$ .

Given a matroid $M=(E,\mathcal{I})$ , we obtain a matroid $M^{\prime}=(E\setminus X,\mathcal{I}^{\prime})$ from $M$ by applying the operations “contraction” and “deletion” for subsets $X\subseteq E$ . The deletion of $X$ from $M$ yields the matroid $M^{\prime}$ with $\mathcal{I}^{\prime}:=\{I\,|\,I\subseteq E\setminus X,I\in\mathcal{I}\}$ . In this paper, we only consider deletions that do not decrease the rank of the matroid, i.e., satisfy $r(M)=r(M^{\prime})$ . Contracting an independent set $X$ in $M$ yields a matroid $M^{\prime}$ with independent sets $\mathcal{I}^{\prime}$ defined as subsets $I\subseteq E\setminus X$ with $I\cup X\in\mathcal{I}$ . A matroid $M^{\prime}$ obtained from $M$ by a series of contractions and deletions is called a minor of $M$ .

We consider weighted matroids $M=(E,\mathcal{I},w)$ , in which each element $e\in E$ has an associated weight $w_{e}\in\mathbb{R}$ . The weight of a basis $B$ of $M$ is $w(B)\coloneqq\sum_{e\in B}w_{e}$ . We seek a minimum-weight basis (MWB) of $M$ . Note that an MWB of $M$ may not be unique.

2.2 Properties of Bases

Throughout the paper, we use well-known properties to argue that a basis $B$ is an MWB. The propositions follow, e.g., from [15, Thm. 6.1], and the observation is proved in the full version [4].

Proposition 1.

Let $B$ be a basis of the matroid $M=(E,\mathcal{I},w)$ . If $w_{e}\leq w_{e^{\prime}}$ holds for all $e\in B$ and all $e^{\prime}\in E\setminus\textrm{span}_{M}(B-e)$ , then $B$ is an MWB of $M$ .

Proposition 2.

Let $B$ be a basis of the matroid $M=(E,\mathcal{I},w)$ . If $w_{e}\geq w_{e^{\prime}}$ holds for all $e\in E\setminus B$ and all $e^{\prime}\in C^{B}_{e}$ , then $B$ is an MWB of $M$ .

Observation 3.

Let $B$ be a basis of the matroid $M=(E,\mathcal{I},w)$ . If $C$ is a circuit of $M$ with $e\in B\cap C$ , then there is an $e^{\prime}\in C-e$ such that $e^{\prime}\notin\textrm{span}_{M}(B-e)$ .

2.3 Uncertainty Matroids and Certificates

In an uncertainty matroid, weights $w_{e}$ are not known, but we are given uncertainty areas guaranteed to contain them.

Definition 4 (Uncertainty Matroid).

An uncertainty matroid $\mathcal{M}=(E,\mathcal{I},A)$ is a matroid $M=(E,\mathcal{I})$ and a function $A:E\rightarrow\mathbb{R}$ such that for each $e\in E$ , $A(e)$ is a non-empty finite union of bounded real intervals (either open or closed). We call $\mathcal{M}=(E,\mathcal{I},A,w)$ a weighted uncertainty matroid if $\mathcal{M}=(E,\mathcal{I},A)$ is an uncertainty matroid and $w:E\rightarrow\mathbb{R}$ is such that $w_{e}:=w(e)\in A_{e}$ for all $e\in E$ . We define $A_{e}:=A(e)$ , $L_{e}:=\inf A_{e}$ , and $U(e):=\sup A_{e}$ . We call $A_{e}$ the uncertainty area of $e$ and say $e$ is trivial if $A_{e}$ consists of the single value $w_{e}$ .

Consider the problem of computing an MWB in a weighted uncertainty matroid, where the exact weights are initially unknown but the true weight of an element $e$ can be revealed through a query, which incurs a cost $c_{e}\geq 0$ . We are now faced with the problem of determining an MWB at the lowest possible total query cost. We use the notion of certificates, where a certificate is a set $Q\subseteq E$ such that querying $Q$ reveals sufficient information about the uncertain weights in $A$ to identify a basis $B$ that is an MWB, irrespective of the exact weights of the elements not in $Q$ . We make this precise in the definitions below. Note that the formal definition of an uncertainty matroid only specifies uncertainty areas for the matroid elements $e$ , not specific weights $w_{e}$ . In what follows, we sometimes identify a weighted uncertainty matroid $\mathcal{M}(E,\mathcal{I},A,w)$ with its associated weighted matroid $M=(E,I,w)$ . For example, when we refer to a basis $B$ of $\mathcal{M}(E,\mathcal{I},A,w)$ , we mean a basis of $M=(E,I,w)$ .

Definition 5 (Consistent weight assignment).

Consider a weighted uncertainty matroid $\mathcal{M}=(E,\mathcal{I},A,w)$ . A weight assignment $w^{*}$ for $\mathcal{M}$ is a function $w^{*}\colon E\rightarrow\mathbb{R}$ such that $w^{*}_{e}\in A_{e}$ holds for each $e\in E$ . We say a weight assignment $w^{*}$ for $\mathcal{M}$ is consistent with $Q$ if it additionally satisfies $w_{e}=w^{*}_{e}$ for each $e\in Q$ .

Definition 6 (Verification and certificates).

Consider a weighted uncertainty matroid $\mathcal{M}=(E,\mathcal{I},A,w)$ . Let $B$ be an MWB of $\mathcal{M}$ . We say that a certificate $Q$ verifies $B$ if for every weight assignment $w^{*}$ for $\mathcal{M}$ that is consistent with $Q$ (Definition 5), $B$ is an MWB of the weighted matroid $M^{\prime}=(E,\mathcal{I},w^{*})$ .

Definition 7 (Minimum-cost certificate).

Consider a weighted uncertainty matroid $\mathcal{M}=(E,\mathcal{I},A,w)$ . Let $\mathcal{Q}$ be the set of all certificates that verify a basis of $\mathcal{M}$ . Then, $Q\in\mathcal{Q}$ is a minimum-cost certificate for $\mathcal{M}$ , if $c(Q)\coloneqq\sum_{e\in Q}c_{e}$ is minimal among all certificates in $\mathcal{Q}$ .

2.3.1 Characterization of Certificates

To further characterize certificates, define $L_{e}(Q)=w_{e}$ if $e\in Q$ and $L_{e}(Q)=L_{e}$ if $e\not\in Q$ . Similarly, define $U_{e}(Q)=w_{e}$ if $e\in Q$ and $U_{e}(Q)=U_{e}$ if $e\not\in Q$ . Intuitively, $L_{e}(Q)$ and $U_{e}(Q)$ denote the upper and lower limits of $e$ after querying the certificate $Q$ .

Lemma 8.

Let $B$ be an MWB of $\mathcal{M}=(E,\mathcal{I},A,w)$ . A set $Q\subseteq E$ is a certificate that verifies $B$ if and only if $U_{e}(Q)\leq L_{f}(Q)$ for all $e\in B$ and $f\in(E\setminus\textrm{span}_{M}(B-e))-e$ .

Proof.

First, assume $U_{e}(Q)\leq L_{f}(Q)$ for all $e\in B$ and $f\in(E\setminus\textrm{span}_{M}(B-e))-e$ . Consider any weight assignment $w^{*}$ consistent with $Q$ . Then, for each $e\in B$ , we have $w^{*}_{e}\leq U_{e}(Q)\leq L_{f}(Q)\leq w^{*}_{f}$ for all $f\in(E\setminus\textrm{span}_{M}(B-e))-e$ . This implies $B$ is an MWB for $w^{*}$ , by Proposition 1. Thus $Q$ verifies $B$ by Definition 6.

Next, assume it does not hold that $U_{e}(Q)\leq L_{f}(Q)$ for all $e\in B$ and $f\in(E\setminus\textrm{span}_{M}(B-e))-e$ . Let $e\in B$ and $f\in(E\setminus\textrm{span}_{M}(B-e))-e$ be such that $L_{f}(Q)<U_{e}(Q)$ . Then, there exists a weight assignment $w^{*}$ , consistent with $Q$ , such that $w^{*}_{e}>w^{*}_{f}$ . Thus $B^{\prime}=B-e+f$ is independent and satisfies $w^{*}(B^{\prime})<w^{*}(B)$ , and so $Q$ does not verify $B$ by Definition 6. $\hfill\blacktriangleleft$

The lemma implies the following alternative characterization, which we prove in the full version [4].

Corollary 9.

Let $B$ be an MWB of $\mathcal{M}=(E,\mathcal{I},A,w)$ . A set $Q\subseteq E$ is a certificate that verifies $B$ if and only if the following property holds for every $f\not\in B$ , and the fundamental circuit $C_{f}^{B}$ : for every $e\in C_{f}-f$ , $U_{e}(Q)\leq L_{f}(Q)$ .

2.3.2 Exchange Properties of Certificates

We continue by showing some exchange properties of certificates.

Lemma 10.

Let $B$ be an MWB of $\mathcal{M}=(E,\mathcal{I},A,w)$ and let $Q$ be a certificate that verifies $B$ . Let $e\in B$ and $e^{\prime}\not\in B$ with $U_{e}=U_{e^{\prime}}=w_{e}=w_{e^{\prime}}$ be such that $e\in C_{e^{\prime}}$ for the fundamental circuit $C_{e^{\prime}}$ of $e^{\prime}$ with respect to $B$ . Then $Q^{\prime}=Q-e^{\prime}+e$ is a certificate for $B^{\prime}=B-e+e^{\prime}$ .

Proof.

During this proof, we use $C^{\prime}_{f}$ to refer to the fundamental circuit of $f$ with respect to $B^{\prime}$ for an $f\not\in B^{\prime}$ . To show that $Q^{\prime}$ is a certificate for $B^{\prime}$ , we show for each $f\not\in B^{\prime}$ that $L_{f}(Q^{\prime})\geq U_{f^{\prime}}(Q^{\prime})$ for each $f^{\prime}\in C^{\prime}_{f}-f$ . By Corollary 9, this implies $Q^{\prime}$ is a certificate for $B^{\prime}$ .

We distinguish between the two cases (1) $f=e$ and (2) $f\not=e$ .

Case (1):

Assume $f=e$ and consider circuit $C^{\prime}_{e}$ . Since $B^{\prime}=B-e+e^{\prime}$ , we have $C^{\prime}_{e}=C_{e^{\prime}}$ . Since $Q$ is a certificate for $B$ with $e^{\prime}\not\in B$ , we have $w_{e^{\prime}}\geq L_{e^{\prime}}(Q)\geq U_{f^{\prime}}(Q)$ for all $f^{\prime}\in C_{e^{\prime}}-e^{\prime}$ by Corollary 9. For every $f^{\prime}\in C_{e^{\prime}}-\{e,e^{\prime}\}$ , the membership of $f$ and $f^{\prime}$ in $Q$ and $Q^{\prime}$ is identical, so $U_{f^{\prime}}(Q^{\prime})=U_{f^{\prime}}(Q)$ . Since $C_{e^{\prime}}=C^{\prime}_{e}$ , $e\in Q^{\prime}$ and by definition $w_{e}=w_{e^{\prime}}=U_{e^{\prime}}$ , this implies $L_{e}(Q^{\prime})=w_{e}=w_{e^{\prime}}\geq L_{e^{\prime}}(Q)\geq U_{f^{\prime}% }(Q)=U_{f^{\prime}}(Q^{\prime})$ for all $f^{\prime}\in C^{\prime}_{e}-\{e,e^{\prime}\}$ . Further, $L_{e}(Q^{\prime})=w_{e^{\prime}}=U_{e^{\prime}}\geq U_{e^{\prime}}(Q^{\prime})$ .

Case (2):

Assume $f\not=e$ and consider the circuit $C^{\prime}_{f}$ . We distinguish two subcases.

$\blacksquare$

If $(C^{\prime}_{f}-f)\subseteq B$ , then $C^{\prime}_{f}=C_{f}$ and $e,e^{\prime}\not\in C^{\prime}_{f}$ . In this case, $L_{f}(Q^{\prime})=L_{f}(Q)\geq U_{f^{\prime}}(Q)=U_{f^{\prime}}(Q^{\prime})$ holds for all $f^{\prime}\in C^{\prime}_{f}-f$ by definition of $Q^{\prime}$ and by our assumption that $Q$ is a certificate for $B$ with $f\not\in B$ (cf. Corollary 9).
$\blacksquare$

If $(C^{\prime}_{f}-f)\not\subseteq B$ , then we must have $e^{\prime}\in C^{\prime}_{f}-f$ . Consequently, $f\in E\setminus\textrm{span}_{M}(B^{\prime}-e^{\prime})=E\setminus\textrm{span% }_{M}(B-e)$ . Note that $w_{e^{\prime}}=U_{e^{\prime}}(Q^{\prime})=U_{e}(Q)$ holds by definition because of $w_{e}=w_{e^{\prime}}=U_{e}=U_{e^{\prime}}$ . Since $Q$ is a certificate for $B$ with $e\in B$ , we must have $w_{e^{\prime}}=U_{e^{\prime}}(Q^{\prime})=U_{e}(Q)\leq L_{f}(Q)=L_{f}(Q^{% \prime})$ by Lemma 8.

If $C^{\prime}_{f}=\{f,e^{\prime}\}$ , then the above argument already shows $L_{f}(Q^{\prime})\geq U_{f^{\prime}}(Q^{\prime})$ for each $f^{\prime}\in C^{\prime}_{f}-f$ , and we are done with the proof for this case. Thus, assume $C^{\prime}_{f}\setminus\{f,e^{\prime}\}\not=\emptyset$ and consider an arbitrary $f^{\prime}\in C^{\prime}_{f}-f-e^{\prime}$ . Then $f^{\prime}\in B\cap C^{\prime}_{f}$ and, by Observation 3, there must be an element $g\in C^{\prime}_{f}-f^{\prime}$ with $g\not\in\textrm{span}_{M}(B-f^{\prime})$ . The only two elements of $C_{f}^{\prime}-f^{\prime}$ that are not in $B-f^{\prime}\subseteq\textrm{span}_{M}(B-f^{\prime})$ are $e^{\prime}$ and $f$ .

If $f\not\in\textrm{span}_{M}(B-f^{\prime})$ , then our assumption that $Q$ is a certificate for $B$ implies $U_{f^{\prime}}(Q^{\prime})=U_{f^{\prime}}(Q)\leq L_{f}(Q)=L_{f}(Q^{\prime})$ . If $e^{\prime}\not\in\textrm{span}_{M}(B-f^{\prime})$ , then our assumption that $Q$ is a certificate for $B$ implies $U_{f^{\prime}}(Q^{\prime})=U_{f^{\prime}}(Q)\leq L_{e^{\prime}}(Q)\leq w_{e^{% \prime}}=U_{e}(Q)\leq L_{f}(Q^{\prime})$ , where the last inequality uses $U_{e}(Q)\leq L_{f}(Q^{\prime})$ as argued above. In all cases, $U_{f^{\prime}}(Q^{\prime})\leq L_{f}(Q^{\prime})$ .

$\hfill\blacktriangleleft$

The next lemma is a dual version of Lemma 10. The proof is in the full version [4].

Lemma 11.

Let $B$ be an MWB of $\mathcal{M}=(E,\mathcal{I},A,w)$ and let $Q$ be a certificate that verifies $B$ . Let $e\notin B$ and $e^{\prime}\in B$ with $L_{e}=L_{e^{\prime}}=w_{e}=w_{e^{\prime}}$ be such that $e^{\prime}\in C_{e}$ for the fundamental circuit $C_{e}$ of $e$ with respect to $B$ . Then $Q^{\prime}=Q-e^{\prime}+e$ is a certificate for $B^{\prime}=B+e-e^{\prime}$ .

It is easy to show the following exchange property for trivial elements.

Lemma 12.

Let $B$ be an MWB of $\mathcal{M}=(E,\mathcal{I},A,w)$ and let $Q$ be a certificate that verifies $B$ . Let $e\in B$ and $e^{\prime}\not\in B$ with $w_{e}=w_{e^{\prime}}$ be such that $B^{\prime}=B-e+e^{\prime}$ is independent. If each $f\in\{e,e^{\prime}\}$ is either trivial or contained in $Q$ , then $Q$ also verifies $B^{\prime}$ .

3 Computing an MWB that has a Minimum-Cost Certificate

Given a weighted uncertainty matroid $\mathcal{M}=(E,\mathcal{I},A,w)$ , we compute an MWB $B$ that admits a minimum-cost certificate, though we do not yet compute the certificate itself. To this end, we introduce a set of contraction and deletion rules. Starting from $B=\emptyset$ , these rules allow us to safely add elements to $B$ (contraction) and ban elements from ever entering $B$ (deletion) while maintaining the invariant that there is a minimum-cost certificate which verifies a basis $B^{\prime}$ that contains $B$ and does not contain any deleted elements. We formalize this invariant by introducing the notion of a “compatible minor” which intuitively is the remaining (uncertainty) matroid after applying contractions and deletions. We refer to sets of contracted and deleted elements as $K$ and $D$ , respectively.

Definition 13.

Let $\mathcal{M}=(E,\mathcal{I},A,w)$ be a weighted uncertainty matroid with a minimum-cost certificate of cost $c^{*}$ and let $D,K\subseteq E$ . Let $M[D,K]$ be the matroid obtained from $M=(E,\mathcal{I})$ by deleting $D$ and contracting $K$ . We say $M[D,K]$ is a compatible minor of $\mathcal{M}$ if there is a query set for $\mathcal{M}$ with cost $c^{*}$ that verifies an MWB $B$ of $\mathcal{M}$ with $K\subseteq B$ and $D\cap B=\emptyset$ . Furthermore, we say that a certificate $Q$ for $\mathcal{M}$ is compatible with $M[D,K]$ if $Q$ verifies a basis $B$ of $\mathcal{M}$ with $K\subseteq B$ and $D\cap B=\emptyset$ .

Our goal is to iteratively create sets $D$ and $K$ until $K$ becomes an MWB while maintaining the invariant that there is a minimum-cost certificate compatible with $D$ and $K$ . To this end, we first introduce a series of observations and lemmas that, given a compatible minor $M[D,K]$ , allow us to compute a larger compatible minor $M[D^{\prime},K^{\prime}]$ (Section 3.1). Formally, larger means $D^{\prime}\supseteq D$ , $K^{\prime}\supseteq K$ and $D^{\prime}\supset D$ or $K^{\prime}\supset K$ . We also refer to these observations and lemmas as contraction and deletion rules. We use the phrase applying a rule to refer to the process of computing the larger compatible minor $M[D^{\prime},K^{\prime}]$ and replacing the given one, i.e. we set $K:=K^{\prime}$ and $D:=D^{\prime}$ . We will show that exhaustively applying these rules in a certain order until $K$ is a basis and $D=E\setminus K$ yields an MWB that can be verified with minimum-cost. Afterwards, we show that the rules can be implemented with a polynomial-time algorithm (Section 3.2), which will imply the following theorem.

Theorem 14.

There is a polynomial-time algorithm that computes, for any given weighted uncertainty matroid $\mathcal{M}$ , an MWB $B$ that can be verified by a minimum-cost certificate.

3.1 Contraction and Deletion Rules

Consider a weighted uncertainty matroid $\mathcal{M}=(E,\mathcal{I},A,w)$ . Elements that appear in every MWB of $\mathcal{M}$ or in none can be safely contracted (added to $K$ ) or deleted (added to $D$ ). The next observations follow from standard arguments (proofs are in the full version [4]).

Observation 15.

Let $M^{\prime}:=M[D,K]$ be a compatible minor of $\mathcal{M}$ . If there is a circuit $C$ in $M[D,K]$ with an element $e\in C$ that has the unique maximum weight in $C$ , then $M[D+e,K]$ is a compatible minor of $\mathcal{M}$ .

Observation 16.

Let $M^{\prime}:=M[D,K]$ be a compatible minor of $\mathcal{M}$ . If there is a basis $B$ of $M^{\prime}$ with an element $e\in B$ that has unique minimum weight in $E(M^{\prime})\setminus\textrm{span}_{M^{\prime}}(B-e)$ , then $M[D,K+e]$ is a compatible minor of $\mathcal{M}$ .

We continue by giving contraction and deletion rules for extreme case elements $e$ satisfying $w_{e}=U_{e}$ or $w_{e}=L_{e}$ . The existence of these elements separates our work from [8].

3.1.1 Rules for Non-Trivial Extreme Case Elements

We start by considering non-trivial extreme case elements. For each $w\in\{w_{e}\mid e\in E\}$ , we define $E_{w}^{L}=\{e\in E\mid L_{e}=w\land e\text{ is non-trivial}\}$ and $E_{w}^{U}=\{e\in E\mid U_{e}=w\land e\text{ is non-trivial}\}$ .

Lemma 17.

Let $M^{\prime}:=M[D,K]$ be a compatible minor of $\mathcal{M}$ . Let $e$ be a non-trivial element such that (i) $e\in B$ for some MWB $B$ of $M^{\prime}$ , (ii) $w_{e}=U_{e}$ , (iii) $e$ has minimum weight in $E(M^{\prime})\setminus\textrm{span}_{M^{\prime}}(B-e)$ and (iv) $e$ has maximum query cost in $(E(M^{\prime})\setminus\textrm{span}_{M^{\prime}}(B-e))\cap E_{w_{e}}^{U}$ . Then $M[D,K+e]$ is a compatible minor of $\mathcal{M}$ .

Proof.

Let $Q^{*}$ denote a minimum-cost certificate for $\mathcal{M}$ that is compatible with $M^{\prime}$ . Then, this certificate must also verify some MWB $B^{\prime}$ for $M^{\prime}$ .

To prove the lemma, we have to show that there exists a minimum-cost certificate that verifies an MWB $B^{\prime\prime}$ of $\mathcal{M}$ with $K+e\subseteq B^{\prime\prime}$ and $D\cap B^{\prime\prime}=\emptyset$ . If $e\in B^{\prime}$ , then this directly follows for $Q^{*}$ and the MWB $B^{\prime\prime}=K\cup B^{\prime}$ of $\mathcal{M}$ . Thus, assume $e\not\in B^{\prime}$ and let $C$ denote the fundamental circuit of $e$ with respect to $B^{\prime}$ . By Observation 3, there exists an $e^{\prime}\in C-e$ such that $e^{\prime}\notin\textrm{span}_{M^{\prime}}(B-e)$ . Also, $e^{\prime}\in B^{\prime}-e$ because $C^{\prime}-e\subseteq B^{\prime}$ . By assumption that $e$ has minimum weight in $E(M^{\prime})\setminus\textrm{span}_{M^{\prime}}(B-e)$ and that $B^{\prime}$ is an MWB of $M^{\prime}$ , we have $U_{e}=w_{e}=w_{e^{\prime}}$ . We distinguish the following cases:

1.

If $e,e^{\prime}\in Q^{*}$ , then $Q^{*}$ also verifies that $B^{\prime\prime}=K\cup(B^{\prime}-e^{\prime}+e)$ is an MWB by Lemma 12. Note that $(B^{\prime}-e^{\prime}+e)$ is an MWB for $M^{\prime}$ and $B^{\prime\prime}$ is an MWB for $\mathcal{M}$ .
2.

If $e\in Q^{*}$ and $e^{\prime}\not\in Q^{*}$ , then we must have $w_{e}\geq U_{e^{\prime}}$ . Otherwise, $Q^{*}$ would not verify that $e$ has maximum weight in $C$ . Since $U_{e^{\prime}}\geq w_{e^{\prime}}=w_{e}=U_{e}$ , we get $U_{e}=U_{e^{\prime}}$ . By Lemma 10, this implies that $Q=(Q^{*}-e+e^{\prime})$ verifies the MWB $B^{\prime\prime}=K\cup(B^{\prime}-e^{\prime}+e)$ . Note that $e^{\prime}$ can be trivial, in which case we can just use $Q=(Q^{*}-e)$ instead.

If $e^{\prime}$ is trivial, then we clearly have $c(Q)\leq c(Q^{*})$ . Otherwise, i.e., if $e^{\prime}$ is non-trivial, we have $e^{\prime}\in E_{w_{e}}^{U}$ as we already argued that $U_{e^{\prime}}=w_{e^{\prime}}=w_{e}$ . By assumption (iv) of the lemma, this implies $c_{e}\geq c_{e^{\prime}}$ and, thus, $c(Q)\leq c(Q^{*})$ .
3.

If $e\not\in Q^{*}$ , then we must have $w_{e^{\prime}}\leq L_{e}$ . Otherwise $Q^{*}$ cannot verify that $e$ has maximum weight in $C$ . However, this implies $w_{e^{\prime}}=U_{e}\leq L_{e}$ , which can only be the case if $e$ is trivial; a contradiction to the requirements of the lemma.

$\hfill\blacktriangleleft$

The next lemma is a dual of Lemma 17 and can be shown analogously (cf. the full version [4]).

Lemma 18.

Let $M^{\prime}:=M[D,K]$ be a compatible minor of $\mathcal{M}$ . Let $e$ be a non-trivial element such that (i) there exists a circuit $C$ in $M[D,K]$ with $e\in C$ , (ii) $w_{e}=L_{e}$ , (iii) $e$ has maximum weight in $C$ and (iv) $e$ has maximum query cost in $C\cap E_{w_{e}}^{L}$ . Then $M[D+e,K]$ is a compatible minor of $\mathcal{M}$ .

Iteratively and exhaustively applying the deletion rules in Lemma 18 and Observation 15, and the contraction rules in Lemma 17 and Observation 16, yields $D$ and $K$ such that $M[D,K]$ satisfies the following assumption, enabling further rules depending on this assumption.

Assumption 19.

We may assume that a compatible minor $M^{\prime}:=M[D,K]$ of $\mathcal{M}$ does not contain non-trivial elements $e$ with any of the following properties:

(i)

$w_{e}=L_{e}$ and $e$ is a maximum weight element in a circuit $C$ of $M^{\prime}$ .
(ii)

$w_{e}=U_{e}$ and $e$ is a minimum weight element in $E(M^{\prime})\setminus\textrm{span}_{M^{\prime}}(B-e)$ for a basis $B$ of $M^{\prime}$ that contains $e$ .

3.1.2 Rules for Trivial Extreme Case Elements

We continue by introducing deletion and contraction rules for trivial extreme case elements in instances that satisfy Assumption 19. We defer the following two proofs to the full version [4], but remark that they follow a similar proof strategy as the proof of Lemma 17.

Lemma 20.

Let $M^{\prime}:=M[D,K]$ be a compatible minor of $\mathcal{M}$ and assume that Assumption 19 is satisfied. Let $e$ be a trivial element such that (i) there exists basis $B$ of $M^{\prime}$ with $e\in B$ and (ii) $e$ has minimum weight among elements not in $\textrm{span}_{M^{\prime}}(B-e)$ . Then $M[D,K+e]$ is a compatible minor of $\mathcal{M}$ .

Lemma 21.

Let $M[D,K]$ be a compatible minor of $\mathcal{M}$ and assume that Assumption 19 is satisfied. Let $e$ be a trivial element such that (i) there exists a circuit $C$ in $M[D,K]$ with $e\in C$ and (ii) $e$ has maximum weight in $C$ . Then $M[D+e,K]$ is a compatible minor of $\mathcal{M}$ .

Given a compatible minor $M[D,K]$ that satisfies Assumption 19, we check for an element $e$ that meets the requirements of Lemma 20 or Lemma 21. If such an element exists, we apply the corresponding rule to extend $D$ or $K$ , while maintaining our invariant that $M[D,K]$ is a compatible minor. We then return to applying the rules of the previous sections to restore Assumption 19, and repeat this argument until no such element $e$ remains. The resulting compatible minor $M[D,K]$ satisfies the following properties:

1.

$M[D,K]$ does not contain elements $e$ with $w_{e}=L_{e}$ such that $e$ is a maximum-weight element in some circuit of $M[D,K]$ .
2.

$M[D,K]=:M^{\prime}$ does not contain elements $e$ with $w_{e}=U_{e}$ such that there is a basis $B$ of $M^{\prime}$ with $e\in B$ and $e$ has minimum weight among elements not in $\textrm{span}_{M^{\prime}}(B-e)$ .
3.

There is a minimum-cost certificate that is compatible with $D$ and $K$ .

In any basis $B$ of $M^{\prime}$ with these properties, no element $e\in B$ with $w_{e}=U_{e}$ has minimum-weight in $E(M^{\prime})\setminus\textrm{span}_{M^{\prime}}(B-e)$ . Hence, such elements $e\in B$ with $w_{e}=U_{e}$ cannot be part of any MWB $B$ of $M^{\prime}$ as we can swap $e$ with an element of $E(M^{\prime})\setminus\textrm{span}_{M^{\prime}}(B-e)$ that has strictly smaller weight. Thus, we can delete all these elements $e\in B$ with $w_{e}=U_{e}$ and add them to $D$ while maintaining the property that there is a minimum-cost certificate that is compatible with $D$ and $K$ . Note that this corresponds to applying Observation 15. Similarly, we can argue that all remaining elements $e$ with $w_{e}=L_{e}$ can be contracted by applying Observation 16. This way we compute sets $D$ and $K$ that satisfy the following assumption.

Assumption 22.

We may assume that a compatible minor $M[D,K]$ of a weighted uncertainty matroid $\mathcal{M}$ does not contain elements $e$ with $w_{e}=U_{e}$ or $w_{e}=L_{e}$ .

The rules for extreme case elements imply the following (cf. the full version [4] for a proof).

Corollary 23.

Let $M[D,K]$ be a compatible minor of $\mathcal{M}$ with $A_{e}=\{L_{e},U_{e}\}$ for all $e\in E(M)$ that satisfies Assumption 19, then $K$ is an MWB that can be verified with a minimum-cost certificate. If in addition the query costs are uniform and all $A_{e}$ are uniform and non-trivial, then every MWB $B$ of $M$ has the same verification cost.

3.1.3 Rules for Instances without Extreme Case Elements

Instances $M^{\prime}:=M[D,K]$ that satisfy Assumption 22 essentially behave like instances with open intervals, since all elements satisfy $w_{e}\in(L_{e},U_{e})$ (although we still might have $A_{e}\not=(L_{e},U_{e})$ ). For the special case of graphic matroids with open intervals, the results in [7, 8] imply that all MWB can be verified with minimum-cost certificates. In the full version [4], we generalize these insights to arbitrary matroids and prove the following lemma.

Lemma 24.

Let $M^{\prime}:=M[D,K]$ be a compatible minor of $\mathcal{M}$ such that Assumption 22 is satisfied, and let $B$ be any MWB of $M^{\prime}$ . Then, $M[D^{\prime},K^{\prime}]$ with $K^{\prime}=K\cup B$ and $D^{\prime}=D\cup(E(M^{\prime})\setminus B)$ is a compatible minor of $\mathcal{M}$ .

Once we create a compatible minor $M^{\prime}:=M[D,K]$ that satisfies Assumption 22 by applying the contraction and deletion rules of the previous sections, Lemma 24 allows us to just fix any MWB $B$ of $M^{\prime}$ , contract (delete) the elements of $B$ (of $E(M^{\prime})\setminus B$ ) and add them to $K$ (to $D$ ). Afterwards, $K$ is a basis that can be verified with a minimum-cost certificate.

3.2 A Polynomial-time Algorithm

The results of Section 3.1 imply a sequence of contraction and deletion rules applied to an uncertainty matroid, leading to a compatible minor that has a unique MWB with a minimum-cost certificate. Algorithm 1 exhaustively applies these rules in the right order to compute this MWB, and runs in polynomial time, as we show with the following lemma. This proves Theorem 14.

Algorithm 1 Computing an MWB

B

that can be verified with a minimum-cost certificate.

Lemma 25.

Algorithm 1 runs in polynomial time.

Proof.

The values of $L_{e}$ and $U_{e}$ can be easily computed at the beginning for each $e\in E$ , using the list of intervals for each $A_{e}$ . Subsequently, no further information is needed about $A_{e}$ .

Since the number of iterations of the while-loop is bounded by the number of elements, it only remains to argue that each iteration can be executed in polynomial time. To this end, we mainly have to argue that, for an element $e$ , we can check in polynomial time whether the prerequisites of Observation 15 and 16 or Lemmas 17 to 21 are satisfied.

We separately argue about the different lemmas and observations. Assume there is given a compatible minor $M^{\prime}:=M[D,K]$ of an uncertainty matroid $\mathcal{M}$ .

(a)

Observation 16: Checking whether an element $e$ satisfies the condition of Observation 16 is equivalent to checking whether $e$ is part of every MWB of $M^{\prime}$ . To check whether an element $e$ is part of every MWB w.r.t. the weights $w$ , we can just compute some minimum-weight basis $B$ using the standard greedy algorithm. If $e\not\in B$ , then Observation 16 clearly does not apply. Otherwise, i.e., $e\in B$ , we can check whether $e$ can be exchanged with an element $e^{\prime}\in E\setminus B$ with $w_{e^{\prime}}\leq w_{e}$ . If this is possible, then $e$ is not part of every minimum-weight basis. If not, then $e$ is part of every minimum-weight basis. The running time of this test is dominated by the running time of the greedy algorithm and, thus, polynomial in the input size.
(b)

Observation 15: Using matroid duality arguments allows us to argue in the same way as in the previous case.
(c)

Lemma 17: Checking whether there exists an element $e$ that is non-trivial and (i) there exists a basis $B$ of $M^{\prime}$ with $e\in B$ , (ii) $w_{e}=U_{e}$ , (iii) $e$ has minimum weight in $E(M^{\prime})\setminus\textrm{span}_{M^{\prime}}(B-e)$ and (iv) $e$ has maximum query cost in $E(M^{\prime})\setminus\textrm{span}_{M^{\prime}}(B-e)\cap E_{w_{e}}^{U}$ , can also be done in polynomial time.

Note that a non-trivial element $e$ that satisfies (i)-(iii) is a non-trivial element $e$ with $w_{e}=U_{e}$ that is in at least one MWB $B$ . To decide whether a non-trivial element $e$ with $w_{e}=U_{e}$ is part of at least one MWB $B$ , we can just compute some MWB $B^{\prime}$ and check whether $e\in B^{\prime}$ or, if not, whether $e$ can swapped into $B^{\prime}$ by exchanging it with an equal-weight element in the fundamental circuit of $B^{\prime}$ w.r.t. $e$ . Note that this check can be performed in polynomial time, as the running time is dominated by the running time for computing the MWB $B^{\prime}$ . If the element $e$ is not in $B^{\prime}$ and cannot be swapped into $B^{\prime}$ , then $e$ is not part of any MWB and, therefore, does not satisfy the properties (i)-(iii). Otherwise, it satisfies the properties (i)-(iii).

Executing this check for each non-trivial element $e$ with $w_{e}=U_{e}$ , we can either find such an element $e$ that satisfies (i)-(iii) or determine that Lemma 17 cannot be applied. In the latter case, we are done. If we find an element $e$ with $w_{e}=U_{e}$ that satisfies (i)-(iii), then the check procedure described above also gives us an MWB $B$ with $e\in B$ (this is either $B^{\prime}$ or the MWB that is created by swapping $e$ into $B^{\prime}$ ). Given such a pair of $e$ and MWB $B\ni e$ , we can easily check whether $e$ has maximum query cost in $(E(M^{\prime})\setminus\textrm{span}_{M^{\prime}}(B-e))\cap E_{w_{e}}^{U}$ , i.e., satisfies (iv). If this is the case, then we are done. If not, then some other element of $(E(M^{\prime})\setminus\textrm{span}_{M^{\prime}}(B-e))\cap E_{w_{e}}^{U}$ satisfies the condition of Lemma 17 and we are done anyway.
(d)

Lemma 18: Using matroid duality arguments allows us to argue in the same way as in the previous case.
(e)

The conditions of Lemma 20 and 21 can be checked similarly to Observation 15 and 16 plus checking Assumption 19, which is trivial.
(f)

The final step of the algorithm consists of computing an MWB of the minor $M[D,K]$ which can be done by the greedy algorithm in polynomial time.

$\hfill\blacktriangleleft$

4 Computing a Minimum-Cost Certificate to Verify a Given Basis

In this section, we provide an algorithm for computing a minimum-cost certificate that verifies a given MWB. In particular, the algorithm can be applied to the MWB produced by Algorithm 1, thereby yielding a minimum-cost certificate for $\mathcal{M}$ .

Lemma 26 is a key result that dictates specifically what elements must be in $Q$ in order for it to adhere to Corollary 9.

Lemma 26.

Let $B$ be an MWB of a weighted uncertainty matroid $\mathcal{M}=(E,\mathcal{I},A,w)$ . For a non-basis element $e$ of $B$ , let $C_{e}$ be the fundamental circuit of $e$ with respect to $B$ , let $F_{e}$ be the set of elements $f\in C_{e}-e$ with $U_{f}>L_{e}$ , and let $\hat{F_{e}}$ be the set of elements $f\in C_{e}-e$ with $U_{f}>w_{e}$ . A subset $Q\subseteq E$ is a certificate of $B$ if and only if for each non-basis element $e$ of $B$ , the following holds:

1.

If $w_{e}\geq U_{f}$ for all $f\in C_{e}-e$ , and there exists $f^{\prime}\in C_{e}-e$ such that $w_{f^{\prime}}>L_{e}$ , then $e\in Q$ .
2.

If $w_{e}\geq U_{f}$ for all $f\in C_{e}-e$ , and $w_{f}\leq L_{e}$ for all $f\in C_{e}-e$ , then $e\in Q$ or $F_{e}\subseteq Q$ .
3.

If there exists $f\in C_{e}-e$ such that $w_{e}<U_{f}$ , and there exists $f^{\prime}\in C_{e}-e$ (could have $f^{\prime}=f$ ) such that $w_{f^{\prime}}>L_{e}$ , then $\hat{F_{e}}+e\subseteq Q$ .
4.

If there exists $f\in C_{e}-e$ such that $w_{e}<U_{f}$ , and for all $f^{\prime}\in C_{e}-e$ it holds that $w_{f^{\prime}}\leq L_{e}$ , then $F_{e}\subseteq Q$ or $\hat{F_{e}}+e\subseteq Q$ .

Proof.

Let $Q$ be a certificate that verifies $B$ . Consider a non-basis element $e$ , and the fundamental circuit $C_{e}$ with respect to $B$ . Let $w^{*}$ be some weight assignment consistent with $Q$ (Definition 5). Given $w^{*}$ , if any element $f\in C_{e}-\{e\}$ satisfies $U_{f}\leq L_{e}$ , it immediately follows that $w^{*}_{e}\geq w^{*}_{f}$ , without including either $e$ or $f$ in $Q$ . Define $F_{e}$ as the set of elements $f\in C_{e}-\{e\}$ where $U_{f}>L_{e}$ . Additionally, define $\hat{F_{e}}$ as the set of elements $f\in C_{e}-\{e\}$ with $U_{f}>w_{e}$ . Clearly, $\hat{F}_{e}\subseteq F$ .

Recall that if $e\in Q$ , then $w_{e}=w^{*}_{e}$ , and if $e\notin Q$ , $w^{*}_{e}\in A_{e}$ . We aim to establish the necessary and sufficient conditions for $Q$ to satisfy Corollary 9 for all elements $f\in F$ , (i.e., for $Q$ to satisfy $L_{e}(Q)\geq U_{f}(Q)$ for all $f\in F$ ). Observe the following cases:

Case 1.

The first case is if $w_{e}\geq U_{f}$ for all $f\in F_{e}$ . Two sub-cases arise in this scenario.

$\blacksquare$

Subcase 1.1: There exists some $f^{\prime}\in F$ where $w_{f^{\prime}}>L_{e}$ . In this case, we claim it is necessary and sufficient to have $e\in Q$ . Suppose $e\notin Q$ . Then by Definition 5, we have $w^{*}_{e}\in A_{e}$ . Since $w_{f^{\prime}}>L_{e}$ , Corollary 9 is not satisfied. Thus, $e$ must be in $Q$ . Conversely, if $e\in Q$ , we have that for all $f\in F_{e}$ , $w^{*}_{e}=w_{e}=L_{e}(Q)\geq U_{f}\geq U_{f}(Q)\geq w_{f}$ and thus $w^{*}_{e}\geq w_{f}$ and Corollary 9 is satisfied.
$\blacksquare$

Subcase 1.2: For all $f\in F_{e}$ , $w_{f}\leq L_{e}$ . We show that in this case, it is necessary and sufficient to have $e\in Q$ or $F_{e}\subseteq Q$ . Suppose $e\not\in Q$ and $F_{e}\not\subseteq Q$ . Then there exists some element $f^{\prime}\in F_{e}\backslash Q$ . By Definition 5, we have $w^{*}_{e}\in A_{e}$ and $w^{*}_{f^{\prime}}\in[L_{f^{\prime}},U_{f^{\prime}}]$ . Since $U_{f^{\prime}}>L_{e}$ , Corollary 9 is not satisfied. Thus, it’s clear that $e\in Q$ or $F_{e}\subseteq Q$ . Conversely, suppose $e\in Q$ or $F_{e}\subseteq Q$ . If $e\in Q$ we have that $w^{*}_{e}=w_{e}=L_{e}(Q)\geq U_{f}\geq U_{f}(Q)\geq w_{f}$ and so $w^{*}_{e}\geq w_{f}$ . If $F_{e}\subseteq Q$ , we have that for all $f\in F_{e}$ , $w_{e}\geq L_{e}(Q)\geq L_{e}\geq U_{f}(Q)=w_{f}=w^{*}_{f}$ and thus $w_{e}\geq w^{*}_{f}$ . Either way, Corollary 9 is satisfied.

Case 2.

The second case is if $w_{e}<U_{f}$ for some $f\in F_{e}$ . Again two sub-cases arise in this scenario.

$\blacksquare$

Subcase 2.1: There exists some $f^{\prime}\in C_{e}-e$ where $w_{f^{\prime}}>L_{e}$ . In this case, we show that it is necessary and sufficient to have $\hat{F_{e}}+e\subseteq Q$ . Suppose $\hat{F_{e}}+e\not\subseteq Q$ . Then either $e\notin Q$ or there exists some $f^{\prime\prime}\in\hat{F_{e}}\backslash Q$ . Suppose $e\notin Q$ . By Definition 5, we have $w^{*}_{e}\in A_{e}$ . Since there exists some $w_{f^{\prime}}>L_{e}$ , Corollary 9 is not satisfied. Suppose $f^{\prime\prime}\notin Q$ . By Definition 5, we have $w^{*}_{f^{\prime\prime}}\in[L_{f^{\prime\prime}},U_{f^{\prime\prime}}]$ . Since $w_{e}<U_{f^{\prime\prime}}$ , Corollary 9 is not satisfied. Thus, $\hat{F_{e}}+e\subseteq Q$ .

Conversely, if $\hat{F_{e}}+e\subseteq Q$ we have for all $f\in\hat{F_{e}}$ that $w^{*}_{e}=w_{e}=L_{e}(Q)\geq U_{f}\geq U_{f}(Q)=w_{f}=w^{*}_{f}$ . For all $f\in F_{e}\setminus\hat{F_{e}}$ , given that $L_{e}<U_{f}\leq w_{e}$ , the inclusion of $e\in Q$ ensures that $w^{*}_{e}=w_{e}=L_{e}(Q)\geq U_{f}\geq U_{f}(Q)\geq w_{f}$ . Therefore, Corollary 9 is satisfied.
$\blacksquare$

Subcase 2.2: For all $f^{\prime}\in C_{e}-\{e\}$ , $w_{f^{\prime}}\leq L_{e}$ . In this case, we show it is necessary and sufficient to have $F_{e}\subseteq Q$ or $\hat{F_{e}}+e\subseteq Q$ . Suppose neither $F_{e}$ nor $\hat{F_{e}}+e$ is contained in $Q$ . Then there exists some $f^{\prime\prime}\in\hat{F_{e}}\backslash Q$ . By Definition 5, we have that $w^{*}_{f^{\prime\prime}}\in[L_{f^{\prime\prime}},U_{f^{\prime\prime}}]$ . Since $w_{e}<U_{f^{\prime\prime}}$ , Corollary 9 is not satisfied. Thus, it’s clear that all such $f^{\prime\prime}$ must be in $Q$ . Now suppose some $f^{\prime\prime}\in F_{e}\backslash\hat{F_{e}}$ is not in $Q$ . This element has the property that $w_{e}\geq U_{f^{\prime\prime}}>L_{e}\geq w_{f^{\prime\prime}}$ . By Definition 5 we have that $w^{*}_{f^{\prime\prime}}\in[L_{f^{\prime\prime}},U_{f^{\prime\prime}}]$ . Since $L_{e}<U_{f^{\prime\prime}}$ , Corollary 9 is not satisfied. However, having $e$ or all such $f^{\prime\prime}\in Q$ will show that $w^{*}_{e}>w^{*}_{f^{\prime\prime}}$ .

By ensuring that $F_{e}\subseteq Q$ or $\hat{F_{e}}+e\subseteq Q$ we have that either $w_{e}\geq L_{e}(Q)\geq L_{e}\geq U_{f}(Q)=w_{f}=w^{*}_{f}$ and so $w_{e}\geq w^{*}_{f}$ for all $f\in F$ or $w^{*}_{e}=w_{e}=L_{e}(Q)\geq U_{f}\geq U_{f}(Q)=w_{f}=w^{*}_{f}$ so $w^{*}_{e}\geq w^{*}_{f}$ for all $f^{\prime\prime}\in\hat{F_{e}}$ . For all $f^{\prime\prime}\in F_{e}\setminus\hat{F_{e}}$ , given that $L_{e}<U_{f}\leq w_{e}$ , the inclusion of $e\in Q$ ensures that $w^{*}_{e}=w_{e}=L_{e}(Q)\geq U_{f}\geq U_{f}(Q)\geq w_{f}$ . Therefore, Corollary 9 is satisfied.

$\hfill\blacktriangleleft$

In all cases, the construction of $Q$ verifies that each element $e\notin B$ is a maximum-weight element on the unique circuit it forms in $B$ , which completes the proof by Corollary 9. Intuitively, Lemma 26 exhaustively formulates the ‘choices’ that a certificate $Q$ has to make to ensure that Corollary 9 is satisfied for a fundamental cycle $C_{e}$ with respect to $B$ of an $e\not\in B$ . For example, if $C_{e}$ falls into the second case of the lemma, then we must have $F_{e}\subseteq Q$ or $e\in Q$ (or both). The ‘choices’ for different $e,e^{\prime}\not\in B$ however, are not necessarily disjoint, e.g., if we have $F_{e}\cap F_{e^{\prime}}\not=\emptyset$ . Similar to verification algorithms in the literature, we define an auxiliary graph $G^{B}$ such that every vertex cover of $G^{B}$ corresponds to a combination of ‘choices’ of Lemma 26, and vice versa. The following definition makes this more precise.

Definition 27.

Given a weighted uncertainty matroid $\mathcal{M}=(E,\mathcal{I},A,w)$ and an MWB $B$ , we define the bipartite (with the exception of self-loops) auxiliary graph $G^{B}=(V^{B},E^{B})$ with $V^{B}=E$ and $E^{B}=\bigcup_{e\in E\setminus B}E^{B}_{e}$ , where the sets $E_{e}^{B}$ for $e\in E\setminus B$ are defined as follows:

1.

If $w_{e}\geq U_{f}$ for all $f\in C_{e}-e$ , and there is a $f^{\prime}\in C_{e}-e$ with $w_{f^{\prime}}>L_{e}$ , then $E^{B}_{e}=\{\{e,e\}\}$ .
2.

If $w_{e}\geq U_{f}$ for all $f\in C_{e}-e$ , and $w_{f}\leq L_{e}$ for all $f\in C_{e}-e$ , then $E^{B}_{e}=\{\{e,f\}\mid f\in F_{e}\}$ .
3.

If there exists $f\in C_{e}-e$ such that $w_{e}<U_{f}$ , and there exists $f^{\prime}\in C_{e}-e$ (could have $f^{\prime}=f$ ) such that $w_{f^{\prime}}>L_{e}$ , then $E^{B}_{e}=\{\{f,f\}\mid f\in\hat{F_{e}}+e\}$ .
4.

If there exists $f\in C_{e}-e$ such that $w_{e}<U_{f}$ , and for all $f^{\prime}\in C_{e}-e$ it holds that $w_{f^{\prime}}\leq L_{e}$ , then $E_{e}^{B}=\{\{e,f\}\mid f\in F_{e}\setminus\hat{F}_{e}\}\cup\{\{f,f\}\mid f\in% \hat{F}_{e}\}$ .

Each case of Definition 27 corresponds to a case of Lemma 26 and exactly models the corresponding ‘choice’ of the lemma. The following corollary follows from Lemma 26 and formally proves (cf. the full version [4]) the connection between Definition 27 and Lemma 26.

Corollary 28.

Given a weighted uncertainty matroid $\mathcal{M}=(E,\mathcal{I},A,w)$ with MWB $B$ , a set $Q$ is a certificate of $B$ if and only if $Q$ is a vertex cover of $G^{B}$ .

Since a set $Q\subseteq E$ is a certificate for $B$ if and only if $Q$ is a vertex cover of $G^{B}$ , we can compute a minimum-cost certificate for $B$ by computing a minimum-cost vertex cover for $G^{B}$ , using the query costs $c_{e}$ as weights for the vertices $V^{B}=E$ . Note that $G^{B}$ is bipartite except for the self-loop edges. To employ polynomial-time vertex-cover algorithms for bipartite graphs (see, e.g., [24]), we modify $G^{B}$ by replacing each loop-edge $\{e,e\}\in E^{B}$ with an edge $\{e,v_{e}\}$ to a distinct new dummy vertex $v_{e}$ with weight $w(v_{e})=w_{e}+\epsilon$ for some $\epsilon>0$ . Executing the algorithm, formalized as Algorithm 2, for the MWB $B$ computed by Algorithm 1 yields a polynomial-time algorithm that computes a minimum-cost certificate.

Algorithm 2 Identifying a Minimum-Cost Certificate of

B

.

Theorem 29.

Let $\mathcal{M}=(E,\mathcal{I},A,w)$ be a weighted uncertainty matroid. Algorithm 2 is a polynomial-time algorithm that computes a minimum-cost certificate $Q$ and an MWB $B$ of $\mathcal{M}$ that is verified by $Q$ .

Proof.

The correctness of the algorithm immediately follows Corollary 28. Thus, it only remains to argue about the running-time. The MWB $B$ can be computed in polynomial time by Lemma 25. Based on $B$ , the graph $G^{B}$ can also be computed in polynomial time.

To show that the minimum-weight vertex cover can be computed in polynomial time, note that $G^{B}$ is bipartite except for the self-loop edges. Indeed, all non-loop edges have one endpoint in $B$ and one endpoint in $E\setminus B$ . To still compute a minimum-weight vertex cover for $G^{B}$ using the algorithms for bipartite graphs (see, e.g., [24]), we define $\bar{G}^{B}$ as a copy of $G^{B}$ that replaces each loop-edge $\{e,e\}\in E^{B}$ with an edge $\{e,v_{e}\}$ to a distinct new vertex $v_{e}$ with weight $w(v_{e})=w_{e}+\epsilon$ for some $\epsilon>0$ . Clearly, the size of $\bar{G}^{B}$ is polynomial in the size of $G^{B}$ and a set $Q$ is a minimum-weight vertex cover of $G^{B}$ if and only if $Q$ is a minimum-weight vertex cover for $\hat{G}^{B}$ . Since $\hat{G}^{B}$ is bipartite, we can compute a minimum-weight vertex cover for $\hat{G}^{B}$ , and thus for $G^{B}$ , by using the classical algorithm for bipartite graphs. $\hfill\blacktriangleleft$

5 Applications

In this section, we show that our verification algorithm and our structural insights, in particular Lemma 26, can be used to obtain new results for the adaptive online variant and for two learning-augmented variants of the MWB problem under uncertainty.

5.1 A Best-Possible Adaptive Online Algorithm for a Given MWB

In the following, we give an optimal algorithm for the adaptive online problem under the assumption that we are given an MWB $B$ that can be verified with a minimum-cost certificate.

In the adaptive online problem, the weights $w_{e}$ are initially unknown, and an algorithm has access only to the uncertainty matroid $\mathcal{M}$ . The goal of the algorithm is to adaptively query elements until the set of queried elements $Q$ verifies some MWB $B$ of $\mathcal{M}$ (cf. Definition 6). Algorithms are analyzed in terms of their competitive ratio. An algorithm is $\rho$ -competitive if $c(Q(\mathcal{M}))\leq\rho\cdot c(Q^{*}(\mathcal{M}))$ for all uncertainty matroids $\mathcal{M}$ , where $Q(\mathcal{M})$ is the set of elements queried by the algorithm on $\mathcal{M}$ , and $Q^{*}(\mathcal{M})$ is a minimum-cost certificate for $\mathcal{M}$ . The competitive ratio of an algorithm is the minimum $\rho$ such that the algorithm is $\rho$ -competitive.

The best-possible competitive ratio heavily depends on the type of uncertainty areas. If all uncertainty areas are either open, i.e., $A_{e}=(L_{e},U_{e})$ , or trivial, i.e., $A_{e}=\{w_{e}\}$ , then the best-possible competitive ratio is $2$ [13]. Once the uncertainty areas can be closed intervals, the best-possible competitive ratio increases to $n$ [11, Section 7]. Both results hold for uniform query costs ( $c_{e}=1$ for $e\in E$ ). Here, we consider the case of uniform query costs.

It is not hard to see that the lower bound of $2$ for minimum spanning trees in the case of open uncertainty areas [13] holds even if the algorithm is given an MWB $B$ with the promise that (i) $B$ is indeed an MWB for the unknown weights and (ii) $B$ can be verified with a minimum-cost certificate. Note that for open uncertainty areas, (ii) is an implication of (i).

Observation 30 (Follows from [13]).

No deterministic algorithm for the online adaptive MWB problem with uniform query costs is better than $2$ -competitive, even if the algorithm is given an MWB $B$ w.r.t. to the unknown weights.

In contrast, the lower bound of $n$ for the case of general uncertainty areas [11, Section 7] does not hold if the algorithm receives the same promise as described above. This contrast highlights that the increase in the competitive ratio from open to general uncertainty areas stems from the algorithm’s task of finding rather than merely verifying an MWB $B$ . In the following, we formally prove this insight. The core of the proof is an application of Lemma 26.

Lemma 31.

There exists an online adaptive algorithm that, given an uncertainty matroid $\mathcal{M}$ and an MWB $B$ (w.r.t. the unknown weights $w$ ) that can be verified with a minimum-cardinality certificate $Q^{*}$ , computes a certificate $Q$ with $|Q|\leq 2|Q^{*}|$ that verifies $B$ .

Proof.

To prove the lemma, we define the following algorithm:

1.

Initialize $Q=\emptyset$ .
2.
For each $e\in E\setminus B$ :
1. (a)
  
  Let $C_{e}$ denote the fundamental circuit of $e$ with respect to $B$ .
2. (b)
  While there exists an $f\in C_{e}-e$ with $U_{f}(Q)>L_{e}(Q)$ :
  1. i.
    
    If there is an element $g\in C_{e}\setminus(\{e\}\cup Q)$ with $U_{g}(Q)>L_{e}(Q)$ , then let $\hat{g}$ denote such an element with maximum $U_{\hat{g}}(Q)$ . Add $\hat{g}$ to $Q$ and query $\hat{g}$ .
  2. ii.
    
    If $e\not\in Q$ , then add $e$ to $Q$ and query $e$ .
3.

Return $Q$ .

It is not hard to see that the set $Q$ computed by the algorithm is a certificate that verifies $B$ : Exploiting the assumption that $B$ is indeed an MWB, the definition of Step 2b ensures that $Q$ satisfies Corollary 9. Hence, $Q$ is a certificate that verifies $B$ .

It remains to show that $|Q|\leq 2\cdot|Q^{*}|$ . The proof will heavily exploit that $Q^{*}$ , by assumption, is a certificate that verifies $B$ . In particular, this means that $Q^{*}$ satisfies Lemma 26 for $B$ , which will help us to bound $|Q|$ in terms of $|Q^{*}|$ .

Let $E\setminus B=\{e_{1},\ldots,e_{k}\}$ be indexed in the order in which the algorithm considers the elements of $E\setminus B$ in the loop of Step 2. For each $j\in\{1,\ldots,k\}$ let $Q_{j}$ denote the set of elements that the algorithm queries during iteration $j$ of the loop of Step 2. We show that

\frac{|Q_{j}|}{|Q_{j}\cap Q^{*}|}\leq 2

(1)

holds for each $Q_{j}$ with $j\in\{1,\ldots,k\}$ . Since the sets $Q_{j}$ form a partition of $Q$ , this then implies $|Q|\leq 2|Q^{*}|$ .

Fix an arbitrary $Q_{j}$ . Define $P_{j}=\bigcup_{j^{\prime}<j}Q_{j^{\prime}}$ . We show that $Q_{j}$ satisfies (1) via case distinction over the cardinality of $Q_{j}$ .

1.

If $|Q_{j}|=0$ , then (1) holds trivially.
2.

If $|Q_{j}|=1$ , then the definition of the loop of Step 2b implies that we must have $Q_{j}=\{e_{j}\}$ as $e_{j}\in Q_{j}$ holds by Step 2bii of the algorithm. The fact that the loop of Step 2b is executed but only queries $e_{j}$ implies that all $g\in C_{e_{j}}\setminus(\{e_{j}\}\cup P_{j})$ have $w_{g}\leq U_{g}(P_{j})\leq L_{e_{j}}(P_{j})=L_{e_{j}}$ (cf. Step 2bi). However, then the fact that the loop of Step 2b is executed implies that there is some $g\in C_{e_{j}}\cap P_{j}$ with $U_{g}(P_{j})=w_{g}>L_{e_{j}}(P_{j})=L_{e_{j}}$ . This in turn implies that $C_{e_{j}}$ either satisfies the first or third case of Lemma 26. Hence, $e_{j}\in Q^{*}$ and $\frac{|Q_{j}|}{|Q_{j}\cap Q^{*}|}=1$ .
3.

If $|Q_{j}|=2$ , then Lemma 26 implies $|Q_{j}\cap Q^{*}|\geq 1$ . Hence, $\frac{|Q_{j}|}{|Q_{j}\cap Q^{*}|}\leq 2$
4.

If $|Q_{j}|>2$ , then the loop of Step 2b is executed at least twice. For the two elements that are queried in the first iteration, we can argue that $Q^{*}$ has to contain at least one of them as in the previous case.

Let $Q_{j}^{\prime}$ denote the subset of $Q_{j}$ that is queried after the first iteration of this Step 2b loop. All $g\in Q_{j}^{\prime}$ have to satisfy $U_{g}>w_{e_{j}}$ , as otherwise the loop would terminate before $g$ is queried. This implies that all $g\in Q_{j}^{\prime}$ are in $\hat{F}_{e_{j}}$ (defined as in Lemma 26). Hence, $C_{e_{j}}$ either satisfies Case 3 or 4 of Lemma 26 and, thus, $Q_{j}^{\prime}\subseteq\hat{F}_{e_{j}}\subseteq Q^{*}$ . We can conclude with $\frac{|Q_{j}|}{|Q_{j}\cap Q^{*}|}\leq\frac{2+|Q_{j}^{\prime}|}{1+|Q_{j}^{% \prime}|}\leq 2$ .

$\hfill\blacktriangleleft$

5.2 Learning-Augmented Algorithms

Recently, online adaptive problems under explorable uncertainty have been studied in learning-augmented settings [6, 7], where the algorithm has access to imperfect predictions $\hat{w}_{e}$ on the unknown weights $w_{e}$ . The goal is to design algorithms that leverage the access to the predictions to achieve an improved competitive ratio in case the predictions are accurate, and at the same time maintain worst-case guarantees even if the predictions are arbitrarily wrong. Such learning-augmented algorithms are analyzed w.r.t. their consistency, the competitive ratio if $w_{e}=\hat{w}_{e}$ for all $e\in E$ , and robustness, the competitive ratio for arbitrary predictions [16, 22].

For the online adaptive MST problem with open uncertainty areas, Erlebach et al. [7] gave a $1.5$ -consistent and $2$ -robust algorithm. In the following we show that our verification algorithm and the insights from the previous section can be used to design learning-augmented algorithms for the online adaptive MWB problem with general uncertainty areas for two prediction models:

1.

Weight predictions: As in [6, 7], the algorithm has access to predictions $\hat{w}_{e}$ on the unknown element weights $w_{e}$ .
2.

Basis predictions: The algorithm has access to a prediction $\hat{B}$ on the MWB $B^{*}$ that can be verified with a minimum-cardinality certificate.

5.2.1 Weight Predictions

Our verification algorithm implies a $1$ -consistent and $n$ -robust algorithm for the case of uniform query costs. Note that this consistency and robustness are optimal due to the aforementioned lower bound given in [11].

1.

Use the verification algorithm to compute and query a minimum-cost certificate under the assumption that the predictions are accurate, i.e., $w_{e}=\hat{w}_{e}$ for all $e\in E$ .
2.

If the instance is not solved yet, then query all remaining elements.

Corollary 32.

The algorithm above runs in polynomial time and is $1$ -consistent and $n$ -robust for the online adaptive MWB problem with weight predictions and uniform query costs.

Proof.

Let $Q$ denote the query set computed by the algorithm and let $Q^{*}$ denote the minimum-cardinality query set. If the predictions are correct, $w_{e}=\hat{w}_{e}$ for all $e\in E$ , then the second step of the algorithm computes and queries a minimum-cardinality certificate for the instance. Hence, Step 2 is never executed and the algorithm is $1$ -consistent. If the predictions are incorrect and the algorithm queries at least one element, then also $|Q^{*}|\geq 1$ . Since the algorithm queries at most $n$ elements, $n$ -robustness follows immediately. $\hfill\blacktriangleleft$

This naive algorithm is a first step towards smooth learning augmented-algorithms for the online adaptive MWB problem with weight predictions, i.e., algorithms with a competitive ratio that smoothly degrades from $1$ to $n$ depending on some error measure describing the quality of the predictions. Next, we give such a smooth algorithm (with a worse consistency) for basis predictions. Since weight predictions can be used to compute a basis prediction, the algorithm can also be interpreted as a smooth algorithm for weight predictions.

5.2.2 Basis Predictions

We consider the prediction model where algorithms have access to a prediction $\hat{B}$ on an MWB $B^{*}$ that can be verified with a minimum cardinality query set $Q^{*}$ . W.l.o.g. we may assume that $\hat{B}$ is indeed a basis of the given uncertainty matroid. This is easy to check and if $\hat{B}$ is not a basis, we remove a minimum number of elements to achieve independence and then augment it to a basis.

We say that the prediction $\hat{B}$ is correct if it is indeed an MWB that can be verified with some minimum cardinality query set. Otherwise, the prediction is incorrect. We now define error measures to quantify the quality of a prediction $\hat{B}$ . Note that a prediction $\hat{B}$ , can have two different types of error. First, $\hat{B}$ might not actually be an MWB. Second, even if $\hat{B}$ is an MWB, it might not be an MWB of minimum verification cost. Our error measure takes both of these error types into account. To this end, let $C_{e}$ for $e\in E\setminus\hat{B}$ denote the fundamental circuit of $e$ with respect to $\hat{B}$ . Define such a circuit $C_{e}$ to be correct if $w_{e}\geq w_{f}$ for all $f\in C_{e}-e$ and $w_{f}\leq w_{g}$ for all $f\in C_{e}-e$ and $g\in E\setminus\textrm{span}_{M}(\hat{B}-f)$ . Otherwise, call $C_{e}$ incorrect. Let $\hat{B}_{s}\subseteq\hat{B}$ denote the set of elements in $\hat{B}$ that are part of a correct fundamental circuit $C_{e}$ , $e\in E\setminus\hat{B}$ . We define two errors:

$\blacksquare$

Let $\hat{B}_{s}^{*}$ denote an MWB with $\hat{B}_{s}\subseteq\hat{B}_{s}^{*}$ such that $\hat{B}_{s}^{*}$ has minimum verification cost among all MWB’s that contain $\hat{B}_{s}$ and let $Q^{\prime}$ denote a minimum-cardinality certificate for $\hat{B}_{s}^{*}$ . In the full version [4], we argue that such an MWB $\hat{B}_{s}^{*}$ always exists. Define $\eta_{1}=|Q^{\prime}|-|Q^{*}|$ , where $Q^{*}$ is the minimum-cardinality certificate. Note that if $\hat{B}$ is an MWB, then $\eta_{1}$ is just the difference between the verification cost of $\hat{B}$ and the minimum verification cost $|Q^{*}|$ .
$\blacksquare$

Let $\eta_{2}$ denote the number of incorrect circuits $C_{e}$ with $e\in E\setminus\hat{B}$ .

Intuitively, $\eta_{1}$ measures how much larger the verification cost of $\hat{B}$ is compared to the minimum-cardinality query set. Error $\eta_{2}$ captures how far $\hat{B}$ is from actually being an MWB.

The following theorem can be achieved using a slight variation of the algorithm in Section 5.1, taking into account that elements $e\in E\setminus\hat{B}$ might not be maximal on circuit $C_{e}$ . In such cases, the algorithm deviates from the procedure in Section 5.1 by querying all elements in circuit $C_{e}$ . In the full version [4], we give the formal definition of this algorithm and the proof of the theorem, and argue that the factor $c_{\max}$ of the error $\eta_{2}$ is indeed necessary.

Theorem 33.

Given an instance of the online adaptive MWB problem with a predicted basis $\hat{B}$ and uniform query costs, there is an algorithm that computes a certificate $Q$ for some MWB $B$ and satisfies $|Q|\leq\min\{2\cdot(|Q^{*}|+\eta_{1})+\eta_{2}\cdot c_{\max},n\}$ , where $Q^{*}$ is a minimum-cardinality certificate and $c_{\max}$ is the size of the largest circuit. In particular, the algorithm is $2$ -consistent and $n$ -robust.

References

[1] Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter. Orienting (hyper)graphs under explorable stochastic uncertainty. In ESA, volume 204 of LIPIcs, pages 10:1–10:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ESA.2021.10.
[2] Steven Chaplick, Magnús M. Halldórsson, Murilo Santos de Lima, and Tigran Tonoyan. Query minimization under stochastic uncertainty. In LATIN, volume 12118 of Lecture Notes in Computer Science, pages 181–193. Springer, 2020. doi:10.1007/978-3-030-61792-9_15.
[3] George Charalambous and Michael Hoffmann. Verification problem of maximal points under uncertainty. In IWOCA 2013, volume 8288 of Lecture Notes in Computer Science, pages 94–105. Springer, 2013. doi:10.1007/978-3-642-45278-9_9.
[4] Haya Diwan, Lisa Hellerstein, Nicole Megow, and Jens Schlöter. Optimal verification of a minimum-weight basis in an uncertainty matroid, 2025. arXiv:2512.17116.
[5] T. Erlebach and M. Hoffmann. Query-competitive algorithms for computing with uncertainty. Bulletin of the EATCS, 116:22–39, 2015. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/335.
[6] Thomas Erlebach, Murilo S. de Lima, Nicole Megow, and Jens Schlöter. Sorting and hypergraph orientation under uncertainty with predictions. In IJCAI, pages 5577–5585. ijcai.org, 2023. doi:10.24963/IJCAI.2023/619.
[7] Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter. Learning-augmented query policies for minimum spanning tree with uncertainty. In ESA, volume 244 of LIPIcs, pages 49:1–49:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ESA.2022.49.
[8] Thomas Erlebach and Michael Hoffmann. Minimum spanning tree verification under uncertainty. In Dieter Kratsch and Ioan Todinca, editors, Graph-Theoretic Concepts in Computer Science, volume 8747 of Lecture Notes in Computer Science, pages 164–175. Springer International Publishing, Cham, 2014. doi:10.1007/978-3-319-12340-0_14.
[9] Thomas Erlebach, Michael Hoffmann, and Frank Kammer. Query-competitive algorithms for cheapest set problems under uncertainty. Theor. Comput. Sci., 613:51–64, 2016. doi:10.1016/J.TCS.2015.11.025.
[10] T. Feder, R. Motwani, R. Panigrahy, C. Olston, and J. Widom. Computing the median with uncertainty. SIAM Journal on Computing, 32(2):538–547, 2003. doi:10.1137/S0097539701395668.
[11] Manoj Gupta, Yogish Sabharwal, and Sandeep Sen. The update complexity of selection and related problems. Theory Comput. Syst., 59(1):112–132, 2016. doi:10.1007/S00224-015-9664-Y.
[12] Magnús M. Halldórsson and Murilo Santos de Lima. Query-competitive sorting with uncertainty. Theor. Comput. Sci., 867:50–67, 2021. doi:10.1016/J.TCS.2021.03.021.
[13] Michael Hoffmann, Thomas Erlebach, Danny Krizanc, Matús Mihalák, and Rajeev Raman. Computing minimum spanning trees with uncertainty. In STACS, volume 1 of LIPIcs, pages 277–288. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany, 2008. doi:10.4230/LIPIcs.STACS.2008.1358.
[14] Simon Kahan. A model for data in motion. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pages 265–277, New York, NY, USA, 1991. Association for Computing Machinery. doi:10.1145/103418.103449.
[15] Eugene L Lawler. Combinatorial optimization: networks and matroids. Courier Corporation, 2001.
[16] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68(4):24:1–24:25, 2021. doi:10.1145/3447579.
[17] Corinna Mathwieser and Eranda Çela. Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty. Networks, 83(3):587–604, 2024. doi:10.1002/NET.22204.
[18] Nicole Megow, Julie Meißner, and Martin Skutella. Randomization helps computing a minimum spanning tree under uncertainty. SIAM J. Comput., 46(4):1217–1240, 2017. doi:10.1137/16M1088375.
[19] Nicole Megow and Jens Schlöter. Set selection under explorable stochastic uncertainty via covering techniques. In IPCO, volume 13904 of Lecture Notes in Computer Science, pages 319–333. Springer, 2023. doi:10.1007/978-3-031-32726-1_23.
[20] J. Meißner. Uncertainty Exploration: Algorithms, Competitive Analysis, and Computational Experiments. PhD thesis, Technischen Universität Berlin, 2018. doi:10.14279/depositonce-7327.
[21] Arturo Merino and José A. Soto. The minimum cost query problem on matroids with uncertainty areas. In ICALP, volume 132 of LIPIcs, pages 83:1–83:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.83.
[22] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In NeurIPS, pages 9684–9693, 2018. URL: https://proceedings.neurips.cc/paper/2018/hash/73a427badebe0e32caa2e1fc7530b7f3-Abstract.html.
[23] Jens Schlöter. On the complexity of knapsack under explorable uncertainty: Hardness and algorithms. In 33rd Annual European Symposium on Algorithms, volume 351 of LIPIcs, pages 6:1–6:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ESA.2025.6.
[24] Alexander Schrijver. Combinatorial Optimization $-$ Polyhedra and Efficiency. Springer, 2003.

[bib.bib1] [1] Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter. Orienting (hyper)graphs under explorable stochastic uncertainty. In ESA, volume 204 of LIPIcs, pages 10:1–10:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ESA.2021.10.

[bib.bib2] [2] Steven Chaplick, Magnús M. Halldórsson, Murilo Santos de Lima, and Tigran Tonoyan. Query minimization under stochastic uncertainty. In LATIN, volume 12118 of Lecture Notes in Computer Science, pages 181–193. Springer, 2020. doi:10.1007/978-3-030-61792-9_15.

[bib.bib3] [3] George Charalambous and Michael Hoffmann. Verification problem of maximal points under uncertainty. In IWOCA 2013, volume 8288 of Lecture Notes in Computer Science, pages 94–105. Springer, 2013. doi:10.1007/978-3-642-45278-9_9.

[bib.bib4] [4] Haya Diwan, Lisa Hellerstein, Nicole Megow, and Jens Schlöter. Optimal verification of a minimum-weight basis in an uncertainty matroid, 2025. arXiv:2512.17116.

[bib.bib5] [5] T. Erlebach and M. Hoffmann. Query-competitive algorithms for computing with uncertainty. Bulletin of the EATCS, 116:22–39, 2015. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/335.

[bib.bib6] [6] Thomas Erlebach, Murilo S. de Lima, Nicole Megow, and Jens Schlöter. Sorting and hypergraph orientation under uncertainty with predictions. In IJCAI, pages 5577–5585. ijcai.org, 2023. doi:10.24963/IJCAI.2023/619.

[bib.bib7] [7] Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter. Learning-augmented query policies for minimum spanning tree with uncertainty. In ESA, volume 244 of LIPIcs, pages 49:1–49:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ESA.2022.49.

[bib.bib8] [8] Thomas Erlebach and Michael Hoffmann. Minimum spanning tree verification under uncertainty. In Dieter Kratsch and Ioan Todinca, editors, Graph-Theoretic Concepts in Computer Science, volume 8747 of Lecture Notes in Computer Science, pages 164–175. Springer International Publishing, Cham, 2014. doi:10.1007/978-3-319-12340-0_14.

[bib.bib9] [9] Thomas Erlebach, Michael Hoffmann, and Frank Kammer. Query-competitive algorithms for cheapest set problems under uncertainty. Theor. Comput. Sci., 613:51–64, 2016. doi:10.1016/J.TCS.2015.11.025.

[bib.bib10] [10] T. Feder, R. Motwani, R. Panigrahy, C. Olston, and J. Widom. Computing the median with uncertainty. SIAM Journal on Computing, 32(2):538–547, 2003. doi:10.1137/S0097539701395668.

[bib.bib11] [11] Manoj Gupta, Yogish Sabharwal, and Sandeep Sen. The update complexity of selection and related problems. Theory Comput. Syst., 59(1):112–132, 2016. doi:10.1007/S00224-015-9664-Y.

[bib.bib12] [12] Magnús M. Halldórsson and Murilo Santos de Lima. Query-competitive sorting with uncertainty. Theor. Comput. Sci., 867:50–67, 2021. doi:10.1016/J.TCS.2021.03.021.

[bib.bib13] [13] Michael Hoffmann, Thomas Erlebach, Danny Krizanc, Matús Mihalák, and Rajeev Raman. Computing minimum spanning trees with uncertainty. In STACS, volume 1 of LIPIcs, pages 277–288. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany, 2008. doi:10.4230/LIPIcs.STACS.2008.1358.

[bib.bib14] [14] Simon Kahan. A model for data in motion. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pages 265–277, New York, NY, USA, 1991. Association for Computing Machinery. doi:10.1145/103418.103449.

[bib.bib15] [15] Eugene L Lawler. Combinatorial optimization: networks and matroids. Courier Corporation, 2001.

[bib.bib16] [16] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68(4):24:1–24:25, 2021. doi:10.1145/3447579.

[bib.bib17] [17] Corinna Mathwieser and Eranda Çela. Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty. Networks, 83(3):587–604, 2024. doi:10.1002/NET.22204.

[bib.bib18] [18] Nicole Megow, Julie Meißner, and Martin Skutella. Randomization helps computing a minimum spanning tree under uncertainty. SIAM J. Comput., 46(4):1217–1240, 2017. doi:10.1137/16M1088375.

[bib.bib19] [19] Nicole Megow and Jens Schlöter. Set selection under explorable stochastic uncertainty via covering techniques. In IPCO, volume 13904 of Lecture Notes in Computer Science, pages 319–333. Springer, 2023. doi:10.1007/978-3-031-32726-1_23.

[bib.bib20] [20] J. Meißner. Uncertainty Exploration: Algorithms, Competitive Analysis, and Computational Experiments. PhD thesis, Technischen Universität Berlin, 2018. doi:10.14279/depositonce-7327.

[bib.bib21] [21] Arturo Merino and José A. Soto. The minimum cost query problem on matroids with uncertainty areas. In ICALP, volume 132 of LIPIcs, pages 83:1–83:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.83.

[bib.bib22] [22] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In NeurIPS, pages 9684–9693, 2018. URL: https://proceedings.neurips.cc/paper/2018/hash/73a427badebe0e32caa2e1fc7530b7f3-Abstract.html.

[bib.bib23] [23] Jens Schlöter. On the complexity of knapsack under explorable uncertainty: Hardness and algorithms. In 33rd Annual European Symposium on Algorithms, volume 351 of LIPIcs, pages 6:1–6:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ESA.2025.6.

[bib.bib24] [24] Alexander Schrijver. Combinatorial Optimization $-$ Polyhedra and Efficiency. Springer, 2003.

Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Related Work

Verification problems.

Online algorithms.

Beyond-worst-case models and the relevance of verification methods.

1.2 Our Results

2 Preliminaries

2.1 Matroid Basics

2.2 Properties of Bases

Proposition 1.

Proposition 2.

Observation 3.

2.3 Uncertainty Matroids and Certificates

Definition 4 (Uncertainty Matroid).

Definition 5 (Consistent weight assignment).

Definition 6 (Verification and certificates).

Definition 7 (Minimum-cost certificate).

2.3.1 Characterization of Certificates

Lemma 8.

Proof.

Corollary 9.

2.3.2 Exchange Properties of Certificates

Lemma 10.

Proof.

Case (1):

Case (2):

Lemma 11.

Lemma 12.

3 Computing an MWB that has a Minimum-Cost Certificate

Definition 13.

Theorem 14.

3.1 Contraction and Deletion Rules

Observation 15.

Observation 16.

3.1.1 Rules for Non-Trivial Extreme Case Elements

Lemma 17.

Proof.

Lemma 18.

Assumption 19.

3.1.2 Rules for Trivial Extreme Case Elements

Lemma 20.

Lemma 21.

Assumption 22.

Corollary 23.

3.1.3 Rules for Instances without Extreme Case Elements

Lemma 24.

3.2 A Polynomial-time Algorithm

Lemma 25.

Proof.

4 Computing a Minimum-Cost Certificate to Verify a Given Basis

Lemma 26.

Proof.

Case 1.

Case 2.

Definition 27.

Corollary 28.

Theorem 29.

Proof.

5 Applications

5.1 A Best-Possible Adaptive Online Algorithm for a Given MWB

Observation 30 (Follows from [13]).

Lemma 31.

Proof.

5.2 Learning-Augmented Algorithms

5.2.1 Weight Predictions

Corollary 32.

Proof.

5.2.2 Basis Predictions

Theorem 33.