New answers tagged graph-algorithms
0
lemma 1. The posted problem (as I understand it) is NP-hard, even on DAGs,
Proof. The proof is by reduction from Subset Sum. Given a Subset Sum instance with $n$ positive integers $x_1, x_2, \ldots, x_n$ and target $T$, the reduction produces the following instance of your problem. The instance will have a minimal solution (one with objective equal to ...
0
I haven't thought of a solution, but here's a way of factoring the problem.
I assume $G$ is finite. Every directed graph can be factored into a DAG of strongly connected components (SCCs) by (IIRC) Tarjan's algorithm.
Pick a vertex $v$ in some root SCC $C$ (i.e. $C$ has in-degree 0 in the DAG of SCCs) where $|C| \geq 2$. If $v$ is activated some in-...
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 ...
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 ...
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 ...
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 ...
Top 50 recent answers are included
