Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in k^2 and Linear in n

11/07/2022
∙
by   Kyungjin Cho, et al.
∙
0
∙

In this paper, we study the problem: Given an undirected planar graph G with n vertices and a set T of k pairs (s_i,t_i)_i=1^k of vertices, the goal is to find a set 𝒫 of k pairwise vertex-disjoint paths connecting s_i and t_i for all indices i∈{1,…,k}. We present a 2^O(k^2)n-time algorithm for the problem. This improves the two previously best-known algorithms: 2^2^O(k)n-time algorithm [Discrete Applied Mathematics 1995] and 2^O(k^2)n^6-time algorithm [STOC 2020].

READ FULL TEXT

Please sign up or login with your details

Continue with:
Or login with email
Enter Password
Re-enter Password

Forgot password? Click here to reset
Success!
Error Icon An error occurred

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×
Pro

Consider DeepAI Pro

Subscribe to DeepAI Pro
DeepAI Pro
Provides a limited generation allowance each month. When exceeded, you are charged overage rates available at deepai.org/pricing. Also includes an ad-free experience and API access. Renews automatically until canceled. Non-refundable.
Subtotal
Total due today

Payment

Add DeepAI credits
DeepAI credits
One-time purchase. Credits are added to your wallet after payment.
Subtotal
Total due today

Payment