Technical Report MSC-2013-26

Title: Parameterizing P: Proximity to Easy Variants
Authors: David Wajc
Supervisors: Nir Ailon, Seffi Naor, Hadas Shachnai
Abstract: The field of parameterized complexity strives to solve intractable problems efficiently, via multivariate analysis of running time, as a function of both the input size n and a parameter k. Such analysis enables to show that some of these problems are fixed parameter tractable (FPT); in other words, they can be solved in time f(k)n^O(1). The rationale behind this approach is the observation that many real-life inputs have small parameter values.

In this work we study multivariate analysis of running time for problems in P, to obtain faster algorithms for these problems. In particular, we (i) present a framework for faster solutions for myriad shortest path problems, and (ii) develop faster algorithms for maximum weight matching. We parameterize the studied problems by k, the number of vertices that need to be removed to obtain a graph from an easier input class.

Our algorithms achieve the same running times as algorithms for the easier input class for fi xed values of k, and signi cantly better than the best known algorithms for a wide range of values of k. For example, we solve the single source shortest path problem for graphs with n vertices and m edges having k vertices with outgoing negative-weight edges in O(k(m + n log n) + k^3) time. This running time is no slower than the state-of-the-art O(mn) ballpark for dense graphs (graphs with m = Omega(n^2) edges) and all values of k, and improves upon this bound for any k<<n. Our results imply that any proof of lower bounds for the time required to solve these problems must assume high parameter values.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2013
To the main CS technical reports page

Computer science department, Technion