- Max Bannach, Malte Skambath, Till Tantau:
Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time.
In Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), LIPIcs,
2020.
Go to website | Show abstract
We analyze a reduction rule for computing kernels for the hitting set problem: In a hypergraph, the link of a set c of vertices consists of all edges that are supersets of c. We call such a set critical if its link has certain easy-to-check size properties. The rule states that the link of a critical c can be replaced by c. It is known that a simple linear-time algorithm for computing hitting set kernels (number of edges) at most k^d (k is the hitting set size, d is the maximum edge size) can be derived from this rule. We parallelize this algorithm and obtain the first AC^0 kernel algorithm that outputs polynomial-size kernels. Previously, such algorithms were not even known for artificial problems. An interesting application of our methods lies in traditional, non-parameterized approximation theory: Our results imply that uniform AC^0-circuits can compute a hitting set whose size is polynomial in the size of an optimal hitting set.
- Max Bannach, Sebastian Berndt, Martin Schuster, Marcel Wienöbst:
PACE Solver Description: PID*.
In Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), LIPIcs,
2020.
Go to website | Show abstract
This document provides a short overview of our treedepth solver PID^{?} in the version that we submitted to the exact track of the PACE challenge 2020. The solver relies on the positive-instance driven dynamic programming (PID) paradigm that was discovered in the light of earlier iterations of the PACE in the context of treewidth. It was recently shown that PID can be used to solve a general class of vertex pursuit-evasion games - which include the game theoretic characterization of treedepth. Our solver PID^{?} is build on top of this characterization.
- Max Bannach, Sebastian Berndt, Martin Schuster, Marcel Wienöbst:
PACE Solver Description: Fluid.
In Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), LIPIcs,
2020.
Go to website | Show abstract
This document describes the heuristic for computing treedepth decompositions of undirected graphs used by our solve fluid. The heuristic runs four different strategies to find a solution and finally outputs the best solution obtained by any of them. Two strategies are score-based and iteratively remove the vertex with the best score. The other two strategies iteratively search for vertex separators and remove them. We also present implementation strategies and data structures that significantly improve the run time complexity and might be interesting on their own.
- Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau, Malte Skambath:
Solving Packing Problems with Few Small Items Using Rainbow Matchings.
In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), LIPIcs,
2020.
Go to website | Go to website | Show abstract
An important area of combinatorial optimization are packing problems. While fundamental problems like bin packing, multiple knapsack, and bin covering have been studied intensively from the viewpoint of approximation algorithms, the use of parameterized techniques for this problems is rather limited. For instances containing no "small'' items, known matching algorithms give exact polynomial-time algorithm. Following the distance from triviality approach, our parameter k is the distance from such easy instances, i. e., the number of small items.
Our main results are randomized fixed-parameter tractable algorithms for vector-versions of bin packing, multiple knapsack, and bin covering parameterized by k, which run in time 4^k * k! * n^O(1) with one-sided error. To achieve this, we introduce a colored matching problem to which we reduce all these packing problems. The colored matching problem is natural in itself and we expect it to be useful for other applications as well. We also present a deterministic parameterized algorithm for bin packing with run time O( (k!)^2 * k * 2^k + n log(n) ).
- Marcel Wienöbst, Maciej Liskiewicz:
Recovering Causal Structures from Low-Order Conditional Independencies.
In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI'20), New York, New York USA, pp. 10302-10309.
AAAI Press,
2020.
Go to website | Show PDF | Show abstract
One of the common obstacles for learning causal models from
data is that high-order conditional independence (CI) relationships
between random variables are difficult to estimate.
Since CI tests with conditioning sets of low order can be performed
accurately even for a small number of observations, a reasonable
approach to determine casual structures is to base merely on the
low-order CIs. Recent research has confirmed that, e.g. in the case of
sparse true causal models, structures learned even from zero- and
first-order conditional independencies yield good approximations
of the models. However, a challenging task here is to provide
methods that faithfully explain a given set of low-order CIs.
In this paper we propose an algorithm which, for a given set
of conditional independencies of order less or equal to $k$,
where $k$ is a small fixed number, computes a faithful graphical
representation of the given set. Our results complete and generalize
the previous work on learning from pairwise marginal independencies.
Moreover, they enable to improve upon the 0-1 graph model which,
e.g. is heavily used in the estimation of genome networks.
