All Questions
10 questions
1
vote
1
answer
298
views
maximal sets of vertices that avoids a clique
I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
CommunityBot
- 1
1
vote
0
answers
94
views
Automated, algorithmic construction of bijective proofs of combinatorial identities
Let $a_n$ and $b_n$ be two different expressions in natural $n$ with values in the set of all nonnegative integers such that we have the identity $a_n=b_n$ for all $n$. As a simplest example, we may ...
- 12.9k
5
votes
1
answer
274
views
Is there a polynomial-time algorithm to check if a signed graph contains an odd-K5 minor?
I suspect this exists, if anyone has a reference please that would be very helpful.
By signed graph, I mean each edge is designated either odd or even (e.g. as in Guenin's result for weakly bipartite ...
- 32.1k
0
votes
0
answers
30
views
Maximum nonintersecting interval pick
This surely has been solved in the context of scheduling already! (Shall I ask on some computer SE instead?)
Assume we have a set of closed "intervals" on $\mathbb Z$ ($\mathbb R$ isn't ...
- 63.9k
18
votes
0
answers
579
views
What is the geometric intuition behind Wilf-Zeilberger theory?
This problem is somehow inspired by a bunch of impressive posts of combinatorial identities by T. Amdeberhan. Earlier this month I learnt from computer scientists that they have a generic algorithmic ...
- 4,280
4
votes
1
answer
519
views
A brief question about the "Eight Queens" Puzzle
The classical Eight Queens puzzle asks whether it is possible to arrange $ 8 $ queens on an $ 8 \times 8 $ chess board, so that no two queens attack each other.
It is well-known that such ...
- 151k
2
votes
3
answers
184
views
Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs
From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...
- 13.2k
2
votes
0
answers
642
views
Hamiltonian paths in subgraphs of rectangular lattice graphs
Is following decision problem NP-hard / NP-complete:
Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists
Having vertex-induced subgraph of rectangular ...
- 47.1k
3
votes
1
answer
277
views
Theorems about the directed bandwidth of a rooted tree?
Let $T$ be a rooted tree with root $r$. Say an ordering $v_1,\ldots,v_n$ of the vertices of $T$ is a search order if $v_1=r$ and for all $2 \leq i \leq n$, there is $j < i$ such that $v_j$ is the ...
- 4,922
8
votes
0
answers
152
views
Disjoint Rooted Paths with Specified Patterns
Let $S:=$ { $s_i : i \in [k]$ } and $T:=$ { $t_i : i \in [k]$ } be disjoint subsets of vertices of a graph $G$. Furthermore, let $A$ be a subset of $S_k$ (the symmetric group on $[k]$). A set of ...
- 32.1k