I’m trying to figure out if there is some deterministic algorithm for this problem. Initially I thought this would be known, but seems like it is not as trivial.

http://www.chaoxuprime.com/

I blog about algorithm and theory related stuff…

I try to get sublime text’s markdown syntax highlighter to work with markdown + latex. (thus support even more of pandoc flavored markdown.)

Here is the current code. https://gist.github.com/Mgccl/195ce33124f384a2f4e4

I’m doing research on ways to compute maximum flow over a unit capacity undirected graph with a subset T of vertices having unit capacity in O(n^2.5) time.

So far.

1. If T is an empty set, then there exist an algorithm to solve the problem in O(n^2.5) time (in fact O(n^2.375) is possible) (see the introduction in Ran Duan: Breaking the O(n^2.5) Time Barrier for Undirected Unit-Capacity Maximum Flow. SODA 2013: 1171-1179 for a survey of such results)

2. If T is the entire set of vertices, then we can also solve it in O(n^2.5) time (and this also works for directed graphs). See this paper. https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/network%20flow%20and%20testing.pdf

but when T is just some arbitrary subset, no known algorithm takes O(n^2.5) time. Combine the techniques in 1 and 2, one can up with an algorithm that runs in O(n^2.5) time if any one of the following is true

1. n-|T| = O(n^¾).

2. number of edges between vertices in |T| = O(n^1.5).

3. Each component of V\T is constant size.

I’m working on checking if one can use link/cut tree to create a generalization of finger tree.

Finger tree maintains a sequence of elements in a monoid(or one can consider a rooted path with each vertex weighted by a monoid element), and we can do many operations really fast. One can split the sequence, concat the sequence and find the sum of a sequence(so, the weight from the root to the end vertex). Note this allow us to find sum of a subsequence by split at appropriate positions and take the sum of the resulting middle sequence.

From what I read, one might want to generalize it to work on a rooted tree instead of a rooted path. We still maintain the nice property the path from the root to any vertex is unique. link/cut tree seems to do the trick as a underlying data structure. The question is more about the semantics. What would be a way to define split,concat,sum so when it is restricted to a rooted path, we get the finger tree behavior, and it’s actually useful for something else…

I guess the idea is to have this CAPTCHA during sign up or shows up once per k actions where k is relatively large? Otherwise participation becomes a chore…

If the solution provided by the user gets stored, then one can use this to find all the interesting ways to solve the same problem.