Radu Curticapean: New insights into counting subgraphs

We consider the problem of counting subgraphs. More specifically, we look at the following problems #Sub(C) for fixed graph classes C: Given as input a graph H from C (the pattern) and another graph G (the host, which does not need to be from C), the task is to count the occurrences of H as a subgraph in G. Our goal is to understand which properties of the pattern class C make the problem #Sub(C) easy/hard. For instance, for the class of stars, we can solve this problem in linear time. For the class of paths however, it subsumes counting Hamiltonian paths and is hence #P-hard. That is, we could count satisfying assignments to Boolean formulas in polynomial time with an oracle for this problem.

As it turns out, the notion of #P-hardness fails to give a sweeping dichotomy for the problems #Sub(C), since there exist classes C of intermediate complexity. However, adopting the framework of fixed-parameter tractability, we showed with Daniel Marx in 2014 how to classify the problems #Sub(C) as either polynomial-time solvable or #W[1]-hard: A class C lies on the polynomial-time side of this dichotomy iff the graphs appearing in C have vertex-covers of constant size.

In this talk, we introduce a new technique that allows us to view the subgraph counting problem from a new perspective. In particular, it allows for the following applications:

We discuss similar dichotomies for the problems of counting colored subgraphs, for counting subgraphs modulo fixed numbers, and for other variations of the problem. These results show that parameterized complexity theory, apart from being interesting on its own, can help to obtain "classical" dichotomies.

The talk will be self-contained and includes an introduction to the necessary concepts from parameterized complexity. It summarizes joint work with Daniel Marx, Holger Dell, and Thore Husfeldt.

Chihao Zhang: FPTAS for Counting Proper Four Colorings on Cubic Graphs

Graph coloring is arguably the most exhaustively studied problem in the area of approximate counting. It is conjectured that there is a fully polynomial-time (randomized) approximation scheme (FPTAS/FPRAS) for counting the number of proper colorings as long as q >= D+1 , where q is the number of colors and D is the maximum degree of the graph. This bound of q = D + 1 is the uniqueness threshold. However, the conjecture remained open even for any fixed D >= 3 (The cases of D=1, 2 are trivial). In this paper, we provide an FPTAS for counting the number of 4-colorings on graphs with maximum degree of 3 and thus confirm the conjecture in the case of D=3. This is the first time to achieve this optimal bound of q = D + 1. Previous, the best FPRAS is for q > 11/6 D and the best deterministic FPTAS is for q > 2.581D + 1 for general graphs. For the case of D=3, the best previous result is an FPRAS for counting 5-colorings. We note that there is a barrier to go beyond q = D + 2 for Glauber dynamics based FPRAS and we overcome this by correlation decay approach. This is a joint work with Pinyan Lu, Kuan Yang and Minshen Zhu.

Zhihao Tang: Online Submodular Maximization with Free Disposal

We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm maintains a feasible set that is independent in the underlying matroid. In each round when a new element arrives, the algorithm may accept the new element into its feasible set and possibly remove elements from it, provided that the resulting set is still independent. The goal is to maximize the value of the nal feasible set under some monotone submodular function, to which the algorithm has oracle access. For k-uniform matroids, we give a deterministic algorithm with competitive ratio at least 0.2959, and the ratio approaches $\frac{1}{\alpha_\infty} \approx0.3178$ as k approaches in nity, improving the previous best ratio of 0.25 by Chakrabarti and Kale (IPCO 2014), Buchbinder et al. (SODA 2015) and Chekuri et al. (ICALP 2015). We also show that our algorithm is optimal among a class of deterministic monotone algorithms that accept a new arriving element only if the objective is strictly increased. Further, we prove that no deterministic monotone algorithm can be strictly better than 0.25-competitive even for partition matroids, the most modest generalization of k-uniform matroids, matching the competitive ratio by Chakrabarti and Kale (IPCO 2014) and Chekuri et al. (ICALP 2015). Interestingly, we show that randomized algorithms are strictly more powerful by giving a (non-monotone) randomized algorithm for partition matroids with ratio $\frac{1}{\alpha_\infty} \approx0.3178$. Finally, our techniques can be extended to a more general problem that generalizes both the online submodular maximization problem and the online bipartite matching problem with free disposal. Using the techniques developed in this paper, we give constant-competitive algorithms for the submodular online bipartite matching problem.

Shaofeng Jiang: Recent Advances on Approximation Algorithms in Doubling Metrics

The study of approximation algorithms in Euclidean spaces is quite fruitful. For instance, the celebrated result by [Arora 98] presents PTASes for several variations of TSP and Stiener tree problems. However, the techniques heavily reply on the geometry of the Euclidean spaces, and it is an important question that whether the bounded dimensionality is sufficient for the existence of PTASes, without the need of geometric properties or the vector representation.

The notion of doubling dimension is widely considered for measuring the intrinsic dimensionality of a metric space. Previous works showed that doubling dimension is more general than many measure of dimensionality. In particular, it is a generalization of Euclidean dimension while it does not possess geometric properties.

In this talk, we discuss several recent results on approximation algorithms in doubling metrics (metric spaces with bounded doubling dimension). We will start with a QPTAS for TSP in doubling metrics which is based on [Talwar, STOC 04]. Then we talk about PTASes for variations of TSP in doubling metrics, which is based on [Bartal, Gottlieb, Krauthgammer, STOC 12] and [Chan, Jiang, SODA 16]. We will also introduce a very recent result - a PTAS for the Stiener forest problem in doubling metrics, which is based on [Chan, Hu, Jiang, FOCS 16].

We conclude by proposing some open questions.

Siu-Wing Cheng: Approximate Shortest Paths in Weighted Regions

Let T be a polygonal subdivision such that each region is associated with a weight. The cost of a path in a region is the path length multiplied by the region weight. The cost of a path in T is the sum of the subpath costs in the regions traversed. Finding the minimum-cost path in T from a given source to a given destination is called the weighted region problem. This problem models the scenario that the difficulty of traversing a region may vary depending its nature. The problem has been studied by several groups since 1991, and I will discuss our recent results on a fast approximation algorithm, the three-dimensional case, and other related problems.

Pavol Hell: Interval-like Graphs and Digraphs

In this talk I will focus on forbidden structure characterizations of geometrically defined graph (and digraph) classes. These include interval graphs and digraphs, and circular arc-graphs. I will propose a general class of digraphs that encompasses many of these classes and present a forbidden structure characterization for it. I will also present a separate forbidden structure characterization for the class of circular-arc graphs. This gives an answer to questions of Klee, and of Hadwiger and Debrunner, from the early 1960's. This is joint with T. Feder, J. Huang, and A. Rafiey for the interval graphs and their generalizations, and with M. Francis and J. Stacho for the circular arc graphs.

Minming Li: Facility Location Games: From Origin to Recent Development

Mechanism Design, as one of the important areas in algorithmic game theory, can be classified into two categories: with money and without money. Facility location game is one of the mostly studied problem in mechanism design without money. Procaccia and tennenholtz proposed and studied the problem back in 2009, where there are n agents on a line and the government will build a facility in a certain location given the agents reported information on their positions. Since every agent wants the facility to be closer to her, the government wants to make sure truth-telling is the best strategy for every agent while achieving some optimization objective. Since then, some bounds on the approximation ratios of the truthful mechanisms have been improved and new models are proposed. In this talk, we will briefly explain the story of the classic model and emphasize on the recent development on new models proposed by us and other groups.

Saket Saurabh: Exact Algorithms via Monotone Local Search

In a vertex subset problem we are given as input a universe U of size n, and a family F of subsets of the universe defined implicitly from the input. The task is to find a subset S in F of smallest possible size. For an example the Vertex Cover problem is a subset problem where input is a graph G, the universe is the vertex set of G, and the family F is the family of all vertex covers of G. Here a vertex set S is a vertex cover of G if every edge of G has at least one endpoint in S. Many problems, such as Vertex Cover, Feedback Vertex Set, Hitting Set and Minimum Weight Satisfiability can be formalized as vertex subset problems. The trivial algorithm for such problems runs in time 2^n. We show that (essentially) any vertex subset problem that admits an FPT algorithm with running time c^kn^O(1), where c is a constant and k is the size of the optimal solution, also admits an algorithm with running time (2-1/c)^n. In one stroke this theorem improves the best known exact exponential time algorithms for a number of problems, and gives tighter combinatorial bounds for several well-studied objects. The most natural variant of our algorithm is randomized, we also show how to get a deterministic algorithm with the same running time bounds, up to a sub-exponential factor in the running time. Our de-randomization relies on a new pseudo-random construction that may be of independent interest.

(Joint work with Daniel Lokshtanov, Serge Gaspers and Fedor Fomin)