Computing with graphs

Problems in this collection

11 problems

Graph isomorphism complexity

Two graphs can look different because their vertices have different names. Can we always decide efficiently whether they have the same connections?

Densest-k-subgraph approximation

Can a fast algorithm always choose k vertices spanning within a fixed factor of the largest possible number of edges?

Metric TSP subtour integrality gap

How much can the best traveling-salesperson tour cost exceed its standard fractional relaxation in the worst metric instance?

Small-Set Expansion hypothesis

Is it computationally hard to distinguish a graph with a small nearly isolated set from one where every equally small set strongly expands?

Polynomial-time parity-game solving

Can the winner of every finite parity game be determined in polynomial time?

Deterministic NC perfect matching

Can a deterministic parallel algorithm find a perfect matching in every general graph with polylogarithmic time and polynomially many processors?

Directed feedback vertex set approximation

Can a polynomial-time algorithm remove all directed cycles while deleting at most a fixed multiple of the minimum possible vertex cost?

#BIS approximability

Can we efficiently estimate how many independent vertex sets an arbitrary bipartite graph has, with a guaranteed small relative error?

Constant-factor treewidth approximation

Can a polynomial-time algorithm find a tree decomposition whose largest bag is within a fixed factor of the smallest possible?

Deterministic distributed maximal independent set

Can a network choose a maximal group of nonadjacent nodes in logarithmically many communication rounds without randomness?

Distributed six-cycle detection

Each computer knows only its own place in a network and can send short messages to neighbors. How many communication rounds are needed to discover whether the network contains a cycle through six different computers?

All collections