0
$\begingroup$

In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$.

$KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey and Fellows in their book give definition as

enter image description here

These two definitions do not seem to be entirely consistent.

We know $W[P]=FPT\implies W[1]=FPT$.

We also know this puts $KSUM$ is $FPT$.

Does it mean $KSUM$ is $FPT$ at a fixed $K$ and independent of length of integer inputs or can it also imply some asymptotic $FPT$ result where $K$ depends non-trivially on number of input integers and length of input integers?

  1. I looked for this information in Grohe's or Downey's book and I am unable to find this information and could someone weight in on this subtlety? That is we might have an algorithm for $KSUM$ that is $FPT$ if input integers have only $O(polylog(n))$ bits each. However if input bitlength is polynomial in $n$ or exponential in $K$ then the $FPT$ algorithm complexity might not be of shape $O(f(K)\cdot poly(n))$. This could still be $FPT$ under Downey's definition. Would such an algorithm still be considered $FPT$ for $KSUM$ as well? It should be but from the working definitions of $FPT$ for $KSUM$ in literature this is unclear.

  2. Is it consistent $W[P]=FPT$ while $KSUM$ is not $FPT$ at bounded or fixed $K$?

$\endgroup$
  • $\begingroup$ I'm not entirely sure if I understand. Are you questioning whether it being in $FPT$ means that it's solvable in $f(k) \cdot n^c$ time vs $f(k) \cdot \vert x \vert ^c$ time where $n$ is the size of the set and $\vert x \vert$ is the total length of the input represented as a binary string? $\endgroup$ – Michael Wehar Jun 26 '18 at 3:36
  • $\begingroup$ Anyway you look at it, the runtime has to depend on $\vert x \vert$ because you have to look at every bit of the input in order to determine if there exists a $k$-SUM. $\endgroup$ – Michael Wehar Jun 26 '18 at 3:38
  • $\begingroup$ Or, are you asking how bounding the input integers affects the parameterized complexity of the $k$-SUM problem? $\endgroup$ – Michael Wehar Jun 26 '18 at 3:39
  • $\begingroup$ @MichaelWehar I think '$FPT$ means that it's solvable in $f(k)\cdot n^c$ time vs $f(k)\cdot |x|^c$ time where $n$ is size of the set and $|x|$ is the total length of the input represented as a binary string' is the query 1. $f(k)\cdot |x|^c$ satisfies what Downey and Fellows have in their definition however when you say $KSUM$ is $FPT$ we usually think of $f(k)\cdot n^c$ (for example wiki says fastest $KSUM$ algorithm is in $n^O(K)$ time and it makes it look like $FPT$ in $KSUM$ case is $f(k)\cdot n^c$ definition which is not what Downey and Fellows have in definition. $\endgroup$ – Turbo Jun 26 '18 at 6:01
  • $\begingroup$ @MichaelWehar Query 2. is about what exactly is the notion of $FPT$ in context of $KSUM$ mean with respect to parameter $K$ (will an algorithm that is $FPT$ in parameter $K$ that is asymptotic to size of the set $n$ (not input length $|x|$) provide $KSUM$ in $FPT$)? $\endgroup$ – Turbo Jun 26 '18 at 6:06

Your Answer

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

Browse other questions tagged or ask your own question.