Skip to main content
added 227 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

No. Fix $k \in \mathbb{N}$ and let $G$ be aan $n$-vertex graph of treewidth at most $k$. If you analyze their polynomial-time algorithm that decides if $G$ has an equitable tree-colouring, you'll notice that the degree of the polynomial depends on $k$. For example, in the proof of Theorem 11, there is a bound of the form $O(n B^2(k+1) \lceil n/r \rceil^{2c(k+1)})$, where $k$ appears in$r$ and $c$ are constants and $B(k+1)$ is the exponent$(k+1)$-th Bell number. An FPT algorithm must run in time at most $f(k)n^d$, where $d$ is a constant independent of $k$. Thus, ittheir algorithm is not an FPT algorithm. Of

Of course, it is widely believed (but not proved) that FPT $\neq$ W[1].

No. Fix $k \in \mathbb{N}$ and let $G$ be a graph of treewidth at most $k$. If you analyze their polynomial-time algorithm that decides if $G$ has an equitable tree-colouring, you'll notice that the degree of the polynomial depends on $k$. For example, in the proof of Theorem 11, there is a bound where $k$ appears in the exponent. Thus, it is not an FPT algorithm. Of course, it is widely believed (but not proved) that FPT $\neq$ W[1].

No. Fix $k \in \mathbb{N}$ and let $G$ be an $n$-vertex graph of treewidth at most $k$. If you analyze their polynomial-time algorithm that decides if $G$ has an equitable tree-colouring, you'll notice that the degree of the polynomial depends on $k$. For example, in the proof of Theorem 11, there is a bound of the form $O(n B^2(k+1) \lceil n/r \rceil^{2c(k+1)})$, where $r$ and $c$ are constants and $B(k+1)$ is the $(k+1)$-th Bell number. An FPT algorithm must run in time at most $f(k)n^d$, where $d$ is a constant independent of $k$. Thus, their algorithm is not an FPT algorithm.

Of course, it is widely believed (but not proved) that FPT $\neq$ W[1].

added 4 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

No. Fix $k \in \mathbb{N}$ and let $G$ be a graph of treewidth at most $k$. If you analyze their polynomial-time algorithm that decides if $G$ has an equitable tree-colouring, you'll notice that the degree of the polynomial depends on $k$. For example, in the proof of Theorem 11, there is a bound where $k$ appears in the exponent. Thus, it is not an FPT algorithm. Of course, it is widely believed (but not proved) that FPT $\neq$ W[1].

No. Fix $k \in \mathbb{N}$ and let $G$ be a graph of treewidth at most $k$. If you analyze their polynomial-time algorithm that decides if $G$ has an equitable tree-colouring, you'll notice that the degree of the polynomial depends on $k$. For example, in proof of Theorem 11, there is a bound where $k$ appears in the exponent. Thus, it is not an FPT algorithm. Of course, it is widely believed (but not proved) that FPT $\neq$ W[1].

No. Fix $k \in \mathbb{N}$ and let $G$ be a graph of treewidth at most $k$. If you analyze their polynomial-time algorithm that decides if $G$ has an equitable tree-colouring, you'll notice that the degree of the polynomial depends on $k$. For example, in the proof of Theorem 11, there is a bound where $k$ appears in the exponent. Thus, it is not an FPT algorithm. Of course, it is widely believed (but not proved) that FPT $\neq$ W[1].

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

No. Fix $k \in \mathbb{N}$ and let $G$ be a graph of treewidth at most $k$. If you analyze their polynomial-time algorithm that decides if $G$ has an equitable tree-colouring, you'll notice that the degree of the polynomial depends on $k$. For example, in proof of Theorem 11, there is a bound where $k$ appears in the exponent. Thus, it is not an FPT algorithm. Of course, it is widely believed (but not proved) that FPT $\neq$ W[1].