14 citations · 51 across the 29 of their papers we have counts for
4 papers · 2 filters
Global and fixed-terminal cuts in digraphs
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +2
The computational complexity of multicut-like problems may vary significantly depending on whether the terminals are fixed or not. In this work we present a comprehensive study of…
Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2
We consider the following basic problem: given an -variate degree- homogeneous polynomial with real coefficients, compute a unit vector that maximize…
LP-branching algorithms based on biased graphs
Euiwoong Lee, Magnus Wahlström
We give a combinatorial condition for the existence of efficient, LP-based FPT algorithms for a broad class of graph-theoretical optimisation problems. Our condition is based on th…
Partitioning a Graph into Small Pieces with Applications to Path Transversal
Euiwoong Lee
Given a graph and an integer , we study -Vertex Seperator (resp. -Edge Separator), where the goal is to remove the minimum number of vertices (resp. edges) su…