# Tag Info

### Algorithm for finding a 3-cycle cover

The cycle cover problem (CC) is the problem of finding a spanning set of cycles in a given directed or undirected input graph. If all the cycles in the cover must consist of at least $k$ edges/arcs, ...
• 5,772
Accepted

### Number of 4 cycles

Yes, this is known. For $d = \Omega(n^{1/2})$ with a sufficiently large implicit constant, any $n$-node graph of average degree $d$ has $\Omega(d^4)$ total $C_4$s. This is best possible because it's ...
• 2,403

### Are there interesting graph classes where the treewidth is hard (easy) to compute?

Treewidth is NP-hard to compute on co-bipartite graphs, indeed the original NP-hardness proof of treewidth of Arnborg et al. shows this. Additionally, Bodlaender and Thilikos showed that it is NP-hard ...
• 3,266
Accepted

### Number of connected components of a random nearest neighbor graph?

For $n$ uniformly random points in a unit square the number of components is $$\frac{3\pi}{8\pi+3\sqrt{3}}n+o(n)$$ See Theorem 2 of D. Eppstein, M. S. Paterson, and F. F. Yao (1997), "On nearest-...
• 51.1k
Accepted

### Are there poly time algorithms to determine if a graph is almost bipartite?

The vertex version is called "odd cycle transversal"; it's NP-complete but fixed-parameter tractable. See: Yannakakis, Mihalis (1978), "Node-and edge-deletion NP-complete problems", Proceedings of ...
• 51.1k
Accepted

### Does Hadwiger conjecture imply that NP = coNP?

I think the problem here is that you are stating the converse of Hadwiger's conjecture. The conjecture (according to Wikipedia) states that "if a graph needs at least k colors for a proper coloring, ...
• 3,722
Accepted

### Smallest vertex cover which is also an independent set

This is the "Independent Vertex Cover" problem. It is solvable in polynomial time. To see this, note that for every edge, exactly one endpoint of the edge must be in a vertex cover. We can reduce the ...
• 27.5k
Accepted

### Connectivity of a random regular graph of degree $d$

For constant $d \geq 3$, a random $d$-regular graph is connected with high probability. In fact, it is an expander with high probability. See for example this note by David Ellis. Friedman even showed ...
• 14.5k
Accepted

### Is the following graph optimization problem approximable within a constant factor?

The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. ...
• 3,909
Accepted

### For which graphs is the DFS tree always a path?

This is equivalent to the property that you can construct a Hamiltonian path by greedily taking an arbitrary edge at every vertex. Searching for greedy Hamiltonian path turned up: Greedily ...
• 1,235
Accepted

### questions on implications Babais quasi P time graph isomorphism result

Johnson graphs are actually easy to recognize. In particular, you can recognize whether an input graph is a Johnson graph in polynomial time, and you can construct an isomorphism between two ...
• 14.5k
Accepted

### Is there a planar 4-regular graph that is 3-acyclic colourable?

I can prove that no 4-regular graphs are 3-acyclic colorable. Consider a 4-regular graph with a 3-coloring. If we call the colors $a, b, c$, then one of the three subgraphs generated by restricting ...
• 806
Accepted

### Isomorphic graph embeddings in the Euclidean Space

This is not possible in general. The 4-cycle is actually helpful to consider: embedding it in $\mathbb{R}^k$ in the way you describe requires the images of all four vertices to be coplanar, forming a ...
• 2,520
Accepted

### Pathwidth of planarized drawing of $K_{3,n}$

A naive drawing of $K_{3,n}$ will have pathwidth $O(n)$. I think that's tight, and that the pathwidth is always $\Omega(n)$. Here's an argument why. (1) Fix a drawing of $K_{3,n}$. Without loss of ...
• 51.1k
Accepted

### Is there an algorithm that finds the forbidden minors?

The answer by Mamadou Moustapha Kanté (who did his PhD under supervision of Bruno Courcelle) to a similar question cites A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second ...
• 3,043
Accepted

### Number of simple paths between two vertices in a DAG

Every simple path is uniquely determined by the subset of vertices that it passes through: if you topologically order the DAG (arbitrarily) then a path through any subset of vertices must go through ...
• 51.1k

### Number of connected components of a random nearest neighbor graph?

EDIT 2: Made explicit the underlying non-asymptotic bounds in the calculation. EDIT: Replaced the calculation for two dimensions by the case of arbitrary constant dimension. Added a table of the ...
• 10.8k
Accepted

### Finding vertex separator such that the induced subgraph has minimal number of edges

An independent set that disconnects its graph is called an "independent cut", graphs that contain an independent cut are called "fragile graphs", and recognizing fragile graphs is ...
• 51.1k
Accepted

### Hard extendability problems

n-coloring the n x n Sudoku graph is trivial, but if some of the colors are given to you (the extendability version) it becomes NP-complete. By the "Sudoku graph" I mean the natural graph whose ...
• 37.4k
Accepted

### The maximum number of induced cycles in a simple directed graph

I don't know what's already known but the obvious bounds are that it is at most $\binom{n}{n/2}$ (Sperner's theorem) and at least $3^{n/3}$ (for $n$ a multiple of three that is at least 9: form a ...
• 51.1k
Accepted

Accepted

### Is the maximum independent set in cubic planar graphs NP-complete?

A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper. Bojan Mohar: "Face Covers and the Genus Problem for Apex Graphs" Journal of ...
• 5,772
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 ...
• 7,615

### What is the best exact algorithm to compute the core of a graph?

The problem of determining whether a given graph is a core graph is easily seen to be in co-NP. In fact, it is co-NP complete. The problem of determining whether a given subgraph H is a core of a ...
Accepted

### Are social networks typically good expanders?

Social networks typically have many vertices with just one or two connections to the rest of the graph. Such vertices will typically lead to a bad spectral gap. What you could hope for is good ...
• 878
Accepted

### Proof that the graph optimization problem is NP-hard

This problem is in P, it can be reduced to the Minimum cut problem. The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from ...
• 126
### For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?
Thanks to my colleague Maxim Zhukovskii for suggesting this answer. It turns out that the answer is negative, and the counterexample is rather simple. Just take $G=K_m\sqcup \overline{K_m}$ and \$H=K_{...