# All Questions

440 questions
Filter by
Sorted by
Tagged with
487 views

### Algorithm to find a simple path with maximum weight less than a constant in DAG

Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should ...
• 385
1k views

### Minimum Path cover in a Directed Acyclic Graph

Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-...
• 385
626 views

### Longest path in a directed acyclic graph with constraints

Given a directed weighted acyclic graph G=(V,D,W) and a subset of edges D' of D. The problem is to find the longest path in G that passes by exactly one edge of D'. What is the complexity of this ...
• 385
56 views

### Non intersecting paths of graphs with obstacle number one

There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but ...
• 13
1 vote
170 views

### Hamiltonian non intersecting path in plane

$N$ points are located in 2D plane. Some of the pair of the points are connected by line segments. What is the complexity of the problem of existence of Hamiltonian non intersecting path? What if we ...
• 13
1 vote
50 views

### Complexity of K-Colorful Coloring Problem for a Hypergraph

I searched a lot trying to find a reference for the complexity of K-colorful coloring problem for a hypergraph but I cannot find it. Please if anyone has a reference for the complexity of the problem ...
• 131
119 views

• 387
1k views

### Showing Cycle is NL-complete?

Consider the following decision problem : Cycle: Given a directed graph G, does G contains a directed cycle? It is very clear why Cycle belongs to NL. My question is - how to show Cycle is ...
• 387
551 views

### NL - iterating all edges of a graph in log space

Given a turing machine which has logrtmic space, and consists of an input tape and a working tape, Is it possible to iterate all egdes of an input graph? I know the answer is probably NO, because ...
• 387
1 vote
2k views

### Reduction from minimum dominating set to the set cover

To solve the min dominating set problem of a graph G, we can reduce it to a set cover problem. For example to find the MDS of the graph G: We can create an instance of the Set Cover problem by: ...
• 245
1 vote
169 views

### Variant of stCON

Consider the following variation on stCON desicion problem: Given a directed graph G, decide whether for every two different vertices $s$ and $t$, there is a directed path between $s$ and $t$. ...
• 11
1 vote
188 views

### Is it NP-complete to test if a graph contains $t$ $k$-cliques?

Given a graph $G$ along with two non-negative integers $t, k \in \mathbb{N}$, The instance $(G,t,k)$ is a yes instance of the problem if and only if the graph $G$ contains $t$ cliques with $k$ ...
• 11
107 views

### Maximum coloring of a graph with paths through uncolored vertices

Last night, I had a dream involving an intelligent spider which was only able to communicate by crawling around on a grid of words/phrases, like this one: When I woke up, I wondered why some of the ...
• 281
107 views

### League and Divisions problem (np-hard)

There is a League. And there are Divisions, that are the disjoint subsets of this League. There are n teams (unique locations are given, let's assume it's x and y for simplicity reasons). Every team ...
820 views

### Is finding a path with more red vertices than blue vertices NP-hard?

Given a connected, directed graph $G=(V,E)$, vertices $s,t \in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either red or blue, is it possible to find a simple path from $s$...
165 views

### Is Hamiltonian cycle problem on graphs with out-degree at most 3 NP hard?

I am trying to show a different form of Hamiltonian cycle problem is NP Hard. The problem is as follows. We have a directed graph and each node can have at most 3 outgoing edges. Determine if this ...
• 49
241 views

### shortest form $s$ to $t$ stopping at $u$

Suppose you want to go from vertex $s$ to vertex $t$ in an unweighted graph $(V, E)$, but you would like to stop by vextex $u$ if it is possible to do so without increasing the length of your path by ...
1k views

### Probabilistic r-way cut set algorithm

I am reading Probability and Computing, by Mitzenmacher and Upfal, and the exercise 1.24 asks for a generalized algorithm for finding the cut-set of a Graph. In this generalized version, instead of ...
• 121
887 views

79 views

### Is TSP a more detailed form of the "Set Inclusion" question?

Background Set Inclusion GIVEN: set of cards, some with blue backs, and each with a positive, integer face value. QUESTION: Are there any [blue-backed cards] with a [face value <= L]? 2 ...
1 vote
2k views

### Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Assume that P ≠ NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems ...
244 views

### Why is Adleman's molecular algorithm for Hamiltonian Path linear?

In Adleman's 1994 paper (archived), he describes a method of manipulating DNA molecules in a lab that results in a solution to the Hamiltonian Path problem with high probability. He claims that "The ...
• 151
5k views

### Given a set of intervals on the real line, find a minimum set of points that "cover" all the intervals

I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval ...
• 151
750 views

### Proving there is no polynomial algorithm for independent set

I need some guidance in an assignment I'm doing. I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the ...
• 9
1 vote
574 views

### Deleting edges such that largest connected component has at most $n/4$ nodes

Let $G = (V, E)$ be a connected undirected graph with $n > 4$ nodes $V = \{v_1, v_2, \dots, v_n\}$ and $m$ edges. Let $\{e_1, e_2, \dots , e_m\}$ be all the edges of $G$ listed in some specific ...
363 views

### Why is dominating set in $W[2]$, but independent set in $W[1]$

In Parameterized Complexity the Independent Set Problem for a Parameter $k$ ist $W[1]$-complete, and Dominating set is $W[2]$-complete. Now the prototypical $W[1]$ problem is deciding by a single-tape ...
• 1,449
463 views

### Does finding a cycle with $\log n$ length in $\text{P}$?

Let $G$ be an arbitrary graph with $n$ vertices and we want to find a simple cycle with $\log n$ length. Is there exists a known polynomial algorithm for this problem?
1 vote
42 views

### Complexity of two cycles which differ by $1$ in length

Given an undirected graph $G(V,E)$, our problem asks whether $G$ contains $2$ simple cycles which differ by $1$ in length. What is the complexity of this problem?
I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...