Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
312
questions with no upvoted or accepted answers
4
votes
0answers
118 views
A variant of hitting set: finding a matching to hit all edge sets
In general, the hitting set problem is given a family $\cal S$ of sub-sets, $\{S_1, \cdots, S_h\}$, and a universal set $U = \bigcup_{i\in [1,h]} S_i$. It asks for a minimum set $H \subseteq U$ ...
4
votes
0answers
127 views
Reduce $m$-clause 3SAT to PLANAR-3SAT in $O(m^{2-\varepsilon})$
The classic reduction from 3SAT to PLANAR-3SAT requires a removal of $O(m^2)$ crossings from a rectilinear representation of 3SAT with $m$ clauses. However, the crossing number inequality suggests ...
4
votes
0answers
128 views
Girth of graphs that decompose into two disjoint union of spanning trees
Let $G$ be an $n$-node graph that can be decomposed into two disjoint union of spanning trees. In particular, $G$ has $2n-2$ edges.
It is not hard to show that the girth of $G$ is at most $O(\log n)...
4
votes
0answers
768 views
Optimizing Maximum Weighted Matching (Edmonds Blossom)
Background:
I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java:
https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java
The original Python implementation ...
4
votes
0answers
140 views
Graph Isomorphism Algorithm of Vertex Transistive Graphs and other
What are the best known Graph-Isomorphism algorithms for below graph classes-
1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive.
Are they GI Complete?...
4
votes
0answers
185 views
Graph Isomorphism of Strongly Regular Graph with fixed parameter
$G, H$ are strongly regular graphs with parameter $(n, r, \lambda, \mu)$ where $\lambda$ is constant.
Here,
$n$ is the number of total vertices. Each graph is $r$ regular. Every two adjacent ...
4
votes
0answers
85 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 ...
4
votes
0answers
246 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. ...
4
votes
0answers
369 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 ...
4
votes
0answers
128 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 arcs?...
4
votes
0answers
146 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, ...
4
votes
0answers
328 views
#EXP-Complete problems
Let #EXP be the counting variant of NEXP, in the same way that #P is the counting variant of NP. Are there any known #EXP-complete problems? In particular, has #Succinct Sat (the natural candidate) ...
4
votes
0answers
351 views
How to go from a DAG model to bounded treewidth?
I am cross posting this question from CS.SE since I believe it is research-related question.
Given a Bayesian Network DAG $G$, we can transform it into a junction tree $T_G$ by performing two steps:...
4
votes
0answers
120 views
What is the complexity of decomposing 2k-regular multigraphs into k-stars?
Imagine we have a graph, which is 2k-regular, and we want to decompose it into copies of k-stars. Then we could just at first decompose the graph into 2-factors, orient each of the factors and then we ...
4
votes
0answers
149 views
Vertex Covers whose vertex induced subgraph has an even number of edges and no isolated vertices
Let $G$ be a graph, and let $C_{E,0}$ be the number of those vertex covers of $G$ satisfying both the following properties:
Their corresponding vertex induced subgraph has an even number of edges.
...
4
votes
0answers
434 views
Dynamic shortest path data structure for DAG
Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted.
I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
4
votes
0answers
2k views
Can the Hungarian method be used with real edge weights?
I had a problem where I need to apply bipartite weighted matching on a graph where the edge weights are real (positive and negative). I have looked at several implementations of the Hungarian method ...
4
votes
0answers
93 views
Explicit combinatorial construction minimizing intersection of sets
I'd like to know if anything is known about the following problem:
Suppose we choose positive integer $t$ to be constant. Let $S = \{1,2,\dots,n\}$, where $n$ is sufficiently large. Consider a ...
4
votes
0answers
104 views
Are there any conditions for which ($k$-)apexness is preserved under $Y-\Delta$ transformations?
Lately, something I've been interested in is finding the set of forbidden minors for the apex graphs. One thing I tried to do was to look at the graphs which were known, and try to find a pattern in ...
4
votes
0answers
181 views
Expansion of constant-size sets
My question refers to the expansion of constant size sets of an expander graph.
Suppose we are given an expander graph with Cheeger constant $\alpha$.
What can be said about the edge expansion of sets ...
4
votes
0answers
234 views
Ising Model and Eulerian Subgraphs
Let $\mathcal{X}= \{1,-1\}^n$, $E$ the set of edges and $J$ some real-valued matrix. Van der Waerden's theorem gives constant $c$ and set of edge weights such that
$$\sum_\mathbf{x\in \mathcal{X}} \...
4
votes
0answers
223 views
Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?
I'm wondering if anybody has followed up on Nair/Tetali's correlation decay tree construction for hypergraphs. I didn't find anything relevant in back-citation on google scholar. Interesting question ...
3
votes
0answers
87 views
Isomorphic subforest problem
I recently read that the following problem is NP-Complete:
Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$?
The reference provide was to the textbook “Computers and ...
3
votes
0answers
132 views
Enumerating Minimal (a,b) vertex separators in a DAG
A vertex subset $S \subseteq V$ is an $(a,b)$ separator for nonadjacent vertices $a$ and $b$ if the removal of $S$ from a graph $G$ separates $a$ and $b$ into distinct connected components.
$S$ is a ...
3
votes
0answers
110 views
Earliest forbidden subgraph characterisation
I wonder, what was the first non-trivial graph class for which there was a forbidden (induced) subgraph characterisation ?
Of course, bipartite graph is one example but I am considering it as trivial ...
3
votes
0answers
74 views
Embed graph in $\ell_2$ space so that edge and non-edge distances are separated by a constant factor
Suppose I have an undirected unweighted graph $G = (V,E)$. Is there a way to compute points $x_v \in \mathbb{R}^d$ for each vertex $v \in V$ such that $||x_v - x_u|| = 1$ whenever $(u,v) \in E$ and $ |...
3
votes
0answers
50 views
Problem of determining if a $4$ connected graph has $k$ Hamiltonian cycles
Definition: Define the $k$-HamiltonianCycles problem as the decision problem that asks if a given graph has at least $k$ distinct Hamiltonian cycles.
Question: Is there some constant $k$ so that the $...
3
votes
0answers
90 views
Counting quotient graphs, but not exactly
All graphs considered will be directed graphs $G=(V,E)$, with $E \subseteq V \times V$ (so possibly with self-loops). For $k \in \mathbb{N}_{\geq 1}$, I will write $[k]$ the set $\{1,\ldots,k\}$. A $k$...
3
votes
0answers
280 views
Generating a random connected bipartite graph
A (n, m, k)-bipartite graph is a bipartite graphs with:
independent sets of size $\{n, m\}$
a total of $k \geq n+m-1$ edges
We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...
3
votes
0answers
82 views
PTIME or NP-Hardness of stochastic objective function
I will begin by linking a previous post where I asked a general question for a stochastic setting which I describe below. It turns out that my "proof" for a restricted case had a mistake and there is ...
3
votes
0answers
90 views
Showing hardness of maximizing stochastic objective function over graph
Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$.
The challenge is to ...
3
votes
0answers
207 views
Hardness of Approximation for minimum path cover in an undirected graph?
Given an undirected graph $G = (V,E)$, a path cover is a set of disjoint paths such that every vertex $v\in V$ belongs to exactly one path. The minimum path cover problem consists of finding a path ...
3
votes
0answers
583 views
Eigenvalues of adjacency matrix of a connected bipartite graph
Let $G=(V,E)$ is a connected d-regular bipartite graph with the same number of vertices on both sides of the bipartition. It's known that that the largest eigenvalue of its adjacency matrix would be d,...
3
votes
0answers
135 views
Maximize number of edges covered by an independent set of vertices
Smallest vertex cover which is also an independent set asks about finding an independent set that covers all edges. This problem is known as the independent vertex cover problem and is equivalent to ...
3
votes
0answers
445 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 ...
3
votes
0answers
104 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
0answers
104 views
How many neighbors does a vertex has which are closest to a source vertex in random regular graphs?
Let $G=(V,E)$ be an undirected, random $r$-regular graph.
Let $s,t\in V$, and denote by $N(v)=\{u\in V\mid (u,v)\in E\}$ the neighborhood of $v$.
I'm looking for the distribution of the number of ...
3
votes
0answers
179 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 ...
3
votes
0answers
434 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 ...
asked Dec 29 '14 at 20:43
Mohammad Al-Turkistany
19.5k4 gold badges51 silver badges134 bronze badges
3
votes
0answers
59 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
0answers
104 views
Online bridge and nonbridge counting (identification)
I was wondering if there is any efficient (possibly armortized poly-logarithmic) online algorithm which supports counting (identification) of bridges- and non-bridges online, i.e. during a sequence of ...
3
votes
0answers
379 views
Finding modular decomposition of graph
I am trying to learn how to find modular decomposition of graph using the method given in the paper Simpler Linear-Time Modular Decomposition via Recursive Factorizing Permutations.
I am unable to ...
3
votes
0answers
229 views
Bipartite small-world networks
The Watts-Strogatz model describes a mechanism of generating small-world networks.
The idea is to start from a ring network in which each node is connected a fixed number of its closest neighbors. ...
3
votes
0answers
251 views
Independent Sets that are Odd Covers
I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
3
votes
0answers
146 views
Bound on a graph diameter, considering the minimal vertex degree
Let $G$ be a connected (strongly connected) graph (digraph).
Assume that the minimal vertex degree (in/out degrees) of the graph is $\delta$ (are $\delta^-,\delta^+$).
What is the maximal diameter ...
3
votes
0answers
165 views
Is there any equivalent for Bondy-Chvátal theorem for directed graphs?
Bondy-Chvátal theorem cannot be applied for directed graphs, is there any equivalent theorem that can be applied for them?
3
votes
0answers
108 views
Intractability of restricted decomposition of connected bridgeless cubic graphs
A 2-factor of graph $G(V, E)$ is a set of vertex-disjoint cycles that cover $V$. It is known that every connected bridgeless cubic graph contains a 2-factor (and a disjoint perfect matching). I'm ...
asked Feb 11 '14 at 16:32
Mohammad Al-Turkistany
19.5k4 gold badges51 silver badges134 bronze badges
3
votes
0answers
115 views
Concentration of Stationary Distribution on Random Directed Graphs
We consider a random directed graph with fixed out-degree $d$. Each vertex chooses $d$ neighbors with replacement, uniformly and independently. Self-loops and multiple arcs are allowed in this model. ...
3
votes
0answers
284 views
Generating random graphs using the preferential attachment model with degree bounds
I am interested to know the structure of random graphs generated by the preferential attachment model with degree bounds. Specifically, when a vertex is chosen with a probability proportional to its ...
3
votes
0answers
2k views
DAG partitioning for parallel computing
Consider a set of processes ($P=\{p_1, p_2,\dots, p_n \}$) and their data dependencies. Each process $p_i$ has an execution runtime which is denoted by $d_i$. We are interested to parallelize these ...
