Parameterized Complexity and Practical Computing Workshop

Title: Theoretical and practical algorithms for CSP parameterized by the number of variables with value-independent constraints

Speaker: Gregory Gutin (Royal Holloway, University of London, UK)

Abstract: 

Unfortunately, CSP parameterized by the number of variables is W[1]-hard and in W[2]. Fortunately, CSP parameterized by the number of variables with value-independent constraints is FPT and of interest in (security) access control. We'll discuss theoretical results for such a CSP as well as results of computational experiments with FPT algorithms and SAT and CSP solvers. Our experiments demonstrate that the best FPT algorithm significantly outperforms the solvers.

Title: Integer Programming and Convolution, with Applications in Scheduling and Knapsack Problems

Speaker: Klaus Jansen, Univ. Kiel

Abstract: 

Integer programs (IP) with a constant number$ $m of constraints are solvable in pseudo-polynomial time. We give a new algorithm based on the Steinitz Lemma and dynamic programming with a better pseudo-polynomial running time than previous results. Vectors $v_1,\ldots,v_n$ in $R^m$ that sum up to the $0$ vector can be seen as a circle in $R^m$ that walks from $0$ to $v_1$ to $v_1 + v_2$, etc. until it reaches $v_1 + \ldots + v_n = 0$ again. The Steinitz Lemma says that if each of the vectors is small with respect to some norm, we can reorder the vectors in a way that each point in the circle is not far away from $0$ w.r.t. the same norm. We show in the talk that a solution to the IP $\max c^T x, A x = b, x >= 0, x in Z^n$ can be found in time $O(m \Delta)^{2m} log(||b||_\infty) + O(nm)$ where $\Delta$ is the biggest absolute value of any entry in $A$.

Moreover, we establish a strong connection to the problem $(min,+)$-convolution. $(min,+)$-convolution has a trivial quadratic time algorithm and it has been conjectured that this cannot be improved significantly. We show that further improvements to our pseudo-polynomial algorithm for any fixed number $m$ of constraints are equivalent to improvements for $(min,+)$-convolution. This is a strong evidence that our algorithm’s running time is best possible. We also present a faster specialized algorithm for testing feasibility of an integer program with few constraints. Our algorithm for the feasibility problem runs in $O(m \Delta)^{m}\log(\Delta) \log(\Delta + ||b||_\infty) + O(nm)$. Finally we show for the feasibility problem also a tight lower bound, which is based on the Strong Exponential Time Hypothesis (SETH), and give some applications for knapsack and scheduling problems. This is joint work with Lars Rohwedder (Univ. Kiel).

Title: Parameterized Graph Algorithms in the Field

Speaker: Blair Sullivan 

Abstract: 

The field of network science has burgeoned in the last two decades, developing new methods for analyzing complex network data of ever-increasing scale. Surprisingly, few tools from structural graph theory and parameterized complexity have been assimilated. In part, this is due to the primarily theoretical nature of the related literature, unrealistic structural assumptions, and a lack of cross-pollination of the research communities. In this talk, we survey several concrete applications which demonstrate the potential of these structure-based approaches in computational biology and quantum computing. We emphasize commonalities and key strategies for fostering practitioner uptake. Finally, we will highlight recent algorithmic approaches aimed at bridging this theory-practice gap.

Title: Near-Linear Time Algorithm for n-fold ILPs via Color Coding

Speaker: Alexandra Anna Lassota

Abstract: 

We study an important case of ILPs $\max\{c^Tx \ \vert\ \mathcal Ax = b, l \leq x \leq u,\, x \in \mathbb{Z}^{n t} \} $ with $n\cdot t$ variables and lower and upper bounds $\ell, u\in\mathbb Z^{nt}$. In \nfold{} ILPs non-zero entries only appear in the first $r$ rows of the matrix $\mathcal A$ and in small blocks of size $s\times t$ along the diagonal underneath. Despite this restriction many optimization problems can be expressed in this form. It is known that \nfold{} ILPs can be solved in FPT time regarding the parameters $s, r,$ and $\Delta$, where $\Delta$ is the greatest absolute value of an entry in $\mathcal A$. The state-of-the-art technique is a local search algorithm that subsequently moves in an improving direction. Both, the number of iterations and the search for such an improving direction take time $\Omega(n)$, leading to a quadratic running time in $n$. We introduce a technique based on Color Coding, which allows us to compute these improving directions in logarithmic time after a single initialization step.

This leads to the first algorithm for \nfold{} ILPs with a running time that is near-linear in the number $nt$ of variables, namely $(rs\Delta)^{\cO(r^2s + s^2)} L^2 \cdot nt \log^{\cO(1)}(nt)$, where $L$ is the encoding length of the largest integer in the input. In contrast to the algorithms in recent literature, we do not need to solve the LP relaxation in order to handle unbounded Variables. Instead, we give a structural lemma to introduce appropriate bounds. If, on the other hand, we are given such an LP solution, the running time can be decreased by a factor of $L$.

Title: Algebraic Methods in Parameterized Theory and Practice

Speaker:  Cornelius Brand

Abstract: 

Algebraic methods have long been employed to successfully solve parameterized problems. A flagship problem in this area is the longest-path problem, where the group-algebra approach of Koutis and Williams proved to be seminal in 2008, breaking below the running time of classic Color-Coding.

A central application of this problem is the analysis of biological networks, most notably in protein-protein interaction networks, but also, more recently, in the analysis of connectomes. 

In this talk, we give an overview of the techniques, comment on their implementability and employability in the mentioned application areas, and discuss limitations of the approaches (including also space requirements of the algorithms).

Title: From Tree-depth to Shrub-depth, Evaluating MSO-Properties in Constant Parallel Constant Time.

Speaker: Yijia Chen

Abstract: 

Courcelle's theorem states that every property definable in monadic second-order logic (MSO) can be evaluated in linear time on graphs of bounded tree-width. But given the huge size of graphs arising in practice, linear time might not be good enough. Therefore, we are interested in classes of graphs on which MSO-properties can be evaluated in parallel constant time. In this talk,I will explain two results in this direction, one is on graphs of bounded tree-depth and the other on graphs of bounded shrub-depth. This is joint work with Jörg Flum.

Title: Near-Linear Approximation Algorithms for Scheduling Problems with Batch Setup Times

Speaker: Max Amadeus Deppert:

Abstract: 

We investigate the scheduling of n jobs divided into c classes on m identical parallel machines. For every class there is a setup time which is required whenever a machine switches from the processing of one class to another class. The objective is to find a schedule that minimizes the makespan. We give near-linear approximation algorithms for the following problem variants: the non-preemptive context where jobs may not be preempted, the preemptive context where jobs may be preempted but not parallelized, as well as the splittable context where jobs may be preempted and parallelized. We present the first algorithm improving the previously best approximation ratio of 2 to a better ratio of 3/2 in the preemptive case. In more detail, for all three flavors we present an approximation ratio 2 with running time (n), ratio 3/2+ε in time (nlog1/ε) as well as a ratio of 3/2. The (3/2)-approximate algorithms have different running times. In the non-preemptive case we get time (nlog(n+Δ)) where Δ is the largest value of the input. The splittable approximation runs in time (n+clog(c+m)) whereas the preemptive algorithm has a running time (nlog(c+m))≤(nlogn). So far, no PTAS is known for the preemptive problem without restrictions, so we make progress towards that question. Recently Jansen et al. found an EPTAS for the splittable and non-preemptive case but with impractical running times exponential in 1/ε.

Title: About the Complexity of 2-Stage Stochastic IPs

Speaker: Kim-Manuel Klein

Abstract:

We consider so called $2$-stage stochastic integer programs  (IPs) and their generalized form of multi-stage stochastic IPs. A $2$-stage stochastic IP is an integer program of the form $\max \{ c^T x \mid \mathcal{A} x = b, l \leq x \leq u, x \in \ZZ^{s + nt} \}$ where the constraint matrix $\mathcal{A} \in \ZZ^{r n \times s +nt}$ consists roughly of $n$ repetitions of a block matrix $A \in \ZZ^{r \times s}$ on the vertical line and $n$ repetitions of a matrix $B \in \ZZ^{r \times t}$ on the diagonal. Hence it is roughly the transposed of the constraint matrix of an n-fold IP.

In this talk, we present new algorithmic results on how to solve this type of IP. The algorithm is based on the Graver augmentation framework where our main contribution is to give an explicit doubly exponential bound on the size of the augmenting steps. The previous bound for the size of the augmenting steps relied on non-constructive finiteness arguments from commutative algebra and therefore only an implicit bound was known that depends on parameters $r,s,t$ and $\Delta$, where $\Delta$ is the largest entry of the constraint matrix. The new improved bound however is obtained by a novel theorem which argues about the intersection of paths in a vector space.

Title: Engineering Kernelization for Maximum Cut

Speaker: Matthias Mnich

Abstract: 

Kernelization is a general theoretical framework for preprocessing instances of NP-hard problems into (generally smaller) instances with bounded size, via the repeated application of data reduction rules. For the fundamental Max Cut problem, kernelization algorithms are theoretically highly efficient for various parameterizations. However, the efficacy of these reduction rules in practice---to aid solving highly challenging benchmark instances to optimality---remains entirely unexplored. We engineer a new suite of efficient data reduction rules that subsume most of the previously published rules and demonstrate their significant impact on benchmark data sets, including synthetic instances, and data sets from the VLSI and image segmentation application domains. Our experiments reveal that current state-of-the-art solvers can be sped up by up to multiple orders of magnitude when combined with our data reduction rules. On social and biological networks in particular, kernelization enables us to solve four instances that were previously unsolved in a ten-hour time limit with state-of-the-art solvers; three of these instances are now solved in less than two seconds. 

(joint work with Damir Ferizovic, Demian Hespe, Sebastian Lamm, Christian Schulz and Darren Strash)

Title: Efficiently Computing the Shapley Value of Connectivity Games in Low-Treewidth Graphs

Speaker: T. C. van der Zanden

Abstract: 

Game-theoretic centrality measures are a powerful tool to identify key players in covert networks (that model, e.g., the interactions between suspected terrorists or criminals). Unfortunately, such measures are often NP-hard to compute and thus intractable, even for small graphs. We show that, for three connectivity games, their Shapely value can be efficiently computed if the underlying graph has low treewidth. We provide a practical implementation of our algorithm. Using this method, we are able to compute the Shapley value for several social networks for which this was previously infeasible (including, notably, the 69-vertex graph of the terrorists involved in the 9-11 attacks studied in previous work on Shapley value-based centrality).

Title: Typical Sequences Revisited

Speaker: Lars Jaffke

Abstract: 

We give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the scheduling of straight-line code (a basic block) to minimize the number of registers is solvable in quadratic time for series-parallel digraphs. Previously, a polynomial-time algorithm was known only for trees [Sethi and Ullman, JACM 1970]. We also show that the Cutwidth, Modified Cutwidth, and Vertex Separation problems can be solved in O(n^2) time for series-parallel digraphs on n vertices. (Joint work with Hans L. Bodlaender and Jan Arne Telle)

Title:  Parameterized complexity of biclique cover and partition

Speaker: Davis Issac

Abstract: 

A biclique of a graph is a complete bipartite subgraph of it. We look at the problems of covering and partitioning the edges of a bipartite graph with bicliques. These problems are called biclique cover and biclique partition respectively. The problems have many practical and theoretical applications. I will explain two of the practical applications, one in display optimization and the other in data compression and mining. The latter application arises due to connections with binary matrix factorization. We study the problems from the point of view of parameterized complexity, where the parameter is taken to be the size of the cover or partition. It was known that both problems are fixed-parameter tractable but the algorithms had running times that had a doubly exponential dependence on the parameter $k$. We show an algorithm for biclique partition that has only $\mathcal{2^{k^2}}$ dependence on $k$. For biclique cover, we show that no improvement over the doubly exponential dependence is possible, by giving a reduction from $3$-SAT on $n$ variables to an instance of biclique cover with the parameter $k=\log n$. We also give kernel lower bounds for biclique cover. I will point out some interesting open problems related to the above problems.

Title: Novel applications of capacitated Cluster-Editing with vertex Split operation

Speaker: Peter Shaw

Abstract: The capacitated form of the cluster-editing produces significant improvements in the size of clinical data that can be processed. Nevertheless, the presence of (hub vertices in the network places undesirable constraints on the max-delete parameter. By introducing a vertex-split operation we can further constrain the parameter, allowing it to handle potentially larger data sets. The Capacitated Cluster-Editing with Vertex Split is NP-Hard and FPT. Our current project is exploring applications of this novel FPT problem in the search algorithm enables the analysis of Acute Respiratory Lung disease (ALRI) which is a major health issue in Australia’s NT. Moreover, many other interesting applications exist and some of them will be briefly shared and discussed.

Title:  Application of Cluster-Editing with Vertex-Split in Logic.

Speaker: Peter Shaw 

Abstract:

Vertex splitting is an underrated operation and has been for quite a long time although a completely natural process when it comes to modeling.  Edges capture relational information, essential for graph modeling. But vertex identity models are different, but also very suited for natural occurrences. So just for a thought experiment, we take, as a starting point, that we want to consider partial orders on graphs (or more generally, relational structures, as in the wider conceptual formation of logic) and we want to take as the starting point the operation of splitting of atoms.

When you a partial order IS defined on finite graphs, IE defined by a finite set of ``local'' operations, which needs to be formalized, although it is quite natural, if we consider it in the area of graph minors, immersions, topological, induced-subgraphs and similar orders. And then further insist that vertex-splitting is one of the allowed operations. What can be achieved….?

Title:  Diverse FPT

Speaker: G. Phillip

Abstract: TBA