-1
votes
1answer
33 views

Is finding negative cycle vertices NP complete?

I was trying to find all the negative cycle vertices using the Bellman–Ford algorithm using this paper solution 7.1(b) in $O(V)$ by tracing back the predecessor subgraph.It is also stated in ...
2
votes
0answers
35 views

What is hiding behind amortized constant delay enumeration?

The following may contain errors. It is precisely because I am not sure I understand the topic that I am asking questions. I do not have books about it and could not find an adequate reference on the ...
1
vote
0answers
51 views

Clique and PSPACE [closed]

I was wondering how I could go about creating an algorithm that gets all the cliques in a graph in PSPACE So far, based on some of the readings I've done, I am considering to use bit-strings (that ...
1
vote
1answer
31 views

Is the minimum weight independent dominating set np-complete in chordal graphs?

I have a found a small article [1] saying (the first paragraph of the introduction) that the minimum-weight independent dominating set is NP-complete in chordal graphs, but at the same time, seems to ...
2
votes
1answer
107 views

Why is determining the size of a maximum independent set or a clique in P?

I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard. With respect to ...
5
votes
1answer
70 views

Why can't you write the 2-paths problem as a max-flow problem?

This is a follow-up question to this. Consider the 2-paths problem: Given a directed graph $D=(V,A)$ and pairs of vertices $(s_1,t_1)$ and $(s_2,t_2)$, are there paths $P_1 = (s_1,\dots, t_1)$ and ...
4
votes
1answer
52 views

Max cut in cubic graphs

The following question is related to the max cut problem in cubic graphs. In this survey paper Theorem 6.5 states A maximal cut of a cubic graph can be computed in polynomial time Browsing ...
0
votes
1answer
118 views

Reduction from 3-SAT to a graphe problem

I have a question, i was trying to reduce 3-SAT to a particular graph problem and i'm not quite sure about a thing i used in the reduction. In fact the reduction build a bipartite graph, the edge ...
1
vote
2answers
192 views

Proving that finding wheel subgraphs is NP-complete

Can you help me with this problem ? Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ ...
10
votes
1answer
251 views

Average length of s-t (simple) paths in a directed graph

Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating ...
6
votes
1answer
185 views

Is induced subgraph isomorphism easy on an infinite subclass?

Is there a sequence of undirected graphs $\{C_n\}_{n\in \mathbb N}$, where each $C_n$ has exactly $n$ vertices and the problem Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$? is ...
2
votes
1answer
107 views

Non-deterministic algorithm for solving figure of 8

I am struggling in trying to figure out a non-deterministic algorithm for the following problem. Consider the following problem, called the figure-of-eight problem (FOE). An instance is an undirected ...
2
votes
1answer
269 views

Prove the following problem is NL-complete

Suppose $$A = \left\{\langle G, d, s, t\rangle \;\Bigg|\; \begin{array}{l} \text{\(G\) undirected}, \\ \text{\(s\) and \(t\) are nodes in \(G\)}, \\ \text{there is a path of length \(d\) from ...
5
votes
1answer
152 views

Showing that Independent set of size $k$ can be decided using logarithmic space

An independent set $I$ is a subset of the nodes of a graph $G$ where: no 2 nodes in $I$ are adjacent in $G$. For natural number $k$, the problem $k-\text{IND}$ asks if there is an independent set of ...
7
votes
1answer
179 views

Can Santa be both fair and efficient?

As the net-evergreen The Physics of Santa establishes, it is physically impossible for Santa to get a gift to every kid on the planet. Route planning won't help much there, but can a good planning ...
3
votes
2answers
405 views

Is the clique problem NP-complete also on bipartite or planar graphs?

We know that the clique problem is NP-complete. Is the restriction of the problem to bipartite graphs or planar graphs still NP-complete?
4
votes
1answer
99 views

Vertex coloring with an upper bound on the degree of the nodes

Consider the set of graphs in which the maximum degree of the vertices is a constant number $\Delta$ independent of the number of vertices. Is the vertex coloring problem (that is, color the vertices ...
4
votes
1answer
273 views

NP-completeness of graph isomorphism through edge contractions with an edge validity condition

Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset ...
17
votes
2answers
371 views

Finding at least two paths of same length in a directed graph

Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$. I would like to know if there are already algorithms for calculating the following decision problem: Are there at least two ...
9
votes
2answers
666 views

NP-Completeness of a Graph Coloring Problem

Alternative Formulation I came up with an alternative formulation to the below problem. The alternative formulation is actually a special case of the problem bellow and uses bipartite graphs to ...
11
votes
0answers
225 views

Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
4
votes
1answer
316 views

Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED

NOTE: Due to the fact that the trip does not end at the same place it started and also the fact that every point can be visited more than once as long as I still visit all of them, this is not really ...
13
votes
1answer
1k views

NP completeness proof of a spanning tree problem

I am looking for some hints in a question asked by my instructor. So I just figured out this decision problem is $\sf{NP\text{-}complete}$: In a graph $G$, is there a spanning tree in $G$ that ...