1
$\begingroup$

$k$-Dominating set:

Given a graph $G=(V,E)$ where $V$ is a set of vertices and $E$ a set of edges, and an integer $k$, the $k$-Dominating set problem determines if there exists a subset of vertices $V′$ of $V$ of size at most $k$, such that for every Vertex $u \in V$, there is an edge $uv \in E$ for some vertex $ v \in V'$.

It is easy to see $k$-Dominating set problem for planar graphs in $O(f(k)\log n)$ space.

Can we solve the $k$-Dominating set problem for planar graphs in $f(k)+c \log n$ space where $c$ is some constant.

Answer to this question is yes[link] Page 11 theorem 2.4.

Their proof based on the FPT algorithm for finding the $k$-Dominating set problem for planar graphs [link] page 11 theorem 2.4.

Can we get the simple proof or process for finding the $k$-Dominating set problem for planar graphs in $f(k)+c \log n$ space where $c$ is some constant?

$\endgroup$

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.