Open Problems Sessions
|Rolf Fagerberg||12/11 2019|
Rolf talked on Fragile Complexity of Comparison-Based Algorithms, looking at situations where elements are somehow damaged by participating in a comparison. Thus, one is interested in minimizing the maximum number of comparisons any element is involved in. After demonstrating the problem by comparing eight different beers, we were all very motivated! For a start, finding the minimum element is logarithmic, using a tournament, and Rolf gave an adversary argument that this is optimal. Turning to sorting networks, any such network gives rise to an algorithm of fragile complexity equal to the depth of the network and work complexity equal to its size. However, there are significant differences, e.g., a comparator network for Median has size at least n log n, while there is a algorithm with logarithmic fragile complexity and linear work complexity. BuildHeap has the same complexities, and the comparison network lower bound is n log log n. Also sorting has the same complexities. Rolf then considered randomization, focusing on reducing the impact on one number (the minimum, say), at some cost for the other elements, and showed a number of trade-off results, given the details of getting the impact for the minimum element down to a constant. Finally, Rolf showed how mergesort can be improved from linear fragile complexity to logarithmic squared, using exponential merging. Actually, just randomizing the input, standard mergesort gets logarithmic fragile complexity with high probability, whereas any deterministic binary mergesort has fragile complexity the logarithm squared. He concluded with some intricate details on the Median problem.
|Nikolai Nøjgaard||1/10 2019|
Nikolai gave a talk on a Generic Group Contribution Method. The starting point was molecules represented as graphs and chemical processes formalized as graph transformations. Modeling this means that chemical processes can be simulated, which poses the question as to whether a (theoretical) transformation can actually be realized in practice. An important ingredient to decide this is the subject of energy change (the energy of a molecule is roughly the sum of its bond energies). A first step is to decompose the graph into so-called functional groups with certain properties (determining these groups must to some extend involve chemists). The decomposition problem is not trivial since a graph can often be decomposed (tiled by the functional groups) in many ways. To attack this, he considers the frequency of a molecule as the number of embeddings into a particular context, and consider formulas that are sums of frequencies times the bias (estimated energy of the relevant bond). Matching variants of this up with sample values, techniques inspired by linear regression (variables are not independent) can be used to determine the energies. After presenting some considerations about contexts, Nikolai went on to give a brief explanation of frequency subgraph mining in this setting, relying heavily on depth-first search enumerations of graphs (in a canonical manner), before he summed up, explaining the overall iteration mechanism, repeating these steps outlined above. Testing was performed on synthetic datasets (training on 90% and testing on the rest) with promising results. On real datasets, more work has to be done, the problems remaining predicted to be partly due to overfitting.
|Jørgen Bang-Jensen||7/5 2019|
Jørgen gave a presentation on acyclic orientations of 2T-graphs, i,e., graphs that are the union of two edge-disjoint spanning trees. Thus, such graphs have 2n-2 edges. A good orientation is an acyclic orientation forming a spanning out-branching and a spanning in-branching tree that are edge-disjoint. A 2T-graph is a generic circuit if all proper subsets of the vertices have at most 2 times the cardinality of the subset minus 3 edges. Jørgen proved by induction that every such generic circuit has a good orientation. A fundamental cycle is the unique cycle that appears when one new edge is added to a spanning tree. All the generic circuits can be generated using this. They form a hyper-forest and Jørgen discussed further graphs theoretical partition results on this structure. For general graphs, it is NP-complete to decide if it partitions into generic circuits, shown by a reduction from exact cover from 4-sets. Open problem: The question of whether or not a graph has a good orientation is NP-complete, for 2T-graphs as well as general graphs.
|Joan Boyar||26/3 2019|
Joan talked on combining the priority algorithms model with advice complexity. The talk was based primarily on the paper Advice Complexity of Priority Algorithms by Allan Borodin, Joan Boyar, Kim S. Larsen, and Denis Pankratov, WAOA 2018. Fixed priority algorithms model greedy-like algorithms where the order in which items are considered is computed from the beginning and not changed during the course of the algorithm. Restricting the class of algorithms under consideration, lower bounds can be proven for a large class of algorithms without any assumptions (such as P ≠ NP). The model employs priority functions, assigning priorities to all possible items (the universe) before the input is seen and processed one item at a time, making irrevocable decisions, similar to online algorithms. Separately from this, advice complexity discusses bounds on which competitive ratios can be obtained by online algorithms if provided with a given number of advice bits from an oracle. In this model, lower bounds can be proven for, for instance, semi-online algorithms. This research considers the combination of these two models. A toy example, Greater Than Mean, was shown to be optimally realizable using a fixed priority algorithm and log(n) bits of advice. Similar to String Guessing from the online algorithms with advice setting, the problem, Pair Matching (guessing if a real, x, has a later match with an item, 1-x), was introduced. This was used to establish reductions, showing hardness of other problems. A general, gadget-like technique for reductions was introduced using a reduction from Independent Set as an example, with theorems for minimization as well as maximization problems, obtaining bounds for problems related to matching, max cut, vertex cover, satisfiability, and scheduling problems.
|Jakob Lykke Andersen||26/2 2019|
Jakob talked on canonicalization of data structures and applications in cheminformatics. The starting point is defining a representation of, for instance, mathematical objects. As an example, rationals can be represented by pairs of integers. This means that objects that are isomorphic in mathematical terms can have more than one representation. A canonicalization is then a function from one representation to another such that two objects are isomorphic if and only if they have the same canonical form. He goes further and define a total ordering on representations that are isomorphic and the canonical representation should be the smallest. The first non-trivial example presented was a representation of circular strings (for RNA), where a canonical form (the lexicographically smallest string) can be found in linear time, and this was used further in pairs of such representations (double stranded RNA) before Jakob moved to anti-parallel strong traces (and graphs in general). With mathematical objects come operations; in this case for instance reverse, rotate, some form of permutation, etc., and the task is to consider how they work as functions from canonical representations to canonical representations. Tools for canonicalization are based on the individualization-refinement paradigm, where the trivial singleton partition is gradually split based on the numbers of neighbors of difference type (degrees), in a manner similar to Hopcroft's DFA minimalization algorithm. Jakob gave a demonstration of his GraphCanon Visualizer and showed how symmetries can be used to prune search trees when graphs are isomorphic, and he hinted at a large collection of problem variations and heuristics. At the end, he considered experimental results and future developments.
|Daniel Merkle||29/1 2019|
Daniel took the paper DNA-Templated Synthesis Optimization by Bjarke N. Hansen, Kim S. Larsen, Daniel Merkle, and Alexei Mihalchuk as the starting point. The motivation for this work was the chemist's dream of one-pot, 100% efficient synthesis. The paper explores DNA-templated synthesis, where compounds are tagged with DNA strands and the binding of DNA material can be used to bring the right compounds together. The most important properties of this elementary operation is that the tags are directional and that exactly one of the two tags from the reacting compounds is attached to the resulting compound. Based on this, a chemical programming language can be defined, using the operations tag, react, release, and block. A number of optimization problems present themselves, driven by economy in the chemical process, such as minimizing the number of different tags, strands or both, the number of tags attached to the input compounds, the number of blockings, the number of steps (program length), etc. A number of (mostly) optimal results (matching upper and lower bounds) were presented for some of the problems, highlighting connections to the Horton-Strahler number and to antipaths in a graph. Some minor gaps were presented as open problems.
|Jørgen Bang-Jensen||11/12 2018|
Jørgen discussed results on antipaths. He defined a trail as an antipath with no arc repetition (thus, vertices can repeat and one can change direction via an odd cycle), and a digraph to be antistrong if all pairs of vertices have a forward-directed (start and end with a forward edge) trail between them. After some initial observations, he turned to CATs - closed antidirected trails. CAT-free sets of arcs form a matroid on the arcs, which turns out to be quite useful. After discussing a polynomial-time algorithm for finding a minimum cardinality set of new arcs to add in order to make a graph antistrong (using its bipartite representation), he moved to the highlights of the presentation, namely a characterization of when a CAT-free orientation exists for graph with |E| ≤ 2|V|-1; the conditions are that |E| ≤ 2|V|-1 for all proper subgraphs, and |E| ≤ 2|V|-2 for all proper bipartite subgraphs. Then he discussed establishing certificates for non-existence, and concluded with results on polynomial-time versus NP-completeness of related questions, and a number of interesting open problems.
|Thomas Bellitto||6/11 2018|
Thomas Bellitto presented restricted-walk graph problems. He first considered forbidden-transition graphs where a set of forbidden (or permitted) transitions are given. A transition is two different consecutive edges. Examples include properly-colored walks, where no two consecutive edges have the same color, and antidirected walks, alternating between forward/backward edges in a digraph. The concept can of course be generalized to forbidden subpaths. A graph is T-connected if there is a T-compatible walk between any two vertices, and then T is a connecting transition set. Finding a minimum connecting transition set is NP-complete. MST gives a trivial upper bound of n-2. A better upper bound can be expressed in terms of connected components of the complementary graph. An important observation is that the problem is the same as finding a connecting hypergraph of minimum cost, and a quadratic 3/2-approximation can be derived from this. At the end, open problems on coloring and odd cycles, as well as connectivity questions in a variety of graph classes were discussed.
|Joan Boyar||2/10 2018|
Joan told about a complexity class for online algorithms, AOC. The complete problems for this class include many accept/reject problems that require large amounts of advice to achieve good competitive ratios. The work defining and analyzing this complexity class was joint with Lene, Christian Kudahl, and Jesper With Mikkelsen. A couple of harder and easier complexity classes were mentioned at the end. Joan is interested in defining further complexity classes for online algorithms.
|Lene M. Favrholdt||11/9 2018|
Lene introduced advice complexity for online algorithms, using multi-coloring on the line and paging as motivating problems. She introduced advice bits and defined advice complexity of an algorithm and of a problem. Then she discussed trade-offs between the competitive ratio (the quality of a solution) and the amount of advice, and introduced the idea of using covering designs to reduce the number of advice bits at a small cost in approximation factor. The talk continued with graph problem examples and the concept of a reduction between these problems, starting with string guessing. In connection with questions from the audience, she discussed the implications of these results in connection with real-life problems. At the end, she discussed the connection between randomized algorithms and algorithms with advice.
|Jørgen Bang-Jensen||15/5 2018|
Jørgen talked on graph orderings, starting with proper circular arc graphs, concave and convex round graphs, and interval-enumerable graphs, ending with excellent/nice orderings, and open problems for -arc strong orientation.
|Joan Boyar||17/4 2018|
Joan introduced priority algorithms, with emphasis on the newer concept of priority stack algorithms, applying this to maximal weighted independent set for chordal graphs. She continued with vertex cover approximation in the setting of fixed and adaptive priority algorithms, respectively.
|Daniel Merkle||6/3 2018|
Daniel explained modeling chemical reactions via hypergraph transformations, and accounted for the use of graph grammars, generating functions, and Boltzmann sampling. Anders detailed progress on Kim's problem from last time, giving a lower bound on the barrier problem for sorting by transpositions.
|Kim Skak Larsen||6/2 2018|
Kim talked about sorting by transpositions and the question of what the maximal number of swaps across a fixed barrier could be. Anders introduced transversal numbers in hyper graphs and existence of Euler tours in edge-colored graphs, where two consecutive edges must have different color. Finally, Jing discussed non-crossing partial matchings on top of a line-graph, transitions between two such structures, and best sequences of such transitions relative to some stability measure.