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

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? ^_^

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