TY - GEN

T1 - Algorithms for implicit hitting set problems

AU - Chandrasekaran, Karthekeyan

AU - Karp, Richard

AU - Moreno-Centeno, Erick

AU - Vempala, Santosh

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2011

Y1 - 2011

N2 - A hitting set for a collection of sets is a set that has a nonempty intersection with each set in the collection; the hitting set problem is to find a hitting set of minimum cardinality. Motivated by instances of the hitting set problem where the number of sets to be hit is large, we introduce the notion of implicit hitting set problems. In an implicit hitting set problem the collection of sets to be hit is typically too large to list explicitly; instead, an oracle is provided which, given a set H, either determines that H is a hitting set or returns a set that H does not hit. We show a number of examples of classic implicit hitting set problems, and give a generic algorithm for solving such problems optimally. The main contribution of this paper is to show that this framework is valuable in developing approximation algorithms. We illustrate this methodology by presenting a simple on-line algorithm for the minimum feedback vertex set problem on random graphs. In particular our algorithm gives a feedback vertex set of size n - ( 1/p) log np( 1 - o(1)) with probability at least 3/4 for the random graph Gn,p (the smallest feedback vertex set is of size n - (2/p) log np(l + o(l))). We also consider a planted model for the feedback vertex set in directed random graphs. Here we show that a hitting set for a polynomial-sized subset of cycles is a hitting set for the planted raindom graph and this allows us to exactly recover the planted feedback vertex set.

AB - A hitting set for a collection of sets is a set that has a nonempty intersection with each set in the collection; the hitting set problem is to find a hitting set of minimum cardinality. Motivated by instances of the hitting set problem where the number of sets to be hit is large, we introduce the notion of implicit hitting set problems. In an implicit hitting set problem the collection of sets to be hit is typically too large to list explicitly; instead, an oracle is provided which, given a set H, either determines that H is a hitting set or returns a set that H does not hit. We show a number of examples of classic implicit hitting set problems, and give a generic algorithm for solving such problems optimally. The main contribution of this paper is to show that this framework is valuable in developing approximation algorithms. We illustrate this methodology by presenting a simple on-line algorithm for the minimum feedback vertex set problem on random graphs. In particular our algorithm gives a feedback vertex set of size n - ( 1/p) log np( 1 - o(1)) with probability at least 3/4 for the random graph Gn,p (the smallest feedback vertex set is of size n - (2/p) log np(l + o(l))). We also consider a planted model for the feedback vertex set in directed random graphs. Here we show that a hitting set for a polynomial-sized subset of cycles is a hitting set for the planted raindom graph and this allows us to exactly recover the planted feedback vertex set.

UR - http://www.scopus.com/inward/record.url?scp=79955717396&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79955717396&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973082.48

DO - 10.1137/1.9781611973082.48

M3 - Conference contribution

AN - SCOPUS:79955717396

SN - 9780898719932

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 614

EP - 629

BT - Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011

PB - Association for Computing Machinery

ER -