Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinding Disjoint Paths on Edge-Colored Graphs: More Tractability Results
169
0
0.0
(
0
)
Added by
Florian Sikora
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected $n$-vertex graph $G$, and a collection $mathcal{M}={(s_1,t_1),ldots,(s_k,t_k)}$ of pairs of its vertices, called source-destination, or demand, pairs. The goal is to route the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a simple greedy algorithm, whose approximation factor is $O(sqrt n)$, while the best current negative result is an $Omega(log^{1/2-delta}n)$-hardness of approximation for any constant $delta$, under standard complexity assumptions. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves an $tilde O(n^{1/4})$-approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is $tilde O(n^{9/19})$. The best currently known lower bound on the approximability of both the
It is conjectured that every edge-colored complete graph $G$ on $n$ vertices satisfying $Delta^{mon}(G)leq n-3k+1$ contains $k$ vertex-disjoint properly edge-colored cycles. We confirm this conjecture for $k=2$, prove several additional weaker results for general $k$, and we establish structural properties of possible minimum counterexamples to the conjecture. We also reveal a close relationship between properly edge-colored cycles in edge-colored complete graphs and directed cycles in multi-partite tournaments. Using this relationship and our results on edge-colored complete graphs, we obtain several partial solutions to a conjecture on disjoint cycles in directed graphs due to Bermond and Thomassen.
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.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
