We propose a new model for studying graph related problems
that we call the \emph{orientation model}. In this model, an undirected
graph $G$ is fixed, and the input is any possible edge orientation
of $G$. A property is now a property of the directed graph that is
obtained by a ... more >>>

One way to quantify how dense a multidag is in long paths is to find
the largest n, m such that whichever ≤ n edges are removed, there is still
a path from an original input to an original output with ≥ m edges
- the larger ... more >>>

Designing algorithms that use logarithmic space for graph reachability problems is fundamental to complexity theory. It is well known that for general directed graphs this problem is equivalent to the NL vs L problem. For planar graphs, the question is not settled. Showing that the planar reachability problem is NL-complete ... more >>>

We develop a new algebraic technique that gives a simple randomized algorithm for the simple $k$-path problem with the same complexity $O^*(1.657^k)$ as in [A. Bj\"orklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010, pp. 173--182, (2010). A. Bj\"orklund, T. Husfeldt, P. Kaski, M. Koivisto. Narrow sieves for parameterized paths and ... more >>>