Algorithms for Implicit Hitting Set Problems

Karthekeyan Chandrasekaran, Richard M. Karp, Erick Moreno-Centeno, Santosh S. Vempala

TL;DR

This paper introduces a framework for solving "Implicit Hitting Set" problems—scenarios where the number of sets to be hit is exponentially large, but a polynomial-time "oracle" can identify missed sets. The authors provide a generic optimal algorithm and demonstrate its power by developing nearly optimal, polynomial-time approximation algorithms for the Minimum Feedback Vertex Set problem in both random and "planted" graph models.

What Problem Does This Paper Address?

In the classic Hitting Set problem, you are given a universe of elements and a collection of subsets. Your goal is to find the smallest number of elements that "hit" (intersect with) every single subset. This is a foundational NP-hard problem with applications across computer science.

However, a major challenge arises in combinatorial optimization: often, the collection of subsets is too massive to list. For example, in the Minimum Feedback Vertex Set (FVS) problem, you want to find the smallest set of vertices to remove from a graph so that no cycles remain. Here, the "subsets" are all possible cycles in the graph—a number that can be exponential relative to the number of vertices.

The authors address the gap between the theoretical hardness of the Hitting Set problem and the practical need to solve instances where the input is defined implicitly rather than explicitly.

Methods

The paper proposes two main algorithmic approaches:

  1. The Generic Implicit Algorithm: The authors define an Implicit Hitting Set (IHS) problem as one where an "oracle" is provided. Given a candidate hitting set $H$, the oracle either confirms $H$ is valid or returns a specific subset that $H$ failed to hit. Their generic algorithm iteratively proposes a candidate, uses the oracle to find a "miss," adds that miss to a growing list of explicit constraints, and re-solves the explicit problem. While the sub-solver is still NP-hard, this framework focuses on minimizing the number of oracle queries.

  2. Algorithm Augment-BFS: Specifically for the Feedback Vertex Set problem, the authors move away from the generic (and potentially slow) solver toward a specialized "online" approach. This algorithm uses a Breadth-First Search (BFS) to explore the graph. When the BFS identifies a cycle, the algorithm immediately "commits" to adding a vertex to the hitting set to break that cycle. This allows the algorithm to run in polynomial time while maintaining an induced tree (an acyclic structure) among the remaining vertices.

Datasets

As a theoretical computer science paper, no real-world datasets were used. Instead, the authors evaluate their algorithms using probabilistic graph models:

  • Erdős-Rényi Random Graphs ($G_{n,p}$): Standard undirected and directed random graphs where edges exist with probability $p$.
  • Planted Feedback Vertex Set Model: A novel model introduced in this paper for directed graphs. In this model, a specific subset of vertices $P$ is chosen to be the FVS, and the remaining graph is constructed to be a Directed Acyclic Graph (DAG) with additional random edges. This serves as a benchmark for "recovery" algorithms.

Key Insights and Ideas

  • The Power of the Oracle: The core "aha moment" is that you don't need to see the whole problem to solve it. By treating the problem as a conversation with an oracle, you can navigate exponential search spaces using only a polynomial number of samples.
  • BFS as a Natural Ordering: For FVS in random graphs, the order in which you hit cycles matters. The authors show that a simple BFS-based ordering is surprisingly effective, allowing a greedy algorithm to stay within a factor of 2 of the existential optimum.
  • Local Hitting for Global Solutions: In the "planted" model, the authors discovered that hitting only small cycles (e.g., triangles or cycles of a fixed length $k$) is sufficient to recover the entire "global" planted feedback vertex set. This suggests that complex global properties can sometimes be reconstructed from local motifs.

Key Results

  • Near-Optimal FVS in Random Graphs: For a random graph $G_{n,p}$ with $p=o(1)$, the algorithm produces an FVS of size $n - (1/p) \log(np)(1-o(1))$ with high probability. This is very close to the theoretical minimum of $n - (2/p) \log(np)$.
  • Exact Recovery in Planted Models: In the directed planted model, the authors proved that their algorithm can exactly recover the hidden feedback vertex set $P$ in polynomial time, provided the graph is dense enough ($p \geq C/n^{1-2/k}$).
  • Framework Versatility: The paper demonstrates that many classic problems—including Max Cut, k-Matroid Intersection, and Maximum Feasible Set of Linear Inequalities—can all be framed as Implicit Hitting Set problems.

Limitations and Future Work

  • Worst-Case Complexity: The generic algorithm still relies on an explicit Hitting Set solver as a subroutine. Since Hitting Set is NP-hard, the generic version remains exponential in the worst case, even if the number of oracle calls is small.
  • The "Factor of 2" Gap: In random graphs, there remains a gap between the algorithm's result and the existential lower bound. The authors note that closing this gap is likely as difficult as the "Maximum Independent Set" problem, a notoriously hard problem in complexity theory.
  • Future Directions: The authors suggest applying this IHS framework to other problems like Synchronization in Acyclic Digraphs or problems motivated by the Unique Games Conjecture.

Summary updated

BibTeX
@inproceedings{chandrasekaran2011algorithms,
  author = {Karthekeyan Chandrasekaran and Richard M. Karp and Erick Moreno-Centeno and Santosh S. Vempala},
  title = {{Algorithms for Implicit Hitting Set Problems}},
  booktitle = {SODA},
  year = {2011},
  doi = {10.1137/1.9781611973082.48},
}
Figure