...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? :-)

Minimum-weight perfect matching in Android system code

Heh.. I've just bounced into this article:
http://www.troodon-software.com/Algorithms/Android/2010/06/20/euclidean-bipartite-matching-multi-touch-and-android/

Check this, it's funny :) Briefly, Android's multitouch dragging uses a function that tries to solve a bipartitate matching problem (aim: track fingers). The function is a greedy algorithm being awkward sometimes. Also, a comment refers to an article in which a near-linear approximation algorithm is developed.

It's maybe just me, but..

• the greedy algorithm seems to be a quick hack and
• the complicated near-linear approximation is an overkill?

I mean.. come on, how large can n, the number of points be in this task? Most people have ten fingers only :-P at this scale, it's not the asymptotic that matters, the constants also play a significant role. So - I would go with the Hungarian method, it's easy to implement and worst-case n^3 is not a big deal at this scale.. I guess.

Bottom line: take care with the hidden constants that hide in the big O. Especially when they are comparable with the input size.

Vickrey is the new Max

Probably most of you already have encountered some kind of an auction system (e.g. buying something on Amazon, eBay etc). There is an item to be sold, a number n of agents, agent i thinks the item worth v_i for him. Of course if this data was available for everyone, then there would be no need for an auction: the agent i who maximizes v_i gets the stuff and pays v_i.
However, such information is sensitive. Thus, during the auction the agents offer bets (either all at once, or sequentially, in one turn or in more turns) and the winner is deduced from the amount he bet.

A possibility for a one-turn sealed-bid auction (sealed-bid means that the agents do not know each other's bets, only the auctioner does) is that the auctioner collects the bids b_i from each agent i, e.g. in sealed envelopes, and agent i who maximizes b_i gets the stuff in exchange for his bid. This is the simplest model and the easiest one to understand.

However, it suffers from the so-called winner's curse: informally, the winner will be almost always unhappy with the outcome. Say there are three agents bidding 1, 2 and 10 respectively. Then Agent 3 will get the stuff for the price of 10. He could have also get the stuff for the price of 3 -- or, if not only integers are in play, for any real number being strictly greater than 2. Thus he can view the situation as "alas, I just lost 8 dollars, I should have bet only 2$ and one cent" which probably makes him unhappy.

There is a simple way for avoiding the winner's curse by employing the Vickrey mechanism: agent i maximizing gets the stuff but he has to pay only the second-highest price. In the previous example, Agent 3 gets the stuff but it costs him only two dollars.
The Vickrey mechanism has numerous other advantages, including:

• it gives an incentive for truthful bidding: each (selfish!) agent now plays his best strategy by bidding exactly b_i := v_i. 
• thus, it's also decision efficient: Agent i maximizing v_i gets the stuff.

(The system is vulnerable to shill bids, though.)

Things get much more complicated when there are more items to sell (either identical or not; an agent can either bet item-wise or for a set of items etc). In that case, complexity and economical problems arise.

Anyone wants to check the literature and write an essay on that? ;-)

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... ;-)

Uniquely solvable puzzles

We know that most "interesting" one-player games (or puzzles) are NP-hard. Read as:

given a puzzle, it's hard to decide whether it has a solution or not.

This question (seemingly) has little to do with the following one:

given a puzzle which is guaranteed to have exactly one solution, compute the solution.

Note that the standard reduction techniques do not preserve the number of solutions (e.g. no UP-complete problem is known as of today). I know that if we drop "exactly" (and write "at least" instead), then we get the class TFNP. But I do not know how this class of "uniqely solvable" problems is called and I'm interested in the current state of the art in this topic :-)

I could use someone to collect and read the literature for me ;-)

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?

Off we go

Hi there,

I've created this blog devoted to various problems in theoretical computer science.

The purpose of the posts here is threefold:

1. I wanted for a long time to have these things all together.
2. I hope it will serve as a basis for students to have some problems to work on if they wish. Students of Uni Szeged can always drop me a few lines, should they become interested in any of these problems -- I'm pretty sure we can arrange a BSc / MSc thesis based on any of these topics.
3. I plan to post (at least occasionaly) a few stories on partial results whenever I succeed to have some progress :) (and also maybe post every now and then on the failures :P ) Think of it as PR. (Theoretical computer science badly needs PR nowadays..)

For all of you readers, welcome and feel free to leave comments, suggestions, ideas etc -- I will be grateful for them.

Cheers,

--szabivan