Questions tagged [graph-theory]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
11 views

Has multiobjective prize collecting steiner tree or TSP been studied?

Suppose we have a graph $G$ a root $r$ and each node $v$ has some amount of $c_{v,i}$ of each resource $i$. I connect a set of nodes that maximizes the minimum amount of any resource using at most a ...
0 votes
0 answers
34 views

Induced subgraphs with interface

I am interested in graphs with interfaces, i.e. graphs with distinguished vertices that can be plugged into a larger context. I call "island" of a graph $G$ a subgraph $I$ such that there ...
0 votes
0 answers
40 views

On a modular inverse graph construction

Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
1 vote
0 answers
61 views

Is there any augmenting graph algorithm available for finding maximum independent set problem in K1,4-free graph in polynomial time

$K_{1,4}$-free graph is the graph with no induced subgraph of the form $K_{1,4}$ An augmenting graph $H$ for $S$ (which is an independent set) is an induced bipartite subgraph of $G$, where $H = (B, ...
32 votes
5 answers
1k views

Maximal classes for which largest independent set can be found in polynomial time?

The ISGCI lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes. I would like to compile ...
1 vote
1 answer
170 views

Is (Restricted) Bigraph Isomorphism Weaker than Graph Isomorphism?

I am investigating a paper from Dominik Grezlak and and Uwe Aßmann: “A Canonical String Encoding for Pure Bigraphs.” On page 2, they define the notion of a bigraph, which is roughly a forest and ...
0 votes
1 answer
79 views

Polynomial time algorihtms for two variants of the decision version of longest walk problem

I want to know if the following variants of the longest path problem over directed graphs have polynomial time algorithm. As I understand it, the longest path problem doesn't allow repetition of edges....
1 vote
1 answer
60 views

Shorter than target vector path algorithm

Consider a generalisation of the shortest path problem on directed graphs with weights in $\mathbb{Q}^k$. Formally, the input is a graph, a source state $s$, a target state $t$, and an objective ...
-1 votes
2 answers
188 views

Bottom up TSP solution?

I'm not sure if this is something new or if I'm just not getting previous efforts. TSP can be thought of as a list of weighted links and nodes. If one takes the Nearest Neighbor (NN) of every node and ...
1 vote
1 answer
116 views

Tractability of computing generalized hypertreewidth on bounded arity hypergraphs

Generalized hypertreewidth is a generalization of treewidth to hypergraphs. Unlike treewidth, it is not tractable, for a fixed width $k \in \mathbb{N}$, given a hypergraph $H$, to determine if $H$ has ...
0 votes
0 answers
116 views

Given $a_i$ -$r$ paths $P_i$ in a planar graph construct a tree spanning $a_i$ such that each root to leaf path intersects few $P_i$

Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and edge disjoint $a_i$-$r$ paths $P_i$ for each $i$ in a planar graph $G$. I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ ...
0 votes
1 answer
53 views

Question about claw-free graphs

Let $G$ be a claw-free graph, and let $x,y,z,u$ be distinct vertices of $G$. Is the following possible in $G$ ? There are three induced paths through $u$: between $y$ and $z$ (i.e., $y \...
1 vote
3 answers
557 views

Minimum number of triangles required to cover a complete graph?

Let $K_n$ be a complete graph, I am interested in knowing the minimum number of triangles required to get a edge cover of $K_n$. In case there is no closed-form solution to this problem, then I would ...
0 votes
0 answers
63 views

Is every 4-claw-free graph a bounded degree graph?

I am looking of some graph properties of 4-claw free graph, where neighborhood of every vertex has independent set of size at most 3. As per my observations, this type of independent set size ...
2 votes
2 answers
169 views

property of minimal triangulations

A graph is chordal if every cycle on four or more vertices contains a chord i.e. an edge between non-adjacent vertices of the cycle. A triangulation (or chordalization) of a graph $G=(V,E)$ is the ...
2 votes
1 answer
299 views

A non-trivial combinatorial optimization

So I stumble over this problem in which I couldn't find anything similar in the literature. I am not even sure if it is NP-hard or solvable in polynomial time. Any thought or suggestion would be ...
0 votes
0 answers
131 views

Error in TAOCP 4a on the bipartite graph constructed from a hypergraph

The first sentence on page 33 of Donald Knuth's The Art of Computer Programming (TAOCP) Vol. 4a reads: Furthermore, a hypergraph is equivalent to a bipartite graph with vertex set $V \cup E$ and ...
3 votes
1 answer
74 views

What is the fastest algorithm for computing exact network reliability?

In the network reliability problem, we are given an undirected graph $G$ on $n$ vertices and a parameter $p\in (0,1)$, and are tasked with determining the probability that $G$ becomes disconnected (i....
1 vote
0 answers
122 views

Upper bound on the number of maximal paths in rooted intransitive DAGs

Let $D(V, A)$ be a DAG. Definition 0: We name a path between two nodes $i$ and $j$ as an $i$-$j$-path. Definition 1: Let $p$ be a path, we call $|p|$ the path length, representing the number of arcs ...
0 votes
1 answer
169 views

Finding the shortest cycle containing a vertex in a graph

Given a connected undirected graph with edges $E$ and verticies $V$ and a vertex $v \in V$, find the length of the shortest cycle containing $v$. The best I could do is $O(|E|*deg(v))$, by trying to ...
3 votes
2 answers
164 views

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes. Does this have a constant approximation? ($p,k$ and the graph are all part of the ...
5 votes
0 answers
126 views

What is the smallest graph of treewidth $k$ having less edges than the $(k+1)$-clique?

Treewidth is a graph parameter measuring how close a graph is to being a tree. I am interested in what is the minimal number of edges required for a graph to have treewidth $k$. A natural family of ...
8 votes
1 answer
2k views

How bad can the greedy coloring (list color) for the c-chromatic number of graph be?

c-chromatic number is defined in the paper Partitions of graphs into cographs. It asks for the minimum number of colors used to color vertices such that each color class is a cograph. Cograph is a P4-...
0 votes
0 answers
47 views

Is hypergraph reachability definable in MSO?

Let $(A,E)$ be a directed 2-uniform hypergraph and $E$ the corresponding binary relation such that $(X,Y) \in E$ iff there is a hyperedge from $X$ to $Y$. We say that there is a path from $X_1$ to $...
1 vote
1 answer
137 views

Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths

I am working on a problem involving partitioning a directed acyclic graph into distinct multiple paths, each with a maximum length constraint. The goal is to minimize the number of paths (this should ...
7 votes
1 answer
561 views

Connectivity of a random regular graph of degree $d$

An Erdős–Rényi graph over $n$ vertices and average degree $d$ is not connected w.h.p. iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be ...
2 votes
1 answer
197 views

Are there any implementations of a graph crossing algorithm?

This is much more focused version of this question: Are there good implementations for easy subclasses of NP-hard graph problems Computing the graph-crossing number $cr(G)$ for a simple graph is ...
3 votes
0 answers
99 views

maximum independent set in graphs with small number of edges

For the classic maximum independent set problem, a hardness of approximation result of $n^{1-\varepsilon}$ is known by [Hastad, 1996] assuming $\textsf{NP} \not \subseteq \textsf{ZPP}$, where $n$ is ...
5 votes
0 answers
56 views

How to prove that all pairwise independent hashing circuits are superconcentrators?

It is mentioned in Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates, A. Gal et al. that "it is also not hard to show that (pairwise-independent) ...
7 votes
1 answer
217 views

Counting the different subsets of nodes seen when iterating a subset through a directed graph

For a given directed graph $G = (V, E)$ (possibly with loops), and some $S\subseteq V$ define the operation $G(S) = \{ v\mid (u,v)\in E\text{ for some } u\in S \}$. Now consider the infinite sequence $...
1 vote
3 answers
109 views

Stable/Robust Traveling Salesman Approximation Methods

I was wondering if there are TSP approximations that are "stable". More specifically, consider the set $G = x_1, ..., x_n$ and the set $G^* = G \cup x_{n+1}$, where $x_i$ are points in $R^d$....
0 votes
0 answers
17 views

Any value in a formula that calculates (not look up) the 'order' of a 'Independent Edge Set' OR a 'I.E.S.' given an 'order' on complete graphs?

Any value or interest in a formula that calculates (not look up) the 'integer order' of a given 'Independent Edge Set' OR given an 'Independent Set' calculates the 'integer order' on Complete Graphs? ...
5 votes
1 answer
488 views

Can Lexicographic BFS be implemented in logspace?

Input: Given graph $G=(V,E)$ with vertices labeled in some order Output: Change the labeling of vertices such that the labeling starts $v_1$ as $u_1$. Next, label the neighbors of $v_1$ as $u_2,u_3,...
-1 votes
1 answer
79 views

Representation of binary strings by graphs and hypergraphs

Let $\Sigma$ be the set $\{ 0, 1 \}$, then the set of all finite binary strings of length $n$ is written as $\Sigma^{\star}_{n}$. Question: Which further ways of representing binary strings of length $...
4 votes
0 answers
77 views

Name for a cyclic path in a graph that visits every vertex while minimizing the maximum number of times a given vertex is revisited?

Me and my colleague are interested in whether anyone has looked into a generalization of Hamiltonian cycles where vertices can be revisited, but we want to minimize the maximum number of times a given ...
1 vote
0 answers
260 views

Graph partitioning to minimize sum of intra-partition edge weights

I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total ...
1 vote
1 answer
628 views

Generate TSP instances with known optimal

Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value? The idea is to be able to generating arbitrary large instances with known optimal value,...
0 votes
1 answer
76 views

A variation of the longest path problem

What about finding a path of maximum length in a given graph which may contain cycles, with the constraint that a vertex (or an edge) can be visited at most X (say 2 or 3) times ? EDIT: X would be ...
0 votes
0 answers
66 views

How to reduce a code down to its configuration

I have built a system where from atomic information of a UI code I could generate a framework specific code. Here is the concept https://github.com/imvetri/ui-editor. For example, the user of this ...
1 vote
0 answers
90 views

Generalization of the Hamiltonian path problem on Grid Graphs

Fix a cost to each of these actions: move up, move down, move left, move right. I.e. fix some function $f: \{\text{move up, move down, move left, move right}\} \to \mathbb N$. Define the following ...
2 votes
4 answers
6k views

Complexity of greedy coloring

I was looking at some heuristics for coloring and found this book on Google books: Graph Colorings By Marek Kubale They describe the Greedy algorithm as follows: ...
0 votes
0 answers
84 views

5-color graph and minor

We have a 5-color graph G without 5-clique. The question is: is there a minor H of G that is a 5-clique? Here the minor definition. With "5-color graph G" I mean $\chi (G)=5$.
2 votes
1 answer
69 views

Upper Bound for distance-two chromatic number in terms of maximum degree

Let us consider simple,finite, undirected graphs. A distance-two colouring of a graph $G$ is a function $f:V(G)\to\{1,2,\dots\}$ such that $f(u)\neq f(v)$ whenever $dist_G(u,v)\leq 2$. A distance-two ...
1 vote
0 answers
33 views

Application LCL definition to vertex coloration

I'm reading the article "What can be computed locally?" by Naor & Stockmeyer and I struggle to understand the definition of an LCL they gave. Here is an extract: (page 2) An Locally ...
4 votes
1 answer
88 views

Independent set queries with preprocessing

Suppose we have a sparse undirected graph $G = (V, E)$ with $|E| = O(|V|)$, and we want to process it and then answer queries of the following type: given a set $A$, is it an independent set in the ...
1 vote
1 answer
52 views

What is known about the complexity of Network Diversion?

In the Network Diversion problem, we are given an undirected graph $G$ on $n$ vertices, with specified nodes $s$ and $t$ and specified edge $e$, and a positive integer $k$, and are tasked with ...
0 votes
1 answer
205 views

Transitive reduction not provably minimal [closed]

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 ...
0 votes
1 answer
76 views

What's the exact complexity of a DFS if we revisit nodes?

By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll ...
3 votes
1 answer
139 views

Approximative counting of matchings in a graph

The work by Jerrum & Sinclair (1989) describes an approximative approach to determining the number of matchings $|M_\ast(G)|$ in a graph $G=(V,E)$. The fundamental ingredient of the approximation ...
3 votes
1 answer
194 views

What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?

Here, by 3D-grid of sidelength $n$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,n\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$. I known how to get the treewidth of $n*n$ grid is ...

1
2 3 4 5
31