Unanswered Questions
613 questions with no upvoted or accepted answers
32
votes
0
answers
7k
views
Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?
Roughly speaking, my question is:
How costly is to make a cyclic graph
acyclic while preserving all simple $s$-$t$ paths?
Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$.
(...
- 10.9k
27
votes
0
answers
1k
views
Counting Isomorphism Types of Graphs
Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula ...
- 5,793
23
votes
0
answers
2k
views
$\Delta = 57, d=2$ Moore Graph
I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years.
You may recall that Hoffman and ...
18
votes
0
answers
442
views
Complexity of the homomorphism problem parameterized by treewidth
The homomorphism problem $\text{Hom}(\mathcal{G}, \mathcal{H})$ for two
classes $\mathcal{G}$ and $\mathcal{H}$ of graphs is defined as follows:
Input: a graph $G$ in $\mathcal{G}$, a graph $H$ in $...
- 9,838
17
votes
0
answers
788
views
Practically Good Algorithms of a Very Low Computational Complexity Class
I am looking for one (or more) examples of a parametric class of algorithms $P_t$ for approximately solving a class $\cal A$ of algorithmic questions with the following properties:
1) Solving the ...
- 5,793
16
votes
0
answers
293
views
When does adding edges decrease the cover time of a graph?
When first learning about random walks on a graph $G$, one may have an intuitive feeling that adding edges to $G$ will decrease its cover time $C(G)$. However, this is not the case. The path graph $...
CommunityBot
- 1
16
votes
0
answers
2k
views
What is the fastest deterministic algorithm for incremental DAG reachability?
As the title. The incremental algorithm maintains the reachability information of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if ...
- 519
15
votes
0
answers
652
views
Is it NP-hard to find (the root of) a small decision tree for a monotone boolean function?
Last year I spent some time trying to prove or disprove the following:
Conjecture. Consider a graph $G$ and define a 2-DNF formula $\phi$ that contains a term $x \land y$ iff $x\mathrel{-\!-}y$ is ...
- 4,796
15
votes
0
answers
391
views
Complexity of approximating the range of a matrix
Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:
$$S_M = |\{Mx : x \in \{-1,1\}^n\}|.$$
I believe that it is NP-hard to compute $S_M$ exactly, by applying ...
CommunityBot
- 1
15
votes
0
answers
238
views
Mixing properties of random walks on graphs
I have a question about this paper (not behind a pay wall) on the Cheeger inequality for graphs.
One of the main ideas of the paper is that random walks on graphs can be used to find sets with small ...
Paul Siegel
14
votes
0
answers
193
views
NP-Hardness of 4-cycle packing problem in complete bipartite digraph?
A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of a ...
- 483
14
votes
0
answers
240
views
Counting solutions to extended MSO formulas, and sampling -- do these appear in the literature?
I am trying to determine if the literature contains various extensions of Courcelle's theorem. Since I haven't been able to find these in the literature, I guess that these are folklore results, or ...
- 1,479
14
votes
0
answers
363
views
Finding all-pairs anti-distance
Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem.
Let $G=(V,E)$ ...
- 21.8k
14
votes
0
answers
415
views
Question on Products of Graphs
Let $S_{n}(G)$, $C_{n}(G)$, $T_{n}(G)$ be the $n$-fold Strong Product, Cartesian Product and Tensor Product of a graph $G$ on $|V|$ vertices.
Let the chromatic number ($\chi(G)$) and the independence ...
- 2,228
14
votes
0
answers
503
views
Bi-partite expander graphs
My question relates to bi-partite expander graphs, defined as bi-partite graphs on $n$ left vertices, $m$ right vertices, constant left-degree $k$, such that
For any linear-sized subset $S$ of the ...
- 7,668