We study a new graph separation problem called Multiway Near-Separator. Given an undirected graph $G$, integer $k$, and terminal set $T \subseteq V(G)$, it asks whether there is a vertex set $S \subseteq V(G) \setminus T$ of size at most $k$ such that in graph $G-S$, no pair of distinct terminals can be connected by two pairwise internally vertex-disjoint paths. Hence each terminal pair can be separated in $G-S$ by removing at most one vertex. The problem is therefore a generalization of (Node) Multiway Cut, which asks for a vertex set for which each terminal is in a different component of $G-S$. We develop a fixed-parameter tractable algorithm for Multiway Near-Separator running in time $2^{O(k \log k)} * n^{O(1)}$. Our algorithm is based on a new pushing lemma for solutions with respect to important separators, along with two problem-specific ingredients. The first is a polynomial-time subroutine to reduce the number of terminals in the instance to a polynomial in the solution size $k$ plus the size of a given suboptimal solution. The second is a polynomial-time algorithm that, given a graph $G$ and terminal set $T \subseteq V(G)$ along with a single vertex $x \in V(G)$ that forms a multiway near-separator, computes a 14-approximation for the problem of finding a multiway near-separator not containing $x$.

We investigate computational problems involving large weights through the lens of kernelization, which is a framework of polynomial-time preprocessing aimed at compressing the instance size. Our main focus is the weighted Clique problem, where we are given an edge-weighted graph and the goal is to detect a clique of total weight equal to a prescribed value. We show that the weighted variant, parameterized by the number of vertices $n$, is significantly harder than the unweighted problem by presenting an $O(n^{3 - \varepsilon})$ lower bound on the size of the kernel, under the assumption that NP $\not \subseteq$ coNP/poly. This lower bound is essentially tight: we show that we can reduce the problem to the case with weights bounded by $2^{O(n)}$, which yields a randomized kernel of $O(n^3)$ bits. We generalize these results to the weighted $d$-Uniform Hyperclique problem, Subset Sum, and weighted variants of Boolean Constraint Satisfaction Problems (CSPs). We also study weighted minimization problems and show that weight compression is easier when we only want to preserve the collection of optimal solutions. Namely, we show that for node-weighted Vertex Cover on bipartite graphs it is possible to maintain the set of optimal solutions using integer weights from the range $[1, n]$, but if we want to maintain the ordering of the weights of all inclusion-minimal solutions, then weights as large as $2^{Ω(n)}$ are necessary.