Skip to main content
Share Your Experience: Take the 2024 Developer Survey

All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
InfiniteSnow's user avatar
0 votes
1 answer
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 ...
Toyllo's user avatar
  • 1
1 vote
1 answer
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 ...
Lebecca's user avatar
  • 113
3 votes
1 answer
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 ...
licheng's user avatar
  • 405
2 votes
2 answers
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 ...
Daniel García's user avatar
3 votes
2 answers
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 ...
knorbika's user avatar
2 votes
0 answers
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 ...
tgnome's user avatar
  • 153
6 votes
0 answers
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 ...
tgnome's user avatar
  • 153
2 votes
1 answer
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 ...
wellknow's user avatar
1 vote
0 answers
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 ...
bbg07's user avatar
  • 11
2 votes
2 answers
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 ...
Maceo Cardinale Kwik's user avatar
2 votes
1 answer
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 ...
Placido Pellegriti's user avatar
8 votes
2 answers
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 ...
licheng's user avatar
  • 405
1 vote
1 answer
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 ...
AmirD's user avatar
  • 13
1 vote
1 answer
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 ...
LargeHorse's user avatar
2 votes
0 answers
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 ...
quTANum's user avatar
  • 21
0 votes
0 answers
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 ...
Kingdom Mutala Akugri's user avatar
0 votes
0 answers
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 ...
MariyaKav's user avatar
  • 101
0 votes
0 answers
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 ...
Gabi G's user avatar
  • 325
2 votes
0 answers
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 ...
hadizadeh.ali's user avatar
1 vote
1 answer
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 ...
Gabi G's user avatar
  • 325
0 votes
0 answers
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 ...
2080's user avatar
  • 251
1 vote
1 answer
51 views

What are the necessary requirements for proving NP is closed under complement?

I've had the following question on a test and I answered: 'False', my answer was incorrect and I'm trying to understand why. $VC = \{<G,k> |\ G =$ undirected graph with a vertex cover of size $k\...
Skynet's user avatar
  • 53
0 votes
1 answer
38 views

How to generate all the possible nodes inside a polygon, if the polygon is represented by its vertices

If a polygon is represented by its vertices(latitudes, longitudes), is it possible to find all the possible points or nodes(latitudes, longitudes). If so, what kind of algorithm is used. The polygon ...
Senthil's user avatar
0 votes
0 answers
81 views

Efficient Algorithm To Find A Path Which Covers Maximum Area Along Polygonal Perimeter For Surveillance Application

In the context of surveillance, I am working on a project where the goal is to find an algorithm that determines a path along a polygonal area, connecting a root node to a target node, while ...
Senthil's user avatar
1 vote
0 answers
27 views

Color a a general graph with maximal degree $\Delta$ using $2^{O(\Delta)}$ colors within $\log^{*}n$ rounds

Consider the following algorithm $A$ to 6-color an rooted tree within $\log^{*}n$ rounds in a distributed system: 1: Assume that initially the nodes have IDs of size $\log(n)$ bits 2: The root is ...
Gabi G's user avatar
  • 325
0 votes
1 answer
37 views

Universal lower bound of the multi message problem

The multi message problem is: Let there be an undirected graph $G = (V,E)$ with $n$ vertices, and let $r \in G$. The algorithm sends a message $M_i$ of size $\Omega(\log(n))$ to each vertex $v_i$ ...
Gabi G's user avatar
  • 325
2 votes
1 answer
105 views

Is the clique decision problem in co-NP?

Is the clique decision problem in co-NP? Definitions: "In the clique decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph ...
Lilith's user avatar
  • 23
1 vote
1 answer
50 views

Given a bipartite graph G and an integer l, how many edge subsets of size l are there such that the degree of each vertex is odd?

Given a bipartite graph $G=(V,E)$ and an integer $l$, how many edge subsets ($E'\subseteq E$) of size $l$ are there such that the degree of each vertex in the resulting subgraph $G'=(V,E')$ is odd? I ...
QNA's user avatar
  • 133
0 votes
1 answer
297 views

Is maximal independent set on maximal planar graphs still NP-complete?

We know that finding the size of the maximal independent set of a planar graph is NP-complete. I'm curious about whether it remains NP-complete for maximal planar graphs, i.e., the graphs in which ...
Soha's user avatar
  • 25
1 vote
0 answers
42 views

what is the worth of non-read once Branching Programs?

In Harvard CS 221 Computational Complexity, Lecture 3, it introduced Branching Programs A branching program is a DAG that has 1 start node and 2 output nodes with out-degree 0, labelled 0 and 1. Each ...
Jxb's user avatar
  • 318
0 votes
1 answer
39 views

If a graph is not 3-COLORable, then there are at most 2 Independant Sets in G?

Assuming $G=(V,E)$ is a 3-colorable graph, then there are 3 disjoint independent subsets of $V$: $S_1,S_2,S_3$ such that $S_1 \cup S_2 \cup S_3=V$, by taking each $S_i$ to include the vertices of ...
Geo's user avatar
  • 47
0 votes
1 answer
67 views

Complexity of counting odd node in an undirected graph?

I want to know if there exist a algorithm to efficiently compute the number of odd vertex in an undirected graph? A graph vertex in a graph is said to be an odd vertex if its vertex degree is odd, ...
Anuj's user avatar
  • 43
1 vote
0 answers
60 views

Restricted Planar 3-SAT NP-hard

As we all know, 3-SAT is NP-hard. Two of the less known results are that Planar 3-SAT is NP-hard and also a 'restricted' 3-SAT, where any literal appears in at most two clauses turns out to be NP-hard....
Freshman's Dream's user avatar
0 votes
0 answers
36 views

The computational complexity of a variant of algorithm for the TSP (Travelling Salesman Problem)

What is the algorithm's computational complexity for a variant of the Travelling Salesman Problem, where every node must be visited at least once, meaning that a node can be visited more than once? (...
AmirHosein Adavoudi's user avatar
1 vote
1 answer
107 views

Proof that STCON is in NL

What is the proof that STCON (returns 1 if there is a path in the directed graph $G = (V,E)$ from $ s \in V$ to $t \in V$ and else, 0. is indeed in NL? (Non-deterministic turing machines with ...
yellowcard123's user avatar
0 votes
1 answer
95 views

Transforming a Travelling Salesman Problem to a Maximum Clique Problem

Say you have a directed graph consisting of n nodes and containing edge weights. A starting node is also given. You want to begin your route at that node and visit each other node in the graph exactly ...
Emily's user avatar
  • 1
0 votes
1 answer
57 views

Is graph isomorphism $P$-hard?

Intuitively speaking, it would seem like the graph isomorphism problem (which might be $NP$-intermediate) should be $P$-hard. But maybe it's not? Or maybe it's an open question? If it is indeed $P$-...
badroit's user avatar
  • 727
1 vote
1 answer
38 views

Independent set problem for graphs with very large independent sets

Is there a number $\alpha < 1$ such that the independent set problem is polynomial for input graphs whose independence number is at least $\alpha n$ (where $n$ is the number of vertices)?
Lior Gishboliner's user avatar
0 votes
1 answer
115 views

Is there a known method for reducing the problem of prime factorization to the problem of determining if a hamiltonian path exists?

I hope this question is not out of place here, but I am currently attempting to implement the problem(a reduction algorithm) stated in the Title. I included the steps I am following as of now and an ...
LargeHorse's user avatar
-1 votes
1 answer
69 views

What is the complexity of determining whether a graph has a maximal clique of a given size?

What is the complexity class of: given a graph G, is the graph has a maximal clique of size k? k is integer less than or equal the number of graph vertices. A related question, Given a Graph G, Find a ...
DrMath's user avatar
  • 1
1 vote
1 answer
36 views

Choosing the ideal problem to prove the hardness

I am research scholar currently working in complexity theory. Recently, i have started working on hard proofs and reductions. It is very well established that there is a polynomial reduction from ...
Balchandar Reddy's user avatar
1 vote
1 answer
233 views

Graph Isomorphism Problem: decisional vs functional

The Graph Isomorphism Problem is a classic in Computer Science. In its decision version $(DGI)$, we are given two graphs $G$ and $H$ and we are asked if there exists an isomorphism between the two. In ...
VashTheStampede's user avatar
0 votes
1 answer
823 views

Why is the complexity of BFS O(V+E) instead of O(V*E)?

CLRS pseudocode: ...
mimmolg99's user avatar
-1 votes
1 answer
66 views

Complexity of DFS : O(m)

We say that dfs runs in $O(n+m)$ . For any connected graph $m \geq n-1 $. Therefore : $$m \geq n-1 \implies O(n+m) = O(m)$$ Do you agree ? Because, I have seen in many algorithms proofs this bound $O(...
tonythestark's user avatar
1 vote
1 answer
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 ...
user1454066's user avatar
2 votes
0 answers
73 views

Playing with boxes: NP-hard? [Graph Theory]

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 \...
Muses_China's user avatar
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 ...
Mostfa Mostfa's user avatar
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, ...
Siolan's user avatar
  • 21
3 votes
1 answer
94 views

Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?

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 ...
Subhankar Ghosal's user avatar

1
2 3 4 5
9