Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Tag Info

Accepted

### Find research partner (profession and beginner)

I don't know of such a page. Most researchers have specific problems that they are interested in working on, and would only want to collaborate on those. If you pick a particular area and focus on ...

### The complexity of determining if a fixed graph is a minor of another

There are old results showing that linear minor testing is possible for some specific graphs H, basically by looking at back-edge patterns in depth-first search, with significant effort for each H, ...

### Finding the single-crossing embedding of a single-crossing graph

You can in cubic time figure out which pair of edges to let cross. For this, try all $O(n^2)$ pairs, augment the graph by replacing the two edges by a degree 4 vertex (representing the crossing), and ...
Accepted

### Complexity of "can we get a cycle by stacking directed bipartite graphs?"

Update: Davide showed that this problem is PSPACE-hard here, settling PSPACE-completeness. NP-hardness This is NP-hard by reduction from 3SAT. Let's consider a formula in $k$ variables. Below is the ...
Accepted

### exact path cover for undirected graph

Found the following paper "NP-completeness of some problems of partitioning and covering in graphs" by B.Péroche. The paper proves that deciding whether the edges of a graph can be ...
Accepted

### Pagerank in directed *acyclic* graphs (DAG)

As suggested by the comments (thanks!), the answer is positive and rather easy. We want to compute the pagerank of all vertices of a DAG (Directed Acyclic Graph) $G = (V,E)$ with $n$ vertices and $m$ ...
Accepted

### Proving a property of minimal st-separators that are not minimum st-separators

It does not hold, as can be seen from the red separator in this example. Furthermore, a vertex in a minimum separator can be separated from $s$ and $t$ by a minimal separator:

### Is there a standard axiomatization of graph width parameters?

This isn't quite what you were asking for, but one of the first papers on treewidth found this parameter by axiomatizing a lattice of parameters for graphs, among which treewidth is the top element. ...
Accepted

### Question about algorithm for enumerating minimal AB-separators

tldr: your counterexample is correct. Longer Answer: The way $A$-$B$-separators are defined above the problem to determine whether at least one $A$-$B$-separator exists is NP-complete. In particular ...
Accepted

### Is a grid graph a vertex-minor of a complete graph?

Vertex-minors of complete graphs are either complete graphs, star graphs, or edgeless graphs, so this does not hold for $k \ge 2$. Proof that vertex-minors of complete graphs are complete, star, or ...
Accepted

### State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson

These are not directly comparable: Goemans–Williamson and related work: find a cut in any graph G [of some graph family] that is at least X times the size of the maximum cut of G. This is the usual ...

### Can this special case of Node Weighted Steiner Tree be solved in polynomial time?

To answer my own question, I have found that this problem is indeed NP-Hard via a reduction from the Cactus Augmentation Problem (which is NP-hard). In "Parameterized Algorithms to Preserve ...

### Dynamic programming and shortest path problem

Here's a less formal answer that I hope nonetheless addresses the spirit of the question. Many standard dynamic-programming algorithms are easily seen to be equivalent to shortest-path (or longest-...

### exact path cover for undirected graph

Just a partial answer. Gallai's conjecture was recently proven for planar graphs: https://arxiv.org/abs/2110.08870. The paper gives an algorithm to find the $\lceil \frac{n}{2}\rceil$ desired paths. ...