Tagged Questions

127 views

Complexity of the decision version of determining a min-cut

I was wondering what the complexity of the following problem is: Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$. Question: Is there an $s$-$t$ cut of capacity at most ...
208 views

Recovering a point embedding from a graph with edges weighted by point distance

Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the ...
61 views

Easy infinite subclass of cubic graphs for Hamiltonian cycle problem

I know that Hamiltonian cycle problem is $NP$-complete for 2-connected planar bipartite cubic graphs. I'm interested in non-trivial infinite subclass of cubic graphs where the Hamiltonian cycle ...
35 views

First Order interpretation of arbitrary structures as a graph

I am currently trying to get some intuition on the concept of First Order reductions, and have come across this exercise question by Immerman, dubbed "Everything is a Graph". Given some arbitrary ...
63 views

Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

Assumptions: given a graph with N nodes, and two specific nodes A and B the graph is undirected and no edge has a negative cost there exists at least one Hamiltonian path with A and B as an end ...
55 views

To show that a graph-problem is in $L$ or $NL$

Consider the following problem: $$A=\left\{ (G(V,E),s,t)\mid\text{conditions 1, 2, 3 and 4 hold} \right\}$$ $G$ is a directed graph. $s,t\in V$. There is a simple path from $s$ to $t$ (a simple ...
58 views

Complexity of calculating independence number of a hypergraph

Let $G$ be a "hypergraph", a collection of vertices $V=\{v_1,v_2,\ldots,v_n\}$ and a collection of "hyperedges" $E=\{e_1,e_2,\ldots,e_m\}$, where $e_i\subseteq V$ and unlike normal edges, an edge may ...
51 views

Relation between digraph and NP-Complete problem

Can there be any relations regarding the number of nodes available in a digraph so that to qualify it as NP-Complete problem. If we consider this problem for instance: Input: A digraph $G=(V,E)$ and ...
171 views

Proving NP-completeness of a graph coloring problem

Given a graph $G=(V,E)$ and a set of colors $k<V$. Find a assignment of colors to vertices that minimizes the number of adjacent vertices in conflict. (Two adjacent vertices are in conflict if they ...
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 ...
68 views

Reducing 3SAT to Triangle Cover Graph

The Triangle Cover Graph problem is this: Given a graph $G = (V,E)$ and an integer $k$, does there exist a set of at most $k$ vertices of $G$ such that every triangle contained in $G$ also ...
101 views

Intractable properties of Two-factor in connected bridgeless cubic graphs

Petersen's Theorem states that every cubic, bridgeless graph $G(V, E)$ contains a 2-factor $F$ (and therefore a perfect matching $E-F$). Alternatively, 2-factor is a set of vertex disjoint cycles that ...
576 views

Counting and finding all perfect/maximum matchings in general graphs

Recently i've been dealing with a problem that led me to the following questions: Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph? Is there a good algorithm ...
62 views

Reduction from max-cut to min-cut

Algorithms for the finding of an MST in a graph can be applied for both maximum and minimum spanning trees. It is well known, however, that the finding of a max-cut in a graph is an NP-hard problem ...
160 views

Problems that are NP but polynomial on graphs of bounded treewidth

I heard here that the Hamiltonian cycle problem is polynomial on graphs of bounded treewidth. I am interested in examples/references to different problems which is essentially hard but having ...
126 views

Hard computational problem on special class of bipartite graphs

I am interested in the properties of a class of bipartite graphs $G(X \cup Y, E)$ where all nodes in $X$ are 3-regular, all nodes in $Y$ are 2-regular, and $|X|=|2Y/3|$. First, Is this a well known ...
31 views

Complexity class of Determining Hamiltonian cycle

I Know that determining Hamiltonian cycle in a graph is NP complete. For the sake of my clarification, I just want to know that whether the problem remains NP complete with following restrictions ? ...
217 views

$O(n^{k-1}$) algorithm for K-clique problem

Clique problem is a well known $NP$-complete problem where the size of the required clique is part of the input. However, k-clique problem has a trivial polynomial time algorithm ($O(n^k)$ when $k$ is ...
106 views

Negative weight cycle vs maximum weight cycle

I'm having trouble understanding why it's easy to detect negative-weight cycles (Bellman Ford) but hard to find the maximum weight cycle in an undirected graph. If we negate the weight of each edge, ...
177 views

Software for testing graph homomorphism

I have graphs $G_k$ and $H_k$ with $|\mathcal{V}(G_k)|=|\mathcal{V}(H_k)|^{2k}=n^{2k}$ with $k\in\Bbb N$ that pass sanity checks such as no-homomorphism lemma. Are there free and easy to use tools to ...
105 views

Direct reduction from Near-Clique to Clique

An undirected graph is a Near-Clique if adding one more edge would make it a clique. Formally, a graph $G=(V,E)$ contains a near-clique of size $k$ if there exists $S\subseteq V$ and $u,v\in S$ ...
104 views

Courcelle's Theorem: Looking for papers

I am looking for an easy and introductory paper on the proof of Courcelle's Theorem. I am also interested in its connection to parameterized complexity regarding the treewidth. I am only a beginner ...
55 views

Is there a graph product that is multiplicative in independence number?

I know that Stable set cannot be approximated to constant factor. I saw a simple proof using OR product sometime back. I am unable to recall it. If anyone here knows what I am talking about could help ...
69 views

What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?

Suppose we are given an MÃ—N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero ...
55 views

Counting modified perfect matchings

Consider a bipartite graph with vertex set partitioned into $X=\{u_1,u_2,u_3\}$ and $Y=\{v_1,v_2,v_3\}$. Consider the graph has the following edges: $\{u_1,v_1\}$, $\{u_2,v_2\}$, $\{u_2,v_3\}$, ...
139 views

Complexity of finding a spanning tree that minimizes the maximum interference

Given $n$ nodes in the plane, connect the nodes by a spanning tree. For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$â€™s furthest neighbor in the spanning ...
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 ...
234 views

Find which vertices to delete from graph to get smallest largest component

Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component. I assume for large $n = |V|$ and large $k$ the problem ...
178 views

Coordinated Attack Problem On The Arbitrary Graph

Let consider a general version of Two Generals' Problem, when there are $n$ generals located on the arbitrary graph and they should agree on exactly the same value whether to attack or not to attack. ...
116 views

Does reachability belong to P?

Reachability is defined as follows: a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$? Is it possible to write a polynomial time algorithm for it? ...
471 views

Longest path in grid like graph

This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness: Find the length of the longest ...
82 views

Is there a program to solve a metric TSP for 80 edges at optimum?

i'm going to use the Christofides heuristic algorithm in order to solve a TSP for about 80 edges. Eventually i should have a solution, that is within the factor 1.5 of the optimum. But when i'm ...
448 views

Show that Vertex-Cover is NP-complete, using Stable-Set

My task is to give proof, the Vertex-Cover problem is NP-complete, assuming it's already shown that the Stable-Set problem is NP-complete, too. My approach: i know, Stable-Set is NP-complete, and all ...
140 views

k-path problem - P, NP or NPC?

I need to determine which complexity class this problem belongs to: Given a graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of length $k$ exist between thesee two ...
54 views

Famous PPAD class of problems is formally defined by specifying one of its complete problems, known as End-Of-The-Line: End-Of-The-Line Problem: $G$ is a (possibly exponentially large) directed ...
145 views

How to reduce INDEPENDENT SET to INDEPENDENT SET SIZE?

Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET: INDEPENDENT SET VALUE Input: An undirected graph G. Output:The size of the largest ...
365 views

Can the edges of a graph be assigned directions such that all nodes in a given subset have in- or outdegree 0, and every other node indegree > 0?

In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges. Show that the following problem is NP-complete. Given an undirected graph ...
917 views

How to check whether a graph is connected in polynomial time?

I have to solve the following problem: Consider the problem Connected: Input: An unweighted, undirected graph $G$. Output: True if and only if $G$ is connected. Show that Connected ...
45 views

complexity of finding the hampath of length $k$ in a graph with $n$ vertexes where $k < n$

A simple question: What would be the complexity of finding whether a hampath of length $k$ exists in a graph with $n$ vertexes where $k < n$? Would this be in NP-complete or just NP?
61 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 ...
239 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 ...
192 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 ...
58 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}\\ ...
44 views

The name of “finding the path of a graph that is a variant of hamiltonian path”

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) ...
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 ...