On the Feasibility of Maintenance Algorithms in Dynamic Graphs

Details On the Feasibility of Maintenance Algorithms in Dynamic Graphs On the Feasibility of Maintenance Algorithms in Dynamic Graphs

2011-07-14

arxiv.org/abs/1107.2722v4

Computer Science

Computational Complexity

Scientific paper

Near ubiquitous mobile computing has led to intense interest in dynamic graph theory. This provides a new and challenging setting for algorithmics and complexity theory. For any graph-based problem, the rapid evolution of a (possibly disconnected) graph over time naturally leads to the important complexity question: is it better to calculate a new solution from scratch or to adapt the known solution on the prior graph to quickly provide a solution of guaranteed quality for the changed graph? In this paper, we demonstrate that the former is the best approach in some cases, but that there are cases where the latter is feasible. We prove that, under certain conditions, hard problems cannot even be approximated in any reasonable complexity bound --- i.e., even with a large amount of time, having a solution to a very similar graph does not help in computing a solution to the current graph. To achieve this, we formalize the idea as a maintenance algorithm. Using r-Regular Subgraph as the primary example we show that W[1]-hardness for the parameterized approximation problem implies the non-existence of a maintenance algorithm for the given approximation ratio. Conversely we show that Vertex Cover, which is fixed-parameter tractable, has a 2-approximate maintenance algorithm. The implications of NP-hardness and NPO-hardness are also explored.

Affiliated with

Also associated with

No associations

Rating

On the Feasibility of Maintenance Algorithms in Dynamic Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Feasibility of Maintenance Algorithms in Dynamic Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Feasibility of Maintenance Algorithms in Dynamic Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-224733