# Tagged Questions

86 views

### Finding an exactly weighted st-path in a digraph

I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic. The question is: given 2 nodes $v_1$ and $v_2$, is there a ...
42 views

### What do we know about covering the edges of a graph by disjoint paths?

Two related things I have heard/know of are, (1) That there exists a polynomial algorithm to find a cover of the vertices by $k$ vertex disjoint cycles. (Can someone give a reference for this?) ...
36 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 ...
38 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 ...
54 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 ...
35 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 ...
109 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 ...
72 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 ...
53 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 ...
120 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 ...
194 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$ ...
274 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 ...
186 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 ...
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 ﬁgure-of-eight problem (FOE). An instance is an undirected ...
275 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 ...
155 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 ...
180 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 ...
446 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?
100 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 ...
277 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 ...
378 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 ...
681 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 ...
231 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 ...
334 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 ...
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 ...