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

learn more… | top users | synonyms (1)

6
votes
1answer
154 views

Problem of graph bi-partition (related to graph isomorphism)

I am considering the following problem: Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$ Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to ...
-4
votes
0answers
39 views

non-Hamiltonian graphs [on hold]

What is the relation between the set of non-Hamiltonian graphs, all of whose members are presumably not known, and the dynamic linear programming and factorial solutions to the TSP in general graphs? ...
0
votes
0answers
44 views

Is there any digraph data set that gives all directed graphs satisfying certain requirements? [closed]

I'm looking for a digraph dataset that can return all directed graphs satisfying certain requirements. Following are some examples: All tournament with 12 vertices; All connected digraphs with 10 ...
0
votes
1answer
65 views

Max-sum graph-partition for maximizing intra-edge weights?

I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results. Input: A graph G with negative or ...
-4
votes
0answers
35 views

How similar are two DFAs? -not just binary equivalence- [on hold]

I'm looking for a metric, a measure, to compute similarity (or distance) between two DFAs. I think it should considers alphabet, transitions, states and global (or local) structure. Have you any ...
7
votes
1answer
216 views

Is the proceedings of WG 2015 published?

Within theoretical computer science, the "Workshop on Graph-Theoretic Concepts in Computer Science (WG)" is one of the main specialized venues for publication of papers dealing with graph theory. It's ...
1
vote
0answers
47 views

About complexity of recovering or learning Bayesian networks

Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...
4
votes
1answer
214 views

Enumerating all (super)orientations of an undirected graph

Given an undirected graph $G$, an orientation of $G$ is a directed graph obtained by assigning every edge a direction, a superorientation of $G$ is a directed graph obtained by orienting every edge in ...
4
votes
0answers
68 views

Graph partition with weighted vertices and edges

I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from ...
7
votes
0answers
108 views

Kleinberg Rubinfeld Short Paths in Expander Graphs for Hypergraphs

In the 1996 paper "Short Paths in Expander Graphs" by Kleinberg and Rubinfeld, the authors show a randomized polynomial-time algorithm for finding an embedding of a graph $H$ into a graph $G$, if $G$ ...
5
votes
0answers
134 views

Machine learning algorithms on hypergrap models

Graphical models are a very useful tool with many applications, whereby a joint distribution of a set of random variables is modeled using only pairwise dependencies between the variables, and two ...
8
votes
1answer
116 views

Tree-decomposition with clique interfaces

Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that: For every edge $\{v_1,v_2\} \in E$, ...
2
votes
1answer
111 views

Partition into triangles in a 3-partite graphe

Let $G=(X\cup Y\cup Z,E)$ be a 3-partite graph such that: $|X|=|Y|=|Z|=q$. $2 \leq d(v) \leq 6$ for all $v \in X\cup Y\cup Z$, where $d(v)$ is the degree of v. $\sum_{x \in X} d(x)=\sum_{y \in ...
6
votes
1answer
106 views

What is the complexity of vertex cover on k-partite graphs?

Given a k-partite graph which is already partitioned into k parts, what is the complexity of finding a vertex cover of minimum size? I guess that it's NP-hard, but couldn't yet prove it or find ...
-5
votes
1answer
87 views

What is the complexity of the fastest method of k-coloring any graph? [closed]

I heard brute-force is the only method. Is there any other way? Is there a way to prove that the complexity cannot be exponential?
8
votes
1answer
143 views

Complexity of the edge-disjoint cycle covers

I am interested in decompositions of a directed graph $G=(V,E)$ into non-intersecting Eulerian subgraphs $G_i=(V_i, E_i)$. I want to find the decomposition that covers the largest number of edges. I ...
4
votes
0answers
265 views

Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism

Given two graphs $G, H$ (each has $n$ vertices). We, split $G$ into subgraphs $G_1, G_2... G_x$ (total $x$ vertex set). Similarly,assume $H$ has subgraphs $H_1, H_2... H_x$ (total $x$ vertex set). ...
2
votes
1answer
90 views

Converting a pictorial representation of a directed graph to a adjacency matrix

I am not sure if there is a better forum to ask this question, so I will try here. Consider an image, say in .jpeg format, representing a directed graph, with nodes. Is there an algorithm, be it a ...
0
votes
0answers
20 views

Optimization of process duration when multiple processes interact

When you have a process composed of multiple steps (e.g., a recipe), where: each step S has a specific duration d(S) steps ...
10
votes
1answer
188 views

Complexity of digraph homomorphism to an oriented cycle

Given a fixed directed graph (digraph) $D$, the $D$-COLORING decision problem asks whether an input digraph $G$ has a homomorphism to $D$. (A homomorphism of $G$ to $D$ is a mapping $f$ of $V(G)$ to ...
5
votes
0answers
228 views

Maximizing the number of selected edges with opposing requirements

Consider the following problem: Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$. Output: a subset of vertices $W$ of size $k$ which maximizes the ...
9
votes
0answers
306 views

Upper Bound on Number of $n \times n$ Boolean matrices of Boolean rank at most $k$

An $n \times n$ Boolean matrix $B$ has Boolean rank $k$ if there exist matrices $L \in \{0,1\}^{n \times k}$ and $R \in \{0,1\}^{k \times n}$, s.t. $B = L \circ R$. Here $\circ$ denotes the Boolean ...
6
votes
2answers
222 views

Local Graph Isomorphism to construct Global Graph Isomorphism

Does there exist a Graph Isomorphism Algorithm that uses Local Isomorphism to construct a Global Isomorphism? For example, two graphs are given, say, $H, G$. it is asked to determine whether $G\simeq ...
8
votes
1answer
140 views

Classes of graphs with superconstant treewidth

There are several interesting classes of graphs with bounded treewidth. For instance, trees (treewidth 1), series parallel graphs (treewidth 2), outerplanar graphs (treewidth 2), $k$-outerplanar ...
1
vote
1answer
126 views

Graph class with easy chromatic number, but NP-hard coloring

Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard? Without any further restriction the answer ...
7
votes
0answers
154 views

Is there a special name for the following type of graphs?

Weighted graphs such that if $x$ and $y$ are nodes in the graph, and $p$ and $p'$ are two paths in the graph between $x$ and $y$, then the weight of $p$ equals the weight of $p'$.
5
votes
2answers
164 views

The relationship between degree of vertex and size of dominating set

I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has ...
0
votes
0answers
86 views

How to efficiently generate a random 0-1 matrix of a given rank

How to efficiently generate a random $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$?
7
votes
1answer
165 views

Complexity of a graph-rewriting problem

I recently came across the following problem which seems to fall in the context of graph rewriting problems: Input: A graph $G=(V,E)$ with maximum degree 3, an edge $e_0 \in E$ and pairs of graphs ...
5
votes
1answer
186 views

Canonical way of coloring graphs (individualization) for isomorphism purpose

Stefan Kratsch and Pascal Schweitzer in their paper Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs give a characterization of graphs on which Graph Isomorphism ...
20
votes
1answer
253 views

Minor closed properties that are explicitly MSO expressible

Below, MSO denotes the monadic second order logic of graphs with vertex-set and edge-set quantifications. Let $\mathcal{F}$ be a minor closed family of graphs. It follows from Robertson and ...
1
vote
0answers
48 views

Optimal distribution of integer edge weights

I am not sure whether the following problem has been studied. Any help would be greatly appreciated. I have $L$ sets, $S_1, S_2,...,S_L$, each of $n$ elements, taken from a universe of $N$ elements. ...
3
votes
1answer
126 views

Does such model exists?

I have a problem on distributed graph, with the following model: 1. There is a Global Graph $G=(V,E)$ 2. There are $k$ computers. 3. Each computer $1 \leq i \leq k$ knows ALL the nodes of the ...
3
votes
2answers
177 views

Generate connected induced subgraphs as the satisfying assignments to a SAT instance

I want a SAT instance (in CNF) whose set of satisfying assignments are the connected induced subgraphs of a given input graph. A general solution would be helpful, but I really only need this when the ...
0
votes
1answer
97 views

Fractional but not integer multi-commodity minimum cost flow

I'm searching for an example digraph for the multi-commodity minimum cost flow problem with integer demand. There shouldn't be an integer but fractional optimal solution. I found here a similar ...
0
votes
0answers
81 views

Find max weight induced graph in a multipartite graph with one vertex from each part

Consider the follow problem: Input: $G=(V,E)$, a weighted $k$-partite graph with $n$ vertices. Output: $U \subseteq V$, one vertex from each part, maximizing the total weight of the induced graph ...
-5
votes
1answer
170 views

Is graph isomorphism still open for bounded clique width or bounded rank width? 2015 paper claims it is polynomial [closed]

To my knowledge, graph isomorphism for graphs with bounded clique width or bounded rank width is open. 2015 arxiv paper claims it is polynomial: Isomorphism Testing for Graphs of Bounded Rank Width ...
4
votes
2answers
200 views

Partition graph into 2 or more claw-free subgraphs

Is it NP-hard to partition the vertex set of graph G into k subsets so that they induce k claw-free subgraphs of G?
7
votes
1answer
658 views

Probability of two vertices being connected by some path in a random directed graph

Define $G(n, p)$ as a random directed graph ($n$ vertices; we put edge between two vertices with probability $p$). What are the known results for the following problem: Fix two vertices $v$ and ...
3
votes
0answers
78 views

Embedding distortion under group quotient

The high level question is as follows: Suppose some group (here assumed to be a vector space of $\mathbf{F}_2^n$) has a low-distortion embedding into $l_1$. Under what condition does the quotient of ...
3
votes
5answers
382 views

How to constrain a finite automaton (NFA and DFA) to a tree?

I have a finite automaton by the standard model Hopcroft & Ullman define: $$ M = (Q, \Sigma, \delta, q_0, F) $$ Where $\delta$ is the transition function mapping $Q \times \Sigma \mapsto Q$, such ...
1
vote
1answer
86 views

Is the topsort from “Structuring Depth-First Search Algorithms” guaranteed to be (reverse) stable?

In "Structuring Depth-First Search Algorithms in Haskell", implemented in Data.Graph in the Haskell standard library, an algorithm for topologically sorting graphs is given: ...
1
vote
0answers
116 views

Vertices adjacent to Exterior region of a Planar Graph(Algorithm)

Problem: I am looking for an algorithm which finds all vertices that are adjacent to exterior region of a planar graph(For a planar graph, any region=face can be considered as the exterior region ...
2
votes
2answers
199 views

Submatrix of small rank

Let $G=(V,E)$ be a graph with adjacency matrix $M=(m_{ij};i,j \in V )$ over $\mathbb{F}_2$ and $k \in \mathbb{Z^+}$. How can we find in polynomial time a subset $A \subseteq V$ such that The rank ...
6
votes
1answer
139 views

Graph that maximizes minimum hitting time?

Let $G$ be some connected bidirectional (or undirected) graph. We define a random walk as a walk that begins at a vertex chosen uniformly at random, and at each step proceeds to one of its current ...
15
votes
0answers
216 views

When does adding edges decrease the cover time of a graph?

When first learning about random walks on a graph $G$, one may have an intuitive feeling that adding edges to $G$ will decrease its cover time $C(G)$. However, this is not the case. The path graph ...
-1
votes
1answer
63 views

Reconstructing a 2D lattice graph from an unordered adjacency list

Is there any kind of algorithm that can map a set of points and their unordered adjacent neighbours to a 2D lattice graph that would then be addressable using X, Y coordinates? For example, given the ...
1
vote
0answers
43 views

Multicuts (or multiway cuts) for 3 Terminals of Minimum Capacity

For each fixed $k \geq 3$, the following well-known problem is NP-complete. k-Multicut (aka "Multiway Cut", "k-Way Cut", "Multicut") Input: $(N,l)$ where $N=(V,E,T,c)$ is an undirected $k$-terminal ...
3
votes
1answer
193 views

Approximation algorithms for the maximum $2$-independence set problem

I am interested in approximating the maximum $2$-independent set problem in arbitrary graphs. In a graph $G$ a set $I$ of vertices is called $2$-independent if the distance between any two distinct ...
15
votes
2answers
431 views

Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

The $k$-cycle problem is as follows: Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges. Question: Does there exist a (proper) $k$-cycle in $G$? Background: For any ...