# Dynamic programming algorithm to find a colorful subset of disjoint sets

Suppose there is a set $$F=\{X_1 ,...,X_m\}$$, such that $$\forall 1\leq i\leq m: |X_i|=3.$$ Suppose we color the elements of $$\bigcup F$$ in $$3k$$ colors. We wish to know if there is a subset $$F'\subseteq F$$ such that all sets in $$F'$$ are pairwise disjoint, and $$F'$$ is colorful, i.e. $$\bigcup F'$$ uses all $$3k$$ colors.

I'm trying to come up with a parameterized fixed tractable dynamic programming algorithm for the task, but I had a couple of issues.

First I thought of defining $$M[C,i]$$ to be $$true$$ iff there is a solution subset of $$F$$ with respect to $$C$$ and $$i$$, that is, it only uses $$\{X_1,...,X_i\}$$ and all the colors in $$C$$.

But when trying to define the recursive relation, if we set $$I=\{j < i: X_j \cap X_i = \emptyset \}$$, then $$M[C,i]= M[C\setminus col(X_i), I]\vee M[C,i-1]$$ which doesn't make much sense since $$i$$ is a number and $$I$$ is a set, but still I cannot allow selection of a colorful set using $$\{X_1 ,... , X_{i-1}\}$$ since it might not be disjoint of $$X_i$$ even though it is pairwise disjoint within itself.

Any ideas on a better definition or a fix for this definition? (Using subsets of $$1,...m$$ is not an option since that would mean $$\Omega(2^m)$$ entries which is not FPT)

• Note that we can assume $|F'| \le 3k$, so we can use the color coding technique on the elements of $\cup F$, coloring them with $9k$ random colors, and requiring that in $\cup F'$ all elements have different colors. This has FPT success probability and can be solved by DP in FPT time. – Laakeri Apr 30 at 4:33
• why $9k$ colors instead of $3k$? And the problem is actually how to solve this by DP? – user62160 Apr 30 at 18:46
• Sounds like an exercise instead of a research-level question in theoretical computer science. – Laakeri Apr 30 at 19:20
• @Laakeri That's what I was asking for help with. The DP part... – user62160 Apr 30 at 20:19