Computer Science 6789, Winter '14
Course Diary

---

Copyright 2014 by Todd Wareham
All rights reserved

---

Week 1, Week 2, Week 3, Week 4, Week 5, (Class Exam #1 Notes),
Week 6, Week 7, Week 8, Week 9, (Class Exam #2 Notes),
Week 10, Week 11, Week 12, Week 13, (end of diary)

Tuesday, January 7

• Power outages; university closed.

Thursday, January 9 (Lecture #1)
[Class Notes]

• Introduction to course; dates and conventions.
• Motivation for course: Parameterized complexity analysis? Why bother?
  • Many problems of interest cannot be solved in polynomial time. However these proofs of polynomial-time intractability are often stated for versions of problems that are very / ludicrously general.
    • Example: 3-D Robot Motion Planning

      3-D Robot Motion Planning (3DRMP)
      Input: A jointed robot R, a set of obstacles O embedded in some 3-D environment E, and initial and final positions p_I and p_F of R in E.
      Question: Is there a sequence of robot motions that move R from p_I to p_F without colliding with any obstacles in O?

      • Is PSPACE-hard for arbitrary robots and environments. However, robots are seldom arbitrary -- for example, the number of joints in a robot arm less than or equal to 7 and a functional robot hand can be made with on the order of 20 joints.
      • Is there a non-polynomial-time algorithm for 3DRMP whose non-polynomial running-time terms are expressed purely as functions of the number of joints in the robot?
    • It seems the that 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)(Garey and Johnson (1979), Section 4.3).
    • How do we show that such algorithms do (or do not) exist for a particular problem relative to particular aspects? How do we go about finding relevant and/or useful aspects for a given problem? The answers to these questions will be the subject matter of this course.
  • First, though, let's make sure we are all on the same page wrt basic concepts such as computational problems, algorithms, time complexity, and classical computational complexity, i.e, the theory of NP-completeness. To this end, the next several lectures will be a review of such background concepts.
    • Unless otherwise stated, all section and page references in the next several lectures will be to Cormen et al (2001).
  • Background: Problems and Algorithms
    • Computational Problems
      • A computational problem is a relation between inputs and outputs.
      • Types of computational problems.
        • By type of output:
          • Decision problem: Returns a Boolean value (typically the answer to a question about the optimal solution for a given instance of a problem).
          • Cost / Evaluation problem: Returns a number (typically the cost of an optimal solution for a given instance of a problem).
          • Example / Solution problem: Returns a structure (typically an optimal solution for a given instance of a problem).
          • Example: Versions of the Shortest Path problem:

            Shortest Path (Unweighted) [Decision]
            Input: A graph G = (V,E), two vertices u and v in V, and a positive integer k.
            Question: Is there a path P in G from u to v such that the number of edges in P is <= k?

            Shortest Path (Unweighted) [Evaluation]
            Input: A graph G = (V,E) and two vertices u and v in V.
            Output: The length of the path in G from u to v with the smallest possible number of edges.

            Shortest Path (Unweighted) [Solution]
            Input: A graph G = (V,E) and two vertices u and v in V.
            Output: A path P in G from u to v such that the number of edges in P is the smallest possible.

        • By entities in I/O relation:
          • Discrete problem: Manipulates integers and/or discrete structures.
          • Numerical problem: Manipulates (arbitrary-precision) real numbers in addition to integers and/or discrete structures.
      • This course will focus on various discrete problems. In particular, we will be looking at a number of discrete problems in which we are looking for a substructure of a given structure that is optimal relative to some function (combinatorial optimization problems).
    • Algorithms
      • An algorithm for a problem is a finite sequence of instructions relative to a particular computer-model that, given an input for that problem, computes the corresponding output.
      • Types of algorithms.
        • By type of computer-model:
          • Instruction execution mode: Deterministic / Randomized / Non-deterministic
          • Number of processors: Serial (single processor) / Parallel (multiple processors)
        • By type of computation: Discrete / Numerical.
      • This course will focus on deterministic serial discrete algorithms.
  • There are typically many possible algorithms for a particular problem. Which algorithm should we use? Perhaps we should use the one that is most efficient -- this, however, requires a useful and usable measure of algorithm efficiency ...
  • Background: Time Complexity
    • Desirable properties of a measure of algorithm efficiency:
      • Function of input size.
      • Machine independent.
      • Mathematically tractable, i.e., can be derived (relatively) easily for any algorithm.
      • Useful for both assessing individual and comparing groups of algorithms.
    • For most of this course, we will focus on efficiency wrt algorithm running time; however, we will occasionally mention other measures, i.e., space (computer memory).
    • The road from actual running time to asymptotic worst-case time complexity -- necessary lies (or rather, abstractions):

      		C(x)		T(n)		T(n)		O(g(n))
      Actual		Abstract		(Exact)		Worst-Case		Asymptotic
      Running	----->	Running	----->	Time	----->	Time	----->	Worst-Case
      Time		Time		Complexity		Complexity		Time
      								Complexity
      		Instruction		Input Size		Worst-Case		Asymptotic
      		Counts				Selection		Notation

      

    • Let's look at various concepts and techniques mentioned above in more detail.
    • Counting instructions
      • Motivated by the need for "machine" (computer hardware / operating system, programming language) -independent measure of algorithm efficiency.
      • Basic instructions in a program can have a wide range of running times. Can indicate this in an analysis by assigning a separate constant for the running time of each kind of instruction; is accurate, but very cumbersome.
      • We will assume that each kind of basic instruction runs in 1 time unit. Is not accurate but does simplify analyses; moreover, can be justified by our ultimate focus on asymptotic time complexity.
      • We will assume a RAM model of memory in which all stored elements are accessible in 1 time unit. Is not accurate, as we ignore memory hierarchy; however, does simplify analyses.
    • Input size.
      • Motivated by the need to organize set of instruction-counts over the space of all inputs.
      • Isolate a small set of parameters that describe amount of memory used to store input.
      • Hard to define formally; acquired informally via experience doing time complexity analyses.
      • We will assume where possible that we are dealing with small numbers in the input that fit inside a single computer-memory "word"; hence, the size of numbers in the input need not be a parameter in the input size.
    • Time Complexity
      • Time complexity = instruction-count stated as function of input size.
      • Two general methods to deriving a time complexity function for an algorithm:
        • Compute counts for individual instructions and add together to derive function.
        • "Grow" function by starting at innermost level of nesting in algorithm and working outwards.

        Which method you use depends on the intricacy of the given algorithm.

    • Worst-Case Time Complexity
      • Programs involving loops and simple statements naturally give time complexity functions such that every input of a particular size runs in the same time; unfortunately, once we allow if-then-else conditional statements, different inputs of the same size may run in different times, e,g., sorting algorithms on sorted and unsorted lists of the length.
      • Need to summarize set of running times for each input size s by a single number. Several options:
        • Average-case, e.g., average running time relative to some probability distribution over all inputs of size s; useful in practice but hard to compute.
        • Best-case, e.g., lowest running time over all inputs of size s; easy to compute but not that useful in practice.
        • Worst-case, e.g., highest running time over all inputs of size s; easy to compute and useful in practice.
      • Worst-case time complexity functions are both useful and usable; hence, are most commonly in practice.
    • Asymptotic notation
      • Used to smooth and simplify time complexity functions; assumes input size goes out to infinity, and that simplification can be stated in terms of "essential" behavior of function in the limit.
      • What makes a function g(n)) a useful and smooth upper bound of a time complexity function function g(n) ?
        • g(n) upper-bounds f(n):
          f(n) <= g(n) for all n > 0.

        • g(n) upper-bounds f(n) after initial "bumpy" portion:
          f(n) <= g(n) for all n > n0 for some n0 >= 0.

        • g(n) upper-bounds f(n) after initial "bumpy" portion under arbitrary machine model:
          f(n) <= c * g(n) for all n > n0 for some c > 0 and n0 >= 0.

          This allows (to a degree) for instructions whose running-times differ by a constant multiplicative factor on different machines.

        Note that we have re-derived the definition of big-Oh asymptotic upper-bound notation by combining the mathematical requirements of a useful smoothing function.
      • Asymptotic upper bounds: Big-Oh notation (O(g(n)).
        • Example: T(n) = 3n^2 + 4n + 5 is O(n^2) (big_Oh.txt)
        • One could derive the required constant c by fancy algebra; I prefer to set c to the sum of the positive coefficients -- it's very dirty but it's also quick.
        • Example: T(n) = 3n^2 + 4n + 5 is not O(n) (big_Oh.txt)
        • Try to avoid ludicrously loose upper bounds.
        • Example: T(n) = 2n is O(n^57)
        • Relationship between informal "T(n) is O(g(n))" definition and "O(g(n)) as the set of all g(n)-upper-bounded functions" definition given in textbook; keep the latter in mind, but the former is colloquial CS usage. May stem from algorithm-centric and math-centric views of asymptotic notation, respectively.
      • Two caveats on using asymptotic notation:
        • Though it is in a sense an abuse of notation, you will frequently see O(1) used to indicate an unspecified constant in various expressions.
        • The rules about combining separate asymptotic-notation expressions are tricky; be VERY careful if you ever do this in your math -- it might be better off to write out the full constant-bounds and work with those, so you don't make mistakes.
    • Guidelines for deriving asymptotic worst-case time complexity functions (non-recursive algorithms)
      • If you have a worst-case time complexity function on hand, the leading term (minus coefficient) is usually the asymptotic worst-case time complexity function.
      • Example: Though the selection, bubble, and insertion sort algorithms run in T(n) = 4n^2 - 2, T(n) = 7n^2 - 10n + 5, and T(n) = 3n^2 - 1 time, respectively, all of these algorithms run in O(n^2) time.
      • As constants associated with different loops and different numbers of embedded simple statements vanish into the leading constant c in the definition of asymptotic notation, can often derive a near-optimal asymptotic worst-case time complexity function by simply multiplying out the number of iterations for each loop in the deepest chain of nested loops.
      • Example: As both the insertion and selection sort algorithms consist of a pair of nested loops, each of which has at most n iterations, both algorithms run in O(n * n) = O(n^2) time.
      • If you ever have nested loops in which the number of iterations of the inner loop is a function of the index-value for the outer loop, it may be best to employ a hybrid instruction-counting strategy in which the inner loop's contribution is computed separately and added into the instruction-count computed by the "innermost outwards" approach.
      • Example: nested for- and while-loops, inner while-loop executes up to value of for-loop index.
      • The usual way to handle nested if-then-else statements is to assume the largest sub-case always executes. However, if you have a function describing how often the conditional is true, you may be able to do better, e,g., derivation of O(|V| + |E|) time complexity for breadth-first graph traversal algorithm.

Tuesday, January 14 (Lecture #2)
[Class Notes]

• Using standard algorithm design technique, we can often derive a polynomial-time algorithm for a problem of interest and hence prove that this problem is solvable in polynomial time, i.e., the problem is (polynomial-time) tractable.
• However, suppose we run across a problem for which we cannot find a polynomial time algorithm. Are we just not thinking hard enough or is it really the case that there isn't a polynomial-time algorithm for that problem, i.e., the problem is (polynomial-time) intractable?
• Background: Proving Polynomial-Time Intractability
  • Two types of proofs:
    • Absolute (based on examining the problem in isolation)
      • Lower bound theory / information-theoretic arguments.
    • Relative (based on examining a problem in relation to other problems)
      • Based on the concept of a reduction, where a reduction between problems A and B is essentially an algorithm that solves instances of A by calling a subroutine for solving instances of B.
  • Let's focus on the relative approach, in particular, polynomial-time reductions, i.e., reductions whose associated transformations run in polynomial time and make a polynomial calls to the subroutine for B, where the polynomials are in terms of the input size for A.
  • Three very useful properties of polynomial-time reductions:
    • Polynomial-time solvability passes backwards along a reduction, i.e., if A reduces to B and B is solvable in polynomial time than A is solvable in polynomial time.
    • Polynomial-time unsolvability passes forwards along a reduction, i.e., if A reduces to B and A is not solvable in polynomial time than B is not solvable in polynomial time.
    • Polynomial-time reductions are transitive, i.e., if A reduces to B and B reduces to C then A reduces to C.

            Polynomial-time solvability
    
    	      <-------------
            A reduces to B reduces to C
    	      ------------->
    
           Polynomial-time unsolvability
    

  • The upshot is, all we need is one polynomial-time intractable problem to get the ball rolling! But where do we find such a problem?
  • Our quest for a "seed" polynomial-time intractable problem will have two phases:
    • Demonstrating that we need only focus on decision problems.
    • Isolating polynomial-time intractable decision problems.
  • Can use reductions to show that we only need to concern ourselves with decision versions of problem -- can usually show that polynomial-time solvability and unsolvability propagates to cost and example versions.
  • Example: Some computational problems that we will be looking out (unless explicitly noted, all problems are decision problems):

    Clique
    Input: An undirected graph G = (V,E) and an integer k > 0.
    Question: Is there a clique in G of size at least k, i.e., is there a subset V' \subseteq V, |V'| >= k, such that for all u, v \in V', (u,v) \in E?

    Directed Hamiltonian Path (DHP)
    Input: A directed graph G = (V,A).
    Question: Is there a directed Hamiltonian path in G, i.e., is there a directed path in G between any two vertices in G that visits each vertex in G exactly once?

    Graph 3-Colorability (3GC)
    Input: An undirected graph G = (V,E).
    Question: Is G 3-colorable, i.e., is there a function f : V -> {1,2,3} such that f(u) is not equal to f(v) for {u,v} in E?

    Hamiltonian Path (HP)
    Input: An undirected graph G = (V,E).
    Question: Is there a Hamiltonian path in G, i.e., is there a path in G between any two vertices in G that visits each vertex in G exactly once?

    0/1 Knapsack (01KN)
    Input: A set of items U, item size- and value-functions s() and v(), and positive integers B and k.
    Question: Is there a subset U' of U such that the sum of the sizes of the items in U' <= B and the sum of the values of the items in U' >= k?

    Longest Path (LP)
    Input: An undirected graph G = (V,E), vertices u and v in V, and an integer k > 0.
    Question: Is there a path in G between u and v that visits each vertex on that path at most once and contains at least k edges?

    Set Cover (SC)
    Input: A set U = {u_1, ... u_n} of items, a set S = { s_1, ..., s_m} of subsets of U, and an integer k <= m.
    Question: Is there a subset S' \subseteq S such that |S| <= k and the union of s in S' = U?

    Steiner Tree in Graphs (STG)
    Input: An undirected graph G = (V,E), a set V' \subseteq V, and an integer k > 0.
    Question: Is there a tree in G that connects all vertices in V' and contains at most k edges?

    Subset Sum (SS)
    Input: A set S of integers and an integer t >= 0.
    Question: Is there a subset S' of S whose elements sum to t?

    Vertex Cover (VC)
    Input: An undirected graph G = (V,E) and an integer k > 0.
    Question: Is there a vertex cover of G of size at most k, i.e, is there a subset V' \subseteq V such that |V'| <= k and for all edges (u,v) \in E, at least one of u and v is in V'?

    Vertex Cover Cost (VC-C)
    Input: An undirected graph G = (V,E).
    Output: The size of the smallest vertex cover of G.

    Vertex Cover Example (VC-E)
    Input: An undirected graph G = (V,E).
    Output: One of the smallest vertex covers of G.

  • Example Reductions between different vertex cover problems.
    • Vertex Cover (Decision) is solvable in polynomial time if and only if Vertex Cover (Cost) is solvable in polynomial time.
      • If Vertex Cover (Decision) is solvable in polynomial time then Vertex Cover (Cost) is solvable in polynomial time: Prove by giving a polynomial time reduction from Vertex Cover (Cost) to Vertex Cover (Decision):

        VERTEX-COVER-COST(G)
            k = 1
            while not VERTEX-COVER-DECISION(G,k) do
                k = k + 1
            return(k)
        

      • if Vertex Cover (Cost) is solvable in polynomial time then Vertex Cover (Decision) is solvable in polynomial time: Prove by giving a polynomial time reduction from Vertex Cover (Decision) to Vertex Cover (Cost):

        VERTEX-COVER-DECISION(G, k)
            if (VERTEX-COVER-COST(G) <= k then
                return(TRUE)
            else
                return(FALSE)
        

    • Vertex Cover (Decision) is solvable in polynomial time if and only if Vertex Cover (Example) is solvable in polynomial time.
      • If Vertex Cover (Decision) is solvable in polynomial time then Vertex Cover (Example) is solvable in polynomial time: Prove by giving a polynomial time reduction from Vertex Cover (Example) to Vertex Cover (Decision):

        VERTEX-COVER-EXAMPLE(G)
        
            min_cost = 1
            while not VERTEX-COVER-DECISION(G,min_cost) do
                min_cost = min_cost + 1
        
            k = min_cost
            S = {}
            G' = G
            while |S| < min_cost do
                for each vertex v' in V' do
                    G'' = (V' u {x}, E' u {(v',x)})
                    if (VERTEX-COVER-DECISION(G'',k)) then
                        S = S u {v'}
                        G' = G' - {v'}
                        k = k - 1
                        break;
            return(S)
        

        • Reduction uses vertex x and edge attached to x as ``probe'' to see if vertex v' is in the vertex cover. If it is, edge (v',x) is covered by the current cover (VERTEX-COVER-DECISION(G'',k) = TRUE); otherwise, x must be added to cover, creating a cover of size k + 1, rendering VERTEX-COVER-DECISION(G'',k) = FALSE.
      • if Vertex Cover (Example) is solvable in polynomial time then Vertex Cover (Decision) is solvable in polynomial time: Prove by giving a polynomial time reduction from Vertex Cover (Decision) to Vertex Cover (Example):

        VERTEX-COVER-DECISION(G, k)
            if (cost(VERTEX-COVER-EXAMPLE(G)) <= k then
                return(TRUE)
            else
                return(FALSE)
        

    • As we are typically interested in transferring intractability results from decision problems to their corresponding example problems, only need to do the (often MUCH easier) reduction from the decision problem to its corresponding example problem.
      • Even though it is often simple, it is a good idea to do this reduction to make sure you are working with the right decision problem to get intractability results for the example problem.
  • Focusing on decision problems makes our lives much easier when dealing with reductions. Indeed, we can make things even simpler by using just one type of reduction.
    • A (polynomial time) many-one reduces to B if there is a polynomial-time function f that transforms instances of A into instances of B such that the answer to instance I of A is "yes" if and only if the answer to instance f(I) of B is "yes".
  • From the above, we know that a polynomial-time reduction has several parts: the problem-instance transformation encoded in the reduction, a proof that this transformation runs in polynomial time, and a proof of the correctness of the transformation, e.g. is it actually the case that relative to the transformation, the given instance of A has answer "yes"" if and only if the constructed instance of B has answer "yes"? To get an idea how such reductions work and may be derived, in the next lecture, we will look at several sample reductions.

Thursday, January 16 (Lecture #3)
[Class Notes]

• Background: Proving Polynomial-Time Intractability (Cont'd)
  • Exercise: Propagating results in reduction webs.
  • Let's look at a few sample reductions to see what is involved.
  • The simplest type of reduction relates a pair of problems in which one problem is a simple case of the other.
  • Example: Subset Sum many-one reduces to 0/1 Knapsack
    • Given an instance (S = {s1,..,sn},t) of SS, construct an instance (U,s,v,B,k) of 01KN such that U = {u1,..,un} where s(ui) = v(ui) = si, 1 <= i <= n, and B = k = t.
    • Prove that the given instance of SS has answer "yes" iff the constructed instance of 01KN has answer "yes":
      • If the given instance of SS has answer "yes" then the constructed instance of 01KN has answer "yes": Consider a solution S' = {s'1,..,s'm} \subseteq S for the given instance of SS. Construct a candidate solution U' for the constructed instance of 01KN consisting of the items corresponding to the selected numbers in S'. Observe that the summed size and value of this solution is t = B = k, meaning that U' is a solution.
      • If the constructed instance of 01KN has answer "yes" then the given instance of SS has answer "yes": Consider a solution U' to the constructed instance of 01KN. As item values and sizes are the same, the solution size and value most be the same. Thus, if the summed size is <= B and the summed value is >= k, the summed size must be B = k = t. Thus, one can easily construct a solution for the given instance of SS consisting of those integers in S corresponding to items in U'.
  • A more complex type of reduction relates a pair of problems using a mathematical property of the objects being manipulated in the problem ,e.g., graphs..
  • Example: Clique many-one reduces to Vertex Cover (Lemma 3.1, Garey and Johnson (1979))
    • Relies on a nice graph-theoretic characterization of cliques and vertex covers on the same set of vertices.
    • Define the complement Gc = (V,Ec) of a graph G = (V,E) as the graph on V with edge-set Ec = {(u,v) | (u,v) is not in E}.
    • Given an instance (G,k) of Clique, the reduction constructs an instance (Gc,|V| - k) of VC.
    • Prove that the given instance of Clique has answer "yes" iff the constructed instance of VC has answer "yes":
      • If the given instance of Clique has answer "yes" then the constructed instance of VC has answer "yes": Consider a solution S \subseteq V of size k to the given instance of Clique. As each pair of vertices in S is connected by an edge in G, no pair of vertices in S is connected by an edge in Gc. Hence, V - S is a vertex cover of size |V| - k in the constructed instance of VC.
      • If the constructed instance of VC has answer "yes" then the given instance of Clique has answer "yes": Consider a solution S \subseteq V of size |V| - k in Gc to the constructed instance of VC. Consider S' = V - S. None of the vertices in S' are connected by an edge in Gc (else, one of them would have to be in the vertex cover). Hence, there is an edge between each pair of vertices in S' in G, and S' is a clique of size k in the given instance of Clique.
  • A more complex still type of reduction relates a pair of problems by constructing instances of the second problem structured in pieces whose interactions the general structure of the first problem. Such individual pieces are informally known as gadgets. We will see more examples of such reductions later in the course.
  • Example: Vertex Cover many-one reduces to Steiner Tree in Graphs
    • Given and instance (G = (V,E),k) of VC construct an instance (G' = (V',E'),V'',k') of STG such that V' = {r} u {v'1,..,v'|V|} u {e'1,..,e'|E|}, E' = {(r,v'i) | 1 <= i <= |V|} u {(v'i,e'j) | vertex i is an endpoint of edge j in E}, V'' = {r} u {e'1,..,e'|E|}, and k' = k + |E|.
    • This reduction requires that solutions to the constructed instance of STG have a three-level structure in which the top level is the root-vertex r, the second level consists of vertices corresponding to the edges in G, and the vertices in the second level correspond to vertices in a vertex cover for G.
    • Prove that the given instance of VC has answer "yes" iff the constructed instance of STG has answer "yes":
      • If the given instance of VC has answer "yes" then the constructed instance of STG has answer "yes": Consider a solution S \subseteq V of size k for the given instance of VC. For each edge e in E, let end(e) be the endpoint of e in S (if they are both in S, pick one arbitrarily). The tree in G' consisting of V' and the vertices v'i corresponding to vertices in S, along with the edges linking these vertices to r and the vertices e'j (that is, for each vertex e'j corresponding to edge j in E, select edge (e'j,end(j))), is a solution for the constructed instance of STG that contains k + |E| edges.
      • If the constructed instance of STG has answer "yes" then the given instance of VC has answer "yes": A solution tree for the constructed instance of STG of size k' must have at least one edge from r t0 some v'i, but may have multiple pairs of edges that form "wedges" ((v'i,e'j),(v'k,e'j) where there is an edge (r,v'i) in the tree but no edge (r,v'k)). Note that each wedge can be replaced by the edge-pair ((r,v'k),(v'k,e'j)) without changing the cost of the tree. The tree resulting after all such replacements are made will have k edges from r to various v'i and |E+| edges from various v'i to various e'j. The vertices v'i correspond to vertices in G that form a vertex cover of size k.
  • Now we have to isolate a polynomial-time intractable decision problem ... Oddly enough, reductions can help us further in this, if used in tandem with problem classes. This will be the topic of the next lecture.

Tuesday, January 21 (Lecture #4)
[Class Notes]

• Background: Proving Polynomial-Time Unsolvability (Cont'd)
  • A problem class is a set of problems that has a particular type of algorithm.
  • Example: Class P is the set of all decision problems that have polynomial-time algorithms.
  • Use reductions to isolate the most computationally difficult problems in a problem class C using the notions of problem hardness and completeness.
    • A problem A is C-hard if every problem in C reduces to A -- if A is also in C, it is C-complete.
    • C-hard problems are as hard as the hardest problems in C.
    • C-complete problems are the hardest problems in C.
  • Need class C of decision problems that properly includes class P and for which we have complete problems -- can then use these complete problems as basis for reductions to show that problems of interest to us are not in P and hence are not solvable in polynomial time.
    

  • Example: Class EXPTIME is the set of all decision problems that have exponential-time algorithms.
  • Decision versions of all problems we've looked at so far are in EXPTIME; moreover, it is known that P is properly included in EXPTIME.
  • Example: Class NP is the set of all decision problems that have non-deterministic polynomial-time algorithms, i.e., problems such that candidate solutions can be verified in polynomial time.
  • Decision versions of all problems we've looked at so far are in NP.
  • Example: Vertex Cover is in NP courtesy of the O(|E||V'|) time verification algorithm that determines if every edge in G has an endpoint in the given candidate vertex cover V'.
  • Example: 0/1 Knapsack is in NP courtesy of the O(|U'|) time verification algorithm that determines if the summed size of the items in candidate solution U' is <= B and the summed value of the items in U' is >= k.
  • Example: Steiner Tree in Graphs is in NP courtesy of the polynomial time verification algorithm that determines if the specified set of candidate solution tree edges has size <= k and forms a tree in G that connects all vertices in V'.
  • P is certainly included in NP; however. it is not known if this inclusion is proper (hence, the "P = NP?" conjecture). Still, if EXPTIME-complete problems are not useful to us, NP-complete problems might be. Now, all we need is one NP-complete problem to start the ball rolling ...
  • One strategy for obtaining an initial C-hard problem X for class C is to create a generic reduction from any problem in C to X. How might one do this, though?
  • Such a generic reduction is relatively easy to construct for a class C of decision problems relative to a language-recognition machine.
    • Equivalence of decision problems and language acceptance problems (map decision problem to language of bitstrings consisting of instance-encodings of all instances for which answer is "yes").
    • All problems in a class C of decision problems relative to a language-recognition-machine M are reducible to the following problem (which is also typically itself in class C):
      M-Acceptance
      Input: Machine m of type M, input x.
      Question: Does m accept, i.e., produce output "yes", on input x?

  • Example: P is the set of all decision problems whose associated languages of "yes"-instances can be recognized by a polynomial-time deterministic Turing machine (DTM).
  • Example: EXPTIME is the set of all decision problems whose associated languages of "yes"-instances can be recognized by a exponential-time deterministic Turing machine (EDTM).
  • Hence, we have one polynomial-time unsolvable problem -- EDTM-Acceptance! However, there are many problems of interest for which one cannot construct reductions from EDTM-Acceptance. Perhaps these problems are not EXPTIME-hard; need something a bit less difficult, computationally-speaking.
  • Example: NP is the set of all decision problems whose associated languages of "yes"-instances can be recognized by a polynomial-time non-deterministic Turing machine (NDTM).
    • Non-deterministic TM may have arbitrary-choice conditional statements; machine computes "yes" on an input if there is some set of choices at these arbitrary-choice conditionals that yields an accepting computation for the given string.
    • Arbitrary-choice conditionals = way of looking at all possible solutions for a given instance within an NDTM! Hence, nicely encodes notion of polynomial-time verification.
    • NDTM-Acceptance is NP-complete!
  • NDTM-Acceptance may at first glance appear as unnatural a problem as EDTM-Acceptance; however, it is not.
  • Historical route to useful NP-complete problems:
    • NTDM-Acceptance many-one reduces to CNF Satisfiability (Cook (1971))
      • A logic formula is in conjunctive normal form (CNF) if it is the conjunction (AND) of a set of disjunctive (OR) clauses.

        CNF Satisfiability
        Input: A CNF formula F.
        Question: Is there a satisfying assignment for F, i.e., an assignment of values to the variables of F that make F evaluate to True?

      • The reduction is essentially a simulation of an NDTM as a CNF logic formula that describes a sequence of configurations comprising an NDTM computation -- the formula is true iff a sequence of computations leading to string-acceptance exists.
    • CNF Satisfiability many-one reduces to 3-CNF Satisfiability (Karp (1972))
      • A logic formula is in 3-conjunctive normal form (3-CNF) if it is CNF and each clause has exactly three literals.

        3-CNF Satisfiability
        Input: A 3-CNF formula F.
        Question: Is there a satisfying assignment for F?

      • This reduction replaces each CNF clause of strictly less or more than three literals with a set of one or more 3-literal clauses that is true iff the original clause is true.
    • The real genius of Karp (1972) was to show reductions from CNF Satisfiability and 3-CNF Satisfiability to 18 problems of interest drawn from graph theory, scheduling, and network design. This initial list of 18 has since blossomed to thousands (see the Appendix of Garey and Johnson (1979) for a small but nonetheless significant list of known NP-hard problems).
      • Most of the reductions in Karp (1972) are stated without proof.
      • One of Karp's reductions is wrong!
      • Stresses the need for proofs of correctness for reductions.
  • By transitivity of reductions, all problems above are NP-hard. This thus makes for the second (and usually far easier) strategy for proving a problem X C-hard -- that is, give a reduction from known C-hard problem Y to X.
  • Example: 3-CNF Satisfiability many-one reduces to Clique (Theorem 34.11).
  • Example: 3-CNF Satisfiability many-one reduces to Subset Sum (Theorem 34.15).
  • As Clique many-one reduces to Vertex Cover, Vertex Cover many-one reduces to Steiner Tree in Graphs, Subset Sum many-one reduces to 0/1 Knapsack, and both Clique and Subset Sum are NP-complete, Steiner Tree in Graphs and 0/1 Knapsack are NP-hard (as are all other problems mentioned on that list back in the Lecture #2 notes)! Which means that these problems are not solvable in polynomial time!
    ... Doesn't it? ...
    ... Not really ...
    ... Why?
    • We don't know whether or not P is properly contained in NP. Hence, there must always be a qualifying clause attached to an interpretation of an NP-hardness result -- namely, an NP-hard problem X is not solvable in polynomial time unless P = NP.
    • To this day, it is not known if P = NP or not -- however, the best evidence that P != NP is that no-one has yet found a polynomial-time algorithm for an NP-hard problem.

Thursday, January 23 (Lecture #5)
[Class Notes]

• Background: Dealing with Polynomial-Time Intractability
  • There is a dazzling array of problem classes above NP (Johnson (1990)), yielding many opportunities for proofs of membership (and hence completeness) for problems that are NP-hard but not in NP -- however, in this course, where our focus is on ruling out polynomial-time solvability, proofs of NP-hardness will be sufficient.
  • A proof of NP-hardness is technically a wonderful thing, and it does confirm intuitions that a problem is in fact difficult -- however, the inconvenient fact remains that even if a problem is NP-hard, we still need to be able to solve it.
  • Are there alternatives to exponential-time optimal-solution algorithms for NP-hard problems? Yes, there are! To see why, we need to understand exactly what an NP-hardness result 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.

    • Hence, there may still be usable algorithms that violate one or more of the italicized clauses above. Let's look at several of these today, finishing up with the option that we will be studying the rest of this term -- namely, fixed-parameter tractable algorithms.
  • Polynomial-time heuristic algorithms
    • Algorithms that are not required to produce optimal solutions, i.e., algorithms that give some solution quickly.
    • Three general approaches:
      • Hill-climbing (local optimization / greedy heuristic)
      • Simulated annealing (physics metaphor)
      • Genetic algorithms (biological metaphor)
  • Polynomial-time randomized algorithms
    • Algorithms that are allowed to make random choices (cf. non-determinism); in conjunction with assumption of various distributions (typically uniform) on the space of inputs, can derive algorithms with an expected probability of producing a correct (optimal) answer or an expected running time.
    • Two types of algorithms:
      • Monte Carlo: Running time fixed, expected probability of producing a correct (optimal) answer (you don't know if you'll win).
      • Las Vegas: Expected running time, produces correct (optimal) answer (you don't know when you'll win).
    • Typically used to give faster algorithms for problems already known to be solvable in low-order polynomial time, e.g., an O(|V| + |E|) expected time Las Vegas algorithm for deriving minimum spanning trees (Section 10.3, Motwani (Motwani and Raghavan (1995))).
    • Also useful for certain problems not known to be in P, e.g., the Miller-Rabin Monte Carlo algorithm for primality testing (Section 31.8).
  • Polynomial-time bounded-cost approximation algorithms
    • An algorithm A that produce a solution S_A for an instance I whose cost C(S_A) is guaranteed to be within some limit of the cost C(S_O) of the optimal solution.
    • Several types of approximation algorithms:
      • Additive: Algorithm solution within an additive factor of optimal, i.e., |C(S_A) - C(S_O)| <= p(|I|) for some polynomial p().
        • C(S_A) <= C(S_O) + p(|I|) for some polynomial p() (minimization problem)
        • C(S_A) <= C(S_O) - p(|I|) for some polynomial p() (maximization problem)
      • Multiplicative: Algorithm solution within a multiplicative factor of optimal.
        • 1 < C(S_A)/C(S_O) <= p(|I|) for some polynomial p() (minimization problem)
        • 1 < C(S_O)/C(S_A) <= p(|I|) for some polynomial p() (maximization problem)
      • Polynomial-time approximation scheme (PTAS): (1 + 1/e)-approximation algorithm with input (I,1/e) that runs in polynomial time for every fixed value of e > 0.
      • Fully polynomial-time approximation scheme (FPTAS): (1 + 1/e)-approximation algorithm with input (I,1/e) that runs in polynomial time.
    • Many problems have multiplicative approximation algorithms, few problems have FPTAS or PTAS (0/1 Knapsack is one of them (Garey and Johnson (1979), pages 135-137)), and very few problems have additive approximation algorithms, which, ideally, are the ones we want.
  • Fixed-parameter tractable algorithms (Downey and Fellows (1999))
    • An algorithm whose non-polynomial running time terms are expressed in terms of aspects of the input that are of very small size in practice.
    • Such algorithms are of interest, as many problems that are polynomial-time unsolvable in general occur in restricted versions in practice.
    • Example: 3-D Robot Motion Planning

      3-D Robot Motion Planning (3DRMP)
      Input: A jointed robot R, a set of obstacles O embedded in some 3-D environment E, and initial and final positions p_I and p_F of R in E.
      Question: Is there a sequence of robot motions that move R from p_I to p_F without colliding with any obstacles in O?

      • Is PSPACE-hard for arbitrary robots and environments. However, robots are seldom arbitrary -- for example, the number of joints in a robot arm is at most 7 and a robot hand can be made with on the order of 20 joints.
      • Is there a non-polynomial-time algorithm for 3DRMP whose non-polynomial time-complexity terms are expressed purely as functions of the number of joints in the robot?
    • It seems the that 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].
    • Example: Vertex Cover is solvable in O(2^k|V|^2) time; however, Clique does not appear to have any algorithms that run in less than O(|V|^k) time.
• How do we show that fixed-parameter tractable algorithms do (or do not) exist for a particular problem? The "do not" part turned out to be surprisingly difficult to do ...
• Parameterized Complexity Theory: In The Beginning
  • Parameterized Complexity Theory, Take 1: The FL framework
    (Non-uniform fixed-parameter tractability (Fellows (1989), Fellows and Langston (1988)))
    • Based on Robertson-Seymour graph minor theory (see Fellows and Langston (1988) and references)
      • An undirected graph H is a minor of an undirected graph G if H can be obtained from G by deleting edges and vertices and contracting edges.
    • 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 (Robertson and Seymour (2004))): Any set of finite graphs contains only a finite number of minor-minimal elements.
    • Theorem (Robertson and Seymour (1995)): 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 non-constructive polynomial-time algorithms for NP-complete problems whose "yes" or "no" instances can be characterized as minor-closed graph families (Fellows and Langston (1988)).
      • Note that such solvability is non-uniform, in that a different algorithm is required for every parameter-value.
    • Theorem (Fellows and Langston (1988), p. 734): Longest Path is non-uniform non-constructively solvable in polynomial time.
    • This gives a sort of fp-tractability (namely, non-uniform), which is not ideal because it allows tractable problems to be uncomputable; moreover, there is no easy way of proving fp-intractability.
  • Parameterized Complexity Theory, Take 2: The AEFM framework (Non-uniform fixed-parameter (in)tractability (Abrahamson et al (1989); see also p. 25 in Downey and Fellows (1999)))
    • Based on generator-tester pairs ((indexed) relations)
    • Reducibility as many-one reducibility on relations + Turing reductions
    • Enclosing class as IP (set of P-bounded / - indexed / -checkable indexed relations)
    • Both too powerful (like EXPTIME prior to NP) and somewhat arcane wrt definitions and proof-techniques; also, is still based on non-uniform fp-tractability.
  • Parameterized Complexity Theory, Take 3: The DF framework (Uniform fixed-parameter (in)tractability (see Downey and Fellows (1999) and references))
    • Based on parameterized problems (languages (sort of)).
    • Reducibility as parameterized reductions.
    • Enclosing classes are the W-hierarchy = {W[1], W[2], ..., W[P], ..., ParaNP}
  • ... And this one works! How? Details follow, starting in our next lecture ...

Tuesday, January 28 (Lecture #6)
[Class Notes]

• Parameterized Complexity Theory (Downey and Fellows (1999); Downey (2012); Wareham (1999))
  • Fixed-parameter (fp-)Tractability
    • Intuitions that must be captured:
      • Single and multiple parameters, and these parameters need not be numerical values or even be derivable from problem instances efficiently, e.g., graph genus.
      • As there are many possible individual parameters and combinations of these parameters associated with a problem, there are many possible parameterized problems associated with a problem; moreover, each of these may have a different level of computational difficulty.
      • The time complexity of tractable parameterized problems should allow non-polynomial terms only wrt the parameter.
    • Formalization of Intuitions (Downey (2012), Sections 1.2 and 2; Wareham (1999), Section 2.1.2)
      • What is a parameter?
        • Parameter as number (or string encoding non-numerical value).
      • Parameterized problems
        • Model as string-number pairs (\Sigma^* x N) or string-pairs (\Sigma^* x \Sigma^*), in which the second part (k) of each pair (x,k) is the parameter and the first part (x) is known as the main part.
          • Former is preferred, and can simulate latter by some function mapping strings to numbers.
        • Are typically stated as decision problems (each of which has an associated parameterized language); however, could easily generalize to solution problems.
        • No totally satisfactory formal manner for handling multiple parameters (e.g., original, Flum and Grohe parameter-functions); here, assume parameter-function + inverse parameter-functions for extracting individual parameters when necessary.
        • No standard naming convention for parameterized problems; in this course, denote parameterized problem X with parameters k1,k2,...,kn as {k1,k2,...,kn}-X.
        • Note the fp-(in)tractability is always stated relative to a parameter-problem pair, e.g., saying "Vertex Cover is fp-tractable" makes no sense.
      • Example: Some parameterized problems

        {k}-Vertex Cover (VC)
        Input: An undirected graph G = (V,E) and an integer k > 0.
        Parameter: k
        Question: Is there a vertex cover of G of size at most k, i.e, is there a subset V' \subseteq V such that |V'| <= k and for all edges (u,v) \in E, at least one of u and v is in V'?

        {k}-Clique
        Input: An undirected graph G = (V,E) and an integer k > 0.
        Parameter: k
        Question: Is there a clique in G of size at least k, i.e., is there a subset V' \subseteq V, |V'| >= k, such that for all u, v \in V', (u,v) \in E?

        {k}-Independent Set
        Input: An undirected graph G = (V,E) and an integer k > 0.
        Parameter: k
        Question: Is there an independent set in G of size at least k, i.e., is there a subset V' \subseteq V, |V'| >= k, such that for all u, v \in V', (u,v) is not in E?

        {k}-Graph Coloring
        Input: An undirected graph G = (V,E) and an integer k > 0.
        Parameter: k
        Question: Is there a coloring of the vertices of G with at most k colors such that for each edge (u,v) in G, u and v are assigned different colors?

        {k}-Dominating Set
        Input: An undirected graph G = (V,E) and an integer k > 0.
        Parameter: k
        Question: Is there a dominating set in G of size at most k, i.e., is there a subset V' \subseteq V, |V'| <= k, such that for all v \in V, either v is in V' or there is an edge (v,v') in E for some v' in V'?

        {d}-Dominating Set
        Input: An undirected graph G = (V,E) in which each vertex has degree at most d and an integer k > 0.
        Parameter: d
        Question: Is there a dominating set in G of size at most k?

        {k,d}-Dominating Set
        Input: An undirected graph G = (V,E) in which each vertex has degree at most d and an integer k > 0.
        Parameter: k, d
        Question: Is there a dominating set in G of size at most k?

        {|\Sigma|,l}-Longest Common Subsequence
        Input: A set S = {s1, s2, ..., sk} of strings of length at most n over some alphabet \Sigma and an integer l > 0.
        Parameter: |\Sigma|, l
        Question: Is there a string s' of length at least l such that for all s in S, s' is a subsequence of s?

        {d}-Center String
        Input: A set S = {s1, s2, ..., sk} of strings of length n over some alphabet \Sigma and an integer d > 0.
        Parameter: d
        Question: Is there a string s' of length n such that for all s in S, the Hamming distance between s and s' is at most d?

        {l,|Q|}-DFA Intersection
        Input: A set D = {d1, d2, ..., dk} of deterministic finite automata (DFA) operating over an alphabet \Sigma, each of which has at most |Q| states, and an integer l > 0.
        Parameter: |Q|, l
        Question: Is there a string s of length <= l such that s is accepted by every DFA in D?

      • Fixed-parameter tractability
        • A parameterized problem {k}-X is fixed-parameter (fp-)tractable if there is an algorithm for this problem which, for each instance (x,k) of the problem, runs in O(f(k)}x}^c) for some function f() and constant c.
        • Such an algorithm and problem are also said to run in O*(f(k)) time, when the focus is on the nature of the function f().
      • Example: {|\Sigma|,l}-Longest Common Subsequence is fp-tractable (brute-force combinatorics)
      • Example: {k}-Vertex Cover is fp-tractable (bounded search-tree) (Huffner et al (2008), Section 3.1)
  • Though some parameterized variants of some NP-complete problems ({|\Sigma|,l}-Longest Common Subsequence, {k}-Vertex Cover) are fixed-parameter tractable, some do not seem to be, e.g., the best known algorithms for {k}-Clique are brute-force and run in O(|V|^k|V|2) time. Are such problems fp-intractable? If so, how can we prove it? In the next lecture, we will look at techniques for answering these questions.

Thursday, January 30 (Lecture #7)
[Class Notes]

• Parameterized Complexity Theory (Cont'd)
  • Fixed-parameter (fp-)Intractability
    • Parameterized Reducibility
      • Definition
        • A parameterized problem {k}-X fixed-parameter (fp-)reduces to a parameterized problem {k'}-Y if for a given instance (x,k) and constructed instance (x',k'), the transformation runs in time O(f(k)|x|^c) for some function f() and constant c, there is a function g() such k' = g(k), and the answer to (x,k) is "Yes" if and only if the answer to (x',k') is "Yes".
        • Parameterized analogue of polynomial-time many-one reducibility, with added relation between the parameters in the two problems.
      • Properties:
        • if {k}-X fp-reduces to {k'}-Y and {k'}-Y is fp-tractable then {k}-X is fp-tractable.
        • if {k}-X fp-reduces to {k'}-Y and {k}-X is fp-intractable then {k'}-Y is fp-intractable.
        • fp-reducibility is transitive.
      • There is no formally-stated way of handling multiple parameters; however, one can generalize the k' = g(k) condition above such that for given and constructed instances {k1, k2, ..., km}-X and {k'1, k'2, ..., k'n}-Y, for each i, 1, <= i <= n, k'i = gi(k1, k2, ..., km) for some function gi().
      • Example: {t}-Subset Sum fp-reduces to {k}-0/1 Knapsack
      • Example: {t}-Subset Sum fp-reduces to {k,B}-0/1 Knapsack
      • Example: {k}-Clique fp-reduces to {k}-Independent Set
      • Example: {k}-Vertex Cover fp-reduces to {k}-Dominating Set
      • Example: {k}-Dominating Set fp-reduces to {l,|Q|}-DFA Intersection (Wareham (2001), Lemma 6)
      • Can generalize parameterized reducibility in manner analogous to general polynomial-time reducibility to relate parameterized problems and solution equivalents to allow transfer of tractability and intractability results.
        • As in classical complexity analysis, care must be taken in defining the appropriate parameterized decision problem associated with the parameterized solution problem of interest.

Monday, February 3

• Class Exam #1 Notes
  I've finished making up the first in-class exam. The exam will be closed-book. It will be 75 minutes long and has a total of 60 marks (this is not coincidental; I have tried to make the number of marks for a question approximately equivalent to the number of minutes it should take you to do it). The exam will cover material in all course lectures up to and including Lecture # 5. There will be three questions:
  • Asymptotic-worst case time complexity (4 parts / 16 marks total)
  • Class NP and polynomial-time reducibility (4 parts / 24 marks total)
  • Implications of reducibility (5 parts / 20 marks)

  I hope the above helps, and I wish you all the best of luck with this exam.

Tuesday, February 4 (Lecture #8)
[Class Notes]

• Went over answers to Assignment #1.
• Parameterized Complexity Theory (Cont'd)
  • Fixed-parameter (fp-)Intractability (Cont'd)
    • Parameterized problem classes
      • Defined in terms of bounded-input-weight and -weft solution-checking circuits
        • Consider Boolean circuits which allow NOT gates and 2-input and unbounded-#-inputs AND and OR gates, a fixed number of input-nodes, and a single output node.
        • A binary vector is of weight k if there are at most k elements in that vector whose value is 1.
        • A circuit is of weft k if there is at most k unbounded AND or OR gates on any path from an input node to the output node.
      • The W-hierarchy: FPT,W[1], W[2], ..., W[P], ..., XP
        • FPT is the class of all parameterized (decision) problems that are fixed-parameter tractable.
        • Example: {k}-Vertex Cover is in FPT.
        • W[t], t is a constant integer >= 1, is the class of all parameterized problems {k}-X whose solutions can be encoded in binary vectors of weight g(k) for some function g() and for which there is a weft-t circuit C for each distinct value of k such that the answer to an instance (x,k) is "Yes" if and only if the appropriate circuit C relative to binary input encoding (x,k) returns 1.
          • Class W[P] is like the above except is allows polynomial-weft circuits.
        • Example: {k}-Independent Set is in W[1]
        • Example: {k}-Dominating Set is in W[2]
        • XP is the class of all parameterized problems that can be solved by algorithms with running time O(g(k)|x|^{f(k)}|x|^c).
        • Example: {k}-Clique is in XP
        • Only one proper inclusion of classes (FPT is properly contained in XP); all other inclusions are, for the moment, non-proper.
    • Historical route to useful fp-intractable problems (Downey and Fellows (1999), Chapter 10)
      • Done via checking-circuit analogues of generic machine-based class reductions in classical computational complexity theory; for the most part, these problems are then used to show hardness for various W-classes relative to weighted-input versions of Satisfiability, which then reduce outward to other parameterized problems.
        • An exception was class W[1], for which a particular circuit-checking problem reduced in a particularly direct fashion to {k}-Independent Set, and propagated outwards via the reduction from {k}-Independent Set to {k}-Clique described above.
      • Most fp-intractability results for "natural" parameterized problems appear to be relative to hardness for W[1] or W[2]; moreover, almost all fp-reductions known only use polynomial time in their instance transformations.
    • What W-hardness results really means.
      • Such results do not by themselves establish fp-intractability because we don't know whether or not FPT is properly contained in W. Hence, there must always be a qualifying clause attached to an interpretation of a W-hardness result -- namely, a W-hard parameterized problem {k}-X is not fixed-parameter tractable unless FPT = W.
        • To this day, it is not known if FPT = W for any W-class in the W-hierarchy -- however, the best evidence that FPT != W is that no-one has yet found an fp-algorithm for any parameterized problem that is W-hard, {\em e.g.}, {k}-Clique.
      • As noted above, there is a dazzling array of problem classes above FPT, yielding many opportunities for proofs of membership (and hence completeness) for problems that are not fp-tractable -- however, in this course, where our focus is on ruling out fp-tractability where possible, proofs of W- or XP-hardness will be sufficient.
      • A proof of W-hardness is technically a wonderful thing, and it does confirm intuitions that a parameterized problem is in fact fp-intractable (modulo the caveats above) -- however, we may still need to be able to solve it if we cannot add more value--restricted parameters.
      • Are there alternatives? Yes, there are! To see why, we need to understand exactly what a W-hardness result means:
        if a problem is W-hard
        then there is no deterministic algorithm
        
        that gives (optimal*) solutions
        for all instances (x,k) of the problem
        in f(k)|x|^c time
        unless FPT = W.

        • Hence, there may still be usable fp-algorithms violate one or more of the italicized clauses above, e.g., parameterized randomized and/or approximation algorithms (see Downey (2012) and references).

Thursday, February 6

• Blizzard; university closed

Tuesday, February 11 (Lecture #9)
[Class Notes]

• Parameterized Complexity Analysis (Wareham (1999), Section 2.1.3)
  • Modes of parameterized complexity analysis
    • Single-parameter analyses
      • Done in situations where only a single known parameter of a problem is of interest. If the problem is fixed-parameter tractable relative to that parameter, want the best possible algorithm in terms of running time.
      • Such analyses are typically characterized by so-called "FPT races", in which progressively more complex algorithms are developed to improve runtime (FPT Race Home Page).
      • Example: FPT race for Vertex Cover:

        Runtime	Reference
        O(kn + 2^{k}k^{2k+2})	Buss and Goldsmith (1993)
        O(kn + 2^{k}k^2)	Downey and Fellows (1995)
        O(kn + 1.324718^{k}k^2)	Balasubramanian et al (1998)
        O(kn + 1.31951^{k}k^2)	Downey et al (1999)
        O(kn + 1.29175^{k}k^2)	Stege and Fellows (1999)
        O(kn + max(1.25542^{k}2^k, 1.2906^{k}k))	Niedermeier and Rossmanith (1999)
        O(kn + 1.2906^k)	Niedermeier and Rossmanith (2000)
        O(kn + 1.286^k)	Chen et al (2001)
        O(kn + 1.2832^{k}k^{1.5})	Niedermeier and Rossmanith (2003)
        O(kn + 1.2738^k)	Chen et al (2010)

    • Multi-parameter analyses
      • Done in situations where one wants to characterize relative to which combinations of parameters fp algorithms are and are not possible for a problem; subsequent analysis may then, depending on the specific situations of real-world interest, focus on developing the best-possible algorithms relative to the parameters whose values are restricted in those situations.
        • Intent is not to consider all possible parameters of a problem but only those of restricted value in the cases of interest.
        • You can also include some parameters whose values are unbounded for completeness; however, beware of over-interpreting fp-tractability results relative to sets of parameters that together bound problem instance size as a whole. e.g., {k,n}-Longest Common Subsequence.
      • Such analyses are typically characterized by investigation of the parameterized complexity of a problem relative to all possible combinations of a given set of parameters (systematic parameterized complexity analysis), with brute-force combinatorics fp-algorithms used as quick-and-dirty "placeholders" to establish fp-tractability.
        • Such results displayed in tables called intractability maps whose entries correspond to all combinations of the given parameters.
      • Example: Intractability map for Dominating Set wrt {k,d}

        	--	d
        --	NP-c	not in XP
        k	W[2]-c	FPT

      • Example: Intractability map for Longest Common Subsequence wrt {k, l, |\Sigma|}

        		|\Sigma|
        	--	Prm	Con
        --	NP-c	not in XP	NP-c
        k	W[t]-h	W[t]-h	W[1]-c
        l	W[2]-h	FPT	FPT
        k,l	W[1]-c	FPT	FPT

  • Fixed-parameter algorithm design techniques (Huffner et al (2008); see also Sloper and Telle (2008))
    • Brute-force combinatorics
      • Use basic combinatorial rules to describe naive brute-force algorithms that examine all possible candidate solutions to a problem, e.g.,
        • Number of subsets of an item-set of size n = 2^n.
        • Number of ways of choosing k elements from an item-set of size n <= n^k.
        • Number of permutations of an item-set of size n = n! <= n^n.
        • Number of nodes in a tree with node branching-factor d and depth k = d^k.
        • Number of strings of length l over an alphabet \Sigma = |\Sigma|^l.
        • Number of strings of length <= l over an alphabet \Sigma <= l * |\Sigma|^l.
      • Example: {|\Sigma|,l}-Longest Common Subsequence is fp-tractable
        • See if any of the possible strings of length l is an subsequence of each of the k given strings of length <= n; as each such pairwise subsequence computation can be done in time O(ln), the algorithm as a whole runs in O(|\Sigma|^l * kln) time.
      • When combined with algebraic inequalities relating the values of parameters, any one such algorithm may imply others.
      • Example: {k,n}-Longest Common Subsequence is fp-tractable
        • Note that l <= n and |\Sigma| <= kn; hence, the runtime of the algorithm above can be rephrased as O(kn^n * kln).
      • Are such algorithms terrible wrt runtime? Most certainly. However, they are typically very easy to derive and hence good quick-and-dirty ways of establishing initial fp-tractability before applying more complex methods.
    • Bounded search trees
      • Essentially, bounded search trees are brute-force search trees in which either the node branching-factor is a constant and the depth is a function of the parameter, e.g., {k}-Vertex Cover, or both the branching-factor and the depth are functions of the paramete., e.g., {k,d}-Dominating Set and {d}-Center String.
      • A crucial aspect of problems having such trees is that ant instance of that problem can be decomposed into regions of size bounded by some function of the parameter in which local decisions can be made about what parts of that region are in some solution to that instance of the problem.
      • Example: {k}-Vertex Cover is fp-tractable
      • Example: {k,d}-Dominating Set is fp-tractable

Thursday, February 13

• Test #1

Tuesday, February 18

• Midterm break; no lecture

Thursday, February 20 (Lecture #10)
[Class Notes]

• Went over answers to Test #1.
• Parameterized Complexity Analysis (Cont'd)
  • Fixed-parameter algorithm design techniques (Cont'd)
    • Bounded search trees (Cont'd)
      • Example: {d}-Center String is fp-tractable (Huffner et al (2008), Section 3.3).

Tuesday, February 25 (Lecture #11)
[Class Notes]

• Parameterized Complexity Analysis (Cont'd)
  • Fixed-parameter algorithm design techniques (Cont'd)
    • Kernalization
      • Essentially, this technique involves applying reduction rules to a given problem-instance I which are guaranteed to reduce this instance to an equivalent instance I' whose size is bounded by some function of the parameter. If this reduction process is itself fp-tractable wrt the parameter, the reduced instance I' can be solved in fp-tractable time wrt the parameter by a brute-force algorithm, yielding an overall solution algorithm that is fp-tractable.
      • Example: {k}-Vertex Cover is fp-tractable (Huffner et all (2008), Section 2.1).
      • This technique is universal, because it is known that a problem is fp-tractable wrt if only if it is kernalizable (Huffner et al (2008), Theorem 2.1).
      • Example: {k}-Dominating Set is not kernalizable (Huffner et al (2008), p.11).
      • Many kernalizations yield reduced instances of problem instances encountered in practice that are dramatically smaller then the proved theoretical upper bounds.
      • In some cases, kernalization can be combined with bounded search trees to yield faster (albeit much more complex) fp-tractable algorithms (Huffner et al (2008), Section 3.4).
    • There are many other techniques that yield fp-tractable algorithms, e.g., iterative compression, dynamic programming in bounded-treewidth graphs (see Sections 3.3 and 4 of Downey (2012)); however, these tend to be more complex.
    • Many fp-tractable algorithm techniques are applicable only to or have been mainly applied to graph-based problems, but with a bit of ingenuity, come of these techniques can be applied to non-graph problems, e.g., {d}-Center String.
    • Don't forget reductions to parameterized problems known to be in FPT -- these can also yield nice fp-tractable algorithms.
  • Deriving fp-reductions
    • Literature search
      • The single most important rule when doing fp-reductions is don't -- see if an existing NP-hardness reduction in the published computer science literature does what you need it to do wrt the parameters of interest.
        • Remember to focus on reductions from problems that are known to be fp-intractable relative to at least one parameter, e.g., {k}-Clique -- if no such results are known, you probably won't get fp-intractability results out of that reduction. Existing compendiums of parameterized in tractability results such as Appendix A in Downey and Fellows (1999) or Cesati (2006) are invaluable in ensuring this.
        • Look at the original reduction used to show NP-hardness as well as simplifications or variants in textbooks such as Cormen et al (2001).
        • If your parameter of interest is the value of a solution, looking at approximability-preserving reductions may be good idea (see Ausiello et al (1999) and references).
      • If existing reductions show that the problem is NP-hard when the parameters of interest are constants, you get particularly strong fp-intractability results.
        • Proof (sketch): If such a problem is in XP relative to the parameter of interest, then the corresponding XP algorithm could be applied to the case where the parameter is a constant to give a purely (not just effectively) polynomial-time algorithm. However, as the problem is NP-hard in that case, you have a polynomial-time algorithm for an NP-hard problem, which implies that P = NP.
        • Example: {k}-Graph Coloring is not in FPT unless P = NP
        • Example: {d}-Dominating Set is not in FPT unless P = NP
    • Doing new reductions
      • Use "standard" reduction design techniques (see Chapter 3 of Garey and Johnson (1979))
        • Reduction by restriction, e.g., {t}-Subset Sum fp-reduces to {B,k}-0/1 Knapsack.
        • Reduction by local replacement,e.g., {k}-Vertex Cover fp-reduces to {k}-Dominating Set
        • Reduction by component design ("gadgeteering"), .e.g., {k}-Dominating Set fp-reduces to {l,|Q|}-DFA Intersection.
      • Two particularly useful gadgeteering frameworks:
        • FP-reducing from the W[1]-complete problem {k}-Clique
          • Structure reduction as follows:
            • Candidate solution generation: Select k elements from V, verify that these elements are not repeated in the selection, and impose an order v1, v2, ... vk on these elements..
            • Candidate solution checking: For each pair of selected elements vi, vj, 1 <= i < j <= k, ensure that there is an edge between vi and vj in G.
          • As the number of candidate solution checking mechanisms in the constructed instance is a function of k, this is a nice framework for getting fp-intractability results relative to that parameter in the constructed instance.
          • Example: {k}-Clique fp-reduces to {l,k}-DFA Intersection
        • FP-reducing from the W[2]-complete problem {k}-Dominating Set
          • Structure reduction as follows:
            • Candidate solution generation: Select k elements from V and verify that these elements are not repeated in the selection.
            • Candidate solution checking: For each vertex v in G, ensure that for some selected element vi that either v = vi or there is an edge between v and vi in G, i.e., each vertex-neighbourhood in G contains at least one element of the selected elements.
          • The number of candidate solution checking mechanisms in the constructed instance is now a function of |V|; however, as these individual mechanisms are typically very simple, this type of reduction will often yield fp-intractability results relative to parameters characterizing individual mechanisms in the constructed instance.
          • Example: {k}-Dominating Set fp-reduces to {l,|Q|}-DFA Intersection
        • These frameworks gain their power from the folklore observation within the parameterized community that problems in W[1] are characterized by local constraints between elements in a candidate solution (e.g., {k}-Clique) while problems in W[2] are characterized by non-local constraints (e.g., {k}-Dominating Set).
      • Remember to focus on reductions from NP-hard problems that are known to fp-intractable relative to at least one parameter, e.g., {k}-Clique -- if you are lucky, the same reduction will often give you NP- and W-hardness!
    • Always double check that the problem you are reducing from is in fact fp-intractable relative to the parameter you are using in that problem. Given that each problem has many possible parameters and the parameterized complexity of the problem wrt each of these parameters varies wildly, mistakes are very easy to make.
    • Example: Though we know that {t}-Subset Sum fp-reduces to {B,k}-0/1 Knapsack, this does not imply anything for {B,k}-0/1 Knapsack as Subset Sum is only known to be fp-intractable relative to k, not t.
  • Propagating fp-results in multi-parameter analyses
    • Given a set of n parameters of interest, doing a systematic parameterized analysis relative to these parameters may seem initially daunting as there are 2^n -1 parameter-subsets that need to be evaluated. However, by exploiting simple relationships between parameter-sets, one can often get away with deriving only a small number of seed results to populate all entries in an intractability map.
    • Exploiting subset / superset relationships
      • Lemma 1 (Lemma 2.1.30, Wareham (1999)): Given two parameter-sets S and S' for a problem \Pi, if {S'}-\Pi is fp-tractable and S' \subseteq S then {S}-\Pi is fp-tractable.
      • Example: {|\Sigma|,l.k}-Longest Common Subsequence is fp-tractable.
      • Lemma 2 (Lemma 2.1.31, Wareham (1999)): Given two parameter-sets S and S' for a problem \Pi, if {S}-\Pi is C-hard and S' \subseteq S then {S'}-\Pi is C-hard.
      • Example: {|Q|}-DFA Intersection is W[2]-hard.
      • Contrawise to reducibility, fp-tractability travels forwards along the parameter-set subset relation and fp-intractability travels backwards.
      • Given these relationships, two good rules of thumb are to prove fp-tractability relative to the smallest possible sets of parameters and prove fp-intractability relative to the largest possible sets of parameters.
    • Exploiting numerical parameter relationships
      • Given two sets S and S' of numerical-valued parameters for a problem \Pi, we say S <= S' if for s \in S, there is a function g_s() such that s <= g_s(S').
      • Example: In the problem Longest Common Subsequence, {m} <= {x} where x is the length of the shortest given string because there cannot be a subsequence of all of the given strings that is longer than x.
      • Lemma 3 (Lemma 2.1.33, Wareham (1999)): Given two numerical-valued parameter-sets S and S' for a problem \Pi, if {S}-\Pi is fp-tractable and S <= S' then {S'}-\Pi is fp-tractable.
      • Example: {k,n}-Longest Common Subsequence is fp-tractable
      • Lemma 4 (Lemma 2.1.34, Wareham (1999)): Given two numerical-valued parameter-sets S and S' for a problem \Pi, if {S'}-\Pi is C-hard and S <= S' then {S}-\Pi is not fp-tractable unless FPT = C.
      • Contrawise to reducibility, fp-tractability travels forwards along the <= parameter-set relation and fp-intractability travels backwards.
    • Example: Deriving the intractability map for Receiver (van Rooij et al (2011))
      • Done relative to parameter-set {|A|, 1 - p, |GI|, |GC|}.

        	--	|GI|	|GC|	|GI|, |GC|
        --	???	???	???	???
        |A|	???	???	???	???
        1 - p	???	???	???	???
        |A|, 1 - p	???	???	???	???

      • Theorem A: Receiver is NP-hard.

        	--	|GI|	|GC|	|GI|, |GC|
        --	NP-h	???	???	???
        |A|	???	???	???	???
        1 - p	???	???	???	???
        |A|, 1 - p	???	???	???	???

      • Theorem C: {|G|,|GC|}-Receiver is fp-tractable.

        	--	|GI|	|GC|	|GI|, |GC|
        --	NP-h	???	???	FPT
        |A|	???	???	???	FPT
        1 - p	???	???	???	FPT
        |A|, 1 - p	???	???	???	FPT

      • Corollary A: {|A|,|GI|}-Receiver is fp-intractable

        	--	|GI|	|GC|	|GI|, |GC|
        --	NP-h	X	???	FPT
        |A|	X	X	???	FPT
        1 - p	???	???	???	FPT
        |A|, 1 - p	???	???	???	FPT

      • Theorem D: {|A|,1-p,|GC|}-Receiver is fp-intractable

        	--	|GI|	|GC|	|GI|, |GC|
        --	NP-h	X	X	FPT
        |A|	X	X	X	FPT
        1 - p	X	???	X	FPT
        |A|, 1 - p	X	???	X	FPT

      • Corollary B: {|GI|,1-p}-Receiver is fp-tractable

        	--	|GI|	|GC|	|GI|, |GC|
        --	NP-h	X	X	FPT
        |A|	X	X	X	FPT
        1 - p	X	FPT	X	FPT
        |A|, 1 - p	X	FPT	X	FPT

  • Example: Deriving the intractability map for DFA Intersection wrt parameter-set {k,l,|Q|, |\Sigma|} when k <= |Q| (Wareham (2001), Section 3.1).
    • Starting point:

      	--	l	|\Sigma|	l, |\Sigma|
      --	???	???	???	???
      k	???	???	???	???
      |Q|	???	???	???	???
      k, |Q|	???	???	???	???

    • DFA Intersection NP-hard when |\Sigma| = 2 (Theorem 8(1))

      	--	l	|\Sigma|	l, |\Sigma|
      --	NP-h	???	???	???
      k	???	???	???	???
      |Q|	???	???	???	???
      k, |Q|	???	???	???	???

    • {l, |\Sigma|}-DFA Intersection is fp-tractable (Theorem 8(2))

      	--	l	|\Sigma|	l, |\Sigma|
      --	NP-h	???	???	FPT
      k	???	???	???	FPT
      |Q|	???	???	???	FPT
      k, |Q|	???	???	???	FPT

    • {k, |Q|}-DFA Intersection is fp-tractable (Theorem 8(3)).

      	--	l	|\Sigma|	l, |\Sigma|
      --	NP-h	???	???	FPT
      k	???	???	???	FPT
      |Q|	???	???	???	FPT
      k, |Q|	FPT	FPT	FPT	FPT

    • {|Q|,|\Sigma|}-DFA Intersection is fp-tractable (Theorem 8(4)).

      	--	l	|\Sigma|	l, |\Sigma|
      --	NP-h	???	???	FPT
      k	???	???	???	FPT
      |Q|	???	???	FPT	FPT
      k, |Q|	FPT	FPT	FPT	FPT

    • {k, l}-DFA Intersection is W[1]-hard (Theorem 8(5)).

      	--	l	|\Sigma|	l, |\Sigma|
      --	NP-h	X	???	FPT
      k	X	X	???	FPT
      |Q|	???	???	FPT	FPT
      k, |Q|	FPT	FPT	FPT	FPT

    • {l, |Q|}-DFA Intersection is W[2]-hard (Theorem 8(6)).

      	--	l	|\Sigma|	l, |\Sigma|
      --	NP-h	X	???	FPT
      k	X	X	???	FPT
      |Q|	X	X	FPT	FPT
      k, |Q|	FPT	FPT	FPT	FPT

    • {k, |\Sigma|}-DFA Intersection is W[t]-hard, t \geq 1, when |\Sigma| = 2 (Theorem 8(7)).

      	--	l	|\Sigma|	l, |\Sigma|
      --	NP-h	X	X	FPT
      k	X	X	X	FPT
      |Q|	X	X	FPT	FPT
      k, |Q|	FPT	FPT	FPT	FPT

    • {|\Sigma|}-DFA Intersection is not in XP unless P = NP (Theorem 8(8)).

      	--	l	|\Sigma|	l, |\Sigma|
      --	NP-h	X	X	FPT
      k	X	X	X	FPT
      |Q|	X	X	FPT	FPT
      k, |Q|	FPT	FPT	FPT	FPT

Thursday, February 27 (Lecture #12)
[Class Notes]

• Parameterized Complexity Analysis: Case Studies
  • Analogy Derivation in Structure Mapping Theory (van Rooij et al (2008))

Tuesday, March 4

• Intructor sick; class cancelled.

Wednesdcay, March 5

• Class Exam #2 Notes
  I've almost finished making up the second in-class exam. The exam will be closed-book. It will be 75 minutes long and has a total of 50 marks (this is not coincidental; I have tried to make the number of marks for a question approximately equivalent to the number of minutes it should take you to do it). The exam will cover material in all course lectures up to and including Lecture # 11. There will be three questions:
  • Parameterized intractability maps (2 parts / 10 marks total)
  • Parameterized classes and reducibility (3 parts / 10 marks total)
  • Implications of parameterized reducibility (4 parts / 20 marks)

  I hope the above helps, and I wish you all the best of luck with this exam.

Thursday, March 6 (Lecture #13)
[Class Notes]

• Parameterized Complexity Analysis: Case Studies (Cont'd)
  • Re-representation-augmented analogy Derivation in Structure Mapping Theory (Wareham et al (2012))

Tuesday, March 11 (Lecture #14)
[Class Notes]

• Went over answers to Assignment #2.
• Parameterized Complexity Analysis: Case Studies (Cont'd)
  • Phonological processing using Simplified Segmnental Grammars (Wareham (1999), Section 4.1)

Thursday, March 13

• Test #2

Tuesday, March 18 (Lecture #15)
[Class Notes]

• Went over answers to Test #2.
• Parameterized Complexity Analysis: Case Studies (Cont'd)
  • Phonological processing using Simplified Segmnental Grammars (Wareham (1999), Section 4.1) (Cont'd)
  • Computing using non-deterministic Turing machines and context-sensitive grammars (Cai et al (1997))

Thursday, March 20

• Project Presentation #1

Tuesday, March 25 (Lecture #16)
[Class Notes]

• Parameterized Complexity Analysis: Case Studies (Cont'd)
  • 3D Robot Motion Planning (Cesati and Wareham (1995))
  • Designing reactive robots (Wareham et al (2011))

Thursday, March 27 (Lecture #17)
[Class Notes]

• Parameterized Complexity Analysis: Case Studies (Cont'd)
  • Designing reactive robots (Wareham et al (2011)) (Cont'd)

Tuesday, April 1

• Departmental graduate research forum; class cancelled.

Thursday, April 3 (Lecture #18)
[Class Notes]

• Parameterized Complexity Analysis: Case Studies (Cont'd)
  • Designing swarms of reactive robots (Wareham (2013))

Monday, April 14

• Project Presentation #2

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.
• 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.
• Bodlaender, H., Downey, R.G., Fellows, M.R., Hallett, M.T., and Wareham, T. (1995a) "Parameterized Complexity Analysis in Computational Biology." Computer Applications in the Biosciences, 11(1), 49-57.
• Bodlaender, H., Downey, R.G., Fellows, M.R., and Wareham, T. (1995b) "The Parameterized Complexity of Sequence Alignment and Consensus." Theoretical Computer Science, 147(1-2), 31-54.
• Cai, L., Chen, J., Downey, R.G., and Fellows, M.R. (1997) "On the parameterized complexity of short computation and factorization." Archives of Mathematics and Logic, 36, 321-337. (PDF)
• Cesati, M. (2006) Compendium of Parameterized Problems. (PDF)
• Cesati, M. and Wareham, T. (1995) "Parameterized Complexity Analysis in Robot Motion Planning." In Proceedings of the 25th IEEE International Conference on Systems, Man, and Cybernetics: Volume 1. IEEE Press; Los Alamitos, CA. 880-885. (PDF)
• Cook, S. (1971) The complexity of theorem proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing. ACM Press; New York. 151-158.
• Cormen, C.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2001) Introduction to Algorithms (Second Edition). The MIT Press.
• Downey, R. (2012) "A Basic Parameterized Complexity Primer." In H.L. Bodlaender, R.G. Downey, F.V. Fomin, and D. Marx (eds.) The Multivariate Algorithmic Revolution and Beyond. Lecture Notes in Computer Science no. 7370. Springer. 91-128. (PDF)
• 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. 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.
• Huffner, F., Niedermeier, R., and Wernicke, S. (2008) "Techniques for Practical Fixed-Parameter Algorithms." Computer Journal, 51(1), 7-25. (PDF)
• Johnson, D.S. (1990) A catalog of complexity class. In J. van Leeuwen (ed.) Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity. The MIT Press; Cambridge, MA. 67-162.
• Karp, R.M. (1972) Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher (eds.) Complexity of Computer Computations. Plenum Press. 85-103.
• Motwani, R. and Raghavan, P. (1995) Randomized Algorithms. Cambridge University Press.
• Niedermeier, R. (2006) Invitation to Fixed-Parameter Algorithms. Oxford University Press.
• 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.
• Sloper, C. and Telle, J.A. (2008) "An overview of techniques for designing parameterized algorithms." Computer Journal, 51(2), 122-136. (PDF)
• van Rooij, I., Evans, P., Muller, M., Gedge, J., and Wareham, T. (2008) "Identifying Sources of Intractability in Cognitive Models: An Illustration using Analogical Structure Mapping." In B.C. Love, K. McRae, and V.M. Sloutsky (eds.) Proceedings of the 30th Annual Meeting of the Cognitive Science Society. Cognitive Science Society; Austin, TX. 915-920. (PDF (paper)/ PDF (supplmentary materials))
• van Rooij, I., Kwisthout, J., Blokpoel, M., Szymanik, J., Wareham, T., and Toni, I. (2011) "Intentional Communication: Computationally Easy or Difficult?" Frontiers in Human Neuroscience, 5. DOI: 10.3389/fnhum.2011.00052.
• Wareham, T. (1999) Systematic Parameterized Complexity Analysis in Computational Phonology. Ph.D. thesis, Department of Computer Science, University of Victoria. (PDF)
• Wareham, T. (2001) "The Parameterized Complexity of Intersection and Composition Operations on Sets of Finite-State Automata." In Proceedings of the Fifth International Conference on Implementation and Application of Automata. Lecture Notes in Computer Science no. 2088. Springer-Verlag; Berlin. 302-310. (PDF)
• Wareham, T., Kwisthout, J., Haselager, W., and van Rooij, I. (2011) "Ignorance is Bliss: A Complexity Perspective on Adapting Reactive Architectures." In the Proceedings of the First Joint IEEE International Conference on Development and Learning and on Epigenetic Robotics (Volume 2). 1-5. DOI: 10.1109/DEVLRN.2011.6037337. (PDF (paper)/ PDF (supplmentary materials))
• Wareham, T., Robere, R., and van Rooij, I. (2012) "A Change for the Better? Assessing the Computational Cost of Re-Representation." In N. Russwinkel, U. Drewitz, and H. van Rijn (eds.) Proceedings of ICCM 2012: 11th International Conference on Cognitive Modeling. TU Berlin. 111-116. (PDF (paper)/ PDF (supplmentary materials))
• Wareham, T. (2013) "Educating Genghi: A Complexity Perspective on Designing Reactive Swarms." AIfternoon talk, Donders Institute for Brain, Cognition, and Behaviour, Radboud University Nijmegen, The Netherlands.

Created: December 12, 2013
Last Modified: March 24, 2014