Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinding All Useless Arcs in Directed Planar Graphs
114
0
0.0
(
0
)
Added by
Bundit Laekhanukit
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present a linear-time algorithm for simplifying flow networks on directed planar graphs: Given a directed planar graph on $n$ vertices, a source vertex $s$ and a sink vertex $t$, our algorithm removes all the arcs that do not participate in any simple $s,t$-path in linear-time. The output graph produced by our algorithm satisfies the prerequisite needed by the $O(nlog n)$-time algorithm of Weihe [FOCS94 & JCSS97] for computing maximum $s,t$-flow in directed planar graphs. Previously, Weihes algorithm could not run in $O(nlog n)$-time due to the absence of the preprocessing step; all the preceding algorithms run in $tilde{Omega}(n^2)$-time [Misiolek-Chen, COCOON05 & IPL06; Biedl, Brejov{{a}} and Vinar, MFCS00]. Consequently, this provides an alternative $O(nlog n)$-time algorithm for computing maximum $s,t$-flow in directed planar graphs in addition to the known $O(nlog n)$-time algorithms [Borradaile-Klein, SODA06 & J.ACM09; Erickson, SODA10]. Our algorithm can be seen as a (truly) linear-time $s,t$-flow sparsifier for directed planar graphs, which runs faster than any maximum $s,t$-flow algorithm (which can also be seen of as a sparsifier). The simplified structures of the resulting graph might be useful in future developments of maximum $s,t$-flow algorithms in both directed and undirected planar graphs.
rate research
Read More
A new efficient algorithm is presented for finding all simple cycles that satisfy a length constraint in a directed graph. When the number of vertices is non-trivial, most cycle-finding problems are of practical interest for sparse graphs only. We show that for a class of sparse graphs in which the vertex degrees are almost uniform, our algorithm can find all cycles of length less than or equal to $k$ in $O((c+n)(k-1)d^k)$ steps, where $n$ is the number of vertices, $c$ is the total number of cycles discovered, $d$ is the average degree of the graphs vertices, and $k > 1$. While our analysis for the running time addresses only a class of sparse graphs, we provide empirical and experimental evidence of the efficiency of the algorithm for general sparse graphs. This algorithm is a significant improvement over the only other deterministic algorithm for this problem known to us; it also lends itself to massive parallelism. Experimental results of a serial implementation on some large real-world graphs are presented.
The Minimum Path Cover problem on directed acyclic graphs (DAGs) is a classical problem that provides a clear and simple mathematical formulation for several applications in different areas and that has an efficient algorithmic solution. In this paper, we study the computational complexity of two constrained variants of Minimum Path Cover motivated by the recent introduction of next-generation sequencing technologies in bioinformatics. The first problem (MinPCRP), given a DAG and a set of pairs of vertices, asks for a minimum cardinality set of paths covering all the vertices such that both vertices of each pair belong to the same path. For this problem, we show that, while it is NP-hard to compute if there exists a solution consisting of at most three paths, it is possible to decide in polynomial time whether a solution consisting of at most two paths exists. The second problem (MaxRPSP), given a DAG and a set of pairs of vertices, asks for a path containing the maximum number of the given pairs of vertices. We show its NP-hardness and also its W[1]-hardness when parametrized by the number of covered pairs. On the positive side, we give a fixed-parameter algorithm when the parameter is the maximum overlapping degree, a natural parameter in the bioinformatics applications of the problem.
A directed graph $D$ is semicomplete if for every pair $x,y$ of vertices of $D,$ there is at least one arc between $x$ and $y.$ viol{Thus, a tournament is a semicomplete digraph.} In the Directed Component Order Connectivity (DCOC) problem, given a digraph $D=(V,A)$ and a pair of natural numbers $k$ and $ell$, we are to decide whether there is a subset $X$ of $V$ of size $k$ such that the largest strong connectivity component in $D-X$ has at most $ell$ vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for $ell=1.$ We study parametered complexity of DCOC for general and semicomplete digraphs with the following parameters: $k, ell,ell+k$ and $n-ell$. In particular, we prove that DCOC with parameter $k$ on semicomplete digraphs can be solved in time $O^*(2^{16k})$ but not in time $O^*(2^{o(k)})$ unless the Exponential Time Hypothesis (ETH) fails. gutin{The upper bound $O^*(2^{16k})$ implies the upper bound $O^*(2^{16(n-ell)})$ for the parameter $n-ell.$ We complement the latter by showing that there is no algorithm of time complexity $O^*(2^{o({n-ell})})$ unless ETH fails.} Finally, we improve viol{(in dependency on $ell$)} the upper bound of G{{o}}ke, Marx and Mnich (2019) for the time complexity of DCOC with parameter $ell+k$ on general digraphs from $O^*(2^{O(kelllog (kell))})$ to $O^*(2^{O(klog (kell))}).$ Note that Drange, Dregi and van t Hof (2016) proved that even for the undirected version of DCOC on split graphs there is no algorithm of running time $O^*(2^{o(klog ell)})$ unless ETH fails and it is a long-standing problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity $O^*(2^{o(klog k)}).$
The problem of finding paths in temporal graphs has been recently considered due to its many applications. In this paper we consider a variant of the problem that, given a vertex-colored temporal graph, asks for a path whose vertices have distinct colors and include the maximum number of colors. We study the approximation complexity of the problem and we provide an inapproximability lower bound. Then we present a heuristic for the problem and an experimental evaluation of our heuristic, both on synthetic and real-world graphs.
Given a directed graph $G = (V,E)$, undergoing an online sequence of edge deletions with $m$ edges in the initial version of $G$ and $n = |V|$, we consider the problem of maintaining all-pairs shortest paths (APSP) in $G$. Whilst this problem has been studied in a long line of research [ACM81, FOCS99, FOCS01, STOC02, STOC03, SWAT04, STOC13] and the problem of $(1+epsilon)$-approximate, weighted APSP was solved to near-optimal update time $tilde{O}(mn)$ by Bernstein [STOC13], the problem has mainly been studied in the context of oblivious adversaries, which assumes that the adversary fixes the update sequence before the algorithm is started. In this paper, we make significant progress on the problem in the setting where the adversary is adaptive, i.e. can base the update sequence on the output of the data structure queries. We present three new data structures that fit different settings: We first present a deterministic data structure that maintains exact distances with total update time $tilde{O}(n^3)$. We also present a deterministic data structure that maintains $(1+epsilon)$-approximate distance estimates with total update time $tilde O(sqrt{m} n^2/epsilon)$ which for sparse graphs is $tilde O(n^{2+1/2}/epsilon)$. Finally, we present a randomized $(1+epsilon)$-approximate data structure which works against an adaptive adversary; its total update time is $tilde O(m^{2/3}n^{5/3} + n^{8/3}/(m^{1/3}epsilon^2))$ which for sparse graphs is $tilde O(n^{2+1/3})$. Our exact data structure matches the total update time of the best randomized data structure by Baswana et al. [STOC02] and maintains the distance matrix in near-optimal time. Our approximate data structures improve upon the best data structures against an adaptive adversary which have $tilde{O}(mn^2)$ total update time [JACM81, STOC03].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
