# 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

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