Unanswered Questions
882 questions with no upvoted or accepted answers
4
votes
0
answers
134
views
Decidability of CFL Equivalence with Fixed Regular Language
It is a well-known fact that the following problem is undecidable:
Instance: DFA $D$, CFG $G$ over the same alphabet $\Sigma$
Question: Is $L(D) = L(G)$?
This question is undecidable even when it is ...
- 12.4k
-5
votes
1
answer
36
views
Seeking Help to Verify Algorithm for Chromatic Number in Polynomial Time
Recently, I wrote a paper (not published yet) about an algorithm that calculates the chromatic number of any graph in polynomial time. I have mathematical proof to support it, but it needs ...
1
vote
0
answers
46
views
Complexity of isotopy of embedded vertex colored graphs
I am not working in graph theory, but I am looking for a reference for the following. I have two vertex colored graphs, each with |V| vertices. Their valence and color valence are bounded by the same ...
- 11
0
votes
0
answers
43
views
Implementing Lin-Kernighan algorithm for TSP
I'm looking for some guidance in implementing the Lin-Kernighan heuristic for the TSP. I have been trying on and off for a couple of weeks and I have read a bunch of papers, two of the better ones I ...
- 1
1
vote
0
answers
201
views
Is the following spannin tree problem NP-hard or solvable in polynomial time?
Consider the following combinatorial optimization problem in an undirected weighted graph.
Given:
A connected undirected graph $G = (V, E, w)$ where: $ w: E \rightarrow \mathbb{R}_{\geq 0}$ assigns ...
- 71
0
votes
0
answers
16
views
Generalizing LCA in DAGs to Include Proximity and Special Cases
I’m working on a problem involving Directed Acyclic Graphs (DAGs) where I need to compute a generalization of the Lowest Common Ancestor (LCA). Traditional definitions of LCA in DAGs, which focus ...
- 101
3
votes
0
answers
139
views
How to efficiently determine disconnects in a dynamic graph after performing N deletions and M additions
PS: New to this SE, but old time SE/SO user.
Background study - I've gone through this, computer science and computational science SE and also various papers (skimmed) related to fully dynamic ...
- 31
0
votes
0
answers
64
views
tailored case for Dijkstra algorithm can reach O(VElog(V))
I know that this has been debated and discussed millions of times, but I couldn't find anything that explains why the outer while loop in a typical Dijkstra's min-heap implementation is considered 𝑂 (...
- 1
0
votes
0
answers
54
views
Reference for lower bound for realizable PAC learning sample complexity?
Suppose $\mathcal{F} \subset \{0, 1\}^\mathcal{X}$ be a class of functions and denote by $D_m(f) := \{(X_i, f(X_i))\}_{i=1}^m$ a dataset. Here, $X_i$ are iid samples from distribution $P$ on $\mathcal{...
- 213
4
votes
0
answers
128
views
Is this variant of min-cut PTIME?
I am interested in the following variant of the min-cut problem. We are given a directed graph $G=(V,E)$ with $E\subseteq V\times V$, a penalty function $\rho:V\to \mathbb{N}$, and a source $s\in V$ ...
- 1,471
1
vote
0
answers
44
views
Minimum Spanning k-tree
A $k$-tree is a graph obtained by starting with a $k+1$-clique and repeatedly attaching a $k+1$-clique to the graph along a $k$-clique. A tree is then a $1$-tree in this definition.
Is there anything ...
- 111
1
vote
0
answers
57
views
The roles of TCS and swarm intelligence in cognition and other phenomena
Is there any ongoing research on the intersection of TCS with fields such as cognitive science (maybe shedding light onto how humans ideate and reason in specific manners such as in philosophy and ...
- 11
4
votes
0
answers
172
views
Has the Moser-Tardos Algorithm Been Applied to Real-World Problems?
I'm studying the Moser-Tardos algorithm, which is often used to efficiently find solutions to satisfiability problems and avoid bad events in probabilistic settings. I’ve read that it’s mainly applied ...
- 388
4
votes
2
answers
207
views
NP-hardness of the edge covering with dynamic memory problem
I'm studying on the following problem:
Given an undirected graph $G=(V,E)$ and a dynamic memory $M$ with
capacity of $m$ vertices. Initially the memory is empty. It supports two
operations: 1) load($v$...
CommunityBot
- 1
5
votes
0
answers
201
views
Reference request: Undecidability of tiling problem of finite octant
I am seeking a reference/citation for the undecidability of the following (or a similar) tiling problem. While proving its undecidability seems to be an (under)graduate student exercise, I would like ...
- 1,422