Exact algorithms based on specific complexity measures for hard problems

At present, most of the important computational problems - be they decision, search, or optimization problems - are known to satisfy one of the following two criteria:(1) The problem can be solved in polynomial time with respect to the input size n, where the degree of the polynomial is small enough to guarantee that the problem can be tackled efficiently in practice. In particular, the decision version of the problem is in P. Typical time complexities are O(n log n) and O(n^k), k < 4.(2) The problem is NP-hard, and its decision version is NP-complete. We do not know whether the problem can be solved in polynomial time, but it is complex enough to express every other NP-complete problem via polynomial-time transformations. A typical time complexity for this case is O(c^n) with c > 1.1.Under the widely accepted assumption that P does not equal NP, exact algorithms for problems of the second variety inevitably take superpolynomial time (not necessarily for every input, but in the worst case). In terms of worst-case behavior, it is easy to see that the respective algorithms can be infeasible even for instances of moderate size. The thesis at hand addresses this intricacy by combining two concepts, one of which is a well-known paradigm and the other one of which is an analytical tool that has only been used less explicitly in earlier scholarship. Firstly, we consider the parameterized complexity of hard graph problems. In particular, we design and analyze parameterized algorithms, i.e., algorithms whose running times are typically exponential in some parameter of the input (such as the desired size of the solution), but only polynomial in the size of the input. Secondly, we employ problem-specific complexity measures: we identify quantities whose smallness can be exploited in order to solve the problem more efficiently, then prove that they are small in any case, or that they can be made small using bounded additional effort. Such complexity measures are not to be confused with parameters for several reasons. Most importantly, we derive runtime bounds that are functions in the parameter k and the input size n, not in the complexity measure. The term smallness is also used in varied interpretations - for most of the aforementioned problems, we even investigate complexity measures that can be exponentially large in k and thus greater than n. Although the focus of this thesis clearly lies on the theoretical part, we complement the mathematical analysis of the algorithms with case studies and practical experiments. In one case, we exemplify how a theoretical algorithm (i.e., an algorithm tailored to the mathematical analysis) can be implemented and optimized for use in real-world applications.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2007

Author dc:creator

• Mölle, Daniel

Contributors dc:contributor

• Rossmanith, Peter

• info:eu-repo/classification/ddc/004
• Parametrisierte Komplexität
• Informatik
• Exakte Algorithmen
• Parametrisierte Algorithmen
• Exact algorithms
• Parameterized algorithms

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124103%22

OAI identifier oai:identifier

oai:publications.rwth-aachen.de:62539