NP problems + SETH superlinear

# NP problems Why should you care? It's often common to find problems that are easily reducible to some other, more famous problem. However, if said problem is NP or its solution is too slow and you aren't aware of this, you can waste precious contest time solving an "impossible" problem. By knowing the most famous "unsolvable" problems, it's much easier to focus on the extra constraints given that make the problem solvable. ## Knapsack/subset-sum/partition Given a bag of capacity $C$ and $N$ items, each with a value $v$ and weight $w$, select the subset with largest sum whose total weight is $\leq w$. ### Case 1: C is small Can be solved in $O(NC)$. Fancy algorithms exist. If items have 0 value and you want to check if a particular sum is achievable, it can be done in $O(\frac{NC}{64})$ using bitsets (subset-sum). Still not possible to solve in $O(N+\log(C))$ even if every item can be taken an unlimited number of times. But $O(\frac{NC}{64})$ can be beaten. There are other parameterizations. Good blog: https://codeforces.com/blog/entry/98663 ### Case 2: N is small If $N \approx 20$, we can easily do it in $O(2^NN)$. If $N \approx 40$, we use "meet in the middle". Split the items into two disjoint set of roughly equal size, generate all subsets in each, and then solve your problem by combining them quickly. ## Max clique=max indep set=min vertex cover Within the IOI syllabus, no good algorithm exists. There is one in $O(\phi^N)$, but that's not very interesting. In can be solved efficiently in practice, only relevant for ICPC. KACTL's max clique algorithm handles $N \leq 150$. Bigger $N$ are possible using simulated annealing or a better clique algorithm. ### Clique=max indep set **Definition**: complement graph. Take the graph $G$ and create a new one, $G'$, as follows: if an edge exists in $G$, we do *not* add it to $G'$. If an does not exist in $G$, we *do* add to $G'$. This is called the complement graph of $G$. **Theorem**: every clique in $G$ is an independent set of the same size in its complement graph, $G'$. Proof follows from definition. ### Max indep set=vertex cover **Definition**: an independent set is *maximal* if no more vertices can be added to it. **Theorem**: if we have a maximal independent set (need not be maximum) $S$, the set of vertices $V \setminus S$ (all vertices except those in $S$) form a vertex cover. **Proof**: suppose we have a maximal independent set, whose complement is not a vertex cover. Looking at it from the vertex cover side, this implies that there is some edge $a \rightarrow b$, where neither $a$ nor $b$ is in the vertex cover. In turn, this implies that both $a$ and $b$ are in the independent set, contradicting the assumption of independence. Q.E.D. To prove the converse (non-maximal independent set is not a vertex cover), assume that we have a set $S$ that is a non-maximal independent set and a vertex cover. If it is not a maximal independent set, there exists a node $x$ not is $S$, where all its neighbours are not in $S$. This implies that all edges incident to $x$ are not covered, contradicting the assumption that we have a vertex cover. ## Max/min 2-sat Find a solution to a 2-sat instance maximizing/minimizing number of literals set to true. Note that vertex cover can be solved using min 2-sat: for every edge, we pick at least one of its endpoints. ## 3-sat ## Set cover/dominating set Harder versions of vertex cover. ## Hamiltonian path/cycle and longest path/cycle $O(2^N N^2)$ using bitmask DP is best-possible in general using reasonable algorithms. ## TSP ## Max cut Split all vertices into two disjoint sets, maximizing number of edges between them. Equivalently, select largest subset of edges such that they form a bipartite graph. Polynomial time solvable on planar graphs. Not efficiently solvable otherwise (besides $O(2^N)$). ## Counting perfect matchings in a bipartite graph Can be done using DP. Can also be solved quickly if the graph is almost complete https://codeforces.com/problemset/problem/468/E. ## 3D matching Every edge matches 3 vertices instead of 2. ## Largest biconnected subgraph ## Subgraph isomorphism ## ~Graph isomorphism ## Steiner tree https://open.kattis.com/problems/shovelling ## Degree constrained spanning tree ## Graph coloring ## Largest acyclic subset of nodes/edges ## ~Integer factorization # SETH superlinear problems A similar story exists for some polynomial-time solvable problems. You are asked to a problem with $N=10^5$, but there exist no linear-time algorithm. Note that some of these problems are interreducible. ## Longest common subsequence Best general solution: $O(\frac{NM}{64})$. https://sci-hub.st/https://doi.org/10.1016/S0020-0190(01)00182-X https://po2punkt0.kattis.com/problems/lcs Can also be solved in $O(ans \cdot min(N,M))$ by the common DP trick of swapping dimensions. Can also be solved in $O(N \log(N) \cdot \text{character with most occurences}^2)$. Hunt–Szymanski algorithm https://open.kattis.com/problems/doubledeck https://oj.uz/problem/view/IOI24_hieroglyphs ## Longest palindromic subsequence Same problem as LCS. ## Reachability queries in a DAG Best general solution: $O(\frac{NM}{64}+Q)$. In planar graphs, doable faster. https://cses.fi/problemset/task/2143 https://cses.fi/problemset/task/2138 ## Triangle counting Good general solution: ~$O(\frac{M^{1.5}}{\sqrt{64}})$. https://open.kattis.com/problems/gottacatchemall ## Given N numbers, is there a triple with sum 0 Can be solved quickly with FFT if numbers are small https://open.kattis.com/problems/aplusb ## Given a set of points, is there a line that passes through 3 or more points https://open.kattis.com/problems/findinglines ## Is the diameter of a graph 2 or 3? ## Shortest path queries In planar graphs, doable fast. https://open.kattis.com/problems/closenessqueries https://szkopul.edu.pl/problemset/problem/QHh99tBu4p9FMsFohv4da7S7/site/?key=statement ## Shortest path with negative weights Can be solved in $O(N+M)$ in DAGs. In the general case, recent research has obtained $O(Mlog(N)^3)$. However, this is unpractical. Older research has algorithms which are faster: https://web.eecs.umich.edu/~pettie/matching/Gabow-Tarjan-scaling-bipartite-matching.pdf. Implementation: https://github.com/koosaga/olympiad/blob/master/Library/codes/graph/negative_cycle_msqrtnlogw.cpp If the test data is weak, SPFA should work well too https://konaeakira.github.io/posts/using-the-shortest-path-faster-algorithm-to-find-negative-cycles.html https://open.kattis.com/problems/negativegraph ## Range mode queries ## Max plus convolution Can be done fast if convex.