Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the complexity of finding internally vertex-disjoint long directed paths
98
0
0.0
(
0
)
Added by
Ignasi Sau
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
For two positive integers $k$ and $ell$, a $(k times ell)$-spindle is the union of $k$ pairwise internally vertex-disjoint directed paths with $ell$ arcs between two vertices $u$ and $v$. We are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems. We obtain the following complexity dichotomy: for a fixed $ell geq 1$, finding the largest $k$ such that an input digraph $G$ contains a subdivision of a $(k times ell)$-spindle is polynomial-time solvable if $ell leq 3$, and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and present several algorithmic and hardness results.
rate research
Read More
The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph (called MaxCDP) has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate how the complexity of the problem depends on graph parameters (namely the number of vertices to remove to make the graph a collection of disjoint paths and the size of the vertex cover of the graph), which makes sense since graphs in social networks are not random and have structure. The problem was known to be hard to approximate in polynomial time and not fixed-parameter tractable (FPT) for the natural parameter. Here, we show that it is still hard to approximate, even in FPT-time. Finally, we introduce a new variant of the problem, called MaxCDDP, whose goal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of MaxCDP to this new variant, and we prove that unlike MaxCDP, MaxCDDP is already hard on graphs at distance two from disjoint paths.
Paths $P_1,ldots,P_k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P_i$ and $P_j$ have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to decide if a graph $G$ with $k$ pairs of specified vertices $(s_i,t_i)$ contains $k$ mutually induced paths $P_i$ such that each $P_i$ connects $s_i$ and $t_i$. This is a classical graph problem that is NP-complete even for $k=2$. We study it for AT-free graphs. Unlike its subclasses of permutation graphs and cocomparability graphs, the class of AT-free graphs has no geometric intersection model. However, by a new, structural analysis of the behaviour of Induced Disjoint Paths for AT-free graphs, we prove that it can be solved in polynomial time for AT-free graphs even when $k$ is part of the input. This is in contrast to the situation for other well-known graph classes, such as planar graphs, claw-free graphs, or more recently, (theta,wheel)-free graphs, for which such a result only holds if $k$ is fixed. As a consequence of our main result, the problem of deciding if a given AT-free graph contains a fixed graph $H$ as an induced topological minor admits a polynomial-time algorithm. In addition, we show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard with parameter $|V_H|$, even on a subclass of AT-free graph, namely cobipartite graphs. We also show that the problems $k$-in-a-Path and $k$-in-a-Tree are polynomial-time solvable on AT-free graphs even if $k$ is part of the input. These problems are to test if a graph has an induced path or induced tree, respectively, spanning $k$ given vertices.
The canonical tree-decomposition theorem, given by Robertson and Seymour in their seminal graph minors series, turns out to be one of the most important tool in structural and algorithmic graph theory. In this paper, we provide the canonical tree decomposition theorem for digraphs. More precisely, we construct directed tree-decompositions of digraphs that distinguish all their tangles of order $k$, for any fixed integer $k$, in polynomial time. As an application of this canonical tree-decomposition theorem, we provide the following result for the directed disjoint paths problem: For every fixed $k$ there is a polynomial-time algorithm which, on input $G$, and source and terminal vertices $(s_1, t_1), dots, (s_k, t_k)$, either 1. determines that there is no set of pairwise vertex-disjoint paths connecting each source $s_i$ to its terminal $t_i$, or 2.finds a half-integral solution, i.e., outputs paths $P_1, dots, P_k$ such that $P_i$ links $s_i$ to $t_i$, so that every vertex of the graph is contained in at most two paths. Given known hardness results for the directed disjoint paths problem, our result cannot be improved for general digraphs, neither to fixed-parameter tractability nor to fully vertex-disjoint directed paths. As far as we are aware, this is the first time to obtain a tractable result for the $k$-disjoint paths problem for general digraphs. We expect more applications of our canonical tree-decomposition for directed results.
We investigate the parameterized complexity of finding subgraphs with hereditary properties on graphs belonging to a hereditary graph class. Given a graph $G$, a non-trivial hereditary property $Pi$ and an integer parameter $k$, the general problem $P(G,Pi,k)$ asks whether there exists $k$ vertices of $G$ that induce a subgraph satisfying property $Pi$. This problem, $P(G,Pi,k)$ has been proved to be NP-complete by Lewis and Yannakakis. The parameterized complexity of this problem is shown to be W[1]-complete by Khot and Raman, if $Pi$ includes all trivial graphs but not all complete graphs and vice versa; and is fixed-parameter tractable (FPT), otherwise. As the problem is W[1]-complete on general graphs when $Pi$ includes all trivial graphs but not all complete graphs and vice versa, it is natural to further investigate the problem on restricted graph classes. Motivated by this line of research, we study the problem on graphs which also belong to a hereditary graph class and establish a framework which settles the parameterized complexity of the problem for various hereditary graph classes. In particular, we show that: $P(G,Pi,k)$ is solvable in polynomial time when the graph $G$ is co-bipartite and $Pi$ is the property of being planar, bipartite or triangle-free (or vice-versa). $P(G,Pi,k)$ is FPT when the graph $G$ is planar, bipartite or triangle-free and $Pi$ is the property of being planar, bipartite or triangle-free, or graph $G$ is co-bipartite and $Pi$ is the property of being co-bipartite. $P(G,Pi,k)$ is W[1]-complete when the graph $G$ is $C_4$-free, $K_{1,4}$-free or a unit disk graph and $Pi$ is the property of being either planar or bipartite.
We introduce the combinatorial optimization problem Time Disjoint Walks (TDW), which has applications in collision-free routing of discrete objects (e.g., autonomous vehicles) over a network. This problem takes as input a digraph $G$ with positive integer arc lengths, and $k$ pairs of vertices that each represent a trip demand from a source to a destination. The goal is to find a walk and delay for each demand so that no two trips occupy the same vertex at the same time, and so that a min-max or min-sum objective over the trip durations is realized. We focus here on the min-sum variant of Time Disjoint Walks, although most of our results carry over to the min-max case. We restrict our study to various subclasses of DAGs, and observe that there is a sharp complexity boundary between Time Disjoint Walks on oriented stars and on oriented stars with the central vertex replaced by a path. In particular, we present a poly-time algorithm for min-sum and min-max TDW on the former, but show that min-sum TDW on the latter is NP-hard. Our main hardness result is that for DAGs with max degree $Deltaleq3$, min-sum Time Disjoint Walks is APX-hard. We present a natural approximation algorithm for the same class, and provide a tight analysis. In particular, we prove that it achieves an approximation ratio of $Theta(k/log k)$ on bounded-degree DAGs, and $Theta(k)$ on DAGs and bounded-degree digraphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
