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

learn more… | top users | synonyms (1)

0
votes
0answers
30 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 ...
-1
votes
0answers
12 views

determing the max flow with only edge capacities from n/w with additional vertex capacities?

Let ((V, E); s, t; c) be an extended flow network where not only edge capacities, but also vertex capacities are constrained, i. e., c : E ∪ V → R^ + 0 and a flow f : E → R^ + 0 must satisfy, in ...
2
votes
0answers
80 views

Known algorithms for Graph isomorphism [on hold]

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
20 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$ ...
-4
votes
0answers
26 views

Finding a maximum bipartite matching in O((|A| + |B|)^1.5) [closed]

I aim to solve the following puzzler I recently read: A toymaker is faced with a group of $|A|$ buyers for their stock of $|B|$ distinct toys. Each buyer can buy up to 3 toys if available for buying. ...
-1
votes
0answers
62 views

max spanning tree with conditional weights

Consider the max spanning tree problem in which for any $e \in G$ there is a fixed $f(e)$. Suppose I have a graph with conditional values of the following form: $$ f(e) = \begin{cases} v_1 & ...
0
votes
1answer
105 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 ...
0
votes
0answers
56 views

Assign undirected edges in a mixed graph to make graph cyclic/acyclic [migrated]

What is the complexity of the following problem? Given a mixed (some edges directed, some undirected) graph, assign a direction to all the undirected edges to make the graph cyclic. What about to ...
2
votes
1answer
80 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
35 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
25 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 ...
2
votes
1answer
65 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 ...
0
votes
1answer
53 views

stable marriage breaking ties, how to?

I have found the following algorithm proposed by Halldorsson which is a randomized algorithm: ...
2
votes
1answer
151 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$. ...
3
votes
1answer
137 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 ...
7
votes
2answers
136 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
124 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
86 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
234 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
207 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 ...
0
votes
0answers
32 views

Mapping load balancing to graph theory

I'm looking for algorithms that transform/reduce dynamic load balancing problem in a cluster to a flow problem. I have n machines each of them constantly performing a job, suppose a machine is ...
3
votes
0answers
69 views

Definition of Clique width of graph

The clique width of graph $G$ is defined as minimum number of labels required to construct $G$ by using four operations. I would like to know why the name clique width is given to this definition. ...
1
vote
0answers
76 views

Characterization of the Set of all s-t-Min-Cut Sets

I would like to know how to answer the following problem: Input: A family of sets $S$ over a universe $U$. Question: Is there a directed flow network $N$ with an edge labeling ...
7
votes
1answer
52 views

Minimal polynomial reduction of dominating set to max clique

Let $G$ be a simple undirected graph. Recall that $S \subseteq V(G)$ is a dominating set of $G$ if every vertex of $v \in V(G) \setminus S$ has a neighbour in $S.$ It is well known that it is NP ...
0
votes
1answer
86 views

Graph theory: definiton of the crown of a graph

I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand: A crown of a ...
4
votes
1answer
79 views

How to Quantify Entropy in a Data Set

I'm currently creating a program in Java to analysis the pathological cases of Quicksort. Namely, the transition of complexity from O(n^2) to O(nlogn) as a data set gets less ordered. Since Quicksort ...
0
votes
1answer
42 views

Assign each biclique to a distinct left

Given a minimum biclique edge cover, is it always possible to assign each biclique to a distinct left node (which it contains)? ie one such assignment for this graph (from wikipedia): ...
1
vote
0answers
29 views

Common subgraph isomorphism with K vertex [migrated]

I'm looking for subgraph isomorphism of at least K vertex between Graph A and B. I only can come up with the dumbest algorithm, which is: Compute all combination of vertices with length K of Graph ...
6
votes
0answers
63 views

Approximating a max-cut's intersection with other cuts

For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any ...
9
votes
0answers
97 views

Advances towards proving the Held-Karp conjecture for TSP

I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture. The Held-Karp relaxation is conjectured to have an integrality gap of ...
-1
votes
0answers
82 views

NP-hardness of the following problem

A subgraph $H \subseteq G$ is said to be 'valid' if all the paths in $H$ satisfy the property $x$. The property $x$ is closed under taking sub-paths. Given a directed graph $G$ and a set of all ...
4
votes
0answers
117 views

The largest connected component of a random subgraph

Let a graph on $|V|$ vertices and $|E|$ edges. We randomly sample $s= c \cdot \frac{|V|}{{d_{\text{av}}}}$ vertices, without replacement, where $d_{\text{av}}$ is the average degree of $G$ and $c$ is ...
8
votes
1answer
178 views

A curious asymmetry in good characterizations

There are quite a few theorems, mostly in graph theory and combinatorial optimization, that are often referred to as good characterizations. They typically put a property in $NP\cap co-NP$, by showing ...
-1
votes
2answers
84 views

Steiner trees - the added edges and vertices [closed]

I have been reading up on Steiner Tree. I am a beginner. The explanation I find is this : The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of ...
-2
votes
1answer
95 views

Connecting partial paths to form a hamiltonian cycle [closed]

For an undirected graph that consists of partial paths such that each vertex is a part of one of those paths and that there are edges between all the paths, is there an efficient algorithm to connect ...
0
votes
0answers
92 views

Best Hamiltonian Cycle Problem solver

What is the best Hamiltonian Cycle Problem (HCP) solvers available in the market? Googling so far shows that there is one created by Flinders University that can solve at most 5000 node instances. I ...
4
votes
0answers
119 views

Can we decide Red-blue cut problem in polynomial time?

Given a directed graph whose arcs are coloured red and blue and integers $r$ and $b$, can we decide in polynomial time whether the digraph has a cut with at most $r$ red arcs and at most $b$ blue ...
2
votes
2answers
97 views

Graph-theoretic properties of the Wiener index

The Wiener index of a graph is the sum of the lengths of the shortest paths between all pairs of its vertices. Are there useful graph-theoretic properties of this index?
5
votes
0answers
119 views

The minimum entropy of a proper coloring of a graph

The chromatic number $\chi(G)$ of an undirected graph $G$ is the minimum number of colors in a proper coloring of the vertices of $G$ (where a proper coloring uses different colors for two vertices ...
4
votes
0answers
114 views

Recognition problem of cycle permutation graphs

A cycle permutation graph is a cubic graph composed from two $n$-cycles each labeled $1, 2,..., n$, with additional edges connecting vertex $i$ in the first cycle to vertex $\pi(i)$ in the second, ...
8
votes
0answers
289 views

Is it possible to solve perfect matching in linear time

As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft. Is it possible to solve perfect matching problem in linear time for given ...
2
votes
1answer
368 views

Is DAG isomorphism NP-C

Given two directed acyclic graphs $G_1$ and $G_2$, is it NP-Complete to find a one-to-one mapping $f:V(G_1) \rightarrow V(G_2)$ such that $(v_i,v_j) \in D(G_1)$ if and only if $(f(v_i),f(v_j)) \in ...
5
votes
0answers
116 views

lower bound for difference between max cut and min cut

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e. ...
4
votes
0answers
160 views

Is this graph polynomial known? Can it be efficiently computed?

Consider a connected simple graph $G$ with $n$ vertices and $m$ edges. View each edge $\ell$ as a transposition $t_{\ell}$ acting on the set of vertices. [To be more explicit, given an edge $\ell$ ...
-2
votes
1answer
133 views

Finding cliques in weighted graph

We have given a weighted graph $G=\{V,E\}$, where $V=\{v_1, v_2,...,v_n\}$, and for all $i,j$, the weight of edges $w(v_i, v_j)\in (0,W)$. And we have also given a weight threshold s $w$ (where ...
2
votes
1answer
146 views

Planar separator theorem and tree decomposition

The Wikipedia article about the Planar Separator Theorem states that it is possible to use a hierarchy of separators to construct a tree decomposition for a planar graph and moreover provides an ...
6
votes
2answers
339 views

Complexity of finding even cuts for a graph

Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V_a$ and $V_b$ such that every vertex in ...
6
votes
0answers
85 views

General Results for Complicated Constraint Satisfaction Problem

Consider the following problem: on a finite two-dimensional grid (say the grid points are vertices of a graph), I need to color the vertices in such a way to satisfy the existence and nonexistence of ...
2
votes
1answer
70 views

When polynomial GI implies polynomial (edge) colored GI?

Crossposted from MO. (edge) colored graph isomorphism is GI which preserves the colors (of edges if it is edge colored). There are several reductions using transformations/gadgets of (edge) colored ...
5
votes
1answer
74 views

Is there an extension to the stable roommates problem with multiple roommates per room?

The stable roommates problem presents a set of N two-person rooms and 2N would-be roommates with preferences over each other, and asks for a stable allocation of roommates to rooms (and, really, to ...