Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAlternative parameterizations of Metric Dimension
201
0
0.0
(
0
)
Added by
Gregory Gutin
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A set of vertices $W$ in a graph $G$ is called resolving if for any two distinct $x,yin V(G)$, there is $vin W$ such that ${rm dist}_G(v,x) eq{rm dist}_G(v,y)$, where ${rm dist}_G(u,v)$ denotes the length of a shortest path between $u$ and $v$ in the graph $G$. The metric dimension ${rm md}(G)$ of $G$ is the minimum cardinality of a resolving set. The Metric Dimension problem, i.e. deciding whether ${rm md}(G)le k$, is NP-complete even for interval graphs (Foucaud et al., 2017). We study Metric Dimension (for arbitrary graphs) from the lens of parameterized complexity. The problem parameterized by $k$ was proved to be $W[2]$-hard by Hartung and Nichterlein (2013) and we study the dual parameterization, i.e., the problem of whether ${rm md}(G)le n- k,$ where $n$ is the order of $G$. We prove that the dual parameterization admits (a) a kernel with at most $3k^4$ vertices and (b) an algorithm of runtime $O^*(4^{k+o(k)}).$ Hartung and Nichterlein (2013) also observed that Metric Dimension is fixed-parameter tractable when parameterized by the vertex cover number $vc(G)$ of the input graph. We complement this observation by showing that it does not admit a polynomial kernel even when parameterized by $vc(G) + k$. Our reduction also gives evidence for non-existence of polynomial Turing kernels.
rate research
Read More
It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most $k$ vertices whose deletion results in a chordal graph, when parameterized by $k$. While this investigation fits naturally into the recent trend of what are called `structural parameterizations, here we assume that the deletion set is not given. One method to solve them is to compute a $k$-sized or an approximate ($f(k)$ sized, for a function $f$) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least $k^{mathcal{O}(k)}n^{mathcal{O}(1)}$ running time when we use the known parameterized or approximation algorithms for finding a $k$-sized chordal deletion set on an $n$ vertex graph. In this work, we design $2^{mathcal{O}(k)}n^{mathcal{O}(1)}$ time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in time $2^{mathcal{O}(k)}n^{mathcal{O}(1)}$ where each bag is a union of four cliques and $mathcal{O}(k)$ vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest. Our algorithms are adaptive (robust) in the sense that given an integer $k$, they detect whether the graph has a chordal vertex deletion set of size at most $k$ or output the special tree decomposition and solve the problem. We also show lower bounds for the problems we deal with under the Strong Exponential Time Hypothesis (SETH).
In this paper we revisit the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our focus lies on structural parameterizations for the problem that allow for efficient (polynomial-time or fpt) algorithms. As our first result, we answer an open question stated in Fleszar, Mnich, and Spoerhase (2016), by showing that the problem can be solved in polynomial time if the input graph has a feedback vertex set of size one. We also show that EDP parameterized by the treewidth and the maximum degree of the input graph is fixed-parameter tractable. Having developed two novel algorithms for EDP using structural restrictions on the input graph, we then turn our attention towards the augmented graph, i.e., the graph obtained from the input graph after adding one edge between every terminal pair. In constrast to the input graph, where EDP is known to remain NP-hard even for treewidth two, a result by Zhou et al. (2000) shows that EDP can be solved in non-uniform polynomial time if the augmented graph has constant treewidth; we note that the possible improvement of this result to an fpt-algorithm has remained open since then. We show that this is highly unlikely by establishing the W[1]-hardness of the problem parameterized by the treewidth (and even feedback vertex set) of the augmented graph. Finally, we develop an fpt-algorithm for EDP by exploiting a novel structural parameter of the augmented graph.
In the Maximum Common Induced Subgraph problem (henceforth MCIS), given two graphs $G_1$ and $G_2$, one looks for a graph with the maximum number of vertices being both an induced subgraph of $G_1$ and $G_2$. MCIS is among the most studied classical NP-hard problems. It remains NP-hard on many graph classes including forests. In this paper, we study the parameterized complexity of MCIS. As a generalization of textsc{Clique}, it is W[1]-hard parameterized by the size of the solution. Being NP-hard even on forests, most structural parameterizations are intractable. One has to go as far as parameterizing by the size of the minimum vertex cover to get some tractability. Indeed, when parameterized by $k := text{vc}(G_1)+text{vc}(G_2)$ the sum of the vertex cover number of the two input graphs, the problem was shown to be fixed-parameter tractable, with an algorithm running in time $2^{O(k log k)}$. We complement this result by showing that, unless the ETH fails, it cannot be solved in time $2^{o(k log k)}$. This kind of tight lower bound has been shown for a few problems and parameters but, to the best of our knowledge, not for the vertex cover number. We also show that MCIS does not have a polynomial kernel when parameterized by $k$, unless $NP subseteq mathsf{coNP}/poly$. Finally, we study MCIS and its connected variant MCCIS on some special graph classes and with respect to other structural parameters.
In this article, the author proposes another way to define the completion of a metric space, which is different from the classical one via the dense property, and prove the equivalence between two definitions. This definition is based on considerations from category theory, and can be generalized to arbitrary categories.
A fundamental problem in computational biology is the construction of phylogenetic trees, also called evolutionary trees, for a set of organisms. A graph-theoretic approach takes as input a similarity graph $G$ on the set of organisms, with adjacency denoting evolutionary closeness, and asks for a tree $T$ whose leaves are the set of organisms, with two vertices adjacent in $G$ if and only if the distance between them in the tree is less than some specified distance bound. If this exists $G$ is called a leaf power. Over 20 years ago, [Nishimura et al., J. Algorithms, 2002] posed the question if leaf powers could be recognized in polynomial time. In this paper we explore this still unanswered question from the perspective of two alternative models of leaf powers that have been rather overlooked. These models do not rely on a variable distance bound and are therefore more apt for generalization. Our first result concerns leaf powers with a linear structure and uses a model where the edges of the tree $T$ are weighted by rationals between 0 and 1, and the distance bound is fixed to 1. We show that the graphs having such a model with $T$ a caterpillar are exactly the co-threshold tolerance graphs and can therefore be recognized in $O(n^2)$ time by an algorithm of [Golovach et al., Discret. Appl. Math., 2017]. Our second result concerns leaf powers with a star structure and concerns the geometric NeS model used by [Brandstadt et al., Discret. Math., 2010]. We show that the graphs having a NeS model where the main embedding tree is a star can be recognized in polynomial time. These results pave the way for an attack on the main question, to settle the issue if leaf powers can be recognized in polynomial time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
