title: Algorithm for selecting subset of people who use same stuff NP-hard?
body: <p>This isn't homework, but a question I encountered during my research. I need to know whether this problem is NP-hard or not. In the first case, I require an approximate algorithm and in the latter case an efficient one providing me with the optimal solution.</p>
  
  <p><strong>Informal description:</strong></p>
  
  <p>Imagine p persons using some of t tools. Every person uses only a couple of tools, but not all. Someone writes down who used which tool. Question: How-to find the largest group of persons, for which each person used at least k tools that everyone else uses too? [prior problem description: the same tools as everyone else?] The number of tools is restricted to t'
  
  <p><strong>I developed a formal description of this problem, which might help:</strong></p>
  
  <p>Let G=(P,T,E) be a <strong>bipartite graph</strong> in which P represents the set of people and T the set of tools. There is an edge between a node p in P and t in T if the person used that tool. The goal is to find the sets P', T' for which the following conditions apply: 1) From any p' in P', any t' in T' can be reached with a single edge. 2) |P'|, i.e. the number of nodes in P', is maximum.</p>
  
  <p>An inefficient approach would be to take each subset P' and calculate the intersection of each t' associated with a p' in P'. Unfortunately, the number of such subsets grows exponentially and the calculation becomes soon intractable.</p>
  
  <p>Thank you very much!</p>