Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userReachability and Matching in Single Crossing Minor Free Graphs
63
0
0.0
(
0
)
Added by
Rahul Jain
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We show that for each single crossing graph $H$, a polynomially bounded weight function for all $H$-minor free graphs $G$ can be constructed in Logspace such that it gives nonzero weights to all the cycles in $G$. This class of graphs subsumes almost all classes of graphs for which such a weight function is known to be constructed in Logspace. As a consequence, we obtain that for the class of $H$-minor free graphs where $H$ is a single crossing graph, reachability can be solved in UL, and bipartite maximum matching can be solved in SPL, which are small subclasses of the parallel complexity class NC. In the restrictive case of bipartite graphs, our maximum matching result improves upon the recent result of Eppstein and Vazirani, where they show an NC bound for constructing perfect matching in general single crossing minor free graphs.
rate research
Read More
Temporal graphs (in which edges are active at specified times) are of particular relevance for spreading processes on graphs, e.g.~the spread of disease or dissemination of information. Motivated by real-world applications, modification of static graphs to control this spread has proven a rich topic for previous research. Here, we introduce a new type of modification for temporal graphs: the number of active times for each edge is fixed, but we can change the relative order in which (sets of) edges are active. We investigate the problem of determining an ordering of edges that minimises the maximum number of vertices reachable from any single starting vertex; epidemiologically, this corresponds to the worst-case number of vertices infected in a single disease outbreak. We study t
The problem of graph Reachability is to decide whether there is a path from one vertex to another in a given graph. In this paper, we study the Reachability problem on three distinct graph families - intersection graphs of Jordan regions, unit contact disk graphs (penny graphs), and chordal graphs. For each of these graph families, we present space-efficient algorithms for the Reachability problem. For intersection graphs of Jordan regions, we show how to obtain a good vertex separator in a space-efficient manner and use it to solve the Reachability in polynomial time and $O(m^{1/2}log n)$ space, where $n$ is the number of Jordan regions, and $m$ is the total number of crossings among the regions. We use a similar approach for chordal graphs and obtain a polynomial-time and $O(m^{1/2}log n)$ space algorithm, where $n$ and $m$ are the number of vertices and edges, respectively. However, we use a more involved technique for unit contact disk graphs (penny graphs) and obtain a better algorithm. We show that for every $epsilon> 0$, there exists a polynomial-time algorithm that can solve Reachability in an $n$ vertex directed penny graph, using $O(n^{1/4+epsilon})$ space. We note that the method used to solve penny graphs does not extend naturally to the class of geometric intersection graphs that include arbitrary size cliques.
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.
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.
A graph drawn in the plane with n vertices is k-fan-crossing free for k > 1 if there are no k+1 edges $g,e_1,...e_k$, such that $e_1,e_2,...e_k$ have a common endpoint and $g$ crosses all $e_i$. We prove a tight bound of 4n-8 on the maximum number of edges of a 2-fan-crossing free graph, and a tight 4n-9 bound for a straight-edge drawing. For k > 2, we prove an upper bound of 3(k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
