0
$\begingroup$

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)

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Laakeri Apr 30 at 4:33
  • $\begingroup$ why $9k$ colors instead of $3k$? And the problem is actually how to solve this by DP? $\endgroup$ – user62160 Apr 30 at 18:46
  • $\begingroup$ Sounds like an exercise instead of a research-level question in theoretical computer science. $\endgroup$ – Laakeri Apr 30 at 19:20
  • $\begingroup$ @Laakeri That's what I was asking for help with. The DP part... $\endgroup$ – user62160 Apr 30 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy