Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

learn more… | top users | synonyms (1)

2
votes
1answer
83 views

Efficient recalculation of the maximum flow when edge capacities are reduced

Assume that we have a (directed) graph $G(V \cup \{s, t\}, E)$ and an (integer) capacity function $c : E \mapsto \mathbb{N}$. Let $f : E \mapsto \mathbb{N}$ be a maximum $s-t$ flow on this graph. ...
1
vote
1answer
65 views

Minimum order of partite in a bipartite graph

I want to create a bipartite graph where the first partite $U$ contains $L$ vertices with degree $k$ and the second partite $V$ contains $N$ other vertices with degree $a$. I need to find the minimum ...
-1
votes
0answers
31 views

Many-one reduction from inequality problem to equality problem

Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is: ...
0
votes
0answers
60 views

Finding Contextual Nodes in a Knowledge Graph

I'm currently participating in developing a knowledge graph that uses ConceptNet and a few others as its data sources. It uses the same architecture as ConceptNet namely it is stored as a Hypergraph ...
-1
votes
0answers
29 views

Pseudoflow in oriented graph

I have a hard time solving the following problem: We have an oriented graph with positive integer capacities. We are also given for each vertex v the minimal sum of flows from edges in in-direction ...
1
vote
1answer
132 views

Has this formulation of pursuit evasion been researched? Similar to Helicopter Cops and Robbers Game

There are pursuers and evaders in the vertices of a directed graph G with one component. Each vertex must have atleast one outgoing edge (can be a loop). At each time t: The evaders must move ...
-4
votes
0answers
48 views

non-Hamiltonian cubic planar graphs [on hold]

What is the current state of knowledge about whether a polynomial deterministic algorithm has to be able to output every Hamiltonian circuit in every instance of a cubic planar graph $G$ in order to ...
0
votes
0answers
93 views

Example of scalable non-Hamiltonian cubic planar graph

Suppose I have a non-Hamiltonian cubic planar graph $G_1$ = ($V$, $E$) where no face has fewer than five sides, and that I can partition V into two Hamiltonian subgraphs. Suppose further that $G_1$ ...
2
votes
0answers
106 views

$CIS_G$ problem deterministic lower bound

In notes, http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/clique-notes.pdf, it is mentioned towards end of section $4$ that http://dl.acm.org/citation.cfm?id=237817 shows that ...
1
vote
0answers
39 views

Transitive reduction not provably minimal

Working on finding minimal equivalent graphs, which unlike transitive reductions only allows for edge removals from the original graph. I was under the impression that if you allow for new edges to be ...
3
votes
1answer
115 views

Finding a minimum directed cut that splits a weakly connected bipartite graph into two such non-edgeless graphs

Consider a directed, weakly connected bipartite graph $G = (U, V, E)$ where $U$ and $V$ are sets comprising the nodes of $G$, and $E \subseteq U \times V$ is the set of edges. The task is to find a ...
2
votes
1answer
120 views

Algorithms for computing the minimal vertex separator of a graph

Background: Let $u,v$ be two vertices of an undirected graph $G=(V,E)$. A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$ belong to different connected components of $G−S$. If no proper ...
1
vote
1answer
110 views

Comparison between the maximum clique and maximum biclique problem

It seems to be commonly believed that the maximum biclique problem (on a bipartite graph) is more difficult than the original maximum clique problem. Is there a formal proof for this claim? (For ...
-4
votes
0answers
33 views

hardness of approximating $|V| + OCT$

I try to establish a hardness result for the (strange) objective function "|V|+OCT", where OCT is an odd cycle transversal. I can cleary get that there is no PTAS, but I would like to improve this. ...
0
votes
1answer
98 views

What is the Algorithm to find all the possible chordal graphs which can be formed by a given 'n' number of vertices

A chordal Graph is a connected graph which contains no chord-less cycle of size greater than three. They are also called as Triangulated graphs. All Paths are Chordal Graphs (No cycles). All Trees ...
4
votes
1answer
330 views

The complexity of a multi-objective shortest path problem

I have the following shortest path problem. Consider a directed graph with $n$ levels. Each level has $m$ nodes. Each node at level $i$ is connected to all nodes at level $i+1$. Let us also make a ...
0
votes
0answers
48 views

DAG reduce edges by transitivity

I have a DAG like this $G_1 = \lbrace A \to B \to C \rbrace$ My algorithm modify $G_1$ so it will be like this $ G_2 = \lbrace A \to C, B \to C \rbrace $ I now that $G_2$ is not a transitive ...
4
votes
2answers
326 views

Weird claim of graphclasses about complexity of domination

EDIT this got 'fixed' on graphclasses, as per answers/comments, so you might not reproduce it, unless you have their earlier database, which is publicly available via sage - http://sagemath.org. ...
5
votes
0answers
94 views

Complexity of coloring in weakly perfect graphs?

A graph is weakly perfect if the clique number equals the chromatic number, i.e. $\omega(G)=\chi(G)$. Deciding membership is NP-complete according to the paper. Because of the inequality $\omega(G) ...
2
votes
0answers
125 views

How much faster is solving Clique in properly colored graph?

Given a graph $G$ and a proper vertex coloring $C$ with the minimum numbers of colors, how much faster can a maximum clique be found than when just $G$ is given? Additional information doesn't make ...
4
votes
1answer
155 views

Graph theoretic restriction to Proofs in Proof Complexity Theory

Proof complexity is a most basic area of computational complexity theory. An ultimate purpose of this area is to prove $NP\neq coNP$, that is, any prover cannot give a proof of unsatisfiability of ...
0
votes
1answer
40 views

polytime transformation from a graph to a set of binary strings

$d_H$ denotes the Hamming distance between two binary strings of the same size. The problem is stated as follows. Given any undirected graph $(V, A)$, does there always exist a one-to-one ...
3
votes
3answers
219 views

Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof?

Good Evening! I am aware that the minimum (cardinality) vertex cover problem on cubic graphs ($3$-regular) graphs is $NP$-hard. Say positive integer $k>2$ is fixed. Has there been any ...
3
votes
1answer
191 views

Graph with minimum number of edges having given sets of nodes as its paths

Consider the following problem: Input: a list of subsets $P_1, P_2, \ldots, P_k \subseteq V = \{1, \ldots, n\}$ Output: a graph $G = (V,E)$ with minimum number of edges such that for every $P_i$ ...
7
votes
1answer
126 views

Complexity results about locally bipartite graphs

A graph is locally bipartite if the open neighborhood of every vertex induces a bipartite graph. (According to searches the same name might be used for something else related to surfaces). Which ...
4
votes
1answer
111 views

Addding edges to spanning tree without destroying planarity

Given a graph $G=(V,E)$ with n vertices, m edges, and the maximum degree $\Delta$. Let $T$ be a spanning tree of $G$. Let $E_c \subseteq E - E(T)$ be the maximum number of edges that we can add to $T$ ...
5
votes
0answers
162 views

Less known graphical representations of Boolean functions

A Boolean function $f: \{0, 1\}^n \rightarrow \{0, 1\}$ admits a canonical graphical representation in terms of a reduced ordered binary decision diagram (ROBDDs or BDDs for short). There are other ...
15
votes
1answer
358 views

Is this dense version of Kruskal's algorithm well-known?

About a year ago, a friend and I thought of a way to implement Kruskal's algorithm for dense graphs in better than the usual $O(m \log m)$ bound (without assuming pre-sorted edges). Specifically, we ...
1
vote
1answer
59 views

An edge orientation procedure to generate all acyclic orientations of a graph

Consider the following scheme for enumerating acyclic digraphs (DAGs) by orienting the edges in an undirected graph $G$ with $n = ||V||$ vertices: (1) Generate all $n!$ possible permutations $p_i$ of ...
3
votes
0answers
321 views

$NP$-complete problems on cubic Hamiltonian graphs

The class of cubic Hamiltonian graphs is well studied class. I came across the fact that independent set problem is $NP$-complete when restricting input to cubic Hamiltonian graphs. I am interested in ...
5
votes
1answer
115 views

Why does the transformation in the proof for SL=L preserve connectedness of s and t?

I'm currently working on this paper showing that $\mathcal{SL} = \mathcal{L}$. But I keep wondering how the transformation $\tau$ in definition 3.1 preserves the connectivity of $s$ and $t$. $\tau$ ...
0
votes
0answers
94 views

Steiner Tree and minimum spanning tree

If I must connect: $$2^k$$ terminals in a Steiner Tree choosen randomly and connect them with the cheapest component; "loss - contracting algorithm" is a good way? Or is an "Iterative Randomized ...
1
vote
0answers
50 views

Realization of a bipolar orientation by a mixed graph

Given an undirected graph $G(V,E)$ and a bipolar orientation $s$ over $G$, consider the problem of identifying $s$ by finding the minimum number of edges such that when orienting them in a particular ...
4
votes
0answers
62 views

size bounds for circuits recognizing graph properties (reachability, cyclicity, …)

I am interested in the following. Let the inputs of the circuit correspond to the arcs of a directed graph. The circuit has to output 1 iff there is a directed path from a given node S to a given node ...
0
votes
0answers
23 views

Bisection Width of a Mesh Topology

What is the bisection width of a q-dimensional mesh topology with one dimension having k nodes, where bisection width splits the network as evenly as possible into two sets (with a difference of at ...
0
votes
0answers
44 views

Total number of spanning trees of a set of graphs with constraint

This is an extension of the question "Total number of spanning trees of a set of graphs". The original problem has been shown to be #P-complete. Now a new constraint is added to the problem. I have ...
2
votes
0answers
118 views

Known algorithms for Graph isomorphism [closed]

What algorithms are known for the graph isomorphism problem? Can those algorithms be related to algorithms for other graph theoretical problems (e.g. subgraph problem, counting graph isomorphisms)?
1
vote
0answers
23 views

Rate of convergence of graph-theoretic quantity to fractional graph-theoretic counterpart

Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ ...
0
votes
1answer
119 views

checking isomorphism between K regular graph

Problem Input is a k regular graph of n vertices and I have to check whether this is isomorphic to another given k regular graph G. This is a restricted version of graph isomorphism in the sense that ...
2
votes
1answer
104 views

State of the art algorithms for community detection in graphs

Is anyone aware of the must read papers to get knowledge of the most recent algorithms and method for community detection in graphs, especially those that represent social networks?
0
votes
0answers
38 views

Number of k-expressions of graph (clique Width)

The clique-width of a graph $G$ is the minimum number of labels needed to construct G by means of the following 4 operations. The Construction of a graph $G$ using the four operations is represented ...
3
votes
0answers
27 views

APx hardness of Multiterminal Cut Problem

In a Multiterminal Cut problem input is a graph G=(V,E) and a set of k terminals T which is a subset of vertex set V. There is a weight w(e) associated with each edge in the graph. The question is to ...
3
votes
2answers
108 views

Graphs whose maximal clique intersection graph has bounded chromatic number

In general, The chromatic number of the clique intersection graph a graph can again be arbitrarily high. For example, take $n$ maximal cliques of size $n$ such that every pair of maximal cliques has ...
2
votes
1answer
246 views

Modifying Hopcroft-Karp algorithm to get approximate bipartite matching

I am trying to find an algorithm to find an $\epsilon$-approximate maximum matching $M_{\epsilon}$ in a bipartite graph in $O(m/\epsilon)$. The partite groups are of equal size, they are $A$ and $B$. ...
4
votes
1answer
160 views

Total number of spanning trees of a set of graphs

Given an undirected graph G with $n$ nodes, we can compute its number of spanning trees in polynomial time using Kirchhoff's matrix-tree theorem. Now consider a more complicated setting, in which each ...
8
votes
2answers
154 views

Understanding graph minor theorem

This question is two-fold, and is mainly reference-oriented: Is there somewhere where the main intuitions for proving graph minor theorem are given, without going too much into the details? I know ...
0
votes
2answers
148 views

Upper bound for number of independent sets

What is the tightest upper bound known for the number of independent sets in a graph?
5
votes
1answer
89 views

Expected length of longest construction path in Barabási–Albert Model

The Barabási-Albert Model is used for constructing scale-free networks using the preferential attachment technique. The essence, as I understand it, is that nodes are incrementally added to a graph by ...
0
votes
4answers
262 views

Finding outer face in plane graph (embedded planar graph)

I have a planar graph, for which I have computed a combinatorial embedding and coordinates in the plane. So all my arcs are now oriented in the plane, respective to their end vertices. Computing a ...
7
votes
2answers
218 views

Enumerating Planar Graphs of Bounded Treewidth

I am looking for references for the following problem: given integers $n$ and $k$, enumerate all non-isomorphic planar graphs on $n$ vertices and treewidth $\leq k$. I'm interested both in theoretical ...