January 7, 2020 (úterý [Tuesday], 14:00, MFF UK Malá Strana, room 307)
Julia Chuzhoy, Sanjeev Khanna: Polynomial
Flow-Cut Gaps and Hardness of Directed Cut Problems. STOC
2007.
(presented by Petr Kolman)
Abstract: We study the multicut problem in
directed graphs: we are a given an n-vertex graph G along with k
source-sink pairs, and the goal is to find the minimum cardinality
subset of edges whose removal separates all source-sink pairs. The
natural linear programming relaxation for multicut corresponds, by
LP-duality, to the well-studied maximum (fractional)
multicommodity flow problem. Therefore, the integrality gap of the
linear programming relaxation for multicut is also the flow-cut
gap: the maximum ratio, achievable for any graph, between the
maximum flow value and the minimum cost solution for the
corresponding cut problem. Starting with the celebrated max
flow-min cut theorem of Ford and Fulkerson, flow-cut gaps have
played a central role in combinatorial optimization. For many
NP-hard network optimization problems, the best known
approximation guarantee corresponds to our understanding of the
appropriate flow-cut gap. Our first result is that the
flow-cut gap between maximum multicommodity flow and minimum
multicut is Ω(n^{1/7}) in directed graphs. These results
improve upon the long-standing lower bound of Ω(log n) for
flow-cut gaps. We notice that this polynomially large flow-cut gap
is in a sharp contrast to the undirected setting where both these
flowcut gaps are known to be Θ(log n).
Our second result is that directed multicut is hard to
approximate to within a factor of 2^Ω(log^{1−\epsilon} n) for any
constant \epsilon > 0, unless NP⊆ZPP. This improves upon the
recent Ω(log n/ log log n)-hardness result.
December 17, 2019 (úterý [Tuesday], 14:00, MFF UK Malá Strana, room 307)
I. Dinur, P. Manurangsi: ETH-Hardness
of Approximating 2-CSPs and Directed Steiner Network.
ITCS 2018.
(presented by Pankaj Kumar)
Abstract: We study 2-ary constraint satisfaction problems
(2-CSPs), which can be stated as follows: given a constraint
graph G=(V,E), an alphabet set Sigma and, for each edge {u,v}, a
constraint C_uv, the goal is to find an assignment sigma from V to
Sigma that satisfies as many constraints as possible, where a
constraint C_uv is said to be satisfied by sigma if C_uv contains
(sigma(u),sigma(v)).
While the approximability of 2-CSPs is quite well understood when
the alphabet size |Sigma| is constant (see e.g. [37]), many
problems are still open when |Sigma| becomes super constant. One
open problem that has received significant attention in the
literature is whether it is hard to approximate 2-CSPs to within a
polynomial factor of both |Sigma| and |V| (i.e.
(|Sigma||V|)^Omega(1) factor). As a special case of the so-called
Sliding Scale Conjecture, Bellare et al. [5] suggested that the
answer to this question might be positive. Alas, despite many
efforts by researchers to resolve this conjecture (e.g.
[39,4,20,21,35]), it still remains open to this day.
November 19 and 26, 2019 (úterý [Tuesday], 14:00, MFF UK Malá Strana, room 307)
A. Badanidiyuru, R. Kleinberg, and H. Lee: Approximating
Low-Dimensional Coverage Problems. SoCG '12, also https://arxiv.org/abs/1112.0689
(presented by Tung Anh Vu)
Abstract: We study the complexity of the maximum coverage problem, restricted to set systems of bounded VC-dimension. Our main result is a fixed-parameter tractable approximation scheme: an algorithm that outputs a (1-\eps)-approximation to the maximum-cardinality union of k sets, in running time $O(f(\eps,k,d)\cdot poly(n))$ where n is the problem size, d is the VC-dimension of the set system, and f(\eps,k,d) is exponential in (kd/\eps)^c for some constant c. We complement this positive result by showing that the function $f(\eps,k,d)$ in the running-time bound cannot be replaced by a function depending only on (\eps,d) or on (k,d), under standard complexity assumptions. We also present an improved upper bound on the approximation ratio of the greedy algorithm in special cases of the problem, including when the sets have bounded cardinality and when they are two-dimensional halfspaces. Complementing these positive results, we show that when the sets are four-dimensional halfspaces neither the greedy algorithm nor local search is capable of improving the worst-case approximation ratio of 1-1/e that the greedy algorithm achieves on arbitrary instances of maximum coverage.
November 5, 2019 (úterý [Tuesday], 14:00, MFF UK Malá Strana, room 307)
Paweł Rzążewski: Finding (list) homomorphisms from bounded-treewidth graphs
Abstract: In the list homomorphism problem, the input
consists of two graphs G and H, together with a list L(v)⊂V(H) for
every vertex v ∈ V(G). The task is to find a homomorphism φ:V(G)
-> V(H) respecting the lists, that is, we have that φ(v) ∈ L(v)
for every v ∈ V(H) and if u and v are adjacent in G, then φ(u) and
φ(v) are adjacent in H. If H is a fixed graph, then theproblem is
denoted by LHOM(H). Feder, Hell, and Huang provided the complexity
dichotomy for the problem [Feder, Hell, Huang, JGT 2003].
We explore the complexity of the problem parameterized by the
treewidth tw(G) of the input graph G. If a tree decomposition of G
of width tw(G) is given in the input, then the problem can be
solved in time |V(H)|^tw(G)*n^O(1) by naive dynamic programming.
Our main result completely reveals whenand by exactly how much
this naive algorithm can be improved. We introduce asimple
combinatorial invariant i^*(H), which is based on the existence of
certain decompositions and incomparable sets, and show that this
number should appear as the base of the exponent in the best
possible running time. Specifically, we prove for every graph H,
for which LHom(H) is NP-hard:
- If a tree decomposition of width tw(G) is given in the input,
then the problem can be solved in time i^*(H)^tw(G) * n^O(1).
- Assuming the Strong Exponential-Time Hypothesis (SETH), the
problem cannot be solved in time (i^*(H)-ε)^tw(G) * n^O(1) for any
ε>0.
Thus by matching upper and lower bounds, our result exactly
characterizes for every fixed H the complexity of LHOM(H)
parameterized by treewidth.
The results are obtained as a joint work with Karolina Okrasa and
Marta Piecyk.
October 29, 2019 (úterý [Tuesday], 14:00, MFF UK Malá Strana, room 307)
Marek Chrobak (UC Riverside): Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability
Abstract: Some microfluidic lab-on-chip devices contain
modules whose function is to mix two fluids, called reactant and
buffer, in desired proportions. In one of the technologies
for fluid mixing the process can be represented by a
directed acyclic graph whose nodes represent micro-mixers and
edges represent micro-channels. A micro-mixer has two input
channels and two output channels; it receives two fluid droplets,
one from each input, mixes them perfectly, and produces two
droplets of the mixed fluid on its output channels. Such a mixing
graph converts a set I of input droplets into a set T of output
droplets, where the droplets are specified by their reactant
concentrations. The most fundamental algorithmic question
related to mixing graphs is to determine, given an input set I and
a target set T, whether there is a mixing graph that converts I
into T. We refer to this decision problem as mix-reachability.
While the complexity of this problem remains open, we provide a
solution to its natural sub-problem, called perfect mixability, in
which we ask whether, given a collection C of droplets, there is a
mixing graph that mixes C perfectly, producing only droplets whose
concentration is the average concentration of C. We provide a
complete characterization of such perfectly mixable sets and an
efficient algorithm for testing perfect mixability. Further, we
prove that any perfectly mixable set has a perfect-mixing graph of
polynomial size, and that this graph can be computed in polynomial
time.
This is joint work with Miguel Coviello Gonzalez (UCR).
October 15 and 22, 2019 (úterý [Tuesday], 14:00, MFF UK Malá Strana, room 307)
Michal Berg: Increasing the shortest s-t path in planar graphs by deletion of edges and the L-bounded cut
Abstract: Length bounded cut, also known as L-bounded cut, is a problem on graphs with special vertices s and t and integer parameter L where we want to remove the least number of edges such that there is no path from s to t of length L or lower. This is a variant of the standard graph cut problem where we do not want any path from s to t to remain after deleting the cut edges. This seemingly small change has a great impact on complexity of this problem. The problem of L-bounded cut is NP-hard even for L>=4. In this talk we are going to look at problem of L-bounded cut for L=d(s,t)+1 on planar graphs where d(s,t) denotes distance between s and t. In other words, we want to increase the length of the shortest path from s to t by 2 by removing the least number of edges. This problem is known to be NP-hard for general graphs but it is an open problem whether this problem is NP-hard also on planar graphs with special vertices s and t on the outer face. We will try to outline a way, which might lead to showing that this problem is solvable in a polynomial time.
October 8, 2019 (úterý [Tuesday], 14:00, MFF UK Malá Strana, room 307)
Anish Mukherjee: Shortest k-Disjoint Paths via Determinants
Abstract: The well-known k-disjoint paths problem asks for pairwise vertex-disjoint paths between k specified pairs of vertices (s_i, t_i) in a given graph if they exist. In this talk, we will consider the version of this problem where we want to find a solution of minimum total length. We restrict attention to instances on undirected planar graphs where all sources and sinks lie on a single face or on a pair of faces. We provide efficient sequential and parallel algorithms, partly answering an open question of Colin de Verdière and Schrijver for the general one-face case. The algorithms are based on a bijection between a shortest k-tuple of disjoint paths in the given graph and cycle covers in a related digraph. This allows us to non-trivially modify established techniques relating to counting cycle covers to the determinant. Time permitting, I’ll also present some brief ideas about a different proof of the one-face case, again using determinants. Based on joint work with Samir Datta, Raghav Kulkarni, and Siddharth Iyer.