title: Efficient bandwidth algorithm

text:
# Question
Title: Efficient bandwidth algorithm
Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario:

1. Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 Mbps network card.
2. Node 3 is connected to 5 at 50 Mbps. Node 3 has 100 Mbps card.
3. Node 4 is connected to Node 3 at 40 Mbps. Node 4 has 100 Mbps card.

(Sorry about not having a picture)

Problem: If Node 1 starts sending data to its immediate nodes (2 and 3), we can clearly see it's network card capacity will be drained out after Node 3. Whereas if it were to *skip* node 3 and start sending to node 4, the data will eventually reach to node 3 via 4 and hence, node 5 will be getting data via node 3. The problem becomes more complicated if all the links were of 50 Mbps and we can clearly see that node 2 and node 4 are the only way to reach all nodes.

Question: Is there an algorithm which gives the optimal path to ALL nodes keeping the network (card) capacity in mind?

I read the shortest path algorithm,max flow algorithms but none of them seem to address my problems. perhaps,im missing something. I'll appreciate if someone can help me out.

# Answer
According to your description:

1. Each node in the network can relay a certain amount of traffic per time unit.
2. Each link has a certain capacity.

In order to convert your problem to an instance of network flow problem, one can do the following transformation. In the underlying graph of network, $G = (V,E)$, for any vertex $u \in V$ that has an outgoing edge $(u,v) \in E$, add an auxiliary vertex $u'$. Next, add an auxiliary edge $(u,u')$ with capacity equal to the capacity of $u$ for any auxiliary vertex $u'$. Finally, replace all $(u,v) \in E$ with $(u',v)$. Below is an illustration of how the network graph looks like before and after transformation.

The transformed graph can be seen as a flow network with node $1$ as source and nodes $2$ and $5$ as sinks. More generally, nodes with no incoming edges can be treated as source(s) and those with no outgoing edges as sink(s). Introducing an additional vertex to which all other sinks are connected with infinite capacity, you can further reduce your problem to a single-source single-sink flow network.

The goal is to find the optimal path to *all nodes*. Therefore, aside from the value of maximum flow itself, the algorithm you use for finding such a flow is also important. Edmonds-Karp algorithm uses BFS for finding the maximum flow over the shortest path. However, you want your maximum flow to go through as many nodes as possible. Thus, you need to make sure that your flows use longest paths between source and sink.

Luckily, for Directed Acyclic Graphs (DAGs), the longest path problem can be solved in linear time using dynamic programming. Thus, by modifying Edmonds-Karp algorithm such that it uses longest paths for flow augmentation, you ensure that the maximum number of nodes will be visited by each augmenting path.

In your example, the modified algorithm will output the following flows in order:

1. A flow of value $40$ over path $\langle 1,1',4,4',3,3',5 \rangle$.
2. A flow of value $10$ over path $\langle 1,1',3,3',5 \rangle$.
3. A flow of value $50$ over path $\langle 1,1',2 \rangle$.
> 5 votes

---
Tags: algorithms, graphs, optimization, linear-programming
---


title: What is the bitwise xor of an interval?

text:
# Question
Title: What is the bitwise xor of an interval?
Let $\oplus$ be bitwise xor. Let $k,a,b$ be non-negative integers. $\[a..b\]=\\{x\mid a\leq x, x\leq b\\}$, it is called a integer interval.

What is a fast algorithm to find $\\{ k\oplus x\mid x\in \[a..b\]\\}$ as a union of set of integer intervals.

One can prove that $\[a+k..b-k\]\subseteq \\{ k\oplus x\mid x\in \[a..b\]\\}$ by showing that $x-y\leq x\oplus y \leq x+y$.

**Edit:** I should specify the actually input and output to remove ambiguity.

Input: $k, a, b$.

Output: $a\_1, b\_1, a\_2, b\_2,\ldots,a\_m,b\_m$. Such that:

$$ \\{ k\oplus x\mid x\in \[a..b\]\\} = \bigcup\_{i=1}^m \[a\_i..b\_i\] $$

# Answer
Here's an efficient solution based on BDDs

1. Find $n$ such that $k,a,b \< 2^n$. Create $n$ boolean variables, one for each position in an $n-bit$ number
2. Write out a boolean formula representing every number in that interval. For example, if $n=4$ (so that we are only considering possible inputs in $\[0..15\]$), then the interval $\[2..4\]$ can be written as $\neg x\_0 \wedge ((x\_1 \wedge \neg x\_2 \wedge \neg x\_3) \vee (\neg x\_1 \wedge x\_2))$ -- there is a $0$ in the $8$'s position, and either the next three bits read $100$, or the next two bits read $01$. Note that this is equivalent to partitioning the interval into subintervals aligned with powers of $2$.
3. Represent the boolean formula as a BDD
4. Similarly, write $\[k..k\]$ as a boolean formula. Use standard BDD algorithms to XOR the two BDDs.
5. Read the intervals out of the BDD. For example, if $n=5$, and we take the path in the BDD corresponding to setting $x\_0=1,x\_1=0,x\_2=1$, and find that we have reached a true leaf (i.e.: a five-digit binary number that starts with 101 is in the set no matter what its lower two digits are), then the interval $\[20..23\]$ is in the set.

Depending on the application, you might want to leave the set as a BDD rather than reading it out back into intervals, as the BDD representation may be much more compact.

There is also a more elementary and direct solution. Note that XOR'ing by $k$ is equivalent to sequentially XOR'ing by each bit of $k$. Break $k$ into bits, and break $\[a..b\]$ into subintervals aligned with powers of two, and see what happens to each subinterval. You can work this out, and implement it efficiently using segtrees, but I expect that it will be equivalent to the BDD solution, which is faster and allows for the use of standard libraries.

**Analysis**

Analyzing BDDs is slightly tricky, but I'll have a go.

$\[a..b\]$ can be represented using at most $2\lceil\log(b-a)\rceil$ power-of-2-aligned subintervals. I'm not sure how to properly show it, but visualizing the resulting BDD, we see it will have a sort of "triskelion" structure, with size $O(\log(b-a))$.

Let $n=\max(a,b,k)$. XORing each subinterval by $k$ will preserve the subinterval, but may move it. Since each subinterval takes $O(\log n)$ space to represent and there are $O(\log n)$ of them, this lets us bound the size of the resulting BDD as $O((\log n)^2)$. I believe this gives us a $O((\log n)^2)$ bound on the entire operation, but don't quote me on that -- the runtime is proportional to the size of the intermediate BDDs, and I'll have a bit more thinking to do to determine what happens there.
> 7 votes

# Answer
Here is one straightforward algorithm. I'm not sure what the worst case running time is, but it is at most $O(n\log^2 n )$, where $n=\max(a,b,k)$.

1. Compute the list $\[k\oplus a,\ldots,k\oplus b\]$.
2. Split the resulting list into *obvious* intervals, by merging adjacent entries whenever they form an interval, and creating a new interval when they don't.
3. Sort the resulting list of intervals. (This takes potentially $O(n\log n)$ steps, where each comparison is $O(\log n)$.)
4. Merge adjacent intervals.

Here is the algorithm in Haskell:

```
import Data.Bits
import Data.List

-- implements step 2
split (a:as) = split_ (a,a) as
    where split_ (c,d) [] = [(c,d)]
          split_ (c,d) (e:list) | e == d + 1 = split_ (c,e) list
                                | otherwise  = (c,d) : split_ (e,e) list

-- implements step 4
merge (a:as) = merge_ a as
    where merge_ (c,d) [] = [(c,d)]
          merge_ (c,d) ((e,f):list) | e == d + 1 = merge_ (c,f) list
                                    | otherwise  = (c,d) : merge_ (e,f) list

intervals k a b
  = merge $ sortBy (\(a,b) (c,d) -> compare a c) $ split $ map (\x -> xor k x) [a..b]

```
> 4 votes

# Answer
This should be a comment to the nice answer by @JamesKoppel but it is too large for a comment:

I don't think that the size of the BDD for $\[a \ldots b\]$ is $O(\log (b-a))$ because even to test if the $n$ Boolean input variables are equal to a fixed constant requires linear size BDD size in the number of variables, i.e. here $O(\log n)$. Similar to your idea in 2., it is possible to show that the size of the BDD for $\[a \ldots b\]$ has also linear size and can be efficiently constructed (i.e. in linear time according to the BDD size), see e.g. here for the construction and proof idea.

According to the running time: You have one XOR operation on BDDs of size $O(\log n)$. The running time for a XOR operation (and also the size of the resulting BDD) is in the order of the product of the sizes of the involved BDDs, i.e. overall we have a running time of $O(\log^2 n)$. A good reference about the complexity of such operations is the book Branching Programs and Binary Decision Diagrams by Ingo Wegener.

I do not want to go into detail but I think the last step is a little bit more complex than you describe. But I think it can be done in time $O(\log^2 n)$ (i.e. linear to the BDD size) to get the pattern of the 1-inputs and then you need $O(m)$ time to output the intervals.
> 2 votes

---
Tags: algorithms, integers
---


# Question
Title: Is NP-hard closed against cartesian product with arbitrary languages?
If $L\_1$ is NP-hard, $L\_1 \times L\_2$ is NP-hard for every $L\_2 \neq \emptyset$, where

$\qquad \displaystyle L\_1 \times L\_2 = \\{(w\_1,w\_2) \mid w\_1 \in L\_1, w\_2 \in L\_2\\}$

Is it true or false and why?

I can't prove it but I also don't find counter example.

# Answer
> 6 votes
$L\_1 \times L\_2$ is NP-hard.

**Proof:** Let $L$ be a language in NP, let $f$ be a reduction of $L$ to $L\_1$ and let $w\_2$ be in $L\_2$. Define $g(x) = (f(x), w\_2)$. Now $g$ is a polynomial time many-to-one reduction of $L$ to $L\_1 \times L\_2$ because clearly:

$x \in L \quad \Longleftrightarrow\quad (f(x), w\_2) \in L\_1\times L\_2$

---
Tags: complexity-theory, np-hard
---


# Question
Title: Neighbourhood in local search metaheuristic
I cannot seem to find an answer to this question with Google, so I am going to ask here: is it required for a good neighbourhood function that it in principle (i. e. by recursively considering all neighbours of a certain solution - which is not practical) can reach all possible solutions?

My question is whether there are references in literature that explicitely state it's a requirement - I can see that it is a good property of a neighbourhood.

# Answer
I think the property of being able to reach all the successor states from a current state is crucial and needed in order for the problem to be well-defined. If this was not the case, you might miss out on good solutions. Moreover, **you might never reach a goal state and hence run forever.**

The classic AI book by Russell & Norvig, 3rd edition, page 67 gives a formal definition for a problem. One of the components is a successor function which returns all the successor states for a current state. Together the formal components create a search space, that is the set of all states reachable from the initial state. If one uses a different successor function, namely such that it leaves out some successors, the resulting search space is a different one: goal state(s) might be missing and optimal solutions might very well differ. Perhaps the reason you are unable find it from the literature is that the requirement is obvious.
> 3 votes

---
Tags: optimization, heuristics
---


# Question
Title: Find all the special graphs which can reduced to the shortest paths graph
I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative cycle.

An execution of some algorithms will find the lengths (summed weights) of the shortest paths between all pairs of vertices though it does not return details of the paths themselves. For instance, Floyd–Warshall algorithm is straightforward, and it works. Let us denote the result by $G' = (V, E, W')$.

In $G'$, it is possible that for an edge from $i$ to $j$, $w'(i,j) = w'(i, k\_0) + w'(k\_0, k\_1) + \dots + w'(k\_n, j)$. Let us make from $G'$ another graph $G''$ whose any element is same as $G'$ except $w''(i,j) = \infty \neq w'(i,j)$. Therefore we know that an execution of a shortest paths algorithm on $G''$ will give $G'$.

So given a $G'$, I would like to find all the graphs like $G''$, such that for all $i$ and $j$, $w''(i,j) \in \\{ w'(i,j), \infty\\}$, and $G''$ can be reduced to $G'$ via a shortest paths algorithm.

Hope my question is clear... I do not know if an algorithm for this exists already, does anyone have any idea?

# Answer
> -1 votes
Nearest neighbor, nearest insertion, farthest insertion, and cheapest insertion are just some heuristics to get you started. You can also model the problem as a maximum flow integer program.

http://www.ida.liu.se/~TDDB19/reports\_2003/htsp.pdf

---
Tags: algorithms, graphs
---


# Question
Title: Could an artificial neural network algorithm be expressed in terms of map-reduce operations?
Could an artificial neural network algorithm be expressed in terms of map-reduce operations? I am also interested more generally in methods of parallelization as applied to ANNs and their application to cloud computing.

I would think one approach would involve running a full ANN on each node and somehow integrating the results in order to treat the grid like a single entity (in terms of input/output and machine learning characteristics.) I would be curious even in this case what such an integrating strategy might look like.

# Answer
> 13 votes
Yes it can, and has been. In the paper Map-Reduce for Machine Learning on Multicore they discuss using the Map-Reduce paradigm for several common ML algorithms including ANNs.

---
Tags: parallel-computing, artificial-intelligence, neural-networks
---


# Question
Title: How to use dynamic programming to solve this?
Here is the question: suppose we are given x cents, the amount we want to pay, and a 6-tuple (p, n, d, q, l, t) that represents respectively the number of pennies, nickels, dimes, quarters, loonies and toonies you have. Assume that you have enough coins to pay x cents. You do not have to pay exactly x cents; you can pay more. The cashier is assumed to be smart enough to give you back the optimal number of coins as change. We want to minimize the number of coins that changes hands, that is the number of coins you give to the cashier plus the number of coins the cashier gives back to you.

For example, if we want to pay 99 cents and we have 99 pennies and 1 loonie, then the optimal solution would be to give the cashier the loonie and take back 1 penny.

A particularly easy solution that occurs to me is to create a six-dimensional array. But in practice this is not feasible. So I am wondering if anyone can give me a small hint as to how to use dynamic programming to solve this (as this question looks intuitively to me like a DP problem). Once I have a hint, I can perhaps work out the remaining details myself. Thanks.

# Answer
This is the famous change-making problem.

If you want to solve it with dynamic programming, you have to come up with a suitable recursion. The central question is:

> Assuming you know the optimal coin choices for all $k \< n$ (cents), how do you derive the optimal choice of coins for $n$ (cents)?
> 6 votes

# Answer
That looks to me as an instance of the Bounded Knapsack Problem, where there's a limited number of copies of each kind of item, turning the usual maximization of value into a minimization (you want to minimize the total number of coins given, within the possibilities entailed by the coins you have at hand).
> 0 votes

---
Tags: algorithms, optimization, dynamic-programming
---


# Question
Title: How do I construct a doubly connected edge list given a set of line segments?
> For a given planar graph $G(V,E)$ embedded in the plane, defined by a set of line segments $E= \left \\{ e\_1,...,e\_m \right \\} $, each segment $e\_i$ is represented by its endpoints $\left \\{ L\_i,R\_i \right \\}$. Construct a DCEL data structure for the planar subdivision, describe an algorithm, prove it's correctness and show the complexity.

According to this description of the DCEL data structure, there are many connections between different objects (i.e. vertices, edges and faces) of the DCEL. So, a DCEL seems to be difficult to build and maintain.

Do you know of any efficient algorithm which can be used to construct a DCEL data structure?

# Answer
> 13 votes
Data structure (conventions consistent with the Wikipedia article):

```
struct half_edge;

struct vertex {
    struct half_edge *rep;  /* rep->tail == this */
};

struct face {
    struct half_edge *rep;  /* rep->left == this */
};

struct half_edge {
    struct half_edge *prev;  /* prev->next == this */
    struct half_edge *next;  /* next->prev == this */
    struct half_edge *twin;  /* twin->twin == this */
    struct vertex *tail;     /* twin->next->tail == tail &&
                                prev->twin->tail == tail */
    struct face *left;       /* prev->left == left && next->left == left */
};

```

> ### Algorithm
>
> 1. For each endpoint, create a *vertex*.
> 2. For each input segment, create two *half-edges*, and assign their tail vertices and twins.
> 3. For each endpoint, sort the half-edges whose tail vertex is that endpoint in clockwise order.
> 4. For every pair of half-edges `e1, e2` in clockwise order, assign `e1->twin->next = e2` and `e2->prev = e1->twin`.
> 5. Pick one of the half-edges and assign it as the representative for the endpoint. (Degenerate case: if there's only one half-edge `e` in the sorted list, `set e->twin->next = e` and `e->prev = e->twin`). The next pointers are a permutation on half-edges.
> 6. For every cycle, allocate and assign a *face* structure.

---
Tags: algorithms, data-structures, computational-geometry, doubly-connected-edge-list
---


# Question
Title: Getting parallel items in dependency resolution
I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent paths?

# Answer
> 19 votes
I assume that an edge $(u,v)$ means that $u$ has to be executed before $v$. If this is not the case, turn around all edges. I furthermore assume that you are less interested in paths (those are already given by the DAG) than in a good execution strategy given the dependencies.

You can easily adapt the topological sort procedure: instead of appending, merge all items of the same "depth" to one set. You get a list of sets, each of which contains items you can execute/install in parallel. Formally, the sets $S\_i$ are defined thus for the graph $G = (V,E)$:

$\qquad \displaystyle \begin{align} S\_0 &= \\{ v \in V \mid \forall u \in V. (u,v) \notin E \\} \\ S\_{i+1} &= \\{v \in V \mid \forall u \in V. (u,v) \in E \to u \in \bigcup\_{k=0}^i S\_k \\} \end{align}$

You can then execute your tasks like this (let's assume there are $k$ sets):

```
for i=0 to k
  parallel foreach T in S_k
    execute T

```

Of course, this does not yield maximum throughput if tasks take different amounts of time: two parallel, independent linear chains sync after each element. To circumvent this, I suggest you work directly on the DAG with a parallel traversal starting in the source nodes -- those in $S\_0$ -- and syncing/forking in nodes with several incoming/outgoing edges:

```
parallel foreach T in S_0
  recursive_execute T

```

where

```
recursive_execute T {
  atomic { if T.count++ < T.indeg then return }
  execute T
  parallel foreach T' in T.succ
    recursive_execute T'
}

```

and `T.count` is a simple counter holding the number of predecessors of `T` which have been executed already, `T.indeg` the number of predeccessors and `T.succ` the set of successors.

---
Tags: algorithms, graphs, parallel-computing, scheduling
---


# Question
Title: Efficiently calculating minimum edit distance of a smaller string at each position in a larger one
Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently.

That is, for each suffix of $r$ beginning at position $k$, $r\_k$, find the Levenshtein distance of $r\_k$ and $s$ for each $k \in \[0, |r|-1\]$. In other words, I would like an array of scores, $A$, such that each position, $A\[k\]$, corresponds to the score of $r\_k$ and $s$.

The obvious solution is to use the standard dynamic programming solution for each $r\_k$ against $s$ considered separately, but this has the abysmal running time of $O(n m^2)$ (or $O(n d^2)$, where $d$ is the maximum edit distance). It seems like you should be able to re-use the information that you've computed for $r\_0$ against $s$ for the comparison with $s$ and $r\_1$.

I've thought of constructing a prefix tree and then trying to do dynamic programming algorithm on $s$ against the trie, but this still has worst case $O(n d^2)$ (where $d$ is the maximum edit distance) as the trie is only optimized for efficient lookup.

Ideally I would like something that has worst case running time of $O(n d)$ though I would settle for good average case running time. Does anyone have any suggestions? Is $O(n d^2)$ the best you can do, in general?

Here are some links that might be relevant though I can't see how they would apply to the above problem as most of them are optimized for lookup only:

I've also heard some talk about using some type of distance metric to optimize search (such as a BK-tree?) but I know little about this area and how it applies to this problem.

# Answer
> 4 votes
What you are interested in are semi-global and/or local alignments. The usual way to compute those is to adapt the dynamic programing algorithm for the Levenshtein distance:

* Initialise the first row/column with $0$ (instead of $i$/$j$) if free deletions/insertions are allowed at the beginning.
* Select the minimum value from the last row/column as result if free deletions/insertions are allowed at the end.

Different combinations are possible. In your case, assume that $r$ is the horizontal word, you initialise the first row with $0$ (the first column with $i$, no change here) and the result is the minimum of the last row. The result is then the smallest Levenshtein distance between $s$ and any substring of $r$, computed in time and space $O(nm)$.

Now, in order to get scores for *all* starting positions, note that the computation of semi-global alignments with allowed deletions/insertions at the end conveniently provides the wanted array in the last row/column -- well, almost: that gives you the best matches against prefixes up to position $k$. So in order to get best matches against suffixes from position $k$, reverse both $r$ and $s$.

# Answer
> 1 votes
Run the usual DP on rev(r) and rev(s). The answer for the length-k suffix is in the entry (k, m) of the last column, assuming that the table is indexed as (index in r, index in s).

---
Tags: algorithms, runtime-analysis, strings, dynamic-programming, string-metrics
---


# Question
Title: Is the type inference here really complicated?
There's a question on SO asking why in Java the right type doesn't get picked in a concrete case. I know that Java can't do it in such "complicated" cases, but I'm asking myself *WHY*?

The (for simplicity slightly modified) line failing to compile is

```
Map<String, Number> m = ImmutableMap.builder().build();

```

and the methods are defined as1

```
class ImmutableMap {
    public static <K1, V1> Builder<K1, V1> builder() {...}
    ...
}

class Builder<K2, V2> {
    public ImmutableMap<K2, V2> build() {...}
    ...
}

```

The solution `K1=K2=String` and `V1=V2=Number` is obvious to everyone but the compiler. There are 4 variables here and I can see 4 trivial equations, so what's the problem with type inference here?

1I simplified the code piece from Guava for this example and numbered the type variables to make it (hopefully) clearer.

# Answer
> 4 votes
This is a common limitation of type inferencing and it has to do with the distinction between parameters and results of a function. Generally type inferencing is done strictly with the parameters passed to a function. Consider just the expression:

```
ImmutableMap.builder().build();

```

This has to be a valid expression due to how the language works. This means the type inferencing has to work from this expression alone. There is of course nothing in this expression which reveals what type you are expecting, thus it cannot compile (the type of the expression is not known).

It really isn't a question of how complicated the inferencing is, but rather a question of the fundamental structure of the language. It is possible to design a language where the return type becomes an implicit parameter to a function. However, this starts to create a loop in the typing logic in languages where variables can be auto-type (like C++).

---

The reason this happens is because of how the syntax trees for such languages are built (this may be only in theory as the compiler may not match exactly). When you have an expression like the above you have a tree that might look kind something like this:

```
- Assignment
    - LValue: Map<String, Number> m
    - RValue: FunctionCall(
          FunctionCall( ImmutableMap, builder ),
          build
      )

```

In such languages the "RValue" is essentially an expression -- where expressons are something that resolves to a value. These are processed on their own, and thus limited to the variables and sub-expressions which occur in them. Type inferencing doesn't usually go up tree, thus the FunctionCall has no knowledge it is part of the Assignment tree and thus no knowledge of the "LValue" (what it is being assigned to).

This is the traditional way to process languages (it even applies to formal languages like lambda calculus). Languages don't have to work this way, but there it is the most commonly understood way parsing works. You can certainly make a syntax tree which forwards type information in an assignment, but that leads to the pitfall I mentioned if the "LValue" is auto-typed. If you attempt to allow both sides to infere their type you start entering a constraint based typed system (which again, is possible and I have worked on one before).

---

One practical way of doing this in some languages is to pass the return variables by reference (which isn't really possible in Java). In C++ I often do this where the function requires its return type. Instead of doing:

```
var = someFunc(...);

```

I'll do:

```
someFunc( var, ... );

```

And this allows the type of "var" to be known by the function (in this case for template resolution).

---
Tags: programming-languages, typing, java, type-inference
---


# Question
Title: Time to construct a GNBA for LTL formula
I have a problem with the proof for constructing a GNBA (generalized nondeterministic Büchi automaton) for a LTL formula:

**Theorem:** For any LTL formula $\varphi$ there exists a GNBA $G\_{\varphi}$ over alphabet $2^{AP}$ such that:

1. $\operatorname{Word}(\varphi)=L\_{\omega}(G\_{\varphi})$.
2. $G\_{\varphi}$ can be costructed in time and space $2^{O(|\varphi|)}$, where $|\varphi|$ is the size of $\varphi$.
3. The number of accepting states of $G\_{\varphi}$ is bounded above by $O(|\varphi|)$.

My problem lies in the proof of (2), that is, in the proof it says that the number of states in $G\_{\varphi}$ is bounded by $2^{|\operatorname{subf}(\varphi)|}$ but since $|\operatorname{subf}(\varphi)| \leq 2\cdot|\varphi|$ (where $\operatorname{subf}(\varphi)$ is the set of all subformulae) the number of states is bounded by $2^{O(|\varphi|)}$.

But why does $|\operatorname{subf}(\varphi)| \leq 2\cdot|\varphi|$ hold?

# Answer
> 3 votes
In general, logical formulae can be thought of as trees; inner nodes are operators and leaves are atomic propositions. Therefore, every formula consists of as many direct subformulae (that is on the first level) as its top-most operator's arity. For example,

$\qquad \varphi \land \psi$

has two direct subformulae $\varphi$ and $\psi$. This can be continued recursively and we see that

$\qquad \displaystyle |\operatorname{subf}(\varphi)| \leq \sum\_{\circ \in \operatorname{op}(\varphi)} \operatorname{arity}(\circ)$,

where $\operatorname{op}(\varphi)$ is the multi-set of operators occurring in $\varphi$. Informally speaking, every operator contributes its operands to the set of subformulae. Note that we have $\leq$ and not $=$ because a subformula might occur multiple times.

In LTL, all operators have at most arity two, so $|\operatorname{subf}(\varphi)| \leq 2|\varphi|$ provided that $|.|$ counts (at least) operator occurrences.

---
Tags: logic, automata, formal-methods, model-checking, linear-temporal-logic
---


# Question
Title: Are supersets of non-regular languages also non-regular?
I have to proof that if $L\_1 \subset L\_2$ and $L\_1$ is not regular then $L\_2$ it not regular. This is my proof. Is it valid?

Since $L\_1$ is not regular, there does not exists a finite automata $M\_1$ such that $L\_1$ is the language of $M\_1$. Pick $x\in L\_1$. So $x \in L\_2$ and suppose that $L\_2$ is regular. Then there exists a finite automata $M\_2$ such that $L\_2$ is the language of $M\_2$. Since $x \in L\_2$ and $L\_2$ is regular, there exists a state $s\in S$ such that from the initial state in $M\_2$ there is a path $x$ to this final state $s$. Since this holds for all $x \in L\_1$, we can construct a finite automata which language is $L\_1$, so $L\_1$ is regular, so we reached a contradiction, so $L\_2$ is not regular.

Can this be done easier?

# Answer
> 6 votes
I have a very simple counter example. Take $$L\_2 = \Sigma^{\*}$$ (where $\Sigma$ is the alphabet you are working over). Every language is a subset of $L\_2$, in particular the non-regular languages are (strict) subsets of $L\_2$, yet $L\_2$ is regular.

A finite automaton accepting $L\_2$ has only one state and this state is an accept state. For each $x \in \Sigma$ there is an edge going from the only state to itself.

# Answer
> 5 votes
> Since this holds for all $x\in L\_1$, we can construct a finite automata which language is $L\_1$.

And how would you do this? You have an *infinite* amount of paths in hands which you have to mold into a *finite* set of states and edges.

In fact, the statement does not hold.

> Remember that $\Sigma^\*$ is regular but there are non-regular languages.

---
Tags: formal-languages, regular-languages, automata, finite-automata, check-my-proof
---


# Question
Title: Minimizing the total variation of a sequence of discrete choices
My setup is something like this: I have a sequence of sets of integers $C\_i (1\leq i\leq n)$, with $|C\_i|$ relatively small - on the order of four or five items for all $i$. I want to choose a sequence $x\_i (1\leq i\leq n)$ with each $x\_i\in C\_i$ such that the total variation (either $\ell\_1$ or $\ell\_2$, i.e. $\sum\_{i=1}^{n-1} |x\_i-x\_{i+1}|$ or $\sum\_{i=1}^{n-1} \left(x\_i-x\_{i+1}\right)^2$) is minimized. While it seems like the choice for each $x\_i$ is 'local', the problem is that choices can propagate and have non-local effects and so the problem seems inherently global in nature.

My primary concern is in a practical algorithm for the problem; right now I'm using annealing methods based on mutating short subsequences, and while they should be all right it seems like I ought to be able to do better. But I'm also interested in the abstract complexity — my hunch would be that the standard query version ('is there a solution of total variation $\leq k$?') would be NP-complete via a reduction from some constraint problem like 3-SAT but I can't quite see the reduction. Any pointers to previous study would be welcome — it seems like such a natural problem that I can't believe it hasn't been looked at before, but my searches so far haven't turned up anything quite like it.

# Answer
> 4 votes
Here is a dynamic program. Assume that $C\_i = \\{C\_{i\_1}, \ldots, C\_{i\_m}\\}$ for all $i \in \[n\]$ for the sake of clarity; the following can be adapted to work if the $C\_i$ have different cardinalities. Let $\operatorname{Cost}(i, j)$ be the minimum cost of a sequence over the first $i$ sets, ending with $C\_{i\_j}$. The following recursion describes $\operatorname{Cost}$:

$\qquad \displaystyle \begin{align} \operatorname{Cost}(1,j) &= 0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad, 1\leq j \leq m \\ \operatorname{Cost}(i,j) &= \min\_{k = 1}^m \left(\operatorname{Cost}(i - 1, k) + \lvert C\_{(i-1)\_k} - C\_{i\_j} \rvert\right) \ , 2 \leq i \leq n, 1 \leq j \leq m. \end{align}$

The overall minimum cost is $\min\_{j = 1}^m \text{Cost}(n, j)$; the actual sequence of choices can be determined by examining the argmins along the way. The runtime is $O(nm)$.

# Answer
> 4 votes
It seems that this can be solved by simply computing a shortest path in a directed acyclic graph. The reasoning is that your objective function minimizes the total distance between selected "neighbors" in your sets $\mathcal{C} = \\{C\_1, \dotsc, C\_n\\}$.

Construct an $n$-staged graph $G = (\bigcup\_{i=1}^n V\_i, E)$ where each $v \in V\_i$ corresponds to a unique element $x \in C\_i$. For each $u \in V\_i, v \in V\_{i+1}$, add a directed edge $(u, v)$ the cost being either the $\ell\_1$ or $\ell\_2$ distance.

Now add a source vertex $s$ with 0-cost edges to $V\_1$ and a sink vertex $t$ with 0-cost edges from $V\_n$. Given that $G$ is a DAG and both distance functions force edge costs to be non-negative, you can compute the shortest path in $O(V + E)$ with topological sort and dynamic programming (similar to description here).

---
Tags: algorithms, complexity-theory, optimization
---


# Question
Title: Find string that minimizes the sum of the edit distances to all other strings in set
I have a set of strings $S$ and I am using the edit-distance (Levenshtein) to measure the distance between all pairs.

Is there an algorithm for finding the string $x$ which minimizes the sum of the distances to all strings in $S$, that is

$\arg\_x \min \sum\_{s \in S} \text{edit-distance}(x,s)$

It seems like there should, but I can't find the right reference.

# Answer
The problem is known as "median string problem" and it is NP-complete; some results can be found searching with Google; in particular "2-Approximation Algorithms for Median and Centre String Problems". If $x$ must be one of the points in $S$ then the problem becomes solvable in polynomial time.
> 4 votes

---
Tags: algorithms, reference-request, strings, string-metrics
---


# Question
Title: Maximum number of points that two paths can reach
Suppose we are given a list of $n$ points, whose $x$ and $y$ coordinates are all non-negative. Suppose also that there are no duplicate points. We can only go from point $(x\_i, y\_i)$ to point $(x\_j, y\_j)$ if $x\_i \le x\_j$ and $y\_i \le y\_j$. The question is: given these $n$ points, what is the maximum number of points that we can reach if we are allowed to draw two paths that connect points using the above rule? Paths must start from the origin and may contain repeated points. $(0, 0)$ is of course not included in the points reached.

An example: given $(2, 0), (2, 1), (1, 2), (0, 3), (1, 3), (2, 3), (3, 3), (2, 4), (1, 5), (1, 6)$, the answer is $8$ since we can take $(0, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4)$ and $(0, 0) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 5) \rightarrow (1, 6)$.

If we are allowed to draw only one path, I can easily solve the question by dynamic programming that runs in $O(n^2)$. I first sort the points by decreasing $x\_i+y\_i$. Let $D\[i\]$ be the maximum number of coins that one can pick up from coins $1$ to $i$ in the sorted list. Then $D\[1\] = 1$ and $D\[i\] = \max\limits\_{1\le j \< i, x\_j \le x\_i, y\_j \le y\_i} D\[j\] + 1$. The answer then is just $\max\limits\_{1\le i \le n} D\[i\] + 1$.

But I cannot come up with a recurrence relation for two paths. If anyone has any idea about such a recurrence relation, I would be happy to hear what they are.

# Answer
> 4 votes
The problem, restated and generalized: given a finite set $S$ equipped with a partial order $\le$, find chains $C\_1, C\_2 \subseteq S$ maximizing $\lvert C\_1 \cup C\_2 \rvert$. The question is about the case where $S \subseteq \mathbb R\_+^2$ and $(x, y) \le (z, w) \Longleftrightarrow x \le z \wedge y \le w$.

Naively, one might try to find the single best chain in $S^2$, where best is measured by how many distinct values the components of the chain have. Unfortunately, one component can retrace the steps of the other, e.g., $$\bigl((0,0),(0,0)\bigr) \< \bigl((1,0),(0,0)\bigr) \< \bigl((2,0),(0,0)\bigr) \< \bigl((2,0),(1,0)\bigr),$$ so this notion of best does not have optimal substructure.

Instead, we look for chains in the set $T := \\{(x, y) \mid (x, y) \in S^2 \wedge x \nless y \wedge y \nless x\\}$. By requiring that the components be equal or incomparable, we prevent retracing but now need to argue that some best chain conforms to the new requirement.

**Lemma 1 (no retracing).** Let $C \subseteq T$ be a chain and define $C\_1 := \\{x \mid (x, y) \in C\\}$ and $C\_2 := \\{y \mid (x, y) \in C\\}$. For all $z \in S$, we have $z \in C\_1 \cap C\_2$ if and only if $(z, z) \in C$.

**Proof.** The if direction is trivial. In the only if direction, for all $z \in C\_1 \cap C\_2$, there exist $x, y \in S$ such that $(x, z), (z, y) \in C$. Since $C$ is a chain, $(x, z) \le (z, y) \vee (z, y) \le (x, z)$. Assume symmetrically that $(x, z) \le (z, y)$, which implies that $x \le z \le y$. We know by the definition of $T$ that $x \nless z \wedge z \nless y$, so $x = z = y$, and $(z, z) \in C$.

**Lemma 2 (existence of restricted best chain).** For all chains $C\_1, C\_2 \subseteq S$, there exists a chain $C \subseteq T$ such that $C\_1 \subseteq \\{x \mid (x, y) \in C\\} \subseteq C\_1 \cup C\_2$ and $C\_2 \subseteq \\{y \mid (x, y) \in C\\} \subseteq C\_1 \cup C\_2$.

**Proof (revised).** We give an algorithm to construct $C$. For convenience, define sentinels $\bot, \top$ such that $\bot \< x \< \top$ for all $x \in S$. Let $C\_1' := C\_1 \cup \\{\top\\}$ and $C\_2' := C\_2 \cup \\{\top\\}$.

1. Initialize $C := \varnothing$ and $x := \bot$ and $y := \bot$. An invariant is that $x \nless y \wedge y \nless x$.
2. Let $x'$ be the next element of $C\_1$, that is, $x' := \inf \\{z \mid z \in C\_1' \wedge x \< z\\}$. Let $y'$ be the next element of $C\_2$, that is, $y' := \inf \\{w \mid w \in C\_2' \wedge y \< w\\}$.
3. If $x' \nless y' \wedge y' \nless x'$, set $(x, y) := (x', y')$ and go to step 9.
4. If $y \< x' \< y'$, set $(x, y) := (x', x')$ and go to step 9.
5. If $y \nless x' \< y'$, set $x := x'$ and go to step 9. Note that $x \< x' \wedge x \nless y$ implies that $x' \nless y$.
6. If $x \< y' \< x'$, set $(x, y) := (y', y')$ and go to step 9.
7. If $x \nless y' \< x'$, set $y := y'$ and go to step 9. Note that $y \< y' \wedge y \nless x$ implies that $y' \nless x$.
8. This step is never reached, as the conditions for steps 3–7 are exhaustive.
9. If $x \ne \top$ (equivalently, $y \ne \top$), set $C := C \cup \\{(x, y)\\}$ and go to step 2.

**Dynamic Program.** For all $(x, y) \in T$, compute $$ D\[x, y\] := \sup\biggl(\Bigl\\{D\[z, w\] + \[x \ne z\] + \[y \ne w\] - \[x = y\] \mathrel{\Bigl|\Bigr.} (z, w) \in T \wedge (z, w) \< (x, y)\Bigr\\} \cup \bigl\\{2 - \[x = y\]\bigr\\}\biggr), $$ where $\[\textit{condition}\] = 1$ if $\textit{condition}$ is true and $\[\textit{condition}\] = 0$ if $\textit{condition}$ is false. By Lemma 1, it follows that the bracket expressions correctly count the number of new elements. By Lemma 2, the optimal solution to the original problem is found.

# Answer
> 0 votes
Let $P = p\_1\dots p\_n$ to sorted list of points.

---

Following your recurrence for one path, the first thing to note is that you have to keep track of which points have been visited by the paths; otherwise you can not count correctly. The second thing is that you have now *four* possibilities for every point: neither path may use it, one of them or both. So, we have to find maximising combinations for all three cases.

Formally, let $d : \[0\dots n\] \to (2^{\[n\]} \times 2^{\[n\]})^3$ with $d(i)$ the pair of (sets of) visited nodes of the two paths that maximise the number of visited points from the input set up to the $i$th one, with the first component the maximising pair of paths for which the first one uses $p\_i$, the second component similar for the second path and the third component with both paths using $p\_i$. $d$ is given by the recurrence

$\quad \displaystyle \begin{align} d(0) &= ((\emptyset, \emptyset),(\emptyset, \emptyset),(\emptyset, \emptyset)) \\ d(i) &= (\ \arg\max\_{(L,R) \in (\mathcal{L}' \times \mathcal{R})\_i} |L \cup R|, \\ &\phantom{= (\ } \arg\max\_{(L,R) \in (\mathcal{L} \times \mathcal{R}')\_i} |L \cup R|, \\ &\phantom{= (\ } \arg\max\_{(L,R) \in (\mathcal{L}' \times \mathcal{R}')\_i} |L \cup R| \ ) \\ \end{align}$

with

$\quad \displaystyle (\mathcal{L}' \times \mathcal{R})\_i = \left\\{ (L \cup \\{i\\}, R) \mid (L,R) \in \bigcup\_{j=0}^{i-1} d(j), x\_i \geq \max\_{j \in L} x\_j, y\_i \geq \max\_{j \in L} y\_j \right\\}$,

$(\mathcal{L}' \times \mathcal{R})\_i$ similar with extending $R$ and $(\mathcal{L}' \times \mathcal{R}')\_i$ similar with extending both $L$ and $R$.

Needless to say, this is not very nice. This is because the problem does not lend itself to dynamic programming very well: you can not combine many partial solutions because there is no nice total ordering on the points, and you can not discard intermediate results for the same reason.

---

A nicer view on the problem is to model the set of points as weighted directed acyclic graph $G = (V, E, w)$ with

* $V = \\{(0,0), p\_1, \dots, p\_n, (X,Y)\\}$ with $X = \max x\_i$, $Y = \max y\_i$, and
* $E = \\{ ((x\_1, y\_1),(x\_2,y\_2)) \in V^2 \mid x\_i \leq x\_j, y\_i \leq y\_j\\}$ and
* $w(v\_1,v\_2) = \begin{cases} 0 &, v\_2 = (X,Y) \\ 1 &, \text{ else}\end{cases}$.

Note that you can keep the graph smaller if you remove redundant edges, that is remove $(v\_1,v\_2)$ if there is a path $(v\_1,\dots,v\_2)$, because taking such "shortcuts" is never better advantageous.

For one path, the solution is clearly the length of the longest path $P^\*$ from $(0,0)$ to $(X,Y)$. Now, if we change $w$ so that all edges leading to points on $P^\*$ also have weight $0$ and compute the longest path in this modified graph, we get a path $P^+$ so that $P^\*$ and $P^+$ together cover as many points as two paths can. This leaves us with a runtime in $O(|V| + |E|) \subseteq O(n^2)$ (see here).

---
Tags: computational-geometry, dynamic-programming, recurrence-relation
---


# Question
Title: Finding at least two paths of same length in a directed graph
Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$. I would like to know if there are already algorithms for calculating the following decision problem:

> Are there at least two paths between $A$ and $B$ of the same length?

How about the complexity? Can I solve it in polynomial time?

---

I would like to add a new constrain on the graph, maybe the problem is more solvable. On adjacency matrix, every column is not empty. So, every node has at least one arrow on input and there is also at least one node connected to itself. So if the node is the $i$-th node, then $(i,i)$ is an edge in the graph.

# Answer
Consider a graph $G$, we want to know if there are two different paths from $A$ to $B$ of the same length. What to do? Simple: code two paths in one. Define graph $G'$ with vertices $V \times V \times \\{0,1\\}$. You make a step in $G'$ by making two independent steps in $G$. The additional bit tells you whether the two paths have already split from each other.

Formally, there is an edge $(i,j,e) \to (i',j',e')$ in $G'$ iff $i \to i'$, $j \to j'$ in $G$ and $e'=e ∨ (i,i')≠(j,j')$.

The algorithm checks if there is a path $(A,A,0)$ to $(B,B,1)$ in $G'$, which is $O(V^4)$, or something like $O((V+E)^2)$.

If you agree this algorithm is correct then, as a consequence, the path in $G'$ is of length at most $2n^2$, therefore potential "path collisions" must occur latest at that length. You can get a $O(V^{\omega} \log V)$ algorithm from this observation, where $\omega$ is matrix multiplication complexity (ask if you need a spoiler...).

I strongly feel there is a $O(V+E)$ algorithm, which uses more of the structure of the problem.
> 10 votes

# Answer
Probably i've an answer for this problem, but i'm not sill sure that it works.

It is not important to "find" the two path, the only important thing is to "know" if they exist or not. I don't think that this is an NP complete problem.

So, take the adjacency matrix $\textbf A$. We can easily suppose that it is filled with 0,1 value. (0 = no edge; 1 = there is an edge) Let's use the following algebra with 3 values (0,1,2), where everything works as usual except: $2+\text{\<something\>} = 2$; $2\*\text{\<whatever greater than 0\>} = 2$

So, if there are two paths of same length from $i,j$ i'm expecting that there is a value $p$ such that $(\textbf A^p)\_{i,j} = 2$.

Let $n$ is the number of vertex in the graph (or, let's say, that $\textbf A$ has dimension $n\times n$). I don't know the value of $p$, but if i iterate $\textbf A$ by multiplying with itself for at most $n^2$ i should find the answer. (so, $p\<n^2$) (the sense is that i check $\text A$, then i check $\text A^2$, then i check $\text A^3$ and so on...)

here is my argumentation:

* if the two paths are simple paths, well, it works; if there are, at most i have to iterate $n$ times.
* If there is at least one neasted cycle or there is a path with two cycles, well, i have to find the least common multiple (LCM). $n^2$ is a bigger value for sure and in less than $n^2$ times if there is i should have to find them.
* If the two paths are two distinct paths, both with one cycle, then it's more or less similar to finding a solution for this two equation: $\alpha + \beta m = \gamma + \delta k$, where $m$ and $k$ are the length of these two distinct cycles. Matrix multiplication $\text A^q$, as defined above, says "is there a path from $i$ to $j$ whose length is $q$?" So, if $\textbf A^q$ is grater than $1$ it means that there are more paths leading from $i$ to $j$. By iterating the matrix $n^2$ times we pass through all the possible combination of $\delta$ and $\beta$. Indeed, $LCM(a,b)$ is defined as $(a\*b)/GCD(a,b)$ and no cycle can be greater than $n$.

I stop to iterate once i found $(\textbf A^p)\_{i,j} = 2$.

am i wrong?
> 4 votes

---
Tags: complexity-theory, graphs, time-complexity
---


# Question
Title: Algorithm to test a graph for $t$-transitivity
I am looking for an algorithm, which given a graph $G$ and a natural number $t$, determines if $G$ is $t$-transitive.

I am also interested in knowing if this problem is in P, NP, NPC or some other interesting facts about its complexity class.

# Answer
> 4 votes
If you had an oracle from Graph Isomorphism, then for constant $t$ you can check whether a graph is $t$-transitive. For example, to check if a graph is $1$-transitive, for every vertex $i$ create a variant $G\_i$ of your original graph by attaching an "appendage" at vertex $i$, say a very long path or a very large star. The graph is transitive if all $G\_i,G\_j$ are isomorphic.

---
Tags: algorithms, graphs
---


# Question
Title: 3-dimensional matching approximation algorithm (implementation details)
I have a run-time implementation question regarding the 3-dimensional (unweighted 2-)approximation algorithm below: How can I construct the maximum matching M\_r in S\_r in linear time in line 8?

$X, Y, Z $ are disjoint sets; a matching $M$ is a subset of $S$ s.t. no two triples in $M$ have the same coordinate at any dimension.

$ \text{Algorithm: unweighted 3-dimensional matching (2-approximation)} \\ \text{Input: a set $S\subseteq X \times Y \times Z$ of triples} \\ \text{Output: a matching M in S} $

```
 1) construct maximal matching M in S;
 2) change = TRUE;
 3) while (change) {
 4)   change = FALSE;
 5)   for each triple (a,b,c) in M {
 6)     M = M - {(a,b,c)};
 7)     let S_r be the set of triples in S not contradicting M;
 8)     construct a maximum matching M_r in S_r;
 9)     if (M_r contains more than one triple) {
10)       M = M \cup M_r;
11)       change = TRUE;
12)     } else {
13)       M = M \union {(a,b,c)};
14)     }
15) }

```

---

\[1\] http://faculty.cse.tamu.edu/chen/courses/cpsc669/2011/notes/ch9.pdf, p. 326

# Answer
We don't need the maximum matching, just one of cardinality $2$ if it exists.

Scan $S\_r$ looking for a triple $T$ such that $\lvert T \cap \\{a, b, c\\}\rvert = 1$. If no such $T$ exists, then the maximum cardinality of a matching is clearly $1$. Otherwise, assume without loss of generality that $T = \\{a, x, y\\}$.

Scan $S\_r$ again looking for a triple $U$ such that $T \cap U = \varnothing$. If no such $U$ exists, then every triple intersects both $\\{a, b, c\\}$ and $T$. For every $U \in S\_r$, we have $\\{a\\} \subseteq U$ or $\\{b, x\\} \subseteq U$ or $\\{b, y\\} \subseteq U$ or $\\{c, x\\} \subseteq U$ or $\\{c, y\\} \subseteq U$.

There are several possibilities for a cardinality-$2$ matching $\\{T\_1, T\_2\\}$. There's an easy test for those of type $\\{b, x\\} \subseteq T\_1$ and $\\{c, y\\} \subseteq T\_2$. Similarly, $\\{b, y\\}$ and $\\{c, x\\}$. The only other types are the four like $\\{a\\} \subseteq T\_1$ and $\\{b, x\\} \subseteq T\_2$. To test for those, gather all triples of the form $\\{b, x, z\\} \in S\_r$ and discard the ones in excess of three. Try each of the remainder against all possibilities containing $a$. The three $\\{b, x, z\\}$ candidates suffice because no triple containing neither $b$ nor $x$ intersects all three.
> 0 votes

---
Tags: algorithms, graphs, approximation, matching
---


# Question
Title: Why is GFp -> GFq false in LTL, even though GFp and GFq are false?
Consider the Kripke structure: $$ \begin{array}{ccccccc} \to & (p, \neg q) & \to & (\neg p, \neg q) & \to & (\neg p, q) \\ & \circlearrowright & & \circlearrowright & & \circlearrowright & \\ \end{array} $$

where $(p, \neg q)$ means “$p$ and not $q$” and $\circlearrowright$ is a self loop. We number the states $s\_1, s\_2, s\_3$ from left to right. Now consider the three LTL properties: $$ \begin{array}{ll} M \vDash \mathbf{G}\\,\mathbf{F}\\,p \to \mathbf{G}\\,\mathbf{F}\\,q & \text{false} \\ M \vDash \mathbf{G}\\,\mathbf{F}\\,p & \text{false} \\ M \vDash \mathbf{G}\\,\mathbf{F}\\,q & \text{false} \\ \end{array}$$

The oddity is this: how can $\text{false} \to \text{false}$ be false?

P.S.: I am sure of the results because I used NuSMV with the following code:

```
MODULE main
VAR
   state : {a, b, c};
   p : boolean;
   q : boolean;

ASSIGN
   init(state) := a;
   next(state) :=
       case
         state=a : {a,b};
         state=b : c;
         state=c : c;
   esac;
p :=
  case
    state=a : TRUE;
    state=b : FALSE;
    state=c : FALSE;
  esac;
q :=
  case
    state=a : FALSE;
    state=b : FALSE;
    state=c : TRUE;
  esac;

LTLSPEC
   ((G ( F p = TRUE)) ->  (G ( F q = TRUE)))
LTLSPEC
   (G ( F p = TRUE))
LTLSPEC
   (G ( F q = TRUE))

```

# Answer
> 5 votes
This happens because of the way LTL formulae are evaluated over Kripke structures: Recall that LTL is first of all a logic of traces; when we say that a Kripke structure $S$ satisfies $\varphi$, we mean that all its traces do, i.e. we have an implicit universal quantification.

The consequence is that, for an LTL formula $\varphi$, it is possible that neither $\varphi$ nor $\neg\varphi$ is true for $S$, because neither holds for all traces. Similarly, none of your three formulas above holds for every trace.

If you are more familiar with predicate calculus, this is just saying that $(\forall x.A)\vee(\forall x.\neg A)$ is not a tautology, and neither is $(\forall x.A)\vee(\forall x.B)\vee(\forall x.A\to B)$.

# Answer
> 3 votes
Extending upon Klaus' answer, here are counter-examples:

1. $s\_1^\omega = (p,\lnot q)^\omega$ is a trace -- so $\mathrm{G}\\, \mathrm{F}\\, q$ is not valid.
2. $s\_1s\_2^\omega = (p,\lnot q)(\lnot p,\lnot q)^\omega$ is a trace -- so $\mathrm{G}\\, \mathrm{F}\\, p$ is not valid.
3. $s\_1^\omega = (p,\lnot q)^\omega$ is a trace -- $\mathrm{G}\\, \mathrm{F}\\, p$ holds for this trace but $\mathrm{G}\\, \mathrm{F}\\, q$ does not, so $\mathrm{G}\\, \mathrm{F}\\, p \to \mathrm{G}\\, \mathrm{F}\\, q$ is not valid, either.

Your intuition might have mislead you, saying that "$M \models \phi$ false" meant that $\phi$ did never hold (in $M$), that is "$M \models \lnot \phi$ true". This is not true and is not as odd as you might think. The effect is not restricted to LTL: in all logics you can have formulae which are not valid (that is, are no tautologies), nor are their respective negations (not that you had a negation in your example), nor are implications of them. Just consider $a \lor b$ and $\lnot a \land \lnot b$ in propositional logic.

# Answer
> 0 votes
However shouldn't the trace $s\_1^w$ be more instructive for your reasons? in this trace $\mathrm{G}\\,\mathrm{F}\\,p$ holds always however $\mathrm{G}\\,\mathrm{F}\\,q$ doesn't, therefore $\mathrm{G}\\,\mathrm{F}\\,p \to\mathrm{G}\\,\mathrm{F}\\,p$ becomes false.

---
Tags: logic, modal-logic, linear-temporal-logic
---


# Question
Title: In s-t directed graph, how to find many small cuts?
Solving the maximum flow problem yields one qualified minimal cut. But I want several (maybe hundreds) small cuts as candidates. The cuts don't have to be minimum cuts, as long as they are small (in weight). How do I do that?

# Answer
Are you familiar with the randomized contraction algorithm also known as Karger's algorithm? The algorithm basically works by selecting edges uniformly at random and contracting them with self-loops removed. The process halts when there are two nodes remaining, and the two nodes represent a cut. To increase the probability of success, the randomized algorithm is ran several times. While doing the runs, one keeps track of the smallest cut found so far.

What I suggest now is that you run the randomized contraction algorithm several times. Each time the algorithm outputs a cut, decide whether or not to keep it by checking if it is small enough. Naturally you can halt when you have produced enough of these small enough cuts. Depending on the size of your input, this might even work quite well in practice.
> 3 votes

---
Tags: algorithms, graphs, optimization, approximation
---


# Question
Title: Partition of a set of integer into 3 subsets of approximately equal sum
I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes:

"A hard working mom bought several fruits with different nutritional values for her 3 kids, Amelia, Jessica and Bruno. Both girls are overweight, and they are very vicious and always leave poor Bruno with nothing, so their mother decided to share the food in the following manner:

* Amelia being the heaviest one gets the most amount of Nutritional Value.
* Jessica gets an amount equal or less than Amelia
* Bruno gets an amount equal or less than Jessica, but you need to find a way to give him the highest possible nutritional value while respecting the rule ( $A \geq J \geq B$ )"

One of the test cases given by my teacher is the following:

```
The fruit list has the following values { 4, 2, 1, 8, 11, 5, 1

Input:
7   -----> Number of Fruits
4 2 1 8 11 5 1 ----> Fruits Nutritional Values

Output:
1 11  ---->  One fruit, their nutritional values sum for Amelia
5     ---->  Position of the fruit in the list
3 11  ---->  Three fruits, their nutritional values sum for Jessica
1 2 6 ---->  Position of the fruits in the list
3 10  ---->  Three fruits, their nutritional values sum for Bruno
3 4 7 ---->  Position of the fruits in the list

```

Note: I am aware that there are several ways of diving the fruits among the kids, but it doesn't really matter as long as it follows the rule $A \geq J \geq B$.

I'm trying to make a program in C# that solves this kind of problems but I need an efficient formula to make this work. Generating all the subsets is out of the question because it is very consuming task. The list of fruits can have up to $50$ elements, $2^{50}$ is a huge number.

# Answer
Let $x\_i,\ i=1\ldots,n$, be the list of nutritional values of the $n$ fruits, which I assume are nonnegative integers.

You want to partition $\\{1,\ldots,n\\}$ into three sets $A,B,C$ to maximize the minimum of $x\_A = \sum\_{i\in A} x\_i$, $x\_B = \sum\_{i \in B} x\_i$, $x\_C = \sum\_{i \in C} x\_i$. This is a variant of the set-partitioning problem. It is NP-complete.

However, there is a dynamic programming algorithm that is pseudo-polynomial (i.e. polynomial in $n$ and $S = \sum\_{i=1}^n x\_i$). Namely, for $1 \le m \le n$, $u, v \ge 0$ with $u+v \le \sum\_{i=1}^m x\_i$, let $T(m,u,v) = 1$ if there are disjoint subsets $A(m,u,v), B(m,u,v)$ of $\\{1,\ldots,m\\}$ such that $\sum\_{i \in A(m,u,v)} x\_i = u$ and $\sum\_{i \in B(m,u,v)} x\_i = v$, $T(m,u,v) = 0$ otherwise. Thus $$T(1,0,0) = T(1,0,x\_1) = 1,\ T(1,u,v) = 0 \text{ otherwise.}$$
For $m \> 1$, $$T(m,u,v) = 1 \Longleftrightarrow T(m-1,u,v) + T(m-1,u-x\_m,v) + T(m-1,u,v-x\_m) \ge 1.$$

After computing all $T(m,u,v)$ using this recursion, you want to find the $(u,v)$ with $u$ as large as possible subject to $T(m,u,v) = 1$ and $u \le v \le S - u - v$.
> 4 votes

# Answer
If you just need approximate equality, you can use the naive solution to dividing fruit:

1. Sort the fruit according to nutritional value.
2. Put the fruit with the most nutrition in basket #1.
3. Put the fruit with the next highest nutrition in basket #2.
4. Put the fruit with the next highest nutrition in basket #3.
5. Put the fruit with the next highest nutrition in the basket with the lowest total nutrition.
6. Repeat 5 until all fruit has been placed into baskets.
7. Give Amelia the most nutritious basket, Jessica the next most nutritious basket, and Bruno the least nutritious basket.

Sorting up to 50 elements is trivial, as is dividing them according to the rest of the algorithm. It's $O(n \log n)$ if nutrition values can be any non-negative integers, and $O(n)$ if you are able to effectively use any linear sorts (counting, bucket, radix, etc.) This doesn't produce an optimal division, but if you had one that did, you'd have solved most of the canonical knapsack problems, I believe, so you'd be talking about something significantly less efficient.
> 2 votes

---
Tags: algorithms, integers, approximation, linear-programming
---


title: How to detect stack order?

text:
# Question
Title: How to detect stack order?
We take the sequence of integers from $1$ to $n$, and we push them onto a stack one by one in order. Between each push, we can choose to pop any number of items from the stack (from 0 to the current stack size).

Every time we pop a value from the stack, we will print it out.

For example, $1,2,3$ is printed out when we do `push, pop, push, pop, push, pop`. $3,2,1$ comes from `push, push, push, pop, pop, pop`.

However, $3,1,2$ is not a possible printout, because it is not possible to have $3$ printed followed by $1$, without seeing $2$ in between.

Question: **How can we detect impossible orders like $3,1,2$?**

In fact, based on my observation, I have come out a potential solution. But the problem is I can't prove my observation is complete.

The program that I wrote with the following logic:

When the current value minus the next value is larger than 1, a value between current and next cannot appear after next. For example, if current=3 and next=1, then the value between current (3) and next (1) is 2 which cannot appear after next(1), hence $3,1,2$ violates the rule.

Does this cover all cases?

# Answer
> 7 votes
I couldn't understand your approach exactly (Seems it's correct), but there is a simple rule for impossible orders: The order is impossible $iff$ there is $a\_i,a\_j,a\_k$ such that $a\_i \> a\_k \> a\_j$ and $i\<j\<k$. To such a $a\_i,a\_j,a\_k$ we say bad triple.

Why? First you should prove that if there is bad triple then the sequence is impossible, but this is simple and I'll leave it as exercise (middle number couldn't pop sooner than bigger except smaller poped before all of them).

Second you should prove all impossible orders have at least one bad triple, Assume you have a sequence without any bad triple, you could find the order of push and pop so it's not impossible sequence. For reconstructing the push and pop orders just use naive approach (operation is pop while you iterating over consecutive numbers), but for formal proof (for simplicity) you could use induction, assume for all sequences of length $m$ if there isn't bad triple they aren't impossible. For sequence of length $n$, you can set operations as pop (start from end of sequence), while encountering with increasing consecutive numbers, now you have a sequence of length $m$, with $m \< n$, without bad triple, so you can reconstruct push and pop for this sequence, so original one wasn't impossible. start of induction is sequence of length 3.

---
Tags: algorithms, stacks
---


# Question
Title: Operations on OBDD: negation through Shannon's expansion
I have a problem with the application of the Shannon expansion for to obtain the negation of a formula boolean, than will need for implement the negation operator on OBDD (Order Binary Decision Diagram) that is, show that:

$\qquad \displaystyle \neg f(x\_1,\ldots,x\_n) = (\neg x\_1 \wedge \neg f|\_{x\_1=0}) \vee (x\_1 \wedge \neg f|\_{x\_1=1})$

where $f|\_{x\_i=b}$ is the function boolean in which replaces $x\_i$ with b, that is:

$\qquad \displaystyle f|\_{x\_i=b}(x\_1,\ldots,x\_n)=f(x\_1,\ldots,x\_{i-1},b,x\_{i+1},\ldots,x\_n)$.

The proof says:

$\qquad \displaystyle\neg f(x\_1,\ldots,x\_n) = \neg((\neg x\_1 \wedge f|\_{x\_1=0}) \vee (x\_1 \wedge f|\_{x\_1=1}))$.

Applying the negation (skip the intermediate steps), we get:

$\qquad \displaystyle (x\_1 \wedge \neg x\_1) \vee (\neg x\_1 \wedge \neg f|\_{x\_1=0}) \vee (x\_1 \wedge \neg f|\_{x\_1=1}) \vee (\neg f|\_{x\_1=0} \wedge \neg f|\_{x\_1=1}) $.

Now $(x\_1 \wedge \neg x\_1)= \mathrm{false}$ can be dropped, which leads to

$\qquad \displaystyle (\neg x\_1 \wedge \neg f|\_{x\_1=0}) \vee (x\_1 \wedge \neg f|\_{x\_1=1}) \vee (\neg f|\_{x\_1=0} \wedge \neg f|\_{x\_1=1}) $

which in turn is, finally, equal to

$\qquad \displaystyle (\neg x\_1 \wedge \neg f|\_{x\_1=0}) \vee (x\_1 \wedge \neg f|\_{x\_1=1})$.

Why does this hold?

# Answer
Maybe it is better to understand if you make a truth table for both functions. You can see that if $(\neg f|\_{x\_1=0} \wedge \neg f|\_{x\_1=1})$ is true then $(\neg x\_1 \wedge \neg f|\_{x\_1=0}) \vee (x\_1 \wedge \neg f|\_{x\_1=1})$ is also true, because both $f$ terms are true and either $x\_1$ is true or $\neg x\_1$ is true. And if $(\neg f|\_{x\_1=0} \wedge \neg f|\_{x\_1=1})$ is false then you have to do a case study:

* If both $f$ terms are false then is $(\neg x\_1 \wedge \neg f|\_{x\_1=0}) \vee (x\_1 \wedge \neg f|\_{x\_1=1})$ also false
* If exactly one $f$ term (w.l.o.g. $\neg f|\_{x\_1=0}$) is false then it is equivalent to $(x\_1 \wedge \neg f|\_{x\_1=1})$

Therefore, both formulas $(\neg x\_1 \wedge \neg f|\_{x\_1=0}) \vee (x\_1 \wedge \neg f|\_{x\_1=1}) \vee (\neg f|\_{x\_1=0} \wedge \neg f|\_{x\_1=1})$ and $(\neg x\_1 \wedge \neg f|\_{x\_1=0}) \vee (x\_1 \wedge \neg f|\_{x\_1=1})$ are equivalent.
> 4 votes

---
Tags: logic, information-theory
---


# Question
Title: Balanced weighting of edges in cactus graph
Given a cactus, we want to weight its edges in such a way that

1. For each vertex, the sum of the weights of edges incident to the vertex is no more than 1.
2. The sum of all edge weights is maximized.

Clearly the answer is no more than $\frac{n}{2}$ for $n$ vertices ($\sum d\_i = 2D$ where $d\_i$ is the sum for one vertex and $D$ is the sum over every edge). This bound is achievable for cycle graphs by weighting each edge 1/2.

I found a greedy algorithm for trees. Just assign 1 to edges incident to leaves and remove them and their neighbors from the graph in repeated passes. This prunes the cactus down to a bunch of interconnected cycles. At this point I assumed the remaining cycles were not interconnected and weighted each edge 1/2. This got 9/10 test cases but is, of course, incomplete.

So, how might we solve this problem for cacti in general? I would prefer hints to full solutions, but either is fine.

<sub> This question involves a problem from an InterviewStreet CompanySprint. I already competed but I'd like some thoughts on a problem (solutions aren't released, and I've been banging my head against the wall over this problem). </sub>

# Answer
So this question has been bothering me: why a cactus, if there's already a linear-time algorithm for a more general class?

The primal problem is known as the fractional matching problem, and, unsurprisingly, it has been studied as well. Balinski (whose result was made known to me via Schrijver's book Combinatorial Optimization) characterized the extreme points of the fractional matching polytope as consisting of an integer matching plus half of a collection of odd cycles. Given the relatively low input limits, I suspect that the intended solution of the problem poser was to modify Edmonds's blossom algorithm in a way that, for now, I will leave for you to discover. The structure of the cycles in a cactus makes this algorithm simple enough to be appropriate for a contest.

---

As sxu points out, this problem is amenable to linear programming. If you need just the objective value, the dual LP has the same objective value and is the fractional vertex cover problem. The nice thing about vertex cover is that it has a half-integral optimum; in linear time, you can use depth-first search to compute a tree decomposition of the cactus of width O(1) and solve the dual LP with a dynamic program that tries variable values in {0, 1/2, 1}.

If you actually need a solution for the primal, then complementary slackness might help, but I can't help but suspect that the restriction to cacti is supposed to allow a more elementary solution.
> 5 votes

# Answer
You can always use linear programming: just create a variable for each edge and a constraint for each vertex. However there must be a better solution as this does not use the fact that we have a cactus graph. I also suggest to run LP algorithms on a few examples and try to see if anything interesting is happening on cactus graph but not on general graphs.
> 1 votes

---
Tags: algorithms, graphs, greedy-algorithms
---


# Question
Title: How can I find minimum number required to add to sequence such that their xor becomes zero
Given a sequence of natural numbers, you can add any natural number to any number in the sequence such that their xor becomes zero. My goal is to minimize the sum of added numbers.

Consider the following examples :

1. For $1, 3$ the answer is $2$; adding $2$ to $1$ we get $3 \oplus 3=0$.
2. For $10, 4, 5, 1$ the answer is $6$; adding $3$ to $10$ and $3$ to $5$ we get $13 \oplus 4 \oplus 8 \oplus 1 = 0$.
3. For $4, 4$ the answer is $0$, since $4 \oplus 4 = 0$.

I tried working on binary representations of sequence number but it got so complex. I want to know if there is any simple and efficient way to solve this problem.

# Answer
> 5 votes
It seems to me that $a = a\_i \oplus \dots \oplus a\_n$ holds all necessary information: the $1$bits in $a$ are the bits you need to flip in (exactly) one of the $a\_i$. As you are only allowed to *add*, you have to find one $a\_i$ where the corresponding bit $j$ is $0$ and flip it -- this causes the same cost for all $a\_i$, that is $2^j$, so the choice does not matter. Trouble begins if there is no such $a\_i$.

That is why you have to do this iteratively and work from the least significant bit upwards. Proceed as above; if there is no suitable $a\_i$, choose the $a\_i$ with the maximum number of $1$ bits left of the current position -- this increases the chance of finding a suitable candidate in future iterations --, flip the bit and carry over, that is flip all ones to the left until you flip a zero to a one. Note that we still add $2^j$). As carry propagates only to the left, earlier choices are not invalidated. Recompute $a$ and continue with $j+1$; iterate until you have $a=0$.

Note that this is only a heuristic as far as I can tell: the choice of $i$ may be suboptimal if it causes many bits in $a$ to become non-zero. I am not sure if this can be avoided.

# Answer
> 0 votes
I don't actually have a solution, but here are a few ideas that came up.

If you look at the results of XORing all of the numbers in the sequence, that gives an upper bound on the number of additions you need to do. For example, in your example of $10, 4, 5, 1$, we have $10 \oplus 4 \oplus 5 \oplus 1 = 10$, so you know you don't have to add more than $8$ (because the 8-bit is the highest one set). Distributing up to eight "ones" distributed four ways, is a fairly small set of combinations. I can't remember that formula this late at night, but there's an $n!$ in there somewhere.

To give that statement a little bit more grounding, consider arbitrary integers $A,B$ such that $A \oplus B = 8$. The bits higher than bit 3 obviously all cancel out, so you can ignore them. For the lower four bits, they XOR to 8, so the worst possible case (in terms of number of ones you need to add ) is if $A=8$ and $B=0$ (all zeroes except for the highest bit) because you'll need to add +8 to B to get that top bit set. If there are *any* one bits set in either of the numbers, you need to add less.

Maybe you can start from this, and develop a tighter maximum amount to add.

---
Tags: algorithms, integers, xor
---


# Question
Title: Using hash tables instead of lists for buckets in hash tables
Say instead of using a linked list as buckets for a hash table of size $m$, we use another hash table of size $p$ as buckets this time. What would be the average case for this problem?

I looked up perfect hashing and I got a very close algorithm, and it is $O(1)$. Can someone please clarify?

# Answer
> 6 votes
Using a hash table with $n$ buckets and a hash function $h\_n : S \rightarrow \\{0, 1, ..., n - 1\\}$ , where each bucket is a hash table with $m$ buckets and a hash function $h\_m : S \rightarrow \\{0, 1, ..., m - 1\\}$, is equivalent to a hash table wit $nm$ buckets and a hash function $h\_{nm} : S \rightarrow \\{0, 1, 2, ..., nm - 1\\}$ where $h\_{nm}(x) = mh\_n(x) + h\_m(x)$. In other words, using more than one level has no effect whatsoever on the complexity: it's the same as a for a garden-variety hash table.

Perfect hashing is a completely separate issue.

---
Tags: data-structures, time-complexity, hash-tables
---


# Question
Title: Prove that every two longest paths have at least one vertex in common
If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common.

I think that that common vertex should be in the middle of both the paths. Because if this is not the case then we can have a path of length $\>k$. Am I right?

# Answer
> 25 votes
Assume for contradiction that $P\_{1} = \langle v\_{0},\ldots,v\_{k}\rangle$ and $P\_{2} = \langle u\_{0},\ldots,u\_{k}\rangle$ are two paths in $G$ of length $k$ with no shared vertices.

As $G$ is connected, there is a path $P'$ connecting $v\_{i}$ to $u\_{j}$ for some $i,j \in \[1,k\]$ such that $P'$ shares no vertices with $P\_{1} \cup P\_{2}$ other than $v\_{i}$ and $u\_{j}$. Say $P' = \langle v\_{i},x\_{0},\ldots,x\_{b},u\_{j}\rangle$ (note that there may be no $x\_{i}$ vertices, i.e., $b$ may be $0$ \- the notation is a bit deficient though).

Without loss of generality we may assume that $i,j \geq \lceil\frac{k}{2}\rceil$ (we can always reverse the numbering). Then we can construct a new path $P^{\*} = \langle v\_{0},\ldots,v\_{i},x\_{1},\ldots,x\_{b},u\_{j},\ldots,u\_{0}\rangle$ (by going along $P\_{1}$ to $v\_{i}$, then across the bridge formed by $P'$ to $u\_{j}$, then along $P\_{2}$ to $u\_{0}$).

Obviously $P^{\*}$ has length at least $k+1$, but this contradicts the assumption that $G$ has no paths of length greater than $k$.

So then any two paths of length $k$ must intersect at at least one vertex and your observation that it must be in the middle (if there's only one) follows as you reasoned.

# Answer
> 2 votes
You are right that the common vertex must occur in the middle of both paths.

However that intuition will not solve the actual problem you're trying to solve.

Instead try to demonstrate that, given any point in the path, the path segment from (and including) that point to one of the ends of the original path must have strictly greater than half as many nodes as the full path.

Once you have shown that, you will be able to both solve the problem that you were asked and verify your conjecture.

---
Tags: graphs, combinatorics
---


# Question
Title: When does the function mapping a string to its prefix-free Kolmogorov complexity halt?
In *Algorithmic Randomness and Complexity* from Downey and Hirschfeldt, it is stated on page 129 that

$\qquad \displaystyle \sum\_{K(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$,

where $K(\sigma)\downarrow$ means that $K$ halts on $\sigma$, $\sigma$ being a binary string. $K$ denotes the prefix-free Kolmogorov complexity.

When does $K$ halt? I think it only halts on a finite number of inputs, since the classical proof on non-computability of the Kolmogorov complexity gives an upper bound on the domain of $K$. But then, the finite set of inputs on which $K$ halts can be chosen arbitrary (one just needs to store the finite number of complexities in the source code).

So is this sum well-defined? In other words, is the domain of $K$ well defined?

# Answer
I think you are right; $K$ is a specific function which can not be computed. The author likely means to use *some* (arbitrary) approximative implementation; so no, this does not seem to be well-defined, if you are pedantic. You can also call it abuse of notation.

Consider this instead:

$\qquad \displaystyle \forall {M \in \mathcal{M}\_K}.\ \sum\_{M(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$

with $\mathcal{M}\_K = \\{M\ \mathrm{TM} \mid M(\sigma)\\!\downarrow\ \implies\ M(\sigma)=K(\sigma) \\}$ the set of all Turing machines that compute subfunctions of $K$.

In essence, this means: the bound holds no matter for which strings your implementation can compute the Kolmogorov complexity.

---

As Carl notes in the comments, it is plausible that the notation has nothing to do with halting or computing, as $K$ is not computable. Read $\sum\_{K(\sigma)\\!\downarrow}$ as sum ranging over the domain of $K$.
> 1 votes

---
Tags: computability, terminology, kolmogorov-complexity, descriptive-complexity
---


# Question
Title: What is the significance of the semi clustering formula in the Google Pregel paper?
Semi clustering algorithm is mentioned in the Google Pregel paper. The score of a semi cluster is calculated using the below formula

$\qquad \displaystyle S\_c =\frac{I\_c - f\_BB\_c}{\frac{1}{2}V\_c(V\_c - 1)}$

where

* $I\_c$ is sum of the weights of all the internal edges,
* $B\_c$ is the sum of the weights of all the boundary edges,
* $V\_c$ is the number of edges in the semi cluster and
* $f\_b$ is the boundary edge score factor (user defined between 0 and 1).

The algorithm is pretty straight forward, but I could not understand how the above formula was derived. Note that the denominator is the number of edges possible between $V\_c$ number of vertices.

Could someone please explain it?

# Answer
Think about what a "good" cluster is. It is a set of nodes which

* are strongly interconnected (strong cohesion) and
* weakly connected with nodes outside of the cluster (weak coupling).

In particular, the connection among the nodes should be *stronger* than the connection with the outside. And this is what they do there: $I\_c$ is a measure for cohesion -- more and stronger edges inside the cluster mean more cohesion -- and similarly $B\_c$ is a measure for coupling. $f\_B$ is used to control the influence of coupling.

As for the denominator, they justify it in the slides:

> The score is normalized by dividing with the number of vertices in the clique, so that large clusters do not receive artificially high scores.

That's actually wrong, but the idea is the same: they divide by the number of edges there could be -- which makes sense because they "count" edges in the numerator, too -- in order to get rid of size effects. Without this rescaling, a large cluster (with many edges) would have a higher score than a smaller on with the same or even better properties. You only want to score the *quality* of the clusters, though, so rescaling is in order.

I daresay that $\frac{I\_c}{f\_B B\_c}$ would also make sense (and scale itself). Usually, such scores are formulated ad-hoc and their usefulness validated by experiments (over time). That is, somebody wrote it down, used it for clustering, looked at images and was satisfied with the result. Depending on what semantic the edge weights have, the score may also be a "good" approximation for a more complicated one that is harder to compute or makes clustering (computationally) harder. That said, most clustering algorithms in use *are* approximations -- because clustering is NP-hard -- so the choice of auxiliary score may influence runtime and result quality of those algorithms.
> 3 votes

---
Tags: algorithms, graphs, terminology
---


title: Is this language Context-Free?

text:
# Question
Title: Is this language Context-Free?
Is the language

$$L = \\{a,b\\}^\* \setminus \\{(a^nb^n)^n\mid n \geq1 \\}$$

context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.

# Answer
Hint:

> Yes

Solution:

> $$\\{(a^n b^n)^n \mid n \geq 1 \\} = \\{a^{n\_1} b^{n\_2} \dots a^{n\_{2k-1}} b^{n\_{2k}}\\}: k \geq 1 \land n\_1 = k \land \forall i. n\_i = n\_{i+1} \\}$$
> and therefore the complement is
> $$\\{a,b\\}^{\ast} \setminus \\{(a^n b^n)^n \mid n \geq 1 \\} = \\{a^{n\_1} b^{n\_2} \dots a^{n\_{2k-1}} b^{n\_{2k}}: n\_1 \neq k \lor \exists i. n\_i \neq n\_{i+1}\\}$$
> which is context-free as you can easily write a nondeterministic PDA.
> 8 votes

---
Tags: formal-languages, context-free, pumping-lemma
---


title: Expected number of swaps in bubble sort

text:
# Question
Title: Expected number of swaps in bubble sort
Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p\[i\]$, $0 \leq i \< n$. I have to find the expected number of swaps that will take place to sort the array using bubble sort.

I've tried the following:

1. The probability for an element $A\[i\] \> A\[j\]$ for $i \< j$ can be calculated easily from the given probabilities.
2. Using the above, I have calculated the expected number of swaps as:

```
double ans = 0.0;
for ( int i = 0; i < N-1; i++ ){
    for ( int j = i+1; j < N; j++ ) {
        ans += get_prob(A[i], A[j]); // Computes the probability of A[i]>A[j] for i < j.

```

Basically I came to this idea because the expected number of swaps can be calculated by the number of inversions of the array. So by making use of given probability I am calculating whether a number $A\[i\]$ will be swapped with a number $A\[j\]$.

Note that the initial array elements can be in any order, sorted or unsorted. Then each number can change with some probability. After this I have to calculate the expected number of swaps.

I have posted a similar question before but it did not had all the constraints.

I did not get any good hints on whether I am even on the right track or not, so I listed all the constraints here. Please give me some hints if I am thinking of the problem in an incorrect way.

# Answer
Let $\sf{Bubble Sort}$ be defined as the following:

```
for (j = A.length; j > 1; j--)
    for (i = 0; i < j - 1; i++)
        if (A[i] > A[i + 1])
            swap(i, i + 1, A)

```

Given some permutation $x\_1, \cdots, x\_n$, an *inversion* is said to have occurred if $x\_j \< x\_i$ for some $i \< j.$ We see that $\sf{Bubble Sort}$ performs an inversion check for each pair, and if so, performs a swap. Let $X$ be the number of swaps. It is not hard to see in the worst case there are $X = \binom{n}{2}$ possible swaps made. But we are interested in the expected case, which we can compute by defining $X$ in terms of inversions in $\sf{Bubble Sort}$.

Now let $X = \sum\_j \sum\_{i\<j} I\_{ij}$ where $I\_{ij}$ is the indicator variable that there exists an inversion for some pair $(i,j)$. The expectation is defined as $E\[X\] = E\[\sum\_j \sum\_{i\<j} I\_{ij}\] = \sum\_j \sum\_{i\<j} E\[I\_{ij}\]$. We now need to determine $P\\{I\_{ij}\\}$.

When assuming any possible permutation as input, each with uniform probability, it can been shown that $P\\{I\_{ij}\\} = \frac{1}{2}$. The reasoning behind this is that under any possible permutation, half of the time $x\_j \< x\_i$ and half of the time $x\_i \< x\_j$ for $i \neq j$.

Returning to our expectation calculation we see that $E\[X\] = \sum\_j \sum\_{i\<j}E\[I\_{ij}\] = \sum\_j \sum\_{i\<j} \frac{1}{2} = \binom{n}{2} \cdot \frac{1}{2} = \frac{n(n-1)}{4}$
> 12 votes

---
Tags: algorithms, algorithm-analysis, sorting, average-case
---


# Question
Title: NP-completeness of graph isomorphism through edge contractions with an edge validity condition
Given Graphs $G=(V\_1,E\_1)$ and $H=(V\_2,E\_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset of edges are valid for contraction at each step of the sequence. For example when deciding the first edge for contraction, there are only a subset $E'\subset E\_1$ of edges eligible for contraction. If you pick $e\in E'$ for contraction and get an intermediate graph then when deciding the second edge for contraction in this intermediate graph there are a subset $E''$ of edges eligible for contraction and so on.

Does this problem stay NP-complete ?

# Answer
The answer is yes. Suppose that you had a polynomial-time algorithm to solve your revised problem. Apply that algorithm to the special case where the subset of edges available at each step is the whole set. We'd then have a polynomial time algorithm for the original, known NP-complete, problem.

To have any hope of dreaming up a non-NP-complete version, you'd need to put a restriction on the subsets that were eligible that would prevent an immediate reduction to the original problem. At that point you'd have a new problem which you cannot easily show is NP-complete. However it is in the nature of NP-complete problems that, if your restriction avoids 2+ choices at each step, it very likely to be NP-complete.

(Note, it is currently unknown whether the simpler problem of identifying whether two graphs are isomorphic is NP-complete.)
> 5 votes

---
Tags: complexity-theory, computability, graphs, np-complete, np-hard
---


# Question
Title: Does there exist a Turing complete typed lambda calculus?
Do there exist any Turing complete typed lambda calculi? If so, what are a few examples?

# Answer
Yes, sure. Many typed lambda calculi accept only strongly normalizing terms, by design, so they cannot express arbitrary computations. But a type system can be anything you like; make it broad enough, and you can express all deterministic computations.

A trivial type system that encompasses a Turing-complete fragment of the lambda calculus is the one that accepts every term as well-typed (with a top type). $$\dfrac{}{\Gamma \vdash M : \top}$$

More practically, statically typed functional programming languages have at their core a typed lambda calculus which allows a fixpoint combinator as well-typed. For example, start with the simply typed lambda calculus (or the ML type system or system F or any other type system of your choice) and add a rule that makes some fixpoint combinator like $\mathbf{Y} = \lambda f. (\lambda x. f (x\\,x)) (\lambda x. f (x\\,x))$ well-typed. $$ \dfrac{\Gamma \vdash f : T \rightarrow T} {\Gamma \vdash \mathbf{Y}\\,f : T} \qquad \dfrac{\Gamma \vdash f : T \rightarrow T} {\Gamma \vdash (\lambda x. f (x\\,x)) (\lambda x. f (x\\,x)) : T} $$ The rules as presented above are rather clumsy, as they make terms like $\mathbf{Y}\\,f$ well-typed even though their constituents are not well-typed — they are not fully compositional. A simple fix is to add a fixpoint combinator as a language constant and provide a delta rule for it; then it is a simple matter to have a type system and reduction semantics with type preservation. You do get away from the pure lambda calculus into the realm of lambda calculus with constants. $$\begin{gather\*} \dfrac{}{\Gamma \vdash \textbf{fix} : (T \rightarrow T) \rightarrow T} \\ \textbf{fix}\\,f \to f (\textbf{fix}\\,f) \\ \end{gather\*}$$

Sticking to the pure lambda calculus, an interesting type system is the lambda calculus with intersection types.

$$ \dfrac{\Gamma \vdash M : T\_1 \quad \Gamma \vdash M : T\_2} {\Gamma \vdash M : T\_1 \wedge T\_2} (\wedge I) \qquad\qquad \dfrac{} {\Gamma \vdash M : \top} (\top I) $$

Intersection types have interesting properties with respect to normalization:

* A lambda-term can be typed without using the $\top I$ rule iff it is strongly normalizing.
* A lambda-term admits a type not containing $\top$ iff it has a normal form.

See Characterization of lambda-terms that have union types for an insight as to why intersection types have such a remarkable scope.

So you have a type system that defines a Turing-complete language (since every term is well-typed), and a simple characterization of terminating computations. Of course, since this type system characterizes normalization, it is not decidable.

<sub> A remark on the rule names $(\top I)$ and $(\wedge I)$: they have no formal meaning, but they are chosen deliberately. the $I$ stands for “introduction”, because these are introduction rules — they introduce the symbol ($\wedge$ or $\top$) into the type below the line. Dually, you'll find elimination rules, when a symbol appears above the line but not below. For example, the rule to typecheck a lambda expression in the simply-typed lambda calculus is the introduction rule for $\rightarrow$, and the rule to typecheck an application is the elimination rule for $\rightarrow$. </sub>
> 38 votes

---
Tags: computability, lambda-calculus, type-theory
---


# Question
Title: A regular expression for a given formal language
I wanted to ask if someone can help me to construct a regular expression over the alphabet $\\{a,b,x\\}$ for the language $L$ which is constituted by all strings containing an odd number of $a$'s, and in which between each pair of consecutive $a$'s there is an even number of $b$'s (and an arbirtary number of $x$'s).

For example, $babbxbbxabbxaabxxbax \in L$, $bab \in L$, while $abba \notin L$ and $abbbaa \notin L$.

What is the approach?

# Answer
Try and build it step by step:

* a language with an odd number of $a$'s: $a(aa)^\*$;
* between which there is an even number of $b$'s: $b^\*a((bb)^\*a(bb)^\*a)^\*b^\*$;
* and an arbitrary number of $x$'s: $(b+x)^\*a(x^\*(bx^\*bx^\*)^\*ax^\*(bx^\*bx^\*)^\*a)^\*(b+x)^\*$.
> 2 votes

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: NP-completeness of scheduling to minimise tardy tasks with release times
In "Computers and Intractability A Guide to the Theory of NP-Completeness" textbook pp 236, "Sequencing to minimize tardy tasks" is NP-complete.
To be specific the problem is as follows:

For each task $t \in T$, partial order $\<$ on $T$, a length $l(t)$, and a deadline $d(t)$ and a positive integer $K \leq |T|$. Is there a one-processor schedule $s$ for $T$ that obeys the precedence constraints, that is $s$ is such that $t \< t'$ implies $s(t)+l(t) \< s(t')$, and such that there are at most $K$ tasks for which $s(t) + l(t) \> d(t)$?

Now we associate each task with a release time $r(t)$ and $s(t)$ should be $\geq r(t)$. Does the revised problem stay NP-completeness ?

# Answer
> 2 votes
Assume the new problem was polynomially solvable. Take any instance of the old problem and add release dates $r(t)=0$ for all $t \in T$. Then the new problem has a "yes" answer for the modified instance if and only if the old problem had a "yes" answer for the original instance. We have reduced the old problem to the new one, so the new one is at least as hard.

This reduction works for any scheduling problem if you (only) add release dates.

---
Tags: complexity-theory, scheduling
---


# Question
Title: Is it possible to always construct a hamiltonian path on a tournament graph by sorting?
Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order:

$\qquad \displaystyle a \leq b \iff (a,b) \in E \lor \left(\exists\\, c \in V. a \leq c \land c \leq b\right)$

For context, this came from an observation that the inductive construction in the above page seems to be equivalent to insertion sort using the given order. Is it possible to use other sorting algorithms?

# Answer
> 8 votes
I assume that you intend $\leq$ to be the reflexive and transitive closure of $E$, or directed reachability, that is $\leq$ is really the smallest fixpoint of the equivalence you give:

$\qquad \displaystyle a \leq b \iff \exists\\, v\_0 \dots v\_n. a \to v\_o \to \dots \to v\_n \to b$

with $n \geq 0$ and $v \to u \iff (v,u) \in E$.

The key argument here is that $\leq$ is indeed a total order. If it is, you can use it for sorting, and the result is *by definition of $\leq$* a Hamiltonian path: consider the result of the sort $v\_1 \dots v\_n$. If there were no edge between $v\_i$ and $v\_{i+1}$, by $V\_s = v\_i \leq v\_{i+1}$ there is $v \in V$ such that $v\_i \leq v \leq v\_{i+1}$. This contradicts that $\leq$ is a (total) order and $V\_s$ is sorted with respect to $\leq$.

Unfortunately, $\leq$ is not an order relation: it is not antisymmetric. Consider the small tournament based on $K\_4$:

<sup>\[source\]</sup>

Here, $a \leq d$ and $d \leq a$ (directed cycles are the culprits!) but $a \neq d$. So $\leq$ is only a (well-)quasi-order and there is no such thing as a sorted node list.

---
Tags: algorithms, graphs, sorting
---


# Question
Title: How do we distinguish NP-complete problems from other NP problems?
I just learned that when we have a polynomial algorithm for NP-complete problems, it is possible to use that algorithm to solve all NP problems.

So, the question is how we then distinguish non-NP-complete NP problems from NP-complete problems? It seems that all these problems will have a polynomial algorithm to convert into other problems...

# Answer
To provide the flip side of 042's answer: it's important to understand that if $P=NP$ then *every* problem in $NP$ is $NP$-complete (caveat: under the usual poly-time reductions): $NP$-complete simply means 'every problem within $NP$ can be solved in polynomial time with an oracle for this problem'. But if every problem in $NP$ can be solved in polynomial time—that is, if $P=NP$—then the second part of that statement is vacuous.

On the other hand, if $P\neq NP$ then it's known that the problems that are in $NP$ but not in $P$ have a very rich structure - in particular, there have to be 'intermediate' problems that aren't in $P$ but also aren't $NP$-complete, and in fact an infinite number of distinct ones (that is, such that at least one can't be reduced to the other). For more details on this result (*Ladner's Theorem*), you might start with Lance Fortnow's notes on the topic.
> 5 votes

# Answer
Not really. For instance, the Graph isomorphism problem is believed not to be in P, but on the other hand not being NP-complete (and is obviously in NP). Moreover, also all problems in P (that are also in NP) are not NP-complete, if $P \neq NP$. However, to my knowledge, all of these are mere conjectures, since the answer would solve P vs. NP.
> 2 votes

---
Tags: complexity-theory, terminology, np-complete
---


# Question
Title: Is finding the longest path of a graph NP-complete?
The problem of finding the largest subgraph of a graph that has a Hamiltonian path can be restated as finding the longest path of a graph. Is this NP-complete? Also, is finding the $k$-length path of a graph NP-complete? Is it still NP-complete if we require the path to visit a given vertex?

# Answer
First, it is easy to see that the problem is in $\text{NP}$. The longest path is a Hamiltonian one since it visits all vertices. Indeed, there is a straightforward reduction from $\text{HAM-PATH}$ to it. For details and some special cases, see for example here. Likewise, it is $\text{NP}$-complete to decide whether there is a path of length $k$ with the a similar argument: just set $k$ such that the problem is equivalent of solving $\text{HAM-PATH}$. Finally, if I understood your third point correctly, it doesn't make the problem any easier if you *in addition* require the path to visit a specific vertex $v$. Similar reasoning holds for this case.
> 5 votes

---
Tags: complexity-theory, graphs, np-complete
---


title: regular expression given the language

text:
# Question
Title: regular expression given the language
The language is: $$ L = \\{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \\} $$

My attempt at an answer: $$ (a \cup b)^{3k} $$

This will work if the a OR b can change for each instance in the string that is (3k) long. If not, what can I do to fix this?

# Answer
First off, putting $k$ in the regular expression is not allowed by typical regular expression syntax, unless I'm mistaken. Even adding constant powers is a shorthand notation, not a part of the regular expression formalism. Even if it were possible, using that notation, you could mix $a$s with $b$s, so that not all $a$'s would necessarily come before all $b$s ... so that's not the right direction.

You want strings that begin with $a$s, end with $b$s, and have a total length that is divisible by three. There are a few ways you could go about this. Since you want a regular expression, we might try to develop one directly, without going through a finite automaton.

For a string $x$ from $a^\*b^\*$ to be in your language, its length must be divisible by three. In other words, it must be true that $|x| = 3k$. Let $x = yz$, where $y \in a^\*$ and $z \in b^\*$. Then $|x| = |y| + |z|$. So we must have that $|y| + |z| = 3k$. There are only a finite number of ways in which this can happen:

1. $|y| = 3k\_1$ and $|z| = 3k\_2$, or
2. $|y| = 3k\_1 + 1$ and $|z| = 3k\_2 + 2$, or
3. $|y| = 3k\_1 + 2$ and $|z| = 3k\_2 + 1$.

Suppose you can create regular expressions $r\_1, r\_2, r\_3$ corresponding to those three cases. Then you can find the regular expression for your language by taking the union. Let's see how that would work for each case.

1. This case is easy: the number of $a$'s is divisible by 3, and so is the number of $b$'s. We get a regular expression $r\_1 = (aaa)^\*(bbb)^\*$.
2. Based on the previous answer, this isn't so bad, either: $r\_2 = (aaa)^\*a(bbb)^\*bb$.
3. Finally, $r\_3 = (aaa)^\*aa(bbb)^\*b$.

We get an easy regular expression by taking the union of these (I use $+$, but $\cup$ is sometimes also used): $r = r\_1 + r\_2 + r\_3 = (aaa)^\*(bbb)^\* + (aaa)^\*a(bbb)^\*bb + (aaa)^\*aa(bbb)^\*b$.
> 12 votes

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: Solving Recurrence Relations 'Chip & Conquer'
I've been tasked with solving some recurrence relations, and I've been running into trouble with so called 'chip & conquer' relations.

Here are some example problems:

$$T(n) = T(n-5) + cn^2$$

and

$$T(n) = T(n-2) + \log{n}$$

I'm supposed to be giving an answer in $\Theta$ notation. How do I go around and solving relations like these?

# Answer
For simplicity, let's assume that $5$ divides $n$ and that $n/2=n-5k$ for some integer $k\>0$.

$$ \begin{align\*} T(n) &= T(n-5) + cn^2 \\ T(n) &= cn^2 + c(n - 5)^2 + c(n - 10)^2 + c(n - 15)^2 + ... + c5^2 + c0^2 \\ &= c(n^2 + (n - 5)^2 + (n - 10)^2 + (n - 15)^2 + ... + 5^2 + 0^2) \\ &\ge c(n^2 + (n - 5)^2 + (n - 10)^2 + (n / 2)^2) \ge c(n / 2)(1 / 5)(n / 2)^2) \\ &= cn^3 / 40 = (c / 40)n^3 \\ &= \Omega(n^3) \\ T(n) &= cn^2 + c(n - 5)^2 + c(n - 10)^2 + c(n - 15)^2 + ... + c5^2 + c0^2 \\ &\le c(n / 5)n^2 \le cn^3 \\ &= O(n^3) \\ \end{align\*} $$

We conclude that $T(n) = \Theta(n^3)$.

---

Let's assume for simplicity that $n/2 = n-2k$ for an integer $k\>1$.

$$ \begin{align\*} T(n) &= T(n-2) + \log n = \log n + \log(n - 2) + \log(n - 4) + ... + \log(4) \\ &\ge \log n + \log(n - 2) + \log(n - 4) + ... + \log(n / 2) \ge (n / 2)log(n / 2) \\ &= \Omega(n \log n) \\ T(n) &= T(n-2) + \log n = \log n + \log(n - 2) + \log(n - 4) + ... + \log(4) \\ &\le (n / 2) \log n \\ &= O(n \log n) \\ \end{align\*} $$

We conclude that $T(n)=\Theta(n \log n)$.
> 4 votes

# Answer
Expand the recurrence and sum it up.

Example 1:

$$ \begin{align\*} T(n) &= T(n-5) + O(n^2) = T(n-10) + O(n^2) = \dots \\ &= T(0) + \\{\text{\\(n/5\\) terms, each \\(O(n^2)\\)}\\} \end{align\*} $$

Now let's say $T(0) = c$. This would be generally given in the question.

so this would sum to $(n/5).O(n^2) = O(n^3)$

Example 2:

$$ \begin{align\*} T(n) &= T(n-2)+\log n = T(n-4)+\log(n-2) + \log(n) = \dots \\ &= T(0) + \log(n-2^k) + \dots + log(n) = c + \log(n-2^k) + \dots + \log(n-2) + \log(n) \\ &= c + n \log(n) \end{align\*} $$
> 0 votes

---
Tags: asymptotics, recurrence-relation
---