Share Your Experience: Take the 2024 Developer Survey

# All Questions

435 questions
Filter by
Sorted by
Tagged with
10 views

### Minimum cost hamiltonian path of length K over any subset of nodes in a graph

I came across a situation in real life that maps to this optimization problem: Across all Hamiltonian paths of length $K$ in a fully connected, undirected graph with $N \ge K$ edges, find the one ...
30 views

### Robust maximum weight forests with weights on edges

In an undirected weighted graph with edge weights, the task is to find a spanning tree T. An adversary will delete two edges (not necessarily from T), and subsequently, we can add an edge (excluding ...
1 vote
45 views

### Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

This is the same problem here but with one more condition that the sum of the distance cannot be a negative integer. The full description of the problem is: Is it possible to find a simple path (no ...
• 113
347 views

### Is determining the existence of a Hamiltonian cycle in a chordal graph NP-hard?

The Hamiltonian cycle problem asks if a given graph contains a Hamiltonian cycle. The Hamiltonian cycle problem belongs to the class of NP-complete problems. However, for some special classes of ...
• 405
101 views

### No Neighbor Vertex Cover

Let $G=(V,E)$ be an undirected connected graph with a set of vertices $|V|$ and a set of edges $|E|$. A set cover $D$ satisfies $D \subseteq V$ and $uv \in E \implies u \in D \lor v \in D$. A variant ...
672 views

### Is 2-coloring in NL or L?

The 2-coloring problem is in P. How can I prove that it is in NL or L? I see that I should create a deterministic/nondeterministic algorithm with logarithmic space, but I have no idea how to store ...
• 83
57 views

### Are there $r$ pairwise edge-disjoint $k$-sets of internally disjoint $s$-$t$-paths? Complexity

Given an undirected graph, two vertices $s$ and $t$, and two integers $k$ and $r$, then a $k$-set of internally disjoint $s$-$t$-paths is defined to be a set of exactly $k$ $s$-$t$-paths that share no ...
• 153
170 views

### Are there $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are internally disjoint? Complexity

Given an undirected graph, two vertices $s$ and $t$, and two integers $k$,$l$ - what is the complexity of finding $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are pairwise ...
• 153
76 views

### Proof that the K coloring problem is weakly or strong NP-complete?

As far as I know, the K coloring problem is NP-complete. However, I'm a bit confused about how to determine whether a problem is weakly or strongly NP-complete. If an NP-complete problem is decidable ...
• 21
1 vote
34 views

### Reduction from Hamiltonian path to Tripartite decision problem

I teach a fairly advanced algorithms class to high schoolers and I accidentally presented them with a bunk reduction from Hamiltonian path to the Tripartite graph decision problem. My attempt involved ...
• 11
35 views

### Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes

I am having trouble with a problem where I am given an adjacency list and a list of the nodes that must be visited exactly once to connect two nodes. What is the most efficient way of doing this? This ...
80 views

### Dinitz’ algorithm in simple unit-capacity networks

I am studying for an algorithm design course, and can't understand this demonstration about how Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time. This is what is written on the slides ...
1k views

### Algorithmic Complexity of Recognizing Claw-Free Graphs

Let $H=\left(V_H, E_H\right)$ and $G=(V, E)$ be graphs. A subgraph isomorphism from $H$ to $G$ is a function $f: V_H \rightarrow V$ such that if $(u, v) \in E_H$, then $(f(u), f(v)) \in E$. $f$ is an ...
• 405
1 vote
54 views

### GNI public coin interactive proof: why randomize y?

I've read this scribe that provides a public coin interactive proof for graph non-isomorphism. In the proof, the verifier samples both a pairwise-independent hash function and a target $y$. Then it ...
• 13
1 vote
125 views

### Finding the Largest Partition of Non-Connected Nodes in a Graph in polynomial time

I have a graph, and I want to determine the largest possible set (or partition) of nodes such that no two nodes within this set have an edge between them. I am looking for an efficient algorithm to ...
121 views

### complexity of graph matching with order constraint

Given a graph with $n$ vertices and $m$ edges, $m \le {n \choose 2}$, we index the vertices from 1 to $n$, and denote every edge by $(l,r)$ where $1\le l < r \le n$. Find the maximum $k$ such that ...
• 21
41 views

### Minimum spanning tree using BFS

In finding a minimum spanning tree, if we use a BFS and at any node instead of deleting the edge to a repeated node, we can find the most expensive node in that cycle instead and delete it. In such a ...
31 views

### Complexity of checking whether the vertex has more neighbors of blue or red color

Assume we have a set of $s$ vertices, say $\{w_1,\ldots,w_s\}$. Assume every vertex $w_i$ has at most $q$ neighbours coloured either red or blue, for some positive integer $q\ge 1$. I would like to ...
• 101
49 views

### Algorithm for leader election in synchronous ring with a known network size $n$ with phases of length $\frac{n}{m}$

Consider the following leader election algorithm election of a synchronous ring with a known network size $n$ (simultaneous wakeup and uni-directional communication): The leader is the node with the ...
• 325
44 views

### Has Triangle Finding ever been faster than Matrix Multiplication?

The Triangle Finding problem (TF) in Graph Theory was shown by Itai and Rodeh in 1977 [1] to be solvable as fast$^1$ as Boolean Matrix Multiplication (BMM, Matrix Multiplication over $\{0, 1\}$ with ...
1 vote
46 views

### Showing that nearly regular graphs have a specific $(2,O(\log n))$ ruling set with high probability

An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that ...
• 325
48 views

### How hard is it to find a spring network configuration with the lowest energy?

Given a spring system: where the total tension between the nodes should be minimized, it seems possible that a physics simulation of this graph does not arrive at the lowest energy state, getting ...
• 251
1 vote
51 views

• 211
1 vote
53 views

### Give an example of a language $B$ is $NL-complete$ where $B^* \in L$

I need to give an example of a language $B$ is $NL-complete$ where $B^* \in L$. I know $PATH$ is $NL-complete$ (but not limited to using other languages). I am clueless about that. I know $L$ is not ...
You are playing with boxes on a $K_{1, n}$-$\textbf{subdivision}$ graph $G:=(V, E)$ whose number of vertices is odd, i.e., $|V| \equiv 1$ (mod $2$) with a given central point $C$ such that $\forall v \... • 121 0 votes 0 answers 31 views ### Computational Complexity theory - Confusion about solving by reduction an NPC problem I can't seem to grasp the term of reduction that well. To explain I will take an example the problem of $$\sqrt{k} - clique$$ such that $$k \leq \sqrt{V}$$ Solving by reduction with normal k-clique ... 2 votes 0 answers 56 views ### Subgraph Isomorphism with Same Number of Nodes I am looking at a specific variant of subgraph isomorphism: Instance A graph$G = (V_G, E_G)$and a target graph$H = (V_H, E_H)$such that$|V_G| = |V_H|$. Question Is there a subgraph$G' = (V'_G, ...
Suppose the optimal color assignment of graph $G$ is given. Does there exist any polynomial-time algorithm that provides the optimal color assignment of its complement graph $\overline{G}$? A ...