# Tag Info

7

The color coding technique for deciding if a graph contains a $k$-path, presented for example in the book Parameterized Algorithms, can be turned into output-sensitive enumeration algorithm for such paths. The algorithm works in iterations in which a random coloring of $k$ colors is assigned to the vertices of the graph, and then the paths with distinctly ...

6

No, you can't beat $\Theta(\sqrt{n})$ queries. I will explain how to formalize exfret's proof sketch of this, in a way that works for adaptive algorithms. This is all anticipated in exfret's answer; I am just filling in some of the details. Consider any (possibly adaptive) algorithm that issues a sequence of queries, where each query is either "fetch the $... 5 Let’s assume we can only query the$i$th edge of a given vertex’s adjacency list (which I am assuming is not sorted) or whether two given vertices are adjacent. In this case it should take$\sqrt n$queries to even find a cycle. This is because there is a$1-o(1)$chance that all our queries of the first type return different vertices and that all of our ... 3 I'm going to assume you didn't mean to end up two (maximal) cliques, but instead two disconnected complete graphs. Those are not the same, e.g. for$n = 6$you can end up with extra edges that don't form any other maximal cliques otherwise: If that assumption is correct, your operation is called a bisection of the graph. You want to maximize the remaining ... 3 Path with minimum weight gap: This can be solved in time$\tilde{O}(|E|^2)$, where$|E|$is the number of edges (assuming$|E|\$ is at least linear in the number of vertices). You can loop over the minimum weight, and do binary search (or efficient updates) over the maximum weight, and check connectivity. I do not know whether this can be improved. Path ...

1

To me it was somewhat surprising that minimal vertex cover is a subproblem of the Hungarian Algorithm, namely when determining a minimal set of horizontal or vertical lines that cover all the zeros that were generated by subtracting row and column minima. That amounts to finding a minimal vertex cover in a bipartite graph which, also surprisingly, can be ...

Only top voted, non community-wiki answers of a minimum length are eligible