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

learn more… | top users | synonyms (1)

1
vote
1answer
66 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 ...
2
votes
0answers
63 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
42 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 ...
1
vote
0answers
91 views
+50

In domination perfect graphs is MDS certificate for MIDS?

I suspect this is wrong in case it makes sense at all. According to graphclasses: A graph is domination perfect if for every induced subgraph $H$ a minimum dominating set (MDS) has the same ...
4
votes
2answers
315 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. ...
4
votes
0answers
90 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
119 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
151 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
33 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
193 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
181 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$ ...
6
votes
1answer
116 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
109 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
153 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
352 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
57 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
113 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
92 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
49 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
60 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
20 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
107 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
116 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
99 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 ...
2
votes
2answers
99 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
190 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
155 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
149 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
138 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
88 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
255 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
210 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
33 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
73 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
81 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
76 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
88 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
84 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 ...
-1
votes
1answer
55 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): ...
6
votes
0answers
65 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
103 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 ...
4
votes
0answers
120 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
180 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
95 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
99 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 ...