22 votes

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, ...
Gamow's user avatar
  • 5,772
20 votes
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 ...
GMB's user avatar
  • 2,393
18 votes

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 ...
daniello's user avatar
  • 3,266
17 votes
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-...
David Eppstein's user avatar
16 votes
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 ...
David Eppstein's user avatar
15 votes
Accepted

Classes of graphs with superconstant treewidth

I believe that the universal graphs for trees constructed by Chung and Graham 1983 have treewidth $\Theta(\log n)$. Or for a slightly simpler but similar example consider the transitive closures of ...
David Eppstein's user avatar
15 votes
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 ...
Ryan Williams's user avatar
15 votes
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 ...
Yuval Filmus's user avatar
  • 14.4k
15 votes
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, ...
Michael Lampis's user avatar
14 votes
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'|$. ...
Yury's user avatar
  • 3,899
13 votes
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 ...
Peter Taylor's user avatar
  • 1,235
13 votes
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 ...
Yuval Filmus's user avatar
  • 14.4k
13 votes
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 ...
isaacg's user avatar
  • 806
13 votes
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 ...
Klaus Draeger's user avatar
12 votes
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 ...
David Eppstein's user avatar
12 votes
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 ...
Thomas Klimpel's user avatar
12 votes
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 ...
David Eppstein's user avatar
11 votes
Accepted

What is the complexity of vertex cover on k-partite graphs?

For bipartite graphs, vertex cover is polynomially solvable by routine techniques from matching theory. For $k$-partite graphs with $k\ge3$, we observe the following: Vertex cover is NP-complete on ...
Gamow's user avatar
  • 5,772
11 votes

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 ...
Neal Young's user avatar
  • 10.1k
11 votes
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 ...
David Eppstein's user avatar
10 votes
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 ...
Joshua Grochow's user avatar
10 votes

What is the complexity of the fastest method of k-coloring any graph?

There are non-obvious improvements over simple brute-force search for $k$-coloring (and for many other NP-hard problems). The obvious approach would take roughly $k^n$ time, but one can do it in time $...
Andy Drucker's user avatar
  • 4,634
10 votes
Accepted

Tree-decomposition with clique interfaces

See "Decomposition by clique separators", Robert E. Tarjan, Discrete Mathematics 55 (2): 221–232, 1985. If I understand correctly, your notion of width is essentially the size of the largest piece in ...
David Eppstein's user avatar
10 votes
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 ...
David Eppstein's user avatar
10 votes
Accepted

What is the connection between moments of Gaussians and perfect matchings of graphs?

This fact is a corollary of a more general theorem. Let $\gamma_1,\dots, \gamma_{2n}$ be (jointly) Gaussian random variables; we don't assume that they are independent or identically distributed. Let $...
Yury's user avatar
  • 3,899
10 votes
Accepted

Is this vertex ordering optimization NP-Hard?

Consider your problem restricted to 3-regular graphs. Consider some ordering of the vertices. Define a split vertex to be a vertex $v$ such that both $succ(v)$ and $pred(v)$ are non-empty and define a ...
Mikhail Rudoy's user avatar
10 votes
Accepted

Natural (well studied) classes of graphs with treewidth $\Theta(n^\alpha)$ with $1/2 < \alpha < 1$

The intersection graph of interior disjoint balls in $\mathbb{R}^d$, should have treewidth $O(n^{1-1/d})$, if there is justice in the universe (let me think about it - yep - there is). The treewidth ...
Sariel Har-Peled's user avatar
10 votes
Accepted

Known property? Maximum radius of connected induced subgraph

The property $\Pi_r$, defined as containing exactly the graphs $G$ such that every induced subgraph $H$ of $G$ has diameter at most $r$, is the same as the class of graphs that do not contain a $P_{r+...
Christian Komusiewicz's user avatar
10 votes
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 ...
Gamow's user avatar
  • 5,772
10 votes
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 ...
usul's user avatar
  • 7,615

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