How to survive while visiting a graph (Q1962049): Difference between revisions

Let \(G = (V, E)\) be a graph with \(n\) vertices, and let \(\sigma : V \rightarrow \{1, \ldots, n\}\) be a bijection. For \(1 \leq i \leq n\), the set \(E_i(\sigma)\) of edges accumulated by visit \(\sigma\) from step \(1\) to step \(i\) is the edge set of the subgraph induced by \(\{v \in V : \sigma(v) \leq i\}\). Given a vector \(d =(d_1, \ldots, d_{n-1})\), such a bijection \(\sigma\) is a strong \(d\)-visit of \(G\) if \(|E_{i+1}(\sigma) - E_i(\sigma)|\geq d_i\) for \(1\leq i\leq n\), and \(\sigma\) is a weak \(d\)-visit of \(G\) if \(|E_{i+1}(\sigma)|\geq \sum_{j=1}^i d_j\) for \(1\leq i\leq n\). The authors point out that the problem whether a graph admits a strong (resp. a weak) \(d\)-visit for a given vector \(d\) is NP-complete. For a given positive integer \(k\), if the vector \(d\) satisfies \(d_j=0\) \((1\leq j < k)\) and \(d_j=k\) \((k\leq i < n)\) then a strong/weak \(d\)-visit of \(G\) is also called strong/weak \(k\)-visit. Among others, the authors prove, given a graph \(G\) with \(n\) vertices, an integer \(k >0\), and a set of \(k\) vertices \(\{v_1, \dots, v_k\}\), that (1) there exists an \(O(n^2)\)-time algorithm that finds a strong \(k\)-visit \(\sigma\) of \(G\) with \(\sigma(v_i)=i\) \((1\leq i\leq k)\), if one exists, and returns a negative answer otherwise; in particular, a strong \(k\)-visit (if any at all) can be found in \(O(n^{k+2})\) time, and (2) deciding whether \(G\) admits or does not admit a weak \(k\)-visit \(\sigma\) with \(\sigma(v_i)=i\) \((1\leq i\leq k)\) is NP-complete.