Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

581 questions
162 views

Given a set of distances (no info regarding what points the distances correspond to) from a complete graph, is the realization of the graph unique?

There are $n$ points in $R^2$ (i.e. the 2D real space). We can think of them as a complete graph where edge weights correspond to the distance between points. Let $D$ be the distance matrix between ...
126 views

Finding Tours through Near-Hamiltonian Paths?

Say I have a connected graph. I want to find a tour that visits each vertex at least once. It's not always possible, though, for there to be a solution if there is a bridge in the graph. Is there a ...
2k views

What's the relation between the dominating set and vertex cover?

I wonder if the minimal dominating set is always a subset of the minimal vertex cover in any graph. If so, what's the proof?
94 views

Monomial decomposition as product of smaller monomials

Is there an algorithm to get all possible decompositions of a monomial as the product of smaller monomials ? For example $x^2y^3$ is $x∗xy^3$, $x^2∗y^3$, $xy∗xy^2$, and so on. For a monomial in one ...
2k views

313 views

Generalization of independent set

I know the definition of the independent set problem in graph theory. An independent set cannot contain any two adjacent vertices. How about if you allow no more than $k$ pairs of adjacent vertices? ...
349 views

Streaming Algorithm Lower Bounds by Communication Complexity

I am learning the methods for proving lower bounds on streaming algorithms using communication complexity. My question is about a basic technique to prove lower bounds on streaming models using the ...
116 views

Do expander graphs have the property that with high probability an s-t cut is size min{degree(s),degree(t)}?

If we want a specific example, then how about the Erdos-Renyi random graph?
70 views

Nonnegative Permanent and Ellipsoidal Method

Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph. This was based on the Ellipsoidal Method. Finding a Max Cut is the same for Bipartite Graphs as ...
240 views

Canonical labeling of special classes of DAGs

Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known. What are some special classes of DAGs that can be ...
286 views

Bipartite vertex separator

Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V_1, V_2, E)$ where the selected vertices are constrained to come from one partition of the graph? I have a ...
297 views

Increasing the capacity to maximize the min cut

Consider a graph with all edges having unit capacity. One can find the min cut in polynomial time. Suppose I am allowed to increase the capacity of any $k$ edges to infinity (equivalent to merging ...
360 views

Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature. ...
407 views

Understanding the talks in Conferences and Workshops

I am a graduate student from India. I am very much interested in attending the Workshops, conferences, and invited lecturers given by prominent professors. At the end of the talk as usual some people ...
94 views

PCVRP with prizes reduced over time

Hej guys, I'm working on customizing a Vehicle Routing Problem for a practical case, which is characterized as follows: The set of customers does not change over time, but their respective prizes ...
82 views

Bound for the spectral norm of a boolean function [duplicate]

As we know that the upper bound for the spectral norm of a Boolean function on $n$ variables is $2^{n/2}$. Is it possible to improve this bound..? Can somebody provide me an example of a Boolean ...
769 views

Generating interesting combinatorial optimization problems

I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$...
616 views

Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?

Let $f: \{-1,1\}^n \rightarrow \{-1,1\}$ be a Boolean function. The Fourier expansion of $f$ is $$f(T) = \sum_{S \subseteq [n]} \widehat{f}(S)\ \chi_S(T)$$ where $\widehat{f}(S)$ are real numbers ...
187 views

How can we derive this lower bound of a special cut in a graph?

I have another question about this paper. There the authors prove a special version of the maximal flow-minimal cut theorem for uniform exactly-$k$-splittable $s$-$t$-flows. They define the cut in ...
112 views

Complexity of the packing

Let $(A, \leq)$ be a totally ordered alphabet. The packing ${\tt pack(u)}$ of a word $u \in A^*$ is the word of $\lbrace 1, \dots, k \rbrace^*$, where $k$ is the number of different letters of $u$, ...
2k views

Integer programming with a fixed number of variables

The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of ...
2k views

Good seating arrangements for sequence of meals and tables of size k for a group of people

Given a set $S$ of people I'd like to sit them for a sequence of meals at tables of size $k$. (Of course, there are enough tables to sit all $|S|$ for each meal.) I'd like to arrange this such that ...
125 views

Complexity of the standardization

Let $(A, \leq)$ be a totally ordered alphabet. The standardization ${\tt std}(u)$ of a word $u \in A^n$ is the unique permutation of $n$ elements having the same inversions as $u$ (recall that an ...
660 views

Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?

Consider a permutation $\sigma$ of $[1..n]$. An inversion is defined as a pair $(i, j)$ of indices such that $i < j$ and $\sigma(i) > \sigma(j)$. Define $A_k$ to be the number of permutations ...
388 views

How can I find all numbers for which the XOR-sum is 0?

Given a list of integers $[a_1, a_2, \dots a_n]$, I want to find the number of $n$-tuples $(x_1,\dots,x_n)$ of integers such that the following three conditions are satisfied: \$x_1 \oplus x_2 \oplus \...
352 views

Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory

I read the famous book by Alon and Spencer on the probabilistic method in combinatorics. Is there a survey or lecture notes on recent advances and relationships with the following complexity ...
2k views

Developing A Perfect Tic-Tac-Toe Player - AI [closed]

I'm interested in AI as an area to study on in MSc. I don't have much prior knowledge. So, I decided to develop an AI that plays Tic-Tac-Toe perfectly, as an introduction. I've made some progress that ...