Skip to main content

All Questions

Filter by
Sorted by
Tagged with
3 votes
1 answer
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 ...
Farah Mind's user avatar
4 votes
1 answer
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-...
Farah Mind's user avatar
0 votes
1 answer
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 ...
Farah Mind's user avatar
0 votes
0 answers
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 ...
inaderi's user avatar
  • 13
1 vote
1 answer
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 ...
inaderi's user avatar
  • 13
1 vote
1 answer
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 ...
Salwa's user avatar
  • 131
3 votes
0 answers
119 views

Proving NP-completeness of an extension in List Coloring Problem

In the List Coloring Problem (LCP), one is given an undirected graph $G(V,E)$, each vertex $v \in V$ is given a list of permissible colors $L(v) \subseteq \{1,2,\dots,k\}$, we want to find a coloring $...
Good to learn everything's user avatar
3 votes
1 answer
294 views

Log-Space Reduction $USTCON\le_L CO-2Col$

I want to show that $USTCON\le_L CO-2Col$ (Log-Space reduction) $USTCON$ The $s-t$ connectivity problem for undirected graphs is called $USTCON$. Input: An undirected graph $G=(V,E)$, $s,t \in V$. ...
LioH's user avatar
  • 387
3 votes
1 answer
1k views

Showing Maximum Independent Set is $NP-hard$

I've read about Maximum Independent Set problem being both $NP-hard$ and $CoNP-hard$. I know this can be shown using reduction from the corresponding Max-Clique problem, But I'm wondering - Is that ...
LioH's user avatar
  • 387
2 votes
1 answer
330 views

NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}

Consider the following decision problems: $CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with at least $k$ connected components} $E-CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with exactly $k$ connected ...
LioH's user avatar
  • 387
3 votes
1 answer
1k views

Does a Minimum-Spanning-Tree always give a lower bound for the weight of any Hamiltonian cycle of the graph?

A minimum-spanning-tree (MST) path is always $V-1$ edges and a Hamiltonian Cycle (HC) is always $V$ edges. Because the HC has an extra edge we could say that in general, the weight of every ...
user2668676's user avatar
1 vote
0 answers
26 views

Log-space reduction from $USTCON$

Is it possible to use $USTCON$ log-space decision algorithm in order to show reduction from $USTCON$ to some other decision problem $A$? I mean - the reduction will run $USTCON$ decision algorithm and ...
LioH's user avatar
  • 387
1 vote
1 answer
66 views

Decision problem - vertex with path to all other vertcies

Consider the following decision problem: Given a directed graph $G$, is there a vertex $v$ that has path to all other vertcies. I am able to place this problem in NL, similarly to the strongly-...
LioH's user avatar
  • 387
2 votes
2 answers
138 views

How to verify Hamilton-Path in log-space?

Given an undirected graph $G$ and an undirected path $p$, Is it possible to verify $p$ is a Hamilton path in graph $G$ using logarithmic space? How is it possible to verify the path goes through all ...
LioH's user avatar
  • 387
1 vote
1 answer
81 views

$stCON$ with path of length $≥ n/2$

The following problem seems very similar to the $stCON$ decision problem: {$G, s,t | G = (V, E)$ such as $V$ is a graph, $s,t ∈ V$, there exists in $G$ a simple path from $s$ to $t$ of length $≥ n/...
LioH's user avatar
  • 387
4 votes
1 answer
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 ...
LioH's user avatar
  • 387
4 votes
2 answers
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 ...
LioH's user avatar
  • 387
1 vote
1 answer
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: ...
xmen-5's user avatar
  • 245
1 vote
1 answer
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$. ...
Lior's user avatar
  • 11
1 vote
1 answer
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$ ...
jams's user avatar
  • 11
4 votes
0 answers
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 ...
pommicket's user avatar
  • 281
3 votes
2 answers
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 ...
Artem Zamarayev's user avatar
8 votes
2 answers
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$...
Valerie Poulain's user avatar
4 votes
0 answers
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 ...
Davis's user avatar
  • 49
3 votes
1 answer
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 ...
1597846254899's user avatar
2 votes
1 answer
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 ...
Xaphanius's user avatar
  • 121
2 votes
1 answer
887 views

Reduction to a vertex cover problem-like with weighted vertices and edges

Description Let us define a new problem with an instance $I = (G = (V, E), K, L)$, whereas: $G$ is an undirected graph $K \le |V|$ $L > 0$ is the maximum limit Each vertex $v \in V$ has a weight $...
Adnan's user avatar
  • 315
5 votes
2 answers
1k views

Building maze to maximize shortest path, may be given waypoints and teleports

How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (...
user1902689's user avatar
2 votes
1 answer
956 views

Reducing the vertex cover problem to a variation of the vertex cover problem [duplicate]

The following variation on the vertex cover problem was given: Given is an instance of graph $G = (V, E)$. Does $G$ have a vertex cover of size at most $\frac{|V|}{4}$? I was asked to prove that ...
Adnan's user avatar
  • 315
3 votes
2 answers
2k views

Negative simple path NP-Complete

Given a graph $G=(V,E)$, and positive and negative edge weights, we would like to understand if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$ My approach was to ...
wizz's user avatar
  • 165
2 votes
2 answers
568 views

Easy instances of the coloring problem on graphs with degree at most 4

Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color. In ...
user avatar
1 vote
1 answer
503 views

Reduction Vertex cover into Dominating Set

I have a question to the reduction from Vertex Cover into Dominating Set. So my lecture says if I have a undirected Graph $G = (V,E)$ where $S \subseteq V$ is a vertex cover. Then we construct a new ...
Marc's user avatar
  • 223
3 votes
1 answer
327 views

Is maximum edge-weighted triangle-free graph NP-hard?

Given a graph $G$ with weights $w_e$ on the edges, choose a subset $S$ of the ''edges'' such that $S$ doesn't contain any 3-cycles, maximizing $\sum_{e\in S} w_e$. Is this problem NP-hard? I thought ...
Alex Meiburg's user avatar
2 votes
0 answers
37 views

Reducible from vertex cover for only some inputs

Suppose I have an NP problem, $\text{PROBLEM}(n)$, such that for certain values of $n$ I can get a reduction from vertex cover with $n$ vertices, and for others such a reduction is not possible (if $\...
Recursively Primitive's user avatar
2 votes
1 answer
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 ...
Alberto Romañach's user avatar
1 vote
3 answers
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 ...
Abhijit Sarkar's user avatar
5 votes
1 answer
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 ...
idoby's user avatar
  • 151
3 votes
1 answer
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 ...
Joe Black's user avatar
  • 151
0 votes
1 answer
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 ...
Zed's user avatar
  • 9
1 vote
1 answer
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 ...
user avatar
3 votes
1 answer
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 ...
StefanH's user avatar
  • 1,449
6 votes
1 answer
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?
Mohsen Ghorbani's user avatar
1 vote
1 answer
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?
user avatar
2 votes
2 answers
533 views

Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

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 ...
allrtaken's user avatar
3 votes
0 answers
51 views

Karp hardness of a module in a graph

DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property: For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
Thinh D. Nguyen's user avatar
1 vote
1 answer
42 views

Karp hardness of a vector system allocation

Given an undirected graph $G(V,E)$, a vector system is a set $S$ of ordered pair (intuitively called vector) $(u,v)$ (we shall call $u$ the initial point, and $v$ the terminal point) that satisfies ...
Thinh D. Nguyen's user avatar
1 vote
1 answer
46 views

Karp hardness of a guarding set in digraph

Our problem is to decide whether a digraph has a guarding set of size at most $k$. Definitions are following. A digraph $G(V,A)$ has $V(G)$ as its vertex set and $A(G)$ as its arc set. A guarding set ...
Thinh D. Nguyen's user avatar
4 votes
1 answer
160 views

Vertex cover with covering radius 2

Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices? A vertex included in this vertex cover variant will cover every edge incident to it and every edge ...
Thinh D. Nguyen's user avatar
3 votes
1 answer
86 views

Karp hardness of searching for a matching split

UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC ...
Thinh D. Nguyen's user avatar
3 votes
1 answer
42 views

Karp hardness of searching for a matching erosion

First, read the previous question: Karp hardness of searching for a matching cut As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...
Thinh D. Nguyen's user avatar

1 2 3
4
5
9