# All Questions

440 questions
Filter by
Sorted by
Tagged with
94 views

### Decomposition of graphs that uses centers

Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason (...
• 2,309
4k views

### How to analyze the Steiner tree problem?

I have a problem where I am supposed to analyze the Steiner tree problem by doing the following 3 steps. 1) Look up what the Steiner tree problem is. 2) Find a ...
• 553
237 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 ...
• 3,491
1k views

### Prove finding a near clique is NP-complete

An undirected graph is a near clique if adding an additional edge would make it a clique. Formally, a graph $G = (V,E)$ contains a near clique of size $k$ where $k$ is a positive integer in $G$ if ...
• 369
74 views

• 1,131
182 views

### Cliques in an alternate graph representation

EDITS: corrected $r$ to add edges just like $f$ does in paragraph 8 per the first comment below. Also specified the Clique problem of interest in paragraph 2. Having received no response to this ...
• 925
847 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 ...
• 511
20k views

### Is the k-clique problem NP-complete?

In this Wikipedia article about the Clique problem in graph theory it states in the beginning that the problem of finding a clique of size K, in a graph G is NP-complete: Cliques have also been ...
267 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 ...
• 72.6k
3k views

### Minimum s-t cut in weighted directed acyclic graphs with possibly negative weights

I ran into the following problem: Given a directed acyclic graph with real-valued edge weights, and two vertices s and t, compute the minimum s-t cut. For general graphs this is NP-hard, since one ...
• 352
1k views

### Modification of Hamilton Path

Although I know that the Hamilton Path problem is ${\sf NP}$-complete, I think the following variant can be solved in polynomial time: Given a planar graph with vertex set $V$, edge set $E$, start ...
• 23
4k 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?
• 489
235 views

### Proving following problem NP Hard using known NP Hard partition problem

Least cost travel by intermixing different airline routes having linear discount functions: Lowest air fare route chosen by mixing different routes provided by different airline having different ...
4k views

### Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?

I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists. Is there a good / quick / easy way to see ...
• 1,087
194 views

### Is finding dead-end nodes in NL?

Given a directed graph $G$ and two nodes $s,t$, decide whether there is some node $s'$ such that $s'$ is reachable from $s$ while $t$ is not reachable from $s'$. I am wondering whether this problem ...
• 113
407 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 ...
• 541
8k views

### Is finding the longest path of a graph NP-complete?

The problem of finding the largest subgraph of a graph that has a Hamiltonian path can be restated as finding the longest path of a graph. Is this NP-complete? Also, is finding the $k$-length path of ...
• 249
772 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 ...
889 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 ...
1k views

### Has anyone found polynomial algorithm on Hamiltonian cycle isomorphism?

As the title says, has anyone found a polynomial time algorithm for checking whether two graphs having a Hamiltonian cycle are isomorphic? Is this problem NP-complete?
662 views

• 333