NP-hardness reductions

  • NP-hardness (Wikipedia) ↗
  • NP-completness of 21 classical problems was shown by Karp in paper published 1972 – Reducibility Among Combinatorial Problems.
  • Assumption: $P \ne NP$

We list many problems one may want to reduce from to show NP-hardness.

  • Satisfiability (SAT)
    • Problem: Is a formula satisfiable?
    • Shown to be NP-complete by the Cook–Levin theorem ↗.
    • Reduction is from a non-deterministic machine that solves an NP problem in polynomial time.
  • Satisfiability in conjunctive normal form (CNFSAT)
    • By alteration of the Cook–Levin theorem one can get CNF. (mentioned here ↗ in Consequences section)
  • Satisfiability in CNF with at most 3 literals per clause (3-SAT or 3-CNFSAT)
    • Split every clause of CNF (a or b or c or d) into (a or b or x) and (not x or c or d). Size of the new formula is linear wrt. to the old one. (Karp)
  • 0-1 Integer Programming
  • Clique
    • Problem: Does a graph contain a clique of size at least k?
  • Independent Set
    • Problem: Does a graph contain an independent set of size at least k?
    • Is NP-hard on 3-regular graphs. (noted on page 428 of PA)
  • Set Packing
  • Vertex Cover
    • Problem: Is there a set of k vertices such that every edge is incident to at least one of them?
  • Set Cover
    • Problem: For a system F over universe U, is there a subset of F with at most k elements such that their union is U?
  • Feedback Vertex Set
    • Problem: Does graph contain at most k vertices whose removal makes the graph tree?
  • Feedback Edge Set
    • Problem: Does graph contain at most k edges whose removal makes the graph tree?
  • Directed Hamilton Cycle
  • Undirected Hamilton Cycle
  • Chromatic Number
    • Problem: Does the graph have a proper coloring with k colors?
  • Clique Cover
    • Problem: Is it possible to partition the graph to cliques?
  • Exact Cover
  • Hitting Set
  • Steiner Tree
  • 3-Dimensional Matching
  • Knapsack
  • Job Sequencing
  • Partition
  • Max Cut

W[1]-hardness and W[2]-hardness reductions

The book Parameterized Algorithms (PA) lists several W[1]- and W[2]-hard and complete problems. Several novel problems are also included in the list.

W[1]-hard problems

Assumption: $W[1] \ne FPT$

  • Clique
    • Problem: Does a graph contain a clique of size at least k?
    • Parameter: size of the clique k
  • Clique on regular graphs
    • Problem: Does a regular graph contain a clique of size at least k?
    • Parameter: size of the clique k
    • Reduction from Clique: Let d be max degree of G. Take d copies of G. Create d-N(v) new vertices for each v in V(G) and connecet them to every copy of v in the copies of the graph. (Theorem 13.4, PA)
  • Multicolored Clique (on r-regular graphs)
    • Problem: Does a k-vertex colored graph contain a rainbow clique of size k?
    • Parameter: size of the clique k
    • Polynomial-time reduction from Clique on r-Regular Graphs: Create k copies of V(G) where each copy has its own color. Connect two vertices of different colors iff the original vertices were originally adjacent. (Theorem 13.7, PA)
  • (Multicolored) Independent Set (on r-regular graphs)
    • Problem: Does a graph contain an independent set of size at least k?
    • Parameter: size of the independent sum k
    • Polynomial-time reduction from Clique: Independent set on G is a clique on the complement of G. Parameter does not change. (page 425, PA)
    • reduction from Short Turing Machine Acceptance (see page 441, PA)
    • Regular variant
      • Is FPT for constant r (noted on page 428, PA)
      • Is FPT for combined parameter k+r (noted on page 428, PA)
  • Partial Vertex Cover
    • Problem: For a graph G and integers k and s. Is there a set of k vertices that is incident to at least s distinct edges?
    • Parameter: size of the set of vertices k
    • Polynomial-time reduction from Independent Set on r-Regular Graphs: The r-regular graph G has independent set of size k iff it has k vertices that cover rk edges. (Theorem 13.6, PA)
    • Is FPT for parameter s. (page 428, PA)
  • Grid Tiling
  • Grid Tiling with <=
  • Multidimensional Subset Sum
    • Problem: We have n of d-dimensional vectors A and one d-dimensional vector c. Is there a subset of A so that its sum equals to c?
    • Parameter: the number of dimensions d
  • Relaxed Multidimensional Subset Sum
    • Problem: We have n of d-dimensional vectors A and one d-dimensional vector c. Is there at most d-element subset of A so that its sum equals to c?
    • Parameter: the number of dimensions and size of the chosen subset d
  • Short Turing Machine Acceptance
    • Problem: We are given a nondeterministic Turing machine, input string, and an integer k. Does the Turing machine accept the input string in at most k steps? (page 440, PA)
    • Parameter: the number of steps k
    • reduction from from Independent Set: Use non-determinism to choose a vertex k times and check that there are no edges between the chosen vertices. (page 443, PA)
  • Balanced Vertex Separator
    • Problem: Given a graph G and an integer k, is there a set S of at most k vertices such that every connected component of V(G) / S has at most |V(G)|/2 vertices?
    • Parameter: size of the separator k
    • reduction from Clique (Theorem 13.29, PA)
  • List Coloring
    • Problem: Given a graph G, colors C, and a list of possible colors for each vertex, decide whether there is a proper graph coloring.
    • Parameter: the treewidth of G
    • Polynomial-time reduction from Multicolored Independent Set: New colors represent old vertices. Make one vertex per color class. For each edge have a vertex that contains colors respective to incident vertices. List coloring may not both adjacent vertices as there would be no color left for the vertex which represents the edge. (Theorem 13.30, PA)
  • Odd Set
    • Problem: For a system F over a universe U and an integer k, is there a subset S of U of size at most k such that the intersection of S and every element of F has odd size.
    • Parameter: size of the subset k
    • Polynomial-time reduction from Multicolored Clique (Theorem 13.31, PA)
  • Exact Odd Set (page 456, PA)
  • Exact Even Set (page 456, PA)
  • Unique Hitting Set (page 456, PA)
  • Exact Unique Hitting Set (page 456, PA)
  • Strongly Connected Steiner Subgraph (page 457, PA)
    • Polynomial-time reduction from Multicolored CLique: Represent vertices and edges. Apex vertex for vertices connected with bi-directed edges. Also apex vertex for every pair of colors over edges. Steiner set are the apex vertices. Connect adjacent vertices via a directed path through the incident edge. To be strongly connected the set must contain one of each color vertex and pair-colroed edges; plus, there they must be all connected via the short paths. (Theorem 13.33, PA)

W[2]-hard problems

  • Dominating Set
    • Problem: For a graph G and an integer k. Is there a set of vertices of size at most k such that the union of their closed neighborhoods is V(G)?
    • Parameter: k
    • Polynomial-time reduction from Multicolored Independent Set (showing only W[1]-hardness): Copy the vertices. Connect color classes by clique and connect them to 2 auxiliary vertices to ensure DS chooses each color exactly once. For every edge in G create a vertex that is connected to all vertices of respective colors with exception of the edge’s endpoints, ensuring that both cannot be chosen. (Theorem 13.9, PA)
  • Dominating Set on Directed Graphs
    • Problem: For an oriented graph G and an integer k. Is there a set of vertices of size at most k such that the union of their closed out-neighborhoods is V(G)?
    • Parameter: k
    • Polynomial-time reduction from Dominating Set: Replace each edge with two directed edges in both directions. (noted on page 431, PA)
  • Dominating Set with Pattern
    • Problem: For a graph G, set of its vertices A, and an integer k. Is there a subset of A of size at most k such that the union of its closed neighborhoods is V(G)?
    • reduction, (page 445, PA)
  • Set Cover
    • Problem: For a system F over a universe U, is there a subset of F with at most k elements such that their union is U?
    • Parameter: number of sets in the solution k
    • Polynomial-time reduction from Dominating Set: Create sets for closed neighborhoods. (Theorem 13.10, PA)
    • Polynomial-time reduction from Dominating Set for Directed Graphs: Create sets for closed out-neighborhoods. (noted on page 431, PA)
  • Dominating Set on Tournaments (see Dominating Set on Directed Graphs)
    • reduction from Set Cover: non-trivial (Theorem 13.14, PA)
  • Connected Dominating Set
    • Problem: Is there a Dominating Set of size at most k that is connetced?
    • Polynomial-time reduction from Dominating Set: Create a sibling for every vertex that is connected to its original. Then connect all siblings with a clique. Solution can always be moved into the siblings but covers only neighborhoods in the original graph. Solution in the sibling clique is connected. (Theorem 13.15, PA)

W[t]-hard problems

First several ropes.

  • Boolean circuit is directed acyclic graph; there are inputs, one output, negations, ANDs, and ORs. It is evaluated as one would expect.
  • Weft is the maximum number of vertices with non-constant in-degree on path from inputs to outputs in a boolean circuit.
  • Weighted Circuit Satisfiability (WCS)
    • Problem: For a given boolean circuit and an integer k, is there an input assignment with exactly k inputs set to True such that the output is True?

The following problem defines the W[k] classes.

  • Weighted Circuit Satisfiability (WCS) of weft t
    • Problem: For a given boolean circuit of weft t and an integer k, is there an input assignment with exactly k inputs set to True such that the output is True?

Problem P is in W[t] if there is a parameterized reduction from P to WCS on boolean circuits of weft t and fixed depth d. Problem P is in W[t]-hard if there is a parameterized reduction from WCS on boolean circuits of weft t and fixed depth d to P.

  • Reduction from Independent Set to WCS: First negate vertices, join edges with OR, join all ORs with AND. One cannot choose two inputs that have an edge. Has weft 1, hence Independent Set is in W[1] (page 437, PA)
  • Reduction from WCS to Independent Set (showing W[1]-hardness): non-trivial (noted on page 437, PA)

The following are W[t]-complete (page 438, PA)

For even t >= 2

  • Weighted t-normaliezd Satisfiability
  • Weighted Monotone t-normaliezd Satisfiability
  • Weighted Monotone (t+1)-normaliezd Satisfiability

For odd t >= 3

  • Weighted t-normaliezd Satisfiability
  • Weighted Antimonotone t-normaliezd Satisfiability
  • Weighted Antimonotone (t+1)-normaliezd Satisfiability