Mathematical Research Seminar

Given an undirected graph G=(V, E), two vertices s,t∈ V, and two integers k,l, the Short Secluded Path problem asks whether there exists an s-t path of length at most k with at most l neighbors. The "secluded" problems are motivated by finding structures with little interference, secure structures, or isolated structures. From a parameterized complexity perspective, the Short Secluded Path problem is W[1]-hard when parameterized by k or cliquewidth, while it is fixed-parameter tractable when parameterized by treewidth (how a graph is close to a tree structure). In this paper, we discuss the structural parameterization of the Short Secluded Path problem using dense graph parameters such as cliquewidth (a generalization of treewidth), twin cover number (a generalization of vertex cover; how a graph is close to disjoint union of cliques considering neighborhoods), and neighborhood diversity (how many neighborhood structures a graph has). We show that Short Secluded Path has an XP algorithm by cliquewidth, FPT algorithms by twin cover number and neighborhood diversity, respectively. Furthermore, we introduce the Short Secluded Path problem, which aims to find a shortest s-t path with the minimum number of neighbors. We show that this problem can be solved in polynomial time.