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.