Skip to main content

All Questions

Filter by
Sorted by
Tagged with
6 votes
0 answers
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 (...
frafl's user avatar
  • 2,309
2 votes
1 answer
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 ...
omega's user avatar
  • 553
6 votes
1 answer
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 ...
sdcvvc's user avatar
  • 3,491
3 votes
1 answer
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 ...
idealistikz's user avatar
2 votes
0 answers
74 views

Complexity of computing the first bits of a minimal permuted adjacency matrix

Given any graph $G$ on $V(G)=\{1,\dots,n\}$ and its adjacency matrix $$A(G)=\left(\matrix{ A_{1,1} & A_{1,2} & \dots & A_{1,n}\\ A_{2,1} & A_{2,2} & \dots & A_{2,n}\\ &&...
frafl's user avatar
  • 2,309
0 votes
0 answers
68 views

The name of "finding the path of a graph that is a variant of hamiltonian path" [duplicate]

Suppose that there is some graph, with $n$ vertexes. We wish to find the hamiltonian path, but we make the graph being searched a little different. There is a person A that travels each (undirected) ...
user14154's user avatar
  • 101
4 votes
4 answers
2k views

Find node that splits tree in half

Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \{u\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is the ...
user avatar
1 vote
2 answers
123 views

Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete

I need to prove that the following problem $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete. Given a finite set of variables $V$, a finite set of inequalities of the form $x \le y$ (where $x, y \in ...
angelst00ne's user avatar
1 vote
1 answer
153 views

Prove that 2-Colourability is in L from Undir-Reachability is in L

Let Undir-Reachability be the following problem: given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G? I need to prove that the 2-Colourability is in ...
angelst00ne's user avatar
2 votes
0 answers
242 views

Travelling salesman problem with detours

I am interested if there exists a following version of the travelling salesman problem: INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each pair ...
user6697's user avatar
  • 337
2 votes
1 answer
225 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 ...
sazap10's user avatar
  • 23
8 votes
3 answers
25k views

How to understand the reduction from 3-Coloring problem to general $k$-Coloring problem?

3-Coloring problem can be proved NP-Complete making use of the reduction from 3SAT Graph Coloring (from 3SAT). As a consequence, 4-Coloring problem is NP-Complete using the reduction from 3-Coloring: ...
hengxin's user avatar
  • 9,561
1 vote
1 answer
224 views

For what values of A and B is the gap-VC-[A,B] problem NP-HARD?

For which values $A,B$ is the problem $\mathsf{gap\mathord-VC}\mathord-[A,B]$ NP-hard? VC is the vertex cover problem. I am given three options: $B=\frac{3}{4},A=\frac{1}{2}$ or $B=\frac{3}{4},A=\...
Jozef's user avatar
  • 1,727
5 votes
1 answer
41k views

Reducing Clique to Independent Set

The Clique problem takes a graph $G = (V,E)$ and an integer $k$ and asks if $G$ contains a clique of size $k$. (A clique is a set of vertices such that every pair of vertices in the set is adjacent.) ...
mona's user avatar
  • 69
3 votes
1 answer
2k 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 \(...
Aden Dong's user avatar
  • 1,131
0 votes
2 answers
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 ...
ShyPerson's user avatar
  • 925
5 votes
1 answer
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 ...
Joni's user avatar
  • 511
29 votes
1 answer
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 ...
user avatar
8 votes
1 answer
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 ...
Raphael's user avatar
  • 72.6k
9 votes
1 answer
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 ...
George's user avatar
  • 352
2 votes
1 answer
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 ...
John's user avatar
  • 23
3 votes
2 answers
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?
Queue's user avatar
  • 489
3 votes
1 answer
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 ...
user avatar
8 votes
4 answers
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 ...
Lazer's user avatar
  • 1,087
4 votes
1 answer
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 ...
user29271's user avatar
  • 113
4 votes
1 answer
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 ...
Helium's user avatar
  • 541
4 votes
1 answer
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 ...
Zat Mack's user avatar
  • 249
5 votes
1 answer
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 ...
user1403806's user avatar
21 votes
2 answers
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 ...
Paolo Parisen T.'s user avatar
7 votes
2 answers
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?
Leo Sanchez's user avatar
3 votes
1 answer
662 views

Restricted version of vertex cover

I am interested in the complexity of the restricted version of the vertex cover problem below: Instance: A bipartite graph $G =(L, R, E)$ and an integer $K$. Question: Is there $S \subset L$, $|S| \...
user avatar
7 votes
2 answers
15k views

Reducing minimum vertex cover in a bipartite graph to maximum flow

Is it possible to show that the minimum vertex cover in a bipartite graph can be reduced to a maximum flow problem? Or to the minimum cut problem (then follow max-flow min-cut theorem, the claim holds)...
Summer_More_More_Tea's user avatar
10 votes
2 answers
2k 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 ...
Helium's user avatar
  • 541
22 votes
1 answer
550 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 ...
Geni's user avatar
  • 321
5 votes
1 answer
957 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 ...
Casper's user avatar
  • 53
25 votes
2 answers
3k views

Is Logical Min-Cut NP-Complete?

Logical Min Cut (LMC) problem definition Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...
amirv's user avatar
  • 401
2 votes
1 answer
6k views

NP-completeness of a spanning tree problem

I was reviewing some NP-complete problems on this site, and I meet one interesting problem from NP completeness proof of a spanning tree problem In this problem, I am interested in the original ...
breezeintopl's user avatar
11 votes
1 answer
1k views

Proving that directed graph diagnosis is NP-hard

I have a homework assignment that I've been bashing my head against for some time, and I'd appreciate any hints. It is about choosing a known problem, the NP-completeness of which is proven, and ...
user8879's user avatar
  • 113
23 votes
2 answers
8k 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 ...
initialize's user avatar
30 votes
1 answer
13k views

How hard is counting the number of simple paths between two nodes in a directed graph?

There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search). However it seems that, ...
hugomg's user avatar
  • 1,379

1
5 6 7 8
9