graph - Algorithm for selecting subset of people who use same stuff NP-hard? -

this isn't homework, question encountered during research. need know whether problem np-hard or not. in first case, require approximate algorithm , in latter case efficient 1 providing me optimal solution.

informal description:

imagine p persons using of t tools. every person uses couple of tools, not all. writes down used tool. question: how-to find largest group of persons, each person used @ least k tools else uses too? [prior problem description: same tools else?] number of tools restricted t'

i developed formal description of problem, might help:

let g=(p,t,e) bipartite graph in p represents set of people , t set of tools. there edge between node p in p , t in t if person used tool. goal find sets p', t' following conditions apply: 1) p' in p', t' in t' can reached single edge. 2) |p'|, i.e. number of nodes in p', maximum.

an inefficient approach take each subset p' , calculate intersection of each t' associated p' in p'. unfortunately, number of such subsets grows exponentially , calculation becomes intractable.

thank much!

to find largest group of persons, each person uses same tools else, you'll need group persons set of tools use.

in other words:

• create map: (set of tools) (count of persons using set of tools)
• find set of tools highest count.

this polynomial.

for example:

suppose out tool set {claw hammer, tape measure, utility knife, moisture meter, chisel, level, screwdriver, nail set, sliding bevel, layout square} (source)

we'll create map bit-set (expressed integer of string) integer (count of persons using set of tools).

now, if dan's tools {claw hammer, utility knife, sliding bevel}, we'll add following our map:

key: 1010000010, value: 1.

for adding person, we'll first calculate key. if dave uses same tools dan, we'll same key, we'll increase count:

key: 1010000010, value: 2.

--

• constructing bit-set person's tools-list o(t)
• searching if such key exist in map o(log(p)∙t) (o(t) worst-case comparing 2 strings of length t. better since keys sorted. o(log(p) ignores iterative construction).
• increasing count o(1), alternatively - adding new key map o(log(p)) (actually better because map constructed iteratively).

to summarize - can construct set persons in o(p∙log²(p)∙t). again, can better, prove polynomial.

finding key highest count o(p) - walking on map contains p keys of less.