Cheap and Secure Web Hosting Provider : See Now

[Solved]: Decomposing the search problem into several small problems

, , No Comments
Problem Detail: 

I am looking for papers/methods (or at least problem examples) where the original search problem $P$ can be solved by either:

  1. Searching through the original graph. or
  2. By decomposing it into several subset of problems $P_1,P_2, \dots,P_n$.

Ideally $sol(P )=sol(P_1)\cup sol(P_2)\cup \ldots \cup(P_n)$ with no preprocessing (i.e the union of the subproblems correspond directly to the solution of the problem).

I have no constraint; though prefer the underlying graph to be a DAG and the problem to be a reachability problem. Google seems to fail on finding such papers.

Asked By : seteropere

Answered By : Juho

Consider the $k$-path problem: given a graph $G$ and an integer $k$, is there a simple path of length $k$ in $G$? To solve $k$-path, it suffices to find two paths of length $k/2$ and a vertex $v$ s.t. the paths only intersect in $v$. In general, such algorithms are known as "meet in the middle", or "split and list". Basically, split the problem into two or more parts, enumerate all possible solutions for the smaller parts, and finally combine them to a solution.

Horowitz and Sahni give the classical example for subset-sum (given a list of $n$ integers, is there a sublist whose elements sum up to $0$?). First, split the list into two parts of length $n/2$. For both parts, enumerate all possible $2^{n/2}$ sums. Using sorting and binary search, check if there are two sublists that sum up to zero. In general, such an algorithm gives you a halved exponential dependence on the input size. There are some more examples of this too, for starters you could check out [1].

Also, to add to D.W.'s answer, divide-and-conquer also seems to satisfy your requirements. More specifically, look into graph decompositions. A classical one is the Lipton-Tarjan planar separator theorem, which leads to efficient divide-and-conquer algorithms on planar graphs. There are plenty of other separator theorems and decompositions out there too. One that you see often for directed graphs is a modular decomposition.

[1] Fomin, Fedor V., and Dieter Kratsch. Exact exponential algorithms. Springer, 2010.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback