Computer Science 6743, Winter '10
Guest Lectures (Wareham)

---

Copyright 2010 by H.T. Wareham
All rights reserved

---

Tuesday, March 2 (Lecture #1)

• Overview: Computational Complexity and (In)tractability
  (or: You Can't Always Get What You Want (But Sometimes You Get What You Need))
  • Relative to a particular type of algorithm, a problem P is (in)tractable if there is (not) an algorithm of that type for P.
  • Computational complexity techniques can be used to assess (in)tractability of computational problems. Requires the following 4 components:
    • Description of problems of interest (implicit in this is class U, which is the set of problems)
    • Description of tractable-algorithm type (implicit in this is class T, which is the set of tractable problems).
    • A reducibility on pairs of problems in U that preserves tractability, i.e., a reducibility such that the following two properties hold:
      • If P reduces to Q and Q is in T then P is in T.
      • If P reduces to Q and Q reduces to R them P reduces to R.

      Any such reducibility by definition (in particular, by the first property above) also has the following third property:

      • If P reduces to Q and P is not in T (modulo conjecture X) then Q is not in T (modulo conjecture X).

    • A subset C of U such that T is a (proper) subset of C.

  • Recall that relative to a class C, a problem P is C-hard if every problem in C reduces to P; if P is also in C then P is C-complete.
  • Relative to the framework above, can use C-hardness to show that a problem P is not in T and hence not tractable (possibly modulo some conjecture X)!
  • Example: Theory of NP-completeness
    • Relative to the framework above, U = decision problems, T = P (the class of all decision problems solvable in deterministic polynomial time), the reducibility is polynomial-time many-one reducibility, and C = NP (the class of all decision problems whose candidate solutions can be verified in nondeterministic polynomial time).
    • As NP is only known to contain (rather than properly contain) P, an NP-hardness result for a problem only implies polynomial-intractability if P != NP.
  • Have to read the fine print for any intractability result for a problem P; P may in fact be tractable under different but nonetheless acceptable forms of tractability.
  • Example: What an NP-hardness result really means:

    if a problem is NP-hard
    then there is no deterministic algorithm
    
    that gives optimal solutions
    for all instances of the problem
    in polynomial time
    unless P = NP.

    An NP-hard problem may still have usable algorithms that violate one or more of the italicized clauses above, e.g., polynomial-time randomized optimal-solution algorithms, polynomial-time deterministic approximate-solution algorithms, exponential-time deterministic optimal-solution algorithms that are effectively polynomial-time for problem instances of interest.
    • Over the next three lectures, we'll look at two kinds of tractability that may be options for NP-hard problems -- namely, value / structure approximability and fixed-parameter tractability.
• Value / Structure Approximability
  • Motivation
  • Our universe U will be the set of all optimization problems.
  • Definition: Optimization problem [ACG+99, Definition 1.1.6]
  • Tractability phrased in terms of particular types of approximation algorithms.
  • Definition: Approximation algorithm [ACG+99, Definition 3.1]
  • Two types of approximation criteria: solution value and solution structure
  • Value Approximability ([ACG+99] and references; see also [GJ79, Chapter 6; Gon07; HS78, Chapter 12; Vaz03])
    • Motivation
    • Our approximability criterion is the closeness of the value of the approximation-algorithm solution to optimal-solution value.
    • Definition: Additive approximation (v-a-approx) [ACG+99, Definition 3.3]
    • Definition: Ratio approximation (v-r-approx) [ACG+99, Definition 3.7]
    • Definition: Polynomial-time approximation scheme (PTAS) [ACG+99, Definition 3.10]
    • Definition: Fully polynomial-time approximation scheme (FPTAS) [ACG+99, Definition 3.12]
    • Can prove v-approximability by giving an algorithm with the appropriate properties.
    • Example: Min Coloring for Planar Graphs is 3 v-a-approximable [ACG+99, Example 3.1]
    • Example: Min Vertex Cover is 2 v-r-approximable [CLRS01, Theorem 35.1]
    • Prior to the late 1980's, most proofs of v-inapproximability were done on a problem-by-problem basis.
    • Example: Max Clique is not c v-a-approximable for any constant c > 0 unless P = NP [ACG+99, p. 89]
    • In the next lecture, we will look at the two class-based frameworks for proving v-inapproximability.

Thursday, March 4 (Lecture #2)

• Value / Structure Approximability (Cont'd)
  • Value Approximability (Cont'd)
    • General v-inapproximability: v-approximability class hardness/-completeness
      • v-approximability tractability classes: FPTAS, PTAS, APX, NPO ([CP91]; see also [ACG+99, Section 3]) (note absence of v-a-approx class)
      • There is also a reducibility that preserves v-r-approximability (and hence PTAS and FPTAS qapproximability as well).
      • Definition: L-reduction [PY91, p. 427]
      • Theorem: FPTAS is properly contained in PTAS is properly contained in APX is properly contained in NPO unless P = NP ([CP91, Theorem 6]; see also [ACG+99, Section 3])
      • Complete problems relative to L-reducibility are known for classes APX and NPO (see [ACG+99, Section 8] and references).
    • Short-cut to PTAS inapproximability: MAX SNP-hardness
      • Class MAX SNP is a class of optimization problems whose optimal solutions can be described by a particular type of logic formula. Every problem in this class can be v-r-approximated within a fixed ratio [PY91, Theorem 1].
      • [PY91] gave a number of MAX SNP-complete problems and, given the above, noted that if any such problem had a PTAS, all problems in MAX SNP had a PTAS. However, the converse was shown the following year, when [ALM+92] showed that a particular MAX SNP-complete problem (Max 3SAT) could not have a PTAS unless P = NP [ALMS+92, Theorem 3]. Hence no MAX SNP-hard problem can have a PTAS unless P = NP.
  • Though the Ausiello et al framework deals with many more kinds of v-inapproximability than MAX SNP-hardness, the latter is easier to use; this may be because (1) there are a lot more MAX SNP-hardness results known (and there have been since the beginning [PY91]), (2) these results are for problems that are the basis of many known NP-hardness reductions (and hence, if one is lucky, can be adapted to your problem of interest), and (3) it is a bit easier to find MAX SNP-hardness results, e.g., []PY91], than PTAS- or APX-hardness results (as the [ACG+99] approximability problem compendium is organized by problem name rather than by class-hardness).
    • A general caveat that can be derived from this is, to make a new theory of intractability useful, you need to both have simple usable core definitions of U, T, tractability-preserving reducibility, and C and a good core set of C-hardness/completeness results for basic problems of interest from which new results can be derived.
    • Failing wrt either of these characteristics can cause problems for an intractability theory -- we will see several examples of this over the next two lectures.
  • Structure Approximability [HMRW07]
    • Motivation
    • Focus again on optimization problems and approximation algorithms; however, this time, our criterion is closeness of approximation-algorithm solution structure to optimal-solution structure.
    • Assuming a particular representation of solutions and a distance function d(x, y) on pairs of solutions, measure closeness of structure by value of d(A(x), y), where y is the closest optimal solution to A(x) relative to d() [HMRW07, p. 6].
    • Definition: Additive approximation (s-a-approx) [HMRW07, Definition 8]
    • Definition: Ratio approximation (s-r-approx) [HMRW07, Definition 8]
    • Definition: Polynomial-time structure approximation scheme (sPTAS) [HMRW07, Definition 9]
    • Definition: Fully polynomial-time structure approximation scheme (sFPTAS) [HMRW07, Definition 10]
    • Once again, can prove approximability by giving an algorithm with the appropriate properties.
    • Example: Weighted Max Cut is 0.5|x| / d s-a-approximable and 0.5 / d s-r-approximable [HMRW07, Theorem 12 and Corollary 13]
    • All known proofs of s-inapproximability done on a problem-by-problem basis.
    • Example: Max Clique is not c / d s-a-approximable for any constant c . 0 unless P = NP (see [HMRW07, pp. 16-18])
    • Have defined structural analogues of classical v-approximability classes as well as a structural L-reducibility [HMRW07, pp. 19-21] -- however, to date, no known complete or hard problems for these classes.
      • This is a research opportunity (hint, hint) ...
  • Wrt structural approximability, maybe part of the reason we do not yet have complete/hard problems is that we don't yet have the right definitions for some (or all) of the core concepts. This happens a lot in the early stages of developing a new theory of (in)tractability. We will see one such example of how people initially got it wrong (and perhaps now have it right) when we look at fixed-parameter tractability.
• Fixed-Parameter Tractability (see [DF99] and references; see also [FG06,Nie06])
  • Motivation
    • All forms of exponential time are not created equal; sometimes, if the exponential term in the running time arises from an aspect of the problem that is of restricted or constant value in practice, such algorithms are useful, e.g., O(n^k) and O(2^kn) algorithms are OK if k is small (with the latter being particularly attractive)[GJ79, Section 4.3].
    • Lemma [GJ79, Lemma 3.1]: For any graph G and a subset V' of the vertices V of G, the following statements are equivalent:
      • V' is a vertex cover for G;
      • V - V' is an independent set for G; and
      • V - V' is a clique in the complement of G.

    • Theorem [GJ79, Section 3.1.3]: Vertex Cover, Clique, and Independent Set are NP-complete.
    • Example: Vertex Cover is solvable in O(2^kn^2) time.
    • How do we show that such algorithms do not exist for a particular problem?
    • Example: Clique and Independent Set do not appear to have brute-force algorithms that run in O(n^k) time.

Tuesday, March 9 (Lecture #3)

• Fixed-Parameter Tractability (Cont'd)
  • Fixed-Parameter Tractability, Take 1: The FL framework
    (Nonuniform fp-tractability [Fel89,FL88])
    • Based on Robertson-Seymour graph minor theory (see [FL88] and references)
    • Graph minors.
    • Theorem (Kuratowski): A graph is planar iff it does not have K_5 or K_3,3 as a minor.
    • Minor-closed families of graphs and obstruction sets (= the minor-minimal set of graphs in the complement of a graph family).
    • For a minor-closed family of graphs F, a graph G is in F iff there exists no H in the obstruction set of F such that H is a minor of G!
    • Theorem (formerly known as Wagner's Conjecture) [RS04]: Any set of finite graphs contains only a finite number of minor-minimal elements.
    • Theorem [RS95]: Determining if a fixed graph H is a minor of a given graph G can be done in polynomial time.
    • These theorems in conjunction with the preceding observation yield nonconstructive polynomial-time algorithms for NP-complete problems whose "yes" or "no" instances can be characterized as minor-closed graph families [FL88].
    • Theorem [FL88, p. 734]: The NP-complete k-Longest Path problem is nonconstructively solvable in polynomial time.
    • This gives a nonuniform fp-tractability, but no way of proving fp-intractability.
  • Fixed-Parameter Tractability, Take 2: The AEFM framework (Nonuniform fp-(in)tractability ([AEFM89]; see also [DF99, p. 251])
    • U = generator-tester pairs ((indexed) relations)
    • T = nonuniform fp-tractability
    • Reducibility = many-one reducibility on relations + Turing reductions
    • C = IP (set of P-bounded / - indexed / -checkable indexed relations)
    • Both too powerful (like DEXPTIME prior to NP) and somewhat arcane wrt definitions and proof-techniques; also, is based on nonuniform fp-tractability, which allows tractable problems to be nonrecursive and hence uncomputable.
  • Fixed-Parameter Tractability, Take 3: The DF framework (Uniform fp-(in)tractability (see [DF99] and references))
    • Focus on simple case: decision problems and uniform fp-tractability.
    • U = parameterized problems (languages (sort of))
    • Example: The parameterized problems k-Vertex Cover, k-Clique, and k-Independent Set
    • T = (uniform) fp-tractability / class FPT
    • Are many techniques for deriving fixed-parameter algorithms (see [Nie06] and references).
    • Example: k-Vertex Cover is in FPT
    • reducibility = fp-reducibility
    • Example: k-Clique reduces to k-Independent Set
    • C = {W[1], W[2], ..., W[P], ..., ParaNP} (W-hierarchy)
      • The "W" in W-hierarchy stands for (circuit) weft.
      • W-classes defined in terms of circuits which recognize "yes"-instances of parameterized problems; classes differ by circuit weft.
      • Example: k-Vertex Cover, k-Clique, and k-Independent Set are in W[1].
    • Theorem: k-Independent Set and k-Clique are W[1]-complete [DF99, Theorem 10.8].
    • Inclusions in the W-hierarchy are not known to be proper; hence, the FPT != W[1] conjecture is invoked. This conjecture seems likely, but you never know ...
  • New formulations and versions of parameterized complexity are emerging (see [Fel09,FG06] and references), so this may not yet be the end of the story -- stay tuned ...

References

• Abrahamson, K.A., Ellis, J., Fellows, M.R., and Mata, M. (1989) "On the complexity of fixed-parameter problems (Extended Abstract)." In Proceedings of the 30th Annual IEEE Symposium on the Foundations of Computer Science (FOCS'89). IEEE Press; Los Alamitos, CA. 210-215.
• Arora, S, Lund, C., Motwani, R., Sudan, M., and Szegdy, M. (1992) "Proof verification and hardness of approximation problems." In Proceedings of the 33rd Annual IEEE Symposium on the Foundations of Computer Science (FOCS'92). IEEE Press; Los Alamitos, CA. 14-23.
• Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., and Protasi, M. (1999) Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer; Berlin.
• Cormen, C.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2001) Introduction to Algorithms (Second Edition). The MIT Press.
• Crescenzi, P. and Panconesi, A. (1991) "Completeness in Approximation Classes." Information and Control, 93, 241-262.
• Downey, R.G. and Fellows, M.R. (1999) Parameterized Complexity. Springer; Berlin.
• Fellows, M.R. (1989) "The Robertson-Seymour theorems: A survey of applications." Contemporary Mathematics, 89, 1-18.
• Fellows, M.R. (2009) "Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology." In J. Fiala, J. Kratochvil. and M. Miller (eds.) Proceedings of the 4th International Workshop on Combinatorial Algorithms (IWOCA 2009). Lecture Notes in Computer Science no. 5874. Springer; Berlin. 2-10.
• Fellows, M.R. and Langston, M.A. (1988) "Nonconstructive tools for proving polynomial-time decidability." Journal of the ACM, 35(3), 727-739.
• Flum, J. and Grohe, M. (2006) Parameterized Complexity Theory. Springer; Berlin.
• Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman; San Francisco.
• Gonzalez, T.F. (ed.) (2007) Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC; Boca Raton, FL.
• Hamilton, M., Muller, M., van Rooij, I., and Wareham, T. (2007) "Approximating Solution Structure." In E. Demaine, G.Z. Gutin, D. Marx, and U. Stege (eds.) Structure Theory and FPT Algorithmics for Graphs, Digraphs, and Hypergraphs. Dagstuhl Seminar Proceedings no. 07281. Internationales Begegnungs- und Forschungszentrum fur Informatik (IBFI), Schloss Dagstuhl, Germany. URL: http://drops.dagstuhl.de/portals/07281/
• Horowitz, E. and Sahni, S. (1978) Fundamentals of Computer Algorithms. Computer Science Press; Rockville, MD.
• Niedermeier, R. (2006) Invitation to Fixed-Parameter Algorithms. Oxford University Press.
• Papadimitriou, C.H. and Yannakakis, M. (1991) "Optimization, Approximation, and Complexity Classes." Journal of Computer and System Sciences, 43, 425-440.
• Robertson, N. and Seymour, P.D. (1995) "Graph Minors XIII: The Disjoint Paths Problem." Journal of Combinatorial Theory Series B, 63(1), 65-110.
• Robertson, N. and Seymour, P.D. (2004) "Graph Minors XX: Wagner's Conjecture." Journal of Combinatorial Theory Series B, 92(2), 325-357.
• Vazirani, V.V. (2003) Approximation Algorithms. Springer; Berlin.