A graph G contains a graph H as an induced minor if H can be obtained from G by vertex
deletions and edge contractions. The class of H-induced-minor-free graphs generalizes the …

Abstract Assuming the Exponential Time Hypothesis (ETH), a result of Marx (ToC'10) implies
that there is no time algorithm that can solve 2-CSPs with k constraints (over a domain of …

Abstract In the Hedge Cut problem, the edges of a graph are partitioned into groups called
hedges, and the question is what is the minimum number of hedges to delete to disconnect …

CSP sparsification, introduced by Kogan and Krauthgamer (ITCS 2015), considers the
following question: how much can an instance of a constraint satisfaction problem be …

We provide new algorithms for constructing spanners of arbitrarily edge-or vertex-colored
graphs, that can endure up to f failures of entire color classes. The failure of even a single …

An edge‐labeled graph (ELG) G=(V, E, L) G=(V,E,L) is a graph such that VV is the set of
vertices, EE is the set of edges, LL is the set of labels (colors), and each edge e∈ E e∈E …

We introduce the following submodular generalization of the Shortest Cycle problem. For a
nonnegative monotone submodular cost function f defined on the edges (or the vertices) of …

Computer networks are often multi-layered. For simplicity, let us focus on two-layered
networks with logical layer and physical layer. Such a network can be modeled as a labeled …

Assuming the Exponential Time Hypothesis (ETH), a result of Marx (ToC'10) implies that
there is no $ f (k)\cdot n^{o (k/\log k)} $ time algorithm that can solve 2-CSPs with $ k …

In the weighted minimum Label st Cut problem, we are given a (directed or undirected)
graph G=(V, E), a label set L={1,2,...,q} with positive label weights {w}, a source s∈ V and a …