Many combinatorial optimization problems can be described as follows. We are given a set system $(E,I)$, where $I \subseteq 2^E$ and a weight function $w: E \rightarrow \mathbb{N}$. The goal is to find a member of the set system $S \in I$ with maximum total weight $w(S) = \sum_{e \in S} w(e)$. Examples include maximum independent set of a matroid and maximum matching in a graph.

In some cases, the representation of $I$ in the set system is via a membership oracle that determines if some $S \subseteq E$ is in $I$ in a single query. This is useful for describing set systems that require exponential size in $E$ to represent $I$.

Question: Are there set systems $(E,I)$ that satisfy:

(1) Finding $S \in I$ of maximum weight $w(S)$ where $I$ can be accessed only via a membership oracle cannot be computed in $|E|^{O(1)}$ queries and $|E|^{O(1)}$ other basic operations.

(2) I f we are given a concrete input (with no oracle), such that deciding if some $S \subseteq E$ belongs to $I$ takes $|E|^{O(1)}$ time, then the problem is solvable in time $|E|^{O(1)}$. Note that sometimes $I$ can be efficiently encoded and the encoding size of $I$ can be much smaller than the cardinality of $I$. For example, if $(E,I)$ describes a matching set system, where $E$ are the edges of a graph $G = (V,E)$ and $I$ are all matchings of the graph it suffices to encode only $G$ to solve the problem.

If $(E, I)$ is a matroid then (1) is solvable in time $|E|^{O(1)}$, and therefore this does not answer my question. Can someone provide a reference or describe a simple set system that satisfies both (1) and (2)? what if $(E,I)$ describes a matching set system? In this case, (2) can be computed in polynomial time but I am not sure about (1).

  • $\begingroup$ Does the family of singleton set systems (i.e., $|I| = 1$) work? It is hard to find the unique element of $I$ using oracle access, but trivial if $I$ is given explicitly. $\endgroup$ Commented Nov 11, 2023 at 16:56
  • $\begingroup$ In (2) I do not necessarily mean that the encoding is explicit. I can encode the set system $(E,I)$ such that $I = \{S\}$ where $S \subseteq E$ is the single solution for some NP-Hard problem. Hence, finding $I$ is NP-Hard right? $\endgroup$
    – John
    Commented Nov 13, 2023 at 17:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.