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)
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?
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.
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 |
Which method you use depends on the intricacy of the given algorithm.
This allows (to a degree) for instructions whose running-times differ by a constant multiplicative factor on different machines.
Polynomial-time solvability <------------- A reduces to B reduces to C -------------> Polynomial-time unsolvability
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.
VERTEX-COVER-COST(G) k = 1 while not VERTEX-COVER-DECISION(G,k) do k = k + 1 return(k)
VERTEX-COVER-DECISION(G, k) if (VERTEX-COVER-COST(G) <= k then return(TRUE) else return(FALSE)
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)
VERTEX-COVER-DECISION(G, k) if (cost(VERTEX-COVER-EXAMPLE(G)) <= k then return(TRUE) else return(FALSE)
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?
3-CNF Satisfiability
Input: A 3-CNF formula F.
Question: Is there a satisfying assignment
for F?
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?
{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?
I hope the above helps, and I wish you all the best of luck with this exam.
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) |
-- | d | |
-- | NP-c | not in XP |
k | W[2]-c | FPT |
|\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 |
-- | |GI| | |GC| | |GI|, |GC| | |
-- | ??? | ??? | ??? | ??? |
|A| | ??? | ??? | ??? | ??? |
1 - p | ??? | ??? | ??? | ??? |
|A|, 1 - p | ??? | ??? | ??? | ??? |
-- | |GI| | |GC| | |GI|, |GC| | |
-- | NP-h | ??? | ??? | ??? |
|A| | ??? | ??? | ??? | ??? |
1 - p | ??? | ??? | ??? | ??? |
|A|, 1 - p | ??? | ??? | ??? | ??? |
-- | |GI| | |GC| | |GI|, |GC| | ||
-- | NP-h | ??? | ??? | FPT | |
|A| | ??? | ??? | ??? | FPT | |
1 - p | ??? | ??? | ??? | FPT | |
|A|, 1 - p | ??? | ??? | ??? | FPT |
-- | |GI| | |GC| | |GI|, |GC| | ||
-- | NP-h | X | ??? | FPT | |
|A| | X | X | ??? | FPT | |
1 - p | ??? | ??? | ??? | FPT | |
|A|, 1 - p | ??? | ??? | ??? | FPT |
-- | |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 |
-- | |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 |
-- | l | |\Sigma| | l, |\Sigma| | |
-- | ??? | ??? | ??? | ??? |
k | ??? | ??? | ??? | ??? |
|Q| | ??? | ??? | ??? | ??? |
k, |Q| | ??? | ??? | ??? | ??? |
-- | l | |\Sigma| | l, |\Sigma| | |
-- | NP-h | ??? | ??? | ??? |
k | ??? | ??? | ??? | ??? |
|Q| | ??? | ??? | ??? | ??? |
k, |Q| | ??? | ??? | ??? | ??? |
-- | l | |\Sigma| | l, |\Sigma| | |
-- | NP-h | ??? | ??? | FPT |
k | ??? | ??? | ??? | FPT |
|Q| | ??? | ??? | ??? | FPT |
k, |Q| | ??? | ??? | ??? | FPT |
-- | l | |\Sigma| | l, |\Sigma| | |
-- | NP-h | ??? | ??? | FPT |
k | ??? | ??? | ??? | FPT |
|Q| | ??? | ??? | ??? | FPT |
k, |Q| | FPT | FPT | FPT | FPT |
-- | l | |\Sigma| | l, |\Sigma| | |
-- | NP-h | ??? | ??? | FPT |
k | ??? | ??? | ??? | FPT |
|Q| | ??? | ??? | FPT | FPT |
k, |Q| | FPT | FPT | FPT | FPT |
-- | l | |\Sigma| | l, |\Sigma| | |
-- | NP-h | X | ??? | FPT |
k | X | X | ??? | FPT |
|Q| | ??? | ??? | FPT | FPT |
k, |Q| | FPT | FPT | FPT | FPT |
-- | l | |\Sigma| | l, |\Sigma| | |
-- | NP-h | X | ??? | FPT |
k | X | X | ??? | FPT |
|Q| | X | X | FPT | FPT |
k, |Q| | FPT | FPT | FPT | FPT |
-- | 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 |
-- | 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 |
I hope the above helps, and I wish you all the best of luck with this exam.
Created: December 12, 2013
Last Modified: March 24, 2014