Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userElimination Distance to Topological-minor-free Graphs is FPT
327
0
0.0
(
0
)
Added by
Fahad Panolan
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most $k$ to any minor-closed class of graphs is fixed-parameter tractable parameterized by $k$ [Algorithmica, 2017]. There has been a subsequent series of results on the fixed-parameter tractability of elimination distance to various graph classes. However, one class of graph classes to which the computation of elimination distance has remained open is the class of graphs that are characterized by the exclusion of a family ${cal F}$ of finite graphs as topological minors. In this paper, we settle this question by showing that the problem of determining elimination distance to such graphs is also fixed-parameter tractable.
rate research
Read More
A (1 + eps)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing time. There are strong distance-oracle constructions known for planar graphs (Thorup, JACM04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC06). However, these require Omega(eps^{-1} n lg n) space for n-node graphs. We argue that a very low space requirement is essential. Since modern computer architectures involve hierarchical memory (caches, primary memory, secondary memory), a high memory requirement in effect may greatly increase the actual running time. Moreover, we would like data structures that can be deployed on small mobile devices, such as handhelds, which have relatively small primary memory. In this paper, for planar graphs, bounded-genus graphs, and minor-excluded graphs we give distance-oracle constructions that require only O(n) space. The big O hides only a fixed constant, independent of epsilon and independent of genus or size of an excluded minor. The preprocessing times for our distance oracle are also faster than those for the previously known constructions. For planar graphs, the preprocessing time is O(n lg^2 n). However, our constructions have slower query times. For planar graphs, the query time is O(eps^{-2} lg^2 n). For our linear-space results, we can in fact ensure, for any delta > 0, that the space required is only 1 + delta times the space required just to represent the graph itself.
The class of even-hole-free graphs is very similar to the class of perfect graphs, and was indeed a cornerstone in the tools leading to the proof of the Strong Perfect Graph Theorem. However, the complexity of computing a maximum independent set (MIS) is a long-standing open question in even-hole-free graphs. From the hardness point of view, MIS is W[1]-hard in the class of graphs without induced 4-cycle (when parameterized by the solution size). Halfway of these, we show in this paper that MIS is FPT when parameterized by the solution size in the class of even-hole-free graphs. The main idea is to apply twice the well-known technique of augmenting graphs to extend some initial independent set.
Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a small-complexity graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics: 1. Construction of a light subset spanner. Given a subset of vertices called terminals, and $epsilon$, in polynomial time we construct a subgraph that preserves all pairwise distances between terminals up to a multiplicative $1+epsilon$ factor, of total weight at most $O_{epsilon}(1)$ times the weight of the minimal Steiner tree spanning the terminals. 2. Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion $epsilon D$. Namely, given a minor free graph $G=(V,E,w)$ of diameter $D$, and parameter $epsilon$, we construct a distribution $mathcal{D}$ over dominating metric embeddings into treewidth-$O_{epsilon}(log n)$ graphs such that the additive distortion is at most $epsilon D$. One of our important technical contributions is a novel framework that allows us to reduce emph{both problems} to problems on simpler graphs of bounded diameter. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for vehicle routing with bounded capacity in minor-free metrics; (3) the first efficient approximation scheme for vehicle routing with bounded capacity on bounded genus metrics.
We show that the k-Dominating Set problem is fixed parameter tractable (FPT) and has a polynomial kernel for any class of graphs that exclude K_{i,j} as a subgraph, for any fixed i, j >= 1. This strictly includes every class of graphs for which this problem has been previously shown to have FPT algorithms and/or polynomial kernels. In particular, our result implies that the problem restricted to bounded- degenerate graphs has a polynomial kernel, solving an open problem posed by Alon and Gutner.
A classical problem in comparative genomics is to compute the rearrangement distance, that is the minimum number of large-scale rearrangements required to transform a given genome into another given genome. While the most traditional approaches in this area are family-based, i.e., require the classification of DNA fragments into families, more recently an alternative family-free approach was proposed, and consists of studying the rearrangement distances without prior family assignment. On the one hand the computation of genomic distances in the family-free setting helps to match occurrences of duplicated genes and find homologies, but on the other hand this computation is NP-hard. In this paper, by letting structural rearrangements be represented by the generic double cut and join (DCJ) operation and also allowing insertions and deletions of DNA segments, we propose a new and more general family-free genomic distance, providing an efficient ILP formulation to solve it. Our experiments show that the ILP produces accurate results and can handle not only bacterial genomes, but also fungi and insects, or subsets of chromosomes of mammals and plants.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
