论文标题
通过反馈顶点集和其他结构参数参数化的度量维度参数
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
论文作者
论文摘要
对于图$ g $，如果对于任何两个顶点$ u，in v（g）$，则称为a \ emph {nesolving set}的子集$ s \ subseteq v（g）$，存在$ d（w，w，u）\ neq d（w，w，v，v，v）$。 {\ sc公制尺寸}问题将图形$ g $和一个正整数$ k $作为输入，并询问是否存在最多$ k $的解决方案集。这个问题是在1970年代引入的，被称为\ np-hard〜 [Garey和Johnson的书中的Gt〜61]。在参数化的复杂性领域中，Hartung和Nichterlein〜 [CCC〜2013]证明，当由自然参数$ k $参数化时，问题是\ w [2] - hard。他们还观察到，当由顶点封面编号参数化时，它是\ fpt \，并询问其在\ emph {small}参数下的复杂性，尤其是反馈顶点集号码。我们通过证明{\ sc公制尺寸}是\ w [1] - hard时，我们回答了这个问题，当由组合参数反馈顶点设置数字和路径宽时进行参数化时。这也改善了引擎盖和purohit〜 [ipec 2019]的结果，该结果指出问题是\ w [1] - hard通过路径进行参数化。在正面，我们证明{\ sc公制维度}是\ fpt \当通过群集或群集距离的距离进行参数时，这两个参数都比顶点封面号小。
For a graph $G$, a subset $S \subseteq V(G)$ is called a \emph{resolving set} if for any two vertices $u,v \in V(G)$, there exists a vertex $w \in S$ such that $d(w,u) \neq d(w,v)$. The {\sc Metric Dimension} problem takes as input a graph $G$ and a positive integer $k$, and asks whether there exists a resolving set of size at most $k$. This problem was introduced in the 1970s and is known to be \NP-hard~[GT~61 in Garey and Johnson's book]. In the realm of parameterized complexity, Hartung and Nichterlein~[CCC~2013] proved that the problem is \W[2]-hard when parameterized by the natural parameter $k$. They also observed that it is \FPT\ when parameterized by the vertex cover number and asked about its complexity under \emph{smaller} parameters, in particular the feedback vertex set number. We answer this question by proving that {\sc Metric Dimension} is \W[1]-hard when parameterized by the combined parameter feedback vertex set number plus pathwidth. This also improves the result of Bonnet and Purohit~[IPEC 2019] which states that the problem is \W[1]-hard parameterized by the pathwidth. On the positive side, we show that {\sc Metric Dimension} is \FPT\ when parameterized by either the distance to cluster or the distance to co-cluster, both of which are smaller parameters than the vertex cover number.
