...alternatively...

...or one could also show that L = RL. thanks in advance :)

On NL vs UL

Just for recap: a (decision) problem is in NL if some logspace-bounded nondeterministic machine can decide it. It's in UL if in addition the machine has at most one accepting path for each input. (U is for unambigous here.)

I have not that deep insight in the topic, but it seems to me that NL = UL is highly possible. However, to understand the problem statement of this post, you don't have to know anything about nondeterminism or unambiguity; it suffices to know what logspace computability means.
In order to show this it suffices to define an algorithm f that

• takes a directed graph G=(V,E) as input;
• assigns a positive integer weight w(e) to each edge e of G;
• such that w(e) is bounded by some polynomial of |V|;
• such that for each pair (s,t) of nodes with t being reachable from s there exists a unique path from s to t having minimum weight;
• finally, f has to be computable in logspace.

E.g, without the polynomially-boundedness condition a good f could be one which assigns distinct powers of two to the edges, i.e. edge i has weight 2ⁱ.

The thing would work since the "min-unique" problem (given (G,s,t), say "yes" if t is reachable from s via a unique path, say "no" if t is not rechable from s at all, say anything if there are more s-t paths) is in UL and UL is closed under logspace reductions, thus one has "only" to reduce the NL-complete reachability problem (in dags, or in strictly layered graphs, whatever) to min-uniqueness. Having these weights in logspace, each weighted edge e can be replaced by a path of length w(e), concluding the reduction.

For more details see Raghunath Tewari's PhD dissertation from 2011.

Fav Problem: A 30-year-old conjecture of Zsolt Tuza

Okay, so this one isn't too deeply attached to TCS, but anyways.
Suppose G is a (finite) graph in which we can choose k edge-disjoint triangles but not more.
We want to make the graph triangle-free by removing edges, as few as possible. How many edges suffice?
Trivial observation #1: we have to remove at least k edges -- one from each triangle from a k-element edge-disjoint set of triangles.
Trivial observation #2: 3k edges surely suffice -- fix a maximal edge-disjoint set of triangles and remove all of their edges. (No triangle can remain intact, otherwise the set could not be maximal).
Now K4 is an example for a lower bound of 2k: from K4 we can choose at most one edge-disjoint triangle and we have to remove two edges to eliminate all triangles. (A disjoint sum of k K4s shows an example where k goes to infinity.)
The conjecture states that removing 2k edges always suffices.

Some progress on that: the conjecture holds (among other classes) for...

• planar graphs, Tuza 1985
• tripartite graphs, Haxell 1993
• K3,3-subdivision-free graphs, Krivelevich 1995
• graphs with maximum averagre degree at most 7, Puleo 2013.

I'm interested in the (correctness of the) last result, see here: http://arxiv-web3.library.cornell.edu/abs/1308.2211

anyone else? :-)

What makes some instances of hard probems hard and others rather easy?

We all know that there exist easily solvable instances (with respect to some algorithm, at least) of NP-complete problems, e.g. sudoku puzzles found in daily newspapers etc. And there exist hard ones of course, from NP-hardness (check e.g. this one).
But what makes these instances "easy" and "hard"? A convenient answer is "it depends on the solver algorithm", but it seems to be a more universal notion.
For example, there is a well-known phase transition in the case of the randomly generated 3SAT instances: suppose we generate k clauses over n variables, each having three literals. Now,

• if k is less than 4.25n (approximately), then the generated formula is satisfiable with high probability due to underconstraintedness -- and most solvers can generate a solution within a low runtime;
• if k is more than 4.25n (again, approximately), then the generated formula is whp overconstained and most solvers can deduce a contradiction within a low runtime,
• however,
• if k is around 4.25n, then deciding whether the formula is satisfiable or not is hard for all the solvers available. (that's why benchmarks and testbeds are generated exactly this way, usually).

So, these generated instances are "universally hard" -- but what does universality mean here? Is there a mathematical notion for measuring hardness of problem instances?
Research in this direction can be used to have a better understanding for the structure of NP-hard problems.

Thus it's probably very, very hard.

Any willing BSc / MSc student there? ^_^

Cov(G) vs Rect(G)

Let G=(A,B,E) be a bipartite graph. Cov(G) stands for its biclicque weight: the total weight of a covering of G with bicliques, where the size of a biclique is the number of its vertices. Rect(G) stands for the edge count of the smallest directed graph (V,E') with A U B being a subset of V, and where for each a in A and b in B, b is accessible from a if and only if (a,b) is in E.

The question is, what's the exact relationship between Rect(G) and Cov(G)? Clearly Rect(G) <= Cov(G) <= Rect(G)², but we should close the gaps.

Largest semigroup of "nonpermutational" transformations

Let Tn be the set of all transformations of [n]={1,...,n} for each n>0. Tn is a semigroup with product being function composition, i.e. (fg)(x) := g(f(x)) for each f,g ∈ Tn and x ∈ A. A subsemigroup of Tn is a subset of Tn which is closed under composition.
Call a transformation f: A→A nonpermutational if f(B)={f(x): x∈B}=B implies |B| ≤ 1 for any B ⊆ A. (Equivalently, if A is finite, then f is nonpermutational if it has a unique fixed point Fix(f) and no more cycles saving the loop on Fix(f).)
The nonpermutational transformations of [n] do not form a semigroup. The question is, if T is a subsemigroup of Tn consisting of only nonpermutational transformations, how large can T be?

Partial results so far:

• For each n, there exists a semigroup of nonpermutational transformations having size ⌊e(n-1)!⌋. See http://arxiv.org/abs/1203.2873.
• We can show that the size of any such semigroup is at most n!. See http://arxiv.org/abs/1304.5714.

Probably there will be a follow-up on this subject soon -- stay tuned... ;-)

Addition-substraction chains

While implementing yet another iterated squaring algorithm (yep, this one) and thinking on possible optimizations I've bounced into addition-substraction chains.

An addition-substraction chain for some positive integer N is a list of positive integers which

• begins with 1,
• all the other elements are either the sum or the difference of two earlier members (which can be same in the case of addition) of the list,
• ends with N.

For example, 1,2,4,8,16,32,64,60 is an addition-substraction chain of length 8 for 60.

The question is to determine the complexity of the following question: given an integer N, what is the length of the shortest addition-substraction chain for N?

(Of course it's somewhere around O(lgN).)

Fav Problem #2: R(5,5)

How many vertices can a graph G have at most such that no complete subgraph of 5 nodes appear neither in G, nor in its complement?

The answer is somewhere between 43 and 49.

For more details on Ramsey numbers see this:

http://en.wikipedia.org/wiki/Ramsey's_theorem

Decidability of dot-depth 2

The following problem is well-known and still open for around four decades in the TCS community.

Focusing only on the problem statement: a language L⊆Σ* is of dot-depth two if it is a Boolean combination of languages of the form Σ₁*a₁Σ₂*a₂...Σ_k*a_kΣ_k+1* for some Σ_i⊆Σ and a_i∈Σ. For example, (a+b)*a(b+c)*∩a*b(a+b)* is of dot-depth two.

The question: is the following problem decidable?

• Input: a finite automaton recognizing some language L.
• Output: is L of dot-depth two?

Note: for the case of piecewise testable languages, that is, the case with Σ_i=Σ for each i, there exist several polytime algorithms, the most recent being this one:

http://link.springer.com/chapter/10.1007%2F978-3-642-38771-5_26

It would be interesting to see whether this new proof can be changed to cover a broader class of languages.

Fav Problem #1: Directing partial automata

A partial automaton is a system M=(Q, A, δ ) with Q being the finite nonempty set of states, A being a finite nonempty alphabet and δ being a partial function from Q×A to Q. (meaning something like "if I'm in q and get the symbol a on input, I will be in q'." if δ(q,a)=q' and "if I'm in q and get the symbol a on input, I'm stuck." if δ(q,a) is undefined). Instead of δ(q,a) we often write simply qa.

The action is extended to words as usual, setting qua := (qu)a. Of course if qu is undefined, then so is qua .

A word w is a directing word of M if pw=qw is defined for each state p,q in Q. In other words, if M gets w on input, no matter in which state M is, after processing w it will be in a fixed state. M is called directable if it possesses at least one directing word.

The question can be stated as follows:

Given an n-state directable partial automaton, how long can be its shortest directing word at most?

Known bounds:

1. For each n there exists a directable n-state partial automaton whose shortest directing word has length Ω(3^n/3). See P.V. Martyugin, Lower bounds for length of carefully synchronizing words, Presented at Satellite Workshop on Words and Automata of the International Computer Science Symposium in Russia (CSR'06), St. Petersburg, 2006. Basically a ternary counter is simulated.
2. Every n-state directable partial automaton possesses a directing word of length O(n²·4^n/3). See here: http://dl.acm.org/citation.cfm?id=1570791

My intuition says 3^n/3  is closer to the solution..

Picture languages: is a given set of tiles a maximal code?

The following question is motivated by the recent results of this paper:

http://link.springer.com/chapter/10.1007%2F978-3-642-38771-5_6

A picture is a rectangular array of letters. Given a set S of pictures, let S* stand for the set of those pictures that can be "decomposed" into a composition of members of S as in the following example:

a b c c b a a a b

is a member of the star of S = {

a b

,

c a

,

b

}.

(For formal definitions, see the paper.) 

Now S is a code if every picture in S* can be decomposed in a unique way (with respect to S ofc).

The set S above is a code since there is at most one element of S fitting to the top-left cell of any labeled polyomino (if it's a, we have to use the first domino, if b, the third and if c, the second, iterate).

A code S is maximal if no proper superset of S is a code. (The above S is not maximal since by adding a horizontal domino (a c) we still get a code.)

The question is to determine the complexity of the following problem:

• input: a finite set S of pictures,
• output: YES iff S is a maximal code.

Alternatively, the input can be assumed to be a code.
From the results of the paper we know it's decidable. But is it in P? or coNP-hard?