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

This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.


6

Upon the suggestion of Louis Esperet, I contacted Philippe Gambette and Christophe Paul, who confirmed promptly. Paul designed this graph for his Habilitation thesis. When they created a Wikipedia page for modular decomposition, they used this graph. Maybe it's the beginning of its wide adaption. It's also featured in the well known survey of Michel Habib ...


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


4

Below is a long-winded answer, but tl;dr in the general case there is no hope for such a formulation, but for many of the particular classes of sparse graphs that have regularity lemmas this formulation exists. For background, there are two popular versions of the SRL. They are: for any fixed $\varepsilon > 0$ and any $n$-node graph $G = (V, E)$, one ...


3

The longest path problem can be reduced to this problem. Let $G = (V,E)$ be an instance of longest $s,t$-path problem. For each vertex $v \in V$ create two vertices, $v_{in}$ and $v_{out}$, and a directed edge with weight $-1$ from $v_{in}$ to $v_{out}$. For each edge $(u, v) \in E$, create an edge from $u_{out}$ to $v_{in}$ with weight $0$. Now each trial ...


3

This problem is Feedback Vertex Set in disguise, and hence NP-Hard, but I'd imagine there are good heuristics out there (I don't know the references myself, maybe someone can help me out here). More specifically, for an input graph $G = (V, E)$ with minimal FVS $S \subseteq V$, there is a solution to your problem that copies each member of $S$ once (and no ...


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


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


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


1

Dominating Set and Independent Dominating Set are NP-hard on paths if there is also in the input a "conflict graph", where an edge in this graph is a pair of vertices which cannot be both in the solution. Cornet, Alexis; Laforest, Christian, Domination problems with no conflicts, Discrete Appl. Math. 244, 78-88 (2018). ZBL1387.05181.


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